數(shù)值分析矩陣特征值與特征向量的計(jì)算學(xué)習(xí)教案

1、數(shù)值分析數(shù)值分析(fnx)矩陣特征值與特征向量的矩陣特征值與特征向量的計(jì)算計(jì)算第一頁，共31頁。3.1.1 冪法冪法用于求矩陣(j zhn)A的按模最大的特征值及相應(yīng)的特征向量。一、算法構(gòu)造(guzo)及收斂性分析 1 設(shè)設(shè)階階實(shí)實(shí)方方陣陣 滿滿足足：條條件件nnA o121 ,;有有 個(gè)個(gè)線線性性無無關(guān)關(guān)的的特特征征向向量量nAnxxxo122 ,的的 個(gè)個(gè)線線性性無無關(guān)關(guān)的的特特征征向向量量對對應(yīng)應(yīng)的的特特征征值值滿滿nAnxxx12足足。n下下面面通通過過分分析析由由迭迭代代格格式式( )(1)0,1,2,;初初始始值值任任意意選選取取。(3.1)(3.1)kkuAuku ( )1產(chǎn)產(chǎn)生

2、生的的序序列列的的收收斂斂情情況況來來構(gòu)構(gòu)造造計(jì)計(jì)算算和和它它對對應(yīng)應(yīng)的的特特征征ku 1向向量量 的的計(jì)計(jì)算算方方法法。x第1頁/共31頁第二頁，共31頁。(0)1122,nnuxxx設(shè)設(shè)則則21112211kkknnnxxx 110,(2,3, ) iin不不妨妨設(shè)設(shè)由由得得( )(1)2(2)(0)kkkkuAuA uA u1122= kkknnA xA xA x111222kkknnnxxx 1 lim kiiikx 第2頁/共31頁第三頁，共31頁。( )(0)(3.1),kkuA u 1 1由由于于迭迭代代公公式式本本質(zhì)質(zhì)上上是是計(jì)計(jì)算算于于, ,因因此此稱稱( +1)( )kku

3、u與與對對應(yīng)應(yīng)分分量量近近似似成成比比例例，比比例例因因子子正正好好近近似似等等這這種種迭迭代代法法為為冪冪法法。( )11111121knkkkiiiiuxxx (+1)+1()1111kkkuxu 同同樣樣，我我們們還還有有。( )1ku 可可把把作作為為與與相相應(yīng)應(yīng)的的特特征征向向因因此此，量量的的近近似似。k當(dāng)當(dāng) 充充分分大大時(shí)時(shí)，有有第3頁/共31頁第四頁，共31頁。歸一化處理(chl)與實(shí)際計(jì)算方法(1)(1)(1)(0)( )(1) 1,2,;kkkkkuyukuuAy 任任意意選選取取。2112211112112211kknknnkknnnxxxxxx (1)2(2)(0)(

4、)(1)(2)1(0);kkkkkkkAuA uA uuuAuAu分分析析：( )(0)( )( )(0) ykkkkkuA uuA u第4頁/共31頁第五頁，共31頁。( )( )111111yykkkxkx當(dāng)當(dāng) 充充分分大大時(shí)時(shí)，有有，即即可可近近似似地地作作( )1y=1k 為為對對應(yīng)應(yīng)的的特特征征向向量量，且且特征值的計(jì)算(j sun) ( )(1)(1)1TT(1)( )(1)(1)11 ,kkkkkkkuAyyyuyy 方方法法 由由于于從從而而有有， T(1)( )1T(1)(1)kkkkyuyy 第5頁/共31頁第六頁，共31頁。(1)kky 1 1最最后后作作為為 的的近近似

5、似值值，以以作作為為其其對對應(yīng)應(yīng)的的特特征征向向量量。3.1迭迭代代算算法法 (1)(1)(1)kkkuyu ( )(1)kkuAy T(1)( )T(1)(1)=kkkkkyuyy 1,2,;k 1kkk 終終止止條條件件：。(0)u任任意意選選取取。第6頁/共31頁第七頁，共31頁。 2(1)(1)T(1)(1)(0)( )(1)T(1)( )1(1)3.2 () 1,2,;=kkkkkkkkkkkkkkuyuukuuAyyuy 1 1迭迭代代算算法法使使用用范范數(shù)數(shù)任任意意選選取取。終終止止條條件件：。最最后后作作為為 的的近近似似值值，以以作作為為其其對對應(yīng)應(yīng)的的特特征征向向量量。第7

