MIT Açık Ders Malzemeleri

http://ocw.mit.edu

18.06 Doğrusal Cebir, Bahar 2005

Lütfen aşağıdaki alıntı biçimini kullanın:

Gilbert Strang, 18.06 Doğrusal Cebir, Bahar 2005. (Massachusetts Teknoloji Enstitüsü: MIT Açık Ders Malzemeleri). http://ocw.mit.edu ( MM, DD, YYYY) tarihinde erişildi.

Lisans: Yaratıcı Ortak Özelllik – Ticari Olmayan -- Olduğu gibi Kullanılır.

Not: Lütfen alıntınızda bu malzemeye eriştiğiniz gerçek tarihi kullanınız.

Bu materyallerden alıntı yapmak veya Kullanım Şartları hakkında bilgi almak için http://ocw.mit.edu/terms sitesini ziyaret ediniz.

MIT Açık Ders Malzemeleri

http://ocw.mit.edu

Doğrusal Cebir, Bahar 2005

Transcript - Ders 26

Pekala. Bu derste karmaşık sayılar devreye giriyor. Karmaşık sayılar bu dersin içine girmiştir, çünkü gerçek bir matris dahi karmaşık özdeğerlere sahip olabilir. Karmaşık sayılarla, özdeğerler ve karmaşık özvektörlerde karşılaştık.

Ve biz ---veya bu büyük olasılıkla -- özdeğerler ve özvektörlerle ilgili birçok yapmamız gereken şey var. Ve bu çoğunlukla gerçek olacak.

Fakat bir yerde bir noktada, sayılar karmaşık olduğunda ne yapacağımızı da görmemiz gerekir.

Vektörler karmaşık olduğunda, matrisler karmaşık olduğunda ne olur? İkisinin iç çarpımı nedir? İki karmaşık sayının skalar çarpımı nedir? Değişikliği yapmak zorundayız, sayılar karmaşık olduğunda değişiklik ne olur, görelim. O halde karmaşık sayıların en önemli örneğini size söyleyebilir miyim? O Fourier matrisinde gelir.

Böylece birazdan tanımlayacağım Fourier matrisi bir karmaşık matristir. Şüphesiz o en önemli karmaşık matristir; Fourier dönüşümünde ihtiyacımız olan matristir. Ve gerçekten, hızlı Fourier dönüşümü olarak adlandırılır, size söylemek istediğim özel şey ve herkes ondan FFT olarak bahseder ve hemen hemen bütün bilgisayarlarda vardır ve kullanılır…. Biz burada konuşurken binlerce yerde kullanılıyordur, çünkü dönüştürülmüş bütün endüstriler gibi Fourier dönüşümünü hızlı yapabilmek, -- bu da çarpım demek, şu matrisle hızlı nasıl çarpabilirim -- şu n ye n matrisle, normalde n-ye n matrisle çarpımlarda, normal olarak n kare çarpım olur, çünkü n kare bileşenim vardır ve hiç birisi de sıfır değildir.

Bu bir tam matristir ve dik sütunları olan bir matristir. Demek istiyorum ki o en iyi matris gibidir. Ve bu hızlı Fourier dönüşümü, Fourier dönüşümün işlemleri yavaşlattığı bu n kareyi nlogn’e düşürür – nlogn, aslında iki tabanlı logaritma. Ve bu noktada, bu duruma ulaşıldığında büyük bir fark sağlanmış olur.

Herkes yavaş yavaş anladı ki bu basit fikir, göreceksiniz ki sadece basit bir matrisi çarpanlara ayırma işi, ama bu her şeyi değiştirdi. Tamam.

Böylece geçen seferden biraz özetleyerek karmaşık vektörler ve matrisler hakkında, özellikle de Fourier matrisi hakkında, genel olarak konuşmak istiyorum.

Olan ne ki? Tamam.

Temel nokta, uzunluk hakkında ne diyebiliyoruz? Bir vektör veriliyor, bir x vektörüm var.

Veya, bir an için, karmaşık olduğunu hatırlatması için ona z diyeceğim. Fakat ben daha sonra bileşenleri x olarak adlandıracağım. Hepsi karmaşık sayılar olacak.

Fakat o bir vektör, z1, z2, zn’e kadar. Böylece tek yenilik artık onun R^n de olmadığı. O karmaşık n boyutlu uzayda. Bu sayıların her biri karmaşık sayı. O halde bu z, z1 C^n’de, R^n yerine n boyutlu karmaşık uzay.

Böylece sadece orada farklı bir harf, ama şimdi onun uzunluğu ile ilgili nokta nedir? Uzunluğu ile ilgili olarak z devrik z işe yaramaz, z devrik z….eğer buraya yalnız z devrik yazarsam, z1, z2, zn’e kadar olacak.

