资源描述：
《MIT18_06SCF11_Ses3.2Complex Matrices; Fast Fourier Transform (FFT).pdf》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、Complexmatrices;fastFouriertransformMatriceswithallrealentriescanhavecomplexeigenvalues!Sowecan’tavoidworkingwithcomplexnumbers.Inthislecturewelearntoworkwithcomplexvectorsandmatrices.ThemostimportantcomplexmatrixistheFouriermatrixFn,whichisusedforFouriertransforms.No
2、rmally,multiplicationbyFnwouldrequiren2multiplications.ThefastFouriertransform(FFT)reducesthistoroughlynlogn2multiplications,arevolutionaryimprovement.ComplexvectorsLength⎡⎤z1⎢z2⎥Givenavectorz=⎢.⎥∈Cnwithcomplexentries,howdowefindits⎣.⎦.znlength?Ourolddefinition:⎡⎤z1⎢z2⎥
3、zTz=[zz···zn]⎢⎥12⎣..⎦.znisnogood;thisquantityisn’talwayspositive.Forexample:����11i=0.i��1Wedon’twanttodefinethelengthoftobe0.Thecorrectdefinitionis:i
4、z
5、2=zTz=
6、z1
7、2+
8、z2
9、2+···+
10、zn
11、2.Thenwehave:����2��1��1length=1−i=2.iiTosimplifyournotationwewrite
12、z
13、2=zHz,wherezH=zT.TheH
14、comesfromthenameHermite,andzHzisread“zHermitianz”.InnerproductSimilarly,theinnerordotproductoftwocomplexvectorsisnotjustyTx.Wemustalsotakethecomplexconjugateofy:yHx=yTx=yx+yx++yx1122···nn.1ComplexmatricesHermitianmatricesSymmetricmatricesarerealvaluedmatricesforwhichA
15、T=A.IfAiscom-Tplex,anicerpropertyisA=A;suchamatrixiscalledHermitianandweTHabbreviateAasA.NotethatthediagonalentriesofaHermitianmatrixmustbereal.Forexample,��T23+iA=A=.3−i5Similartosymmetricmatrices,Hermitianmatriceshaverealeigenvaluesandperpendiculareigenvectors.Unita
16、rymatricesWhatdoesitmeanforcomplexvectorsq1,q2,...,qntobeperpendicular(ororthonormal)?Wemustuseournewdefinitionoftheinnerproduct.Foracollectionofqjincomplexspacetobeorthonormal,werequire:�0j�=kqjqk=1j=k��WecanagaindefineQ=q1q2···qn,andthenQHQ=I.Justas“Hermitian”isthecom
17、plexequivalentof“symmetric”,theterm“unitary”isanalogousto“orthogonal”.Aunitarymatrixisasquarematrixwithperpendicularcolumnsofunitlength.DiscreteFouriertransformAFourierseriesisawayofwritingaperiodicfunctionorsignalasasumoffunctionsofdifferentfrequencies:f(x)=a0+a1cosx
18、+b1sinx+a2cos2x+b2sin2x+···.Whenworkingwithfinitedatasets,thediscreteFouriertransformisthekeytothisdecomposition.Inelectrical