6、頁/共31頁第八頁，共31頁。 (1)(1)1(1)(1)(1)(0)T( )(1)( )( )( )12(1)( )1(1)3.3 max 1,2,;,=signkkrjj nkkkrkkkkknkkkrrkkkkkhhuyhkuuAyhhhhhy 1 1迭迭代代算算法法使使用用范范數(shù)數(shù)任任意意選選取取。終終止止條條件件：。最最后后作作為為 的的近近似似值值，以以作作為為其其對對應(yīng)應(yīng)的的特特征征向向量量。第8頁/共31頁第九頁，共31頁。1(0)7612621324121251(1,0,0) ,10 .kkTkAx 例例1 1：用用冪冪法法求求矩矩陣陣的的按按模模最最大大的的特特征征值值和和

7、相相應(yīng)應(yīng)的的特特征征向向量量。取取0 1 2 18 191 0.2407717 0.3617725 0. 0000002 0.00000010 -0.8427010 -0.5878803 -0.4 472137 -0.44721360 -0.4815434 -0.7235450 -0.8 944271 -0.8944272 6.0000000 22.3043478 44. 9999954 44.9999981123kkxxx 3.2解解：應(yīng)應(yīng)用用算算法法的的結(jié)結(jié)果果第9頁/共31頁第十頁，共31頁。0 1 2 12 131 0.2857143 0.5000000 0.0 000420 0.00

8、001680 -1.0000000 -0.8125000 -0.50 00419 -0.50001680 -0.5714286 -1.0000000 -1.0000 000 -1.0000000 6.0000000 16.7142857 44.99 99989 45.0000002123kkxxx 3.3 應(yīng)應(yīng)用用算算法法的的結(jié)結(jié)果果第10頁/共31頁第十一頁，共31頁。( +1)( )( )=kkkuAuu 1 1也也有有. .這這表表明明對對這這種種情情況況冪冪法法仍仍然然有有效效。121 mmn 時(shí)時(shí)冪冪法法是是否否有有效效？12 前前面面假假定定。若若按按模模最最大大的的特特征征值值有

9、有多多個(gè)個(gè)，即即有有112,2mmAn是是重重根根，即即矩矩陣陣 仍仍條條有有件件個(gè)個(gè)線線性性無無關(guān)關(guān)的的特特征征向向量量。此此時(shí)時(shí)有有 ( )11111111kkkkmnmmmmnnuxxxx 1,mk顯顯然然，只只要要不不全全為為零零，當(dāng)當(dāng) 充充分分大大時(shí)時(shí)，就就有有( )111()kkmmuxx111mmxxA因因也也是是矩矩陣陣 相相應(yīng)應(yīng)于于 的的特特征征向向量量，所所以以，( )1kku 當(dāng)當(dāng) 充充分分大大時(shí)時(shí)，仍仍可可近近似似地地作作為為對對應(yīng)應(yīng)的的特特征征向向量量，同同樣樣第11頁/共31頁第十二頁，共31頁。 (1)( )( )kkkxAxx 如如果果按按迭迭代代所所得得向向量

10、量序序列列呈呈有有規(guī)規(guī)律律的的擺擺A綜綜上上可可知知，當(dāng)當(dāng) 的的特特征征值值分分布布為為12n或或12112mmnm ()()1 時(shí)時(shí)，用用冪冪法法可可以以計(jì)計(jì)算算出出及及相相應(yīng)應(yīng)的的特特征征向向量量。 冪冪法法計(jì)計(jì)算算簡簡便便易易行行，它它是是求求大大型型稀稀疏疏矩矩陣陣按按模模最最大大特特An動(dòng)動(dòng)，則則應(yīng)應(yīng)考考慮慮用用別別的的方方法法求求解解。此此外外，當(dāng)當(dāng)矩矩陣陣 無無 個(gè)個(gè)線線性性無無關(guān)關(guān)的的特特征征量量時(shí)時(shí)，冪冪法法收收斂斂很很慢慢，亦亦應(yīng)應(yīng)考考慮慮改改用用其其他他方方法法。征征值值的的常常用用方方法法。第12頁/共31頁第十三頁，共31頁。 ,AnnxA 設(shè)設(shè) 為為階階非非奇奇異異

11、矩矩陣陣，為為 的的特特征征值值與與相相應(yīng)應(yīng)反冪法是計(jì)算(j sun)矩陣按模最小的特征值及特征向量的方法(fngf)，也是修正特征值、求相應(yīng)特征向量的最有效(yuxio)的方法。的的特特征征向向量量，即即111AxxxA xA xx 1AA 此此式式表表明明，的的特特征征值值是是 的的特特征征值值的的倒倒數(shù)數(shù)，而而相相應(yīng)應(yīng)的的1A 特特征征向向量量不不變變。因因此此， 若若對對矩矩陣陣用用冪冪法法，即即可可計(jì)計(jì)算算1AA 出出的的按按模模最最大大的的特特征征值值，其其倒倒數(shù)數(shù)恰恰為為 的的按按模模最最小小的的 特特征征值值。這這就就是是反反冪冪法法的的基基本本思思想想。第13頁/共31頁第十