Şu çarpmayı yapmam bana doğru şeyi vermez.

Neden vermez? Çünkü uzunluğun karesi pozitif olmalı.

Ve eğer çarparsam, bunu 1 ve i gibi kabul edelim. Bileşenleri 1 ve i olan vektörün uzunluğu nedir? Eğer bunu yaparsam böylece n ikidir. C^2 deyim, iki boyutlu karmaşık uzayda, ve vektörümün bileşenleri 1 ve i.

O halde bir çarpı bir ve i çarpı i’yi alır ve toplarsam, z devrik z sıfır olacaktır. Fakat bileşenleri 1 ve i olan vektörün uzunluğu sıfır değildir…..bu çarpım -- gerçekte istediğim z1 eşlenik z1’dir.

z1 eşlenik z1’i hatırlıyorsunuz, görüyorsunuz ki ilk adım z1 eşlenik z1’dir, bu da z1’in uzunluğunun karesidir ki, bu da benim istediğimdir. Bu üçün karesi veya beşin karesi gibidir. Şimdi eğer z1, i ise, -- o zaman eksi i ile çarptığımda bir artı bir verir, böylece uzunluğun bileşeni, i bileşeni, modülünün karesi artı birdir.

Bu çok iyi. O halde yapmak istediğim şey, aradığım z1 çizgi z1, z2 çizgi z2, zn çizgi zn.

Ve hatırlayın ki, -- bunun karmaşık eşlenik olduğunu hatırlıyorsunuz.

Böylece anlatılmak istenen şudur. Şimdi işe yaramaz dediğimi siliyorum ve işe yararı yazıyorum, çünkü bu şimdi sıfır vektörü için sıfır sonucunu veriyor; doğal olarak, aynı zamanda herhangi bir diğer vektör için pozitif uzunluğun karesini verir. O halde bu uzunluğun doğru tanımıdır, esasında mesaj her zaman devriğini aldığımızda aynı zamanda karmaşık eşleniğini de almamızdır.

Şimdi, (1, i) ın uzunluğunu bulalım, (1, i) vektör, yani z, yani z bu vektör.

Şimdi birin eşleniğini alıyorum bir, i’nin eşleniği eksi i. Bu vektörü (1, -i) alıyorum, bir artı bir elde ederim --iki bulurum.

Şu bir vektör ve şu vektörün uzunluğu, ikinin karekökü. Karekök iki bizim uzunluğumuz ve onu, (1-i)’nin karesinden elde edeceğim, sıfır değil. Tamam.

Böylece gerçek mesaj, her ne zaman devrik alırsak aynı zamanda eşleniğini de almamız gerekir. Böylece sembol bu, her ikisini de yapmak için bir sembol. Bu H sembolü adı Hermite olan kişiyi temsil eder, o gerçekte H’yı telaffuz etmemiştir, ama biz telaffuz edelim, o halde buna z Hermitasyon z diyeceğim.

Bu kelimeyi yazayım, onun adı Hermit’dir, ve o halde biz onu Hermitasyon sıfatına dönüştürürüz.

Böylece z Hermityon z. z^Hz.

Tamam. Böylece, şu uzunluğun karesidir. Şimdi iç çarpım nedir? Bakalım, o uyum sağlamalı. İki vektörün iç çarpımı, -- bu yüzden iç çarpım artık y devrik x şeklinde kullanılmıyor. O gerçek vektörler içindi.

Karmaşık vektörler için her ne zaman devriğini alırsak aynı zamanda eşleniği de alırız. Böylece o, y Hermitasyon x olur.

Tabii ki, o artık, genellikle gerçek değil.

.

Yani iç çarpım genellikle karmaşık sayı olacaktır.

Fakat y ve x aynı ise, onlar aynı z ise, o halde z^H z’imiz var demektir, uzunluğun karesine sahibiz, bu da bizim istediğimiz olur, bir vektörün kendisiyle iç çarpımı uzunluğunun karesidir.

Böylece bize dayatılıyor bu, çünkü bizi bu mecbur ediyor. Peki, bu z, herkes bunun neye eşit olduğunu kavrıyor.

Bu z1 kare artı+ ... + zn kare.

Yani uzunluğun karesi olur. Ve bu bize uygun olan iç çarpımdır. Böylece şimdi bu bir karmaşık sayı olabilir. Bir değişiklik daha.

Şey, iki değişiklik daha. Simetrik matris fikrini değiştirmemiz gerekir. Simetrik matrisleri kısaca özetleyeceğim. Simetriğin anlamı A devrik A’ya eşit, fakat eğer A karmaşık ise bu işe yaramaz. O halde gerçek matrislere kusursuz olarak uygulanan bu şeyi ne ile değiştiririz? Fakat şimdi benim matrislerim karmaşık olsaydı, eşlenik devriğinin A’ya eşit olmasını isterdim. İşte bu simetrinin karmaşık uzaylardaki karşılığıdır.

