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.