12、四頁，共31頁。o12o121211 ,;2 ,nnnnnnAAnxxxAnxxx 設(shè)設(shè)階階實(shí)實(shí)方方陣陣 滿滿足足：有有 個(gè)個(gè)線線性性無無關(guān)關(guān)的的特特征征向向量量的的 個(gè)個(gè)線線性性無無關(guān)關(guān)的的特特征征向向量量對對應(yīng)應(yīng)的的特特征征值值滿滿足足 。n 則則用用反反冪冪法法計(jì)計(jì)算算及及相相應(yīng)應(yīng)的的一一個(gè)個(gè)特特征征向向量量的的步步驟驟如如下下: :1( )(1)( )1(1)( ) kkkkkAAAuuuA uuAA 因因?yàn)闉榈牡挠?jì)計(jì)算算比比較較麻麻煩煩，而而且且往往往往不不能能保保持持矩矩陣陣的的一一些些好好性性質(zhì)質(zhì)（如如稀稀疏疏性性），因因此此，反反冪冪法法在在實(shí)實(shí)際際運(yùn)運(yùn)算算時(shí)時(shí)以以求求解解方方

13、程程組組 代代替替冪冪法法迭迭代代求求得得，每每迭迭代代一一次次要要解解一一個(gè)個(gè)線線性性方方程程組組。由由于于矩矩陣陣在在迭迭代代過過程程中中不不變變，故故當(dāng)當(dāng) 的的階階數(shù)數(shù)不不是是很很大大時(shí)時(shí)，可可考考慮慮對對 先先進(jìn)進(jìn)行行三三角角分分解解，則則每每次次迭迭代代只只要要解解兩兩個(gè)個(gè)三三角角形形方方程程組組。第14頁/共31頁第十五頁，共31頁。 ( -1)( -1)( -1)( -1)( )T(1)( )T(1)(1)1( )1 2 3 5 =16 kkkkkkkkkkkkknnkAALUuRuyuLzyUuzyuyyy (0)(0)k k對對 進(jìn)進(jìn)行行三三角角分分解解任任取取非非零零向向量

14、量做做初初始始特特征征向向量量；; ;4 4 解解方方程程組組，；當(dāng)當(dāng)時(shí)時(shí)，以以作作為為的的近近似似值值，作作相相應(yīng)應(yīng)的的近近似似特特征征向向量量。 ()3.4算算法法反反冪冪法法第15頁/共31頁第十六頁，共31頁。* 0 () ()iiiiiAAIAI用帶原點(diǎn)移位的反冪法來修正特征值，并求相應(yīng)的特征向量是非常有效的。設(shè)已知 的一個(gè)特征值 的近似值為，因接近 ，一般有故是矩陣的按模最小的特征值，且由上式可知，比值較小。因此，對用反冪法求一般收斂很快，通常只要經(jīng)過二、三次迭代就能達(dá)到較高的精度。第16頁/共31頁第十七頁，共31頁。 *(0)*( -1)( -1)( -1)( -1)( )T(

15、1)( )T(1)(1)1*( ) 1. (),2. ()3 5 =16 3. 5ijkkkkkkkkkkkkkiikAauNAILUuyuLzyUuzyuyyy k k輸輸入入近近似似值值，初初始始向向量量, ,誤誤差差限限 ，最最大大迭迭 代代次次數(shù)數(shù) 。作作三三角角分分解解 ; ;4 4 解解方方程程組組，；當(dāng)當(dāng)時(shí)時(shí)，以以+ +作作為為 的的近近似似算算值值法法：， 作作相相應(yīng)應(yīng)的的近近似似特特征征向向量量。第17頁/共31頁第十八頁，共31頁。(0)210 021012(0,0,1) . 2.930.9310 2.9300.931010.93100 0100 1/0.931TAAxAI

16、AI例：，用反冪法求矩陣 接近2.93的特征值，并求相應(yīng)的特征向量，取解：對作三角分解得40.931000.931000.93 1/0.9333.0000954,310(1, 0.9992431,0.9991478)(1,-1,1)0.001.TTur按算法迭代 次，與準(zhǔn)確值 的誤差小于，與準(zhǔn)確值比較，殘差第18頁/共31頁第十九頁，共31頁。1222,1(1) , diag(,) (1,2, ),2(),(), Tniijn nnTijn nijiji jAUU AUDinAUAaUBU AUbab 任任意意實(shí)實(shí)對對稱稱矩矩陣陣 可可通通過過正正交交相相似似變變換換化化成成對對角角陣陣 即即