Şimdi simetrinin anlamı devriğini aldığımda, köşegenin etrafında sayılar çevirmek ve eşleniğini almak demektir. Örneğin, burada bir örnek olacaktı. Köşegen üzerindekiler gerçek olursa iyi olur, çünkü çevirdiğimde köşegen hala olduğu yerde kalır ve sonra karmaşık eşleniğini aldığımda hala orada olmalı, bu yüzden gerçek olsa iyi olur, iki ve beş olsun diyelim.

Köşegen dışındaki elemanlar için ne demeli? Eğer bu eleman, diyelim ki üç artı i ise, o halde bu eleman ne olursa iyi olur, çünkü bu ne olursa olsun-- devriğini aldığımda burada ortaya çıkacak ve eşleniğini alacağım.

Böylece orada üç eksi i’ye ihtiyacım var. O halde simetriye karşılık gelen, ama karmaşık elemanlı bir matris var.

Ve bu matrislere Hermityon matrisler denir.

Hermityon matrisler, A^H eşittir A.

İyi. Tamam, bu matrisler gerçek özdeğerlere ve dik özvektörlere sahiptir. Dik’in anlamı nedir? Dik’in anlamı iç çarpım, o halde dik’e geri dönelim. Bakalım, dik vektörlerim varsa, örneğin, onlar q1, q2 qn’ye kadar olsun. Yani q benim dik için kullandığım harftir. Aslında, ben genellikle, aynı zamanda birim uzunluklu vektörleri kastederim. Böylece bunlar dik birim vektörlerdir. Ama şimdi, ..böylece bu bir birimdik taban, hala bu kelimeleri kullanacağım, fakat dik’i nasıl hesaplarım? Dik olmayı nasıl kontrol ederim? Bunun anlamı qi ile qj’nin iç çarpımı, fakat şimdi yalnız devriğini değil, eşleniği de almalıyım, doğru, i j ‘ye eşit değilse sıfır, ve i j’ye eşitse bir olur.

Böylece o bir birim vektörüdür, birim uzunluğu olan, dik --- bütün açılar dik açı, fakat bunlar karmaşık n boyutlu uzayda açılardır.

O halde bu q1, qi çizgi devrik.

Veya kısaca, qi ^H qj.

Böylece hala doğru olacak, bunlardan tekrar bir matris oluşturmama izin verin. Bu q’lar matrisin sütunlarında olacak, q2 qn’ye kadar.

Aynı daha önce yaptığım gibi, bunları matris diline dönüştürmek istiyorum. Bunun anlamı nedir? Bunun anlamı bütün bu iç çarpımlara ihtiyacım var, o halde Q’nun bu sütunlarını alıyorum, satırlarıyla çarpıyorum, bu Q idi -- Q devrik Q eşittir I olarak kullanılmıştı, değil mi? Bu bir dik matris idi.

Ama ne değişti? Şimdi bunlar karmaşık vektörlerdir. Onların iç çarpımları birinci çarpanın eşleniğini almayı gerektirir. Böylece bu değil, bu Q devriğin eşleniğidir.

O Q çizgi devrik Q’dur. Q^H

O halde buna Q^HQ diyelim, bu da I’ya eşit. Böylece bu bizim yeni, -- görüyorsunuz ki sadece tercüme ediyorum, kitap—bu sayfada R^n de gerçek durumda geçerli olan sözcüklerin,-- karmaşık vektör uzayı C^n deki karşılıklarını veriyor.

Tabii ki, C^n bir vektör uzayıdır, çarptığımız sayılar şimdi karmaşık sayılardır, sadece karmaşık n boyutlu uzaya taşıyoruz. Tamam.

Şimdi, gerçekte bu matrisler için simetrik kelimesini Hermityon’a değiştirdiğimizi söylemeliyim. İnsanlar bu dik kelimesini, karmaşık matrislerde de kullanılabileceğini ima etmek amacıyla yeni bir üniter kelimesine değiştirmişler; o halde üniter matris nedir? ki orada karmaşık matrislerle ilgilenmemiz mümkündür, Tam dik matris gibidir.

O bir kare, birimdik sütunlu n-ye n matris, dik sütunlara, birim vektörlere sahip, birim vektörler hesaplanır-- ve diklik, devriğin yanısıra eşleniğinde gerektiği hatırlanarak hesaplanır. Tamam. Böylece kelimeler bunlar şimdi dersin özüne, bu matrislerden biri olan en ünlü karmaşık matrise, girmeye hazırım.

Dik sütunlara sahiptir, ve ona Fourier dönüşümünden geldiği için Fourier ismi verilmiştir, işte bu hepimizin etrafındaki matristir.

Tamam. Öncelikle nxn’lik durumda ne olduğunu söyleyeyim. Sonra n’yi çoğunlukla 4 alacağım çünkü 4 çalışmak için uygun bir büyüklüktür.

Fakat n-ye n Fourier matris burada.

Birinci sütun bir’lerin vektörüdür. Tabii ki n-ye n dir. İkinci sütun kuvvetlerden oluşur, aslında, bir yarım saat için matematik bölümünden elektirik mühendisliği bölümüne gitsem iyi olur ve sonra, lütfen geri dönmeme izin verin. Tamam.

Bu iki bölüm arasındaki fark nedir? Fark, matematik saymaya birle başlar ve elektrik mühendisleri sıfırla başlar. Aslında, onlar çoğunlukla haklılar.

Her neyse..

Böylece bu aslında sıfırlar sütunudur.

Ve n-1’e kadar birinci sütun, ki n-1 elektrik mühendisliğinde uygun olmayan yerdir. Bütün bu ifadeler sıfırla başlar, sorun değil, fakat n-1’de son bulur.

İyi. Bu ders 6’nın zorluğudur. Peki, onlar w diye adlandıracağım sayının kuvvetleridir, w kare, w küp,…şimdi burada kuvvet nedir? Bu sıfırıncı kuvvet, birinci kuvvet, ikinci kuvvet, bu (n-1)’inci kuvvet olacak. İşte sütunumuz.

Sonraki sütun nedir? O, w karenin kuvvetleridir, w üzeri dört, w üzeri altı, w üzeri iki(n-1). Ve sonra daha çok sütun ve daha fazla sütun ve daha fazla sütun ve son sütun nedir? O neyin kuvvetleridir-- görelim.

Biz, aslında eğer satırlara bakarsak, bu matris simetriktir. O mükemmel anlamda değil eski anlamda simetriktir, mükemmel değil -- çünkü bu sayılar karmaşıktır. Ve o halde birinci satırın tamamı birlerdir. Bir w w kare w üzeri n-1’e kadar. Bu son satır w üzeri n-1’in kuvvetleridir, böylece bu şununla uyuyor, ve son olarak burada w üzeri bir şey elde ederiz. Tahmin ediyorum ki o bir şeyin ne olduğunu belirleyebiliriz.

Bu matrisin elemanları nedir? Bu matrisin i j’ninci elemanı, -- i’yi sıfırdan n-1’e kadar değiştirmeme izin verin. O halde i ve j sıfırdan n-1’e kadar değişir.

Böylece sıfıra sıfır elemanı birdir, bu tam olarak aynı W’nin i çarpı j-ninci kuvveti.

Görelim. Burada formüllere atlıyorum ve W’nın ne olduğunu size söylemeliyim ve bu takdirde bu matrisle ilgili her şeyi bileceksiniz. Böylece w…iyi, burada bitirebilir miyiz? Bu nedir, bu (n-1) (n-1) elemanıdır. Bu w üzeri n-1’in karesidir.

Buradaki her şey karma karışık duruyor, çünkü biz ..çok kötü değil, çünkü bütün elemanlar w’nın kuvvetleridir.

Orada hiç birisi sıfır değildir. Bu bir tam matristir.

Fakat w çok özel bir sayıdır. W, n-ninci kuvveti bir olan özel sayıdır. Gerçekte, iyi, aslında, bunun gibi n sayı var.

Tabii ki, onların birisi birdir.

Fakat bizim istediğimiz w, açısı iki pi bölü n’dir. Ben bunu mu demek istiyorum? n bölü iki pi. Hayır, iki pi bölü n.

W, e üzeri i ve açı iki pi bölü n.

Doğru. Karmaşık düzlemde bu w nerededir? O birim çember üzerindedir, değil mi? Bu iki pi bölü n’nin kosinüsü artı, i çarpı iki pi bölü n’nin sinüsü. Fakat aslında, bunu unutun. Kuvvet aldığımızda gerçek ve sanal kısımlarla çalışmak asla iyi değildir, kartezyen koordinatlarda. Bunun onuncu kuvvetini almak -- ne yaptığımızı asla bilemeyiz.

Bu formun onuncu kuvvetini aldığımızda, hemen ne yaptığımızı görürüz, e üzeri i20 pi bölü n olacaktır. Böylece matrisimiz tamamen kuvvetlerle dolu olduğunda, o bu formüldür -- bu karmaşık düzlemde nerededir? Gerçek sayılar buradadır, sanal eksen budur, bir yarıçaplı birim çember buradadır, ve bu bu sayı bu açıyla birim çember üzerindedir ki, bu da tam dönmenin n’de biridir.

Örneğin n=6’yı çiziyor olsaydım, bu e üzeri iki pi, iki pi bölü altı, bu tam dönmenin altıda biri olacaktır, 60 derece olacaktır.