17、存存在在 正正交交矩矩陣陣使使得得其其中中是是 的的特特征征值值中中各各列列即即為為相相應(yīng)應(yīng)的的特特征征向向量量。（ ）在在正正交交相相似似變變換換下下，矩矩陣陣元元素素的的平平方方和和不不變變。設(shè)設(shè)為為正正交交矩矩征征向向量量。理理論論基基礎(chǔ)礎(chǔ)陣陣：，記記則則,1ni j Jacobi方方法法用用來來求求實(shí)實(shí)對對稱稱矩矩陣陣的的全全部部特特征征值值及及相相應(yīng)應(yīng)特特Jacob ,iA通通過過一一次次正正交交變變換換 將將 中中一一對對非非零零的的非非對對角角元元素素化化成成零零 并并且且使使得得非非對對角角元元素素的的平平方方和和減減少少。反反復(fù)復(fù)進(jìn)進(jìn)行行上上述述過過程程，使使變變換換后后的的

18、矩矩陣陣的的非非對對角角元元素素的的平平方方和和趨趨于于零零，從從而而使使該該矩矩陣陣近近似似為為對對角角矩矩陣陣，得得到到全全部部特特征征方方法法的的基基本本思思值值和和特特路路：征征向向量量。第19頁/共31頁第二十頁，共31頁。cos ,1sin ,pqppqqpqqppqUuuunuU 其其中中，的的主主對對角角線線元元素素中中其其余余為為 ；而而其其非非主主對對角角線線元元素素中中維維空空間間中中的的二二維維坐坐其其余余為為標(biāo)標(biāo)旋旋0 0。稱稱為為轉(zhuǎn)轉(zhuǎn)矩矩陣陣。( )pqU 坐坐標(biāo)標(biāo)旋旋轉(zhuǎn)轉(zhuǎn)矩矩陣陣是是正正交交矩矩陣陣. .11cossin1( )1sincos11pqU 第20頁/

19、共31頁第二十一頁，共31頁。(1)(1)(1)22(1)22(1)(1)0, ()cossinsin2 sincossin2 cossin (, ) TpqqppqpqijppppqqpqqqppqqpqpiippiqiAaaAU AUaaaaaaaaaaaaaip qa 設(shè)設(shè) 為為實(shí)實(shí)對對稱稱矩矩陣陣，且且若若記記則則有有(1)(1)(1)(1)(1)(1)sincos ( , )1()sin2cos2 2()cot2 2qiiqpiqiijjiijpqqpqqpppqppqqpqaaaaaai jp qaaaaaaaa 如如果果取取 使使得得(1)(1)(/4)0,.pqqppqqpaa

20、Aaa 則則有有得得到到一一個(gè)個(gè)使使 中中非非零零的的非非對對角角元元素素變變成成零零的的正正交交相相似似變變換換第21頁/共31頁第二十二頁，共31頁。 (1)(2)( )(1)2(1)(1)2(1)(1)(1)(1)(1)(1), ( ),()()( , ),cossin ,kijijijijijjiijpiippiqiqiiqAAAAAE AaE Aaaaai jp q aaaaaa 對對重重復(fù)復(fù)上上述述過過程程得得到到一一個(gè)個(gè)矩矩陣陣序序列列?？煽勺C證，雖雖然然這這種種變變換換不不一一定定能能使使矩矩陣陣中中非非對對角角元元中中零零元元素素的的個(gè)個(gè)數(shù)數(shù)單單調(diào)調(diào)增增加加，但但可可保保證證

21、非非對對角角元元的的平平方方和和遞遞減減。以以 與與為為例例：設(shè)設(shè)，則則由由(1)(1)(1)(1)2(1)2(1)2(1)2(1)2,2222,sincos ,(, )=0()()()2()() +2() 2()( )2( ) piqipqqpijijpiqipqijijip qi jp qijpiqipqijip qi jp qaaip qaaE AaaaaaaaaE AaE A ，上上式式表表明明，在在上上述述旋旋轉(zhuǎn)轉(zhuǎn)變變換換下下，非非對對角角元元的的平平方方和和嚴(yán)嚴(yán)格格單單調(diào)調(diào)遞遞減減，因因而而對對角角元元的的平平方方和和單單調(diào)調(diào)遞遞增增。第22頁/共31頁第二十三頁，共31頁。( )