Ve w kare nerededir? Bu durumda benim w’em e üzeri iki pi bölü altıdır, bu altıya altı Fourier dönüşümüdür ve bu tamamen bu sayı ve onun kuvvetleriyle inşa edilmiştir.

O halde onun kuvvetleri nedir? İyi, onun kuvvetleri birim çember üzerindedir. Çünkü bir sayının, bir karmaşık sayının, karesini aldığımda onun mutlak değerinin karesini alırım, bu da bana tekrar biri verir. Bütün kuvvetler birim çember üzerindedir. Ve açı iki katına çıkar, yüz yirmi olur, böylece w kare burada, w küp burada, w üzeri dört burada, w üzeri beş burada ve w üzeri altı buradadır. Beklediğimiz gibi w üzeri altı tekrar bire geliyor; o halde bunlar altı – bunu TV’de söyleyebilir miyim? Birin altıncı dereceden kökleri, ve bu ilkeli diyeceğiz, ilki, w’dır.

Tamam,. Değiştireyim ---Büyük olasılıkla n=4’e döneceğimi söylemiştim. Bunun için w nedir? Birin dördüncü dereceden köküdür. W üzeri dört, bir olacaktır.

Şimdi w, e üzeri iki pi i bölü dört olacak. Bu nedir? Bu e üzeri i pi bölü ikidir. Bu birim çemberin etrafında çeyrek dönmedir, bu tamtamına i’ye eşittir, tam dönmenin çeyreği. Ve yeteri kadar eminiz ki, i’nin kuvvetleri, i kare, ki eksi birdir, -- i küp, eksi i’dir ve son olarak i üzeri dört, birdir, değil mi?.

O halde w, w kare, w küp, w üzeri dört var, bu dörde dört halinde, onu daha açık görmek amacıyla, Fourier matrisini yazmak için hazırım. Burada onu yapalım.

F4 tamam, bir bir bir bir bir bir bir.. w .. aa, bu i olmalı ...

i kare, bu eksi 1.

i küp --eksi i olur.

i kare ve i küp de yazabilirdim.

Emin olmak için neden tam olarak modeli görmeyelim. i kare, i küp, -- i kare, i küp, i dördüncü, i altıncı, i altıncı ve i dokuzuncu kuvvetleri

Üslerin bu hoş şekilde düştüğünü görüyorsunuz, üs her zaman sıfırdan başlamak üzere satır sayısı çarpı sütun sayısıdır.

Tamam. Ve şimdi eğer isterseniz bu sayıları yerine koyabilirim bir bir bir bir, bir, i, eksi bir eksi i, -- bir, eksi bir, bir, eksi bir ve bir, eksi i, eksi bir, i.

Hayır. Evet.

Tamam. Bu matrisin niçin oldukça dikkate değer olduğunu düşünüyorum? Bu dört noktalı Fourier dönüşümünden gelen dörte dört bir matristir.

Fourier dönüşümünü bulmak istersek, dört bileşenli bir vektörün, dört noktalı Fourier dönüşümü, -- bu F4 veya F4’ün tersiyle çarpmak isteriz.

Bir yönde dönüşümü alıyoruz, bir yönde de ters dönüşümü alıyoruz. Aslında, onlar oldukça yakındır ki ikisini karıştırmak kolaydır.

Bu matrisin tersi de hoş bir matris olacaktır. Peki, ve bu, tabii ki….sanıyorum Fourier bunu biliyordu.

O bu matrisin tersini biliyordu.

Göreceksiniz ki, bu sadece sütunların dik olması gerçeğinden geliyor, sütunların dik olması gerçeğinden, tersin ne olduğu çabucak belirleyeceğiz. Fourier’in bilmediği, gözlemlemediği ne idi, sanıyorum, Gauss bunu gözlemlemişti, fakat ne demek istediğini yeterince anlatamadı ve sonra ortaya çıkan önemli gerçek şu idi ki, bu matris oldukça özeldir, öyle ki onu çok fazla sıfırlı hoş parçalara ayırabilirsin. Bu çarpanlar çok sayıda sıfıra sahiptir ve onunla veya tersiyle çok çok hızlı çarpabilirsin.

Tamam. Fakat derse bu öncelikle nasıl girdi? Çünkü sütunlar diktir. Bu matrisin sütunlarının dik olduğunu hemen kontrol edebilir miyim? Böylece şu sütunun şu sütunla iç çarpımı sıfırdır.

Birinci sütunun üçüncü sütunla iç çarpımı sıfırdır.

İki ve dört’ün iç çarpımı ne durumdadır? İkinci sütunla dördüncü sütunun iç çarpımını yapabilir miyim? Veya hatta iki ile üçün iç çarpımını görelim, -- iki ve dört’ü yapayım.