22、o( )( )1j( )( )o( )( )(1)(1) 0,2 ,max3 cot2,cos24 sin ,( )4 3.6 Jacobik kkkk kk kk kkkkkkp qijinkkp pq qkp qkp qkkijkAAp qaaaaaUUAaa o oo o1 1 令令；求求整整數(shù)數(shù)使使得得計(jì)計(jì)算算旋旋轉(zhuǎn)轉(zhuǎn)矩矩陣陣： 由由計(jì)計(jì)算算相相應(yīng)應(yīng)的的和和并并得得到到旋旋轉(zhuǎn)轉(zhuǎn)矩矩陣陣；計(jì)計(jì)算算法法求求實(shí)實(shí)對對稱稱矩矩陣陣全全部部特特征征值值和和對對應(yīng)應(yīng)的的特特征征向向量量：方方算算法法(1)( )(1)(1)(1)(1)( )( )(1)(1)( )( )o(1)(1) 2(1) (

23、 , ), =0, cossin , (, ) sincos , (, )5()()(),kkkkjiijpqqpkkkkpiippiqikkkkqiiqpiqikkkijijai jp qaaaaaaip qaaaaip qE AaE A ，； , ,若若(1)(1)(1)1122(0)(1)( )o, 12kkknnnaaaQU UUkk 則則為為特特征征值值，的的各各列列為為相相應(yīng)應(yīng)特特征征向向量量；否否則則，返返回回 ，重重復(fù)復(fù)上上述述過過程程。第23頁/共31頁第二十四頁，共31頁。 ( )2(0)( )( )2( )( )( )( )1j(1)(1)( )( )2Jacobi, l

24、im ()=lim0,Jacobi1 max()(1)()() 2() , k kk kk kkkkijkki jkkkkp qijp qinkkkkp qA nAAAAE AaaaaE An nAE AE Aa ：設(shè)設(shè) 為為 階階實(shí)實(shí)對對稱稱陣陣，對對 用用法法得得到到序序列列其其中中則則即即法法收收斂斂。：由由，得得；又又由由計(jì)計(jì)算算的的公公式式可可得得從從收收證證而而有有斂斂定定理理明明1(1)( )1( )22 ()1()1( )(1)(1)22 11,lim ()lim 1( )0(1)(1)JacobikkkkkkkE AE AE An nn nE AE An nn n 因因即即法

25、法收收斂斂。第24頁/共31頁第二十五頁，共31頁。說明(shumng)：o1 Jacobi;定定理理表表明明，法法是是收收斂斂的的Jacobi法法是是求求中中小小型型稠稠密密實(shí)實(shí)對對稱稱矩矩陣陣的的全全部部特特征征值值與與特特征征向向量量的的較較好好方方法法。o2 JacobiAnAn當(dāng)當(dāng) 的的階階數(shù)數(shù) 不不太太高高時(shí)時(shí)，算算法法的的收收斂斂速速度度很很快快；但但當(dāng)當(dāng) 的的 階階數(shù)數(shù) 變變得得較較大大時(shí)時(shí)，其其收收斂斂速速度度將將會會變變慢慢，即即法法 為為適適合合計(jì)計(jì)算算中中等等規(guī)規(guī)模模的的實(shí)實(shí)對對稱稱矩矩陣陣的的特特征征值值問問題題；o3 對對中中等等規(guī)規(guī)模模問問題題，具具有有較較好好的

26、的數(shù)數(shù)值值穩(wěn)穩(wěn)定定性性；求求得得的的結(jié)結(jié)果果 的的精精度度也也很很高高，得得到到的的特特征征向向量量正正交交性性很很好好；o4 不不足足之之處處：運(yùn)運(yùn)算算量量大大，不不能能保保持持矩矩陣陣的的特特殊殊形形狀狀 （如如稀稀疏疏性性）。第25頁/共31頁第二十六頁，共31頁。 00(0)12T(1)(0)(0)(0)0:1,2,cot20,4cos0.7071068,sin0.70710680.70710680.70710680 ( )0.70710680.70710680 ,001100.7071068030.70710680.70710680.70710682kpqUUAUA U 210121012AA 例例：用用JacobiJacobi方方法法求求 的的特特征征值值。解： 第26頁/共31頁第二十七頁，共31頁。11(1)230.707106780.47765830.88807380.45970081 0 00 0.888071:2,3,cot2,cos,sin 38 -0.45970080 0.4597008 ( ) 0.88807kpqUU T(2)(1)(1)(1)38 3.0000000 0.3250576 0.6279630 0.3250576 0.6339746 -0.0000000 0.6279630 0 2.3,U660254UAA