Tamam. Ne -- görüyorum.

Görelim, bu iki sütunun dik olduğuna inanıyorum. Böylece onların iç çarpımını yapayım ve sıfır elde etmeyi ümit edelim. Tamam, şimdi eğer bu dersin ilk yarısını dinlemediyseniz, şununla şunun iç çarpımını aldığınızda, bir ile biri, i ile eksi i’yi çarpacaktınız ve bu biri verecekti, eksi bir ile eksi bir başka bir verecekti, eksi i ile i eksi i^2 olacaktı, ve bu da başka bir 1

Sütunların iç çarpımlarını sonuçlandırabilir miyim, iki ve dördüncü sütunları söyledim, bunların bir ve üçüncü sütunlar olduğunu unuttum. Onların iç çarpımıyla ilgileniyorum ve sıfır olmasını umuyorum, fakat sıfır gibi durmuyor? Buna rağmen sıfırdır. Bu sütunlar diktir. Neden? Çünkü iç çarpımda eşleniğini de almalıyız.

İç çarpımda vektörlerden birinin eşleniğinin alınacağını hatırlıyor musunuz? O halde eşleniğini aldığımda, bu i’yi, eksi i’ye değiştirir, bunu artı i’ye değiştirir,bunları değiştirir, buradaki ikinci işaret ve buradaki dördüncü işaret ve sıfır elde ederim. Böylece bu sütunlar dikdir. O halde sütunlar diktir.

Onlar tam olarak birimdik değil. Fakat bunu kolaylıkla düzeltebilirim. Bu sütunların hepsinin uzunluğu ikidir.

Uzunluğun karesi dörttür, bunun gibi ..oradaki dört …bu uzunluğun karesi, bir artı ..birin karesi birin karesi birin karesi birin karesi dörttür ve karekökü ikidir, o halde eğer gerçekten onları istersem ..hayatı gerçekten düzeltmek istediğimi varsayalım. İki ile bölebilirim ve şimdi gerçekten birimdik sütunlara sahibim. Yani ne? Böylece hemen tersini alabilirim, değil mi? Birimdik sütunların anlamı, şimdi bir an için bu yarımı orada tutuyorum, demek ki F4 hermityan -- şunu kullanabilir miyim? -- eşlenik devrik çarpı F4 I’dır.

Böylece tersin ne olduğunu görüyorum. F4’ün tersi tam dik matris gibi.

Tersi devriğidir, burada tersi devriğinin eşleniğidir. Peki, iyi.

Bu bana F4 hakkında öğrendiğim iyi bir şeyin aynısını -- tersi hakkında benzer bir gerçeği öğrendim, çünkü onun tersi tam olarak devriğinin eşleniğidir.

Tamam, şimdi iyi olan nedir? Bakalım, öncelikle, sütunlar dikdir. O halde bu anahtar gerçektir. Bu tersini kolay yapan şeydir. Fakat hızlı Fourier dönüşümüne götüren özellik nedir? Öyleyse şimdi bu son dakikalarda hızlı Fourier dönüşümü hakkında konuşalım.

Ne, fikir burada. F6, bizim altıya altı matrisimiz, yarısı büyüklüğündeki F3’le düzenli bağlantısı vardır. F8’in F4’le bağlantısı vardır. F(64)’ün F(32) ile bağlantısı vardır. Bu bağlantının ne olduğunu yazabilir miyim? F(64)’ün F(32) ile bağlantısı nedir? F(64), 64x64 lük bir matris olup, w’si 1’in 64üncü köküdür. F(64)’deki w tam dönmenin 64’te biridir. Ve o-- F(32), 32’ye 32 matristir. Hatırlayın, onlar farklı büyüklüktelerdir. Ve 32’ye 32 matrisin w’sı birin 32.ci dereceden köküdür, bu da iki katıdır, anahtar noktayı görüyorsunuz, yani 32 ve 64 w’lerle nasıl bağlantılı olduğunu.

64 için w yolun 64’te biridir, böylece bütün söylediğim, eğer w(64)’ün karesini alırsam, bu bir bölü altmış dört için kullandığım w veya bu Wn’yi, iki pi bölü n -- böylece w(64) çevrenin 64’te biridir. Onun karesini alırsam, ne elde ederim yalnızca w(32)? Değil mi? Eğer bu matrisin karesini alırsam, açıyı iki katına çıkarırım, w(32)’yi elde ederim. Böylece bir şekilde F(32) ile F(64)’ün bağlantısıyla ilğili küçük bir ümit vardır. Ve bağlantı budur.

Tamam, geri döneyim, evet, burada yapacağım.

Bağlantı budur. F(64).

64 e 64’lük Fourier matrisi F(32)’nin iki kopyasıyla bağlantılıdır. Bağlantı için küçük bir boşluk bırakayım. Bu 64’e 64’lük.

Bu aynı büyüklükte bir matris, çünkü onda F(32)’nin iki kopyası ve iki sıfır matrisi var.

Bu sıfır matrisleri anahtardır, çünkü bu matrisle çarparsam, aynı düzgün çarpımdaki gibi, 64’ün karesi kadar küçük çarpımları yapacaktım. Fakat bu matrisin yarısı sıfır.

İyi, tabii ki, ikisi eşit değil.

Eşit işareti koyacağım, fakat doğru yapmak için bir buraya ve bir buraya bazı çarpanların ayarlanması gerekir.

Bunun güzelliği bu ayarlanan çarpanların gerçekten hemen hemen tamamının sıfırlar olması. Bu formülü doğru elde eder etmez, nasıl 64’ün karesi kadar hesaplamadan, --burada orijinal 64’ün karesi hesaplama vardı, --fakat bu bize verecek,-- bu kadara ihtiyacımız yok, yalnızca iki çarpı 32’nin karesi hesaplamaya ihtiyacımız olduğu mükemmel bir fikri verir, çünkü şunun iki katına sahibiz.

Ve artı ayarlama. O halde bu ayarlama matrisinde ne olduğunu söylemeliyim. Aslında sağdaki bir permütasyon matrisi, çok basit bir tekler ve çiftler permütasyon matrisi, ortaya çıkan birler, yeteri kadar bir koymadım, gerçekten bunlardan 32 tanesine ihtiyacım var…iki boşluk ve sonra….onu görüyorsunuz, o bir permutasyon matrisi. O ne yapar, O halde bu P matrisi bir vektörle çarpılırsa ne yapar, tekleri alır….önce çift numaralı bileşenleri ve daha sonra tekleri alır.

Bunu görüyorsunuz, bu her defasında atlayarak x0, x2, x4, x6’yı seçecek ve sonra aşağıdaki gelecek x1, x3, x5’i seçecek. Ve tabii ki, bu donanımlı bir bilgisayarda şipşak yapılabilir.

Bu şunu söyler -- bu ana kadar ne söylemiş olduk? Biz 64’e 64 Fourier matrisinin gerçekten ayrıştırıldığını söylüyoruz, vektörünün teklerini…çift ve tek bileşenlerini ayır, sonra bu ayrılanlara 32 büyüklüklü Fourier dönüşümünü uygula, ve sonra da parçaları tekrar bir araya getir.

Böylece bu parçalar -- bu parçalar bir araya getirilirse, I ve bir köşegen matris ve I eksi aynı köşegen matris haline gelir. O halde ayarlama maliyeti gerçekten bu köşegen D matrisi ile çarpmaktır, çünkü esasında I bölümünde veya permütasyon bölümünde maliyet yoktur, D köşegen olduğundan esasen ayarlama maliyeti 32 çarpıma eşdeğerdir.

Orada görüyorsunuz ki,-- tabii ki formülü kontrol etmedik veya hatta henüz D’nin ne olduğunu söylemedik, fakat söyleyeceğim, bu köşegen D matrisi w’nin kuvvetleridir.

Bir w, w-kare, w-üzeri 31’e kadar. Böylece görüyorsunuz ki, ben D ile çarpma yaptığımda, 32 çarpma yapmam gerekir.

Fakat diğeri, daha ciddi çalışma, iki kez F(32) ile ayrı ayrı çift numaralı ve tek numaralı bileşenlerle çarpma yapmaktır, böylece 32’nin karesinin iki katıdır.

Şimdi 64’ün karesi gitti. Ve bu yeni sayıdır.

Tamam, iyi, fakat sonraki nedir? Böylece şimdi ana hususu elde ettik, işlemleri kontrol etmek zorundayız, ama bu sadece doğru olarak ortaya çıkan birçok toplamı kontrol etmektir. Bu doğrudur, hızlı Fourier dönüşümünü doğru şekilde görmek veya onu görmenin bir doğru yoludur. O halde bir sonraki fikrin ne olduğunu görmeniz gerekir. Bir sonraki fikir 32’leri bölmektir. Bu 32’leri bölmek.

Bu çarpanımız var, ve şimdi F(32)’miz var, halbuki bu buradaki bir parçaya F(16)…..F(16) ayrılır. Her bir F(32) iki tane F(16) kopyasına parçalanır ve sonra bir permütasyonunuz var, böylece bu 64 büyüklüklü permütasyon gibidir; bu 32 büyüklüklü bir permütasyondur, sanıyorum ona iki kez sahip olacağım. Sadece aynı fikri tekrarlı olarak kullanıyorum, bu F(32)’lerin her birinde tekrarlı anahtar kelimedir, burası sıfır sıfır , tam olarak F(32)’nin elde edildiğindeki gibi, bu tek çift permütasyonlar, gördüğünüz gibi bu permütasyonların bir kombinasyonu ve bu şey çiftleri birlere ayırır, çift çiftler, yani sıfır dört sekiz onaltı…ve çift tekler, yani iki, altı, on, ondört ve sonra tek çiftler ve tek tekler. Görüyorsunuz ki bu permütasyonlar birlikte vektörümüzü x’e, çift çifte ve üç diğer parçaya böler.

Bunlar F(16) ile ayrı olarak çarpılan dört parçadır, bu I’lar ve D’ler ve I’lar ve eksi D’lerle ayrı ayrı ayarlanır, böylece bu sayı azaltılır.

Bu sayı şimdi neye indirgenir? Bu gidecek, çünkü 32’nin karesi, bu benim yaptığım değişiklik, değil mi? 32’nin karesi ..şimdi indirgenen budur.

Hala bende onun iki katı var, fakat şimdi 32’nin karesi nedir? İki onaltının karesi artı onaltının yerine ortadan kalkmıştır.

Ve sonra orijinal 32 sabitlenmiştir.

Belki ne olduğunu görüyorsunuz. Hatta bu formülden daha kolay olan, tekrarı ardarda yaparken ortada daha daha basit çarpanlar elde ediyorum. Sonunda iki nokta veya bir noktalı Fourier dönüşümüne geleceğim.

Fakat sağ ve sol tarafta gittikçe artan çarpanlar elde ederim.

Sağ tarafta sadece permütasyon matrisleri elde ederim. Sol tarafta, bu şeyleri elde ediyorum, bu I’lar ve D’ler böylece orada 32 vardı ve bunların her birinin maliyeti 32. Bunların her biri 32 maliyetli. Ve kaç tane olacak? Görüyorsunuz ki bu orijinal ayarlama için 32, çünkü D’de 32 sayı var, bir sonraki ayarlama için 32, çünkü D’de 16 ve 16 daha var. Devam ediyorum. Ortadaki sayı hızlıca kayboldu, bana kalan bütün bu ayarlamaların sayısı, ve kaç tane çarpan, kaç tane ayarlamam var, log n, 64’ten 32’ye bir adım, 16’ya bir adım, sekize bir adım, dört iki ve bir.

Altı adım. O halde altı tane ayarlamam var, altı ayarlama çarpanı. Son olarak 6 çarpı 32 elde ederim. Bu benim son sayım.

64’ün karesi yerine, 64’ün iki tabanlı logoritması çarpı 64, aslında 64’ün yarısı. Böylece aslında, son sayman log iki tabanında n, bu 32, ve -- bir bölü iki.

Böylece bu harika, son derece önemli ve tatmin edici sonucu bir çerçeve içine alabilir miyim?-- Bu hızlı Fourier dönüşümü n-ye n matrisle çarpılır, ancak n kare adımda değil, halbuki bir bölü iki n log n adımda .

Ve sadece saymayı yaparak tamamlarsak,-- varsayalım ..tipik bir durum iki üzeri on olacaktır. Şimdiki halde n’nin karesi milyondan büyüktür. Bu bin yirmi dört çarpı bin yirmi dörttür. Ancak n nedir, n’nin yarısı nedir, doğru şekilde yapıldığında yeni sayı nedir? Bu bin yirmi dört çarpı bir bölü iki ve logoritma nedir? Ondur.

Böylece çarpı on bölü iki. O halde beş çarpı, beş çarpı bin yirmi dört, bu bin yirmi dört çarpı bin yirmi dörttü.

Matrisi uygun şekilde çarparak bu hesabı 200 kere azaltmış olduk.

Bu bin çarpı n idi, şimdi beş çarpı n’ye azaltıldı.

Böylece bir tanesini yapana kadar 200 Fourier dönüşümünü yapabiliriz, ve Fourier dönüşümünün ortaya çıktığı bütün zamanlardaki reel bilimsel hesaplamalarda, modern bilimsel hesaplarının ana adımlarının birinde 200 çarpanı kadar tasarruf etmiş oluyoruz.

Böylece bu hızlı Fourier dönüşümünün temel fikridir ve bütün bu şeyin birimdik sütunlu özel bir matrise dayandığını görüyorsunuz. Tamam, bu aslında karmaşık sayılar içindi. Gelecek sefer gerçekten gerçek sayılara, özdeğerlere ve özvektörlere döneceğim ve pozitif tanımlı matrislerin ana fikri ortaya çıkacak. Pozitif tanımlı matris nedir? Ve müthiştir ki bu ders pozitif tanımlılığa ulaşmış olacak, çünkü bu matrisler uygulamalarda en çok karşılaştığınız matrislerdir. Tamam, gelecek sefere görüşmek üzere.

Teşekkürler.