計(jì)算方法矩陣特征值和特征向量計(jì)算PPT課件

1、 常用解法常用解法1 1、 乘冪法和反冪法乘冪法和反冪法2 2、求實(shí)對稱矩陣特征值的雅可比方法、求實(shí)對稱矩陣特征值的雅可比方法3 3、求矩陣全部特征值的、求矩陣全部特征值的QR方法方法第1頁/共32頁 4.1 4.1 乘冪法和反冪法乘冪法和反冪法一、乘冪法一、乘冪法 乘冪法主要是用來求矩陣的按模最大的特征值與相應(yīng)的特征向量。它是通過迭代產(chǎn)生向量序列，由此計(jì)算特征值和特征向量。設(shè) n 階實(shí)矩陣n nAR的 n 個(gè)特征值為(1,2, )iin， 滿足120n，所對應(yīng)的 n 個(gè)特征向量 01kkuuAu任取非零的初始向量 ，構(gòu)造向量序列12, , nxxx線線性性無無關(guān)關(guān)。 1-1 kkjkjuuu

2、 向向量量逼逼近近A A的的主主特特征征值值（按按模模最最大大的的）對對應(yīng)應(yīng)的的特特征征向向量量，第2頁/共32頁 11211111111210,(2,3, ) lim()0 lim()0 () inkkiiiiiikkinkkkikiiiinxxkuxxx 由由得得故故只只要要 充充分分大大，就就有有1011,2,iniiiinx存在不全為零的常數(shù) （）,（這里假設(shè)0），使得u 101111121()()knnkkkkiiiiiiinkkiiiiuAuA uAxxxx 第3頁/共32頁因此，可把 作為與 相應(yīng)的特征向量的近似，1111 kkkuux 11211111121()()nkiiij

3、jkjinkikjiijjixxuuxx 有有 由111lim()0 =lim,(j1,2,) kjkikkkjunu 11kjkjuu 按上面式子計(jì)算矩陣按模最大的特征值與相應(yīng)的特征向量的方法稱為乘冪法。 乘冪法的收斂速度依賴于比值，比值越小，收斂越快。21 A 第4頁/共32頁1max1max1max1 max(),lim(),lim()( )kkkkkkkkkkkuAVuuuxVuVux，其中是 的絕對值最大的分量 幾點(diǎn)說明：）如果 的選取恰恰使得乘冪法計(jì)算仍能進(jìn)行。因?yàn)橛?jì)算過程中舍入誤差的影響，迭代若干次后，必然會產(chǎn)生一個(gè)向量它在 方向上的分量不為零，可以說實(shí)際中出現(xiàn)的可能性幾乎為零。

4、0111 10,0kuux 3）重根情形乘冪法也可以計(jì)算。）因計(jì)算過程中可能會出現(xiàn)溢出或成為的情形。解決方法：每次迭代所求的向量都要規(guī)范化。因此，乘冪法實(shí)際使用的計(jì)算公式是11111 2,(1)0(1)kkux 第5頁/共32頁二、乘冪法的加速二、乘冪法的加速 因?yàn)槌藘绶ǖ氖諗克俣仁蔷€性的，而且依賴于因?yàn)槌藘绶ǖ氖諗克俣仁蔷€性的，而且依賴于比值比值 ,當(dāng)比值接近于當(dāng)比值接近于1時(shí)，乘冪法收斂很慢。時(shí)，乘冪法收斂很慢。乘冪法加速有多種，重點(diǎn)介紹原點(diǎn)平移法乘冪法加速有多種，重點(diǎn)介紹原點(diǎn)平移法。21 11211 12211 ()() ()()iikkkkkkknnnAApIApApIApIuAuuA

5、pI upppxxxpp矩陣 與的特征值有以下關(guān)系：若是的特征值，則就是的特征值，而且相應(yīng)的特征向量不變。如果用矩陣按計(jì)算，則有 第6頁/共32頁1211 122111211()() ()() (2,3,)kkkkknnniiuApI upppxxxppppppinp 適當(dāng)?shù)剡x取 ，使得且 這樣，用乘冪法計(jì)算的最大模特征值及相應(yīng)特征向量的收斂速度比用乘冪法計(jì)算要快。這種加速收斂的方法稱為原點(diǎn)平移法。1ApIpA 第7頁/共32頁123123221222221121121 00)1(), 2 (2,3,2 ) nnninnnnnnppAppppinpp 原原點(diǎn)點(diǎn)平平移移法法使使用用簡簡便便，但但

6、 的的選選取取困困難難。在在一一些些簡簡單單情情形形， 可可估估計(jì)計(jì)。如如當(dāng)當(dāng)矩矩陣陣 的的特特征征值值滿滿足足（或或時(shí)時(shí)，取取則則有有且且 11 因因此此，用用原原點(diǎn)點(diǎn)平平移移法法求求可可使使收收斂斂速速度度加加快快。第8頁/共32頁三、反冪法三、反冪法 反冪法是計(jì)算矩陣按模最小的特征值及特征向反冪法是計(jì)算矩陣按模最小的特征值及特征向量的方法，也是修正特征值、求相應(yīng)特征向量的最量的方法，也是修正特征值、求相應(yīng)特征向量的最有效的方法。有效的方法。設(shè)為非奇異矩陣，、為的特征值與相應(yīng)的特征向量，即此式表明，的特征值是的特征值的倒數(shù)，而相應(yīng)的特征向量不變。因此，若對矩陣用乘冪法，即可計(jì)算出的按模最大

7、的特征值，其倒數(shù)恰為的按模最小的特征值。 這就是反冪法的基本思想。1111 1 iiiiiiiiAnnxAAxxAxxAAAAA 第9頁/共32頁1111-11-1kkkkkkkAuA uAAAuuuA uuA對矩陣用乘冪法得， 因?yàn)榈挠?jì)算比較麻煩，而且往往不能保持矩陣的一些好性質(zhì)（如稀疏性），因此，反冪法在實(shí)際計(jì)算時(shí)以求解方程組 ，代替迭代求得，每迭代一次要解一線性方程組。 由于矩陣在迭代過程中不變，故可對先進(jìn)行三角分解，每次迭代只要解兩個(gè)三角形方程組。反冪法規(guī)范后的計(jì)算格式反冪法規(guī)范后的計(jì)算格式1max()kkkkkkkAuVCuVuC limm ax()nkknxVx 1limkknC

8、第10頁/共32頁 0 () ()iiijjiiijjiiAAIAI 用用帶帶原原點(diǎn)點(diǎn)平平移移的的反反冪冪法法來來修修正正特特征征值值，并并求求相相應(yīng)應(yīng)的的特特征征向向量量是是非非常常有有效效的的。設(shè)設(shè)已已知知的的一一個(gè)個(gè)特特征征值值的的近近似似值值為為，因因接接近近，一一般般有有故故是是矩矩陣陣的的按按模模最最小小的的特特征征值值，且且由由上上式式可可知知，比比值值較較小小。因因此此，對對用用反反冪冪法法求求一一般般收收斂斂很很快快，通通常常只只要要經(jīng)經(jīng)過過二二、三三次次迭迭代代就就能能達(dá)達(dá)到到較較高高的的精精度度。四、利用原點(diǎn)平移的反冪法求任一特征值和特征向量第11頁/共32頁 4.2 雅

9、可比（ Jacobi ）方法 Jacobi方法是用來求實(shí)對稱矩陣的全部特征方法是用來求實(shí)對稱矩陣的全部特征值和對應(yīng)特征向量的一個(gè)古典算法。值和對應(yīng)特征向量的一個(gè)古典算法。Jacobi方法方法的基本思想是對矩陣的基本思想是對矩陣A做一系列的正交相似變換，做一系列的正交相似變換，使其非對角元素收斂到零，從而使該矩陣近似為使其非對角元素收斂到零，從而使該矩陣近似為對角矩陣，得到全部特征值和特征向量。對角矩陣，得到全部特征值和特征向量。第12頁/共32頁一、古典雅可比方法11122122cossinsincosaaARaa先考慮二維問題，A為實(shí)對稱矩陣，R為正交矩陣1112-1T12122ccos ,

10、sincscs=scscsaaARARRARaa做正交相似變換，記222211122212221122221222111112222()()=()()2c acsas acsacs aacsacs aas acsac a2212221122211212()()=010Tcsacs aaaasscac如果，則RAR 成為對角陣，上述方程等價(jià)于 第13頁/共32頁2212221122211212()()=010Tcsacs aaaasscac如果，則RAR 成為對角陣，上述方程等價(jià)于 2221112sin10cosaastttca令， =代入則有 2,11tcsc tt 解二次方程可以求出 容易得

11、到1TT111122Tcs0sc0aARARRaR（ ）（ ），的兩個(gè)列向量是相應(yīng)的特征向量。第14頁/共32頁0102021211例 考慮三階矩陣 A000.70700.7070100.70700.707將A 中（3,1）和（1,3）位置上的元素變成0，取RT10030.7070=0.70720.70700.7071AR AR做正交相似變換后得到第15頁/共32頁110.8880.46000.4600.8880001 再將A中（2,1）和（1,2）位置上的元素變成0，取RT2113.36600.325=01.6340.6280.3250.6281AR AR做正交相似變換后得到2210000.

12、9750.22600.2260.975再將A 中（2,3）和（3,2）位置上的元素變成0，取R第16頁/共32頁T3223.3660.07350.317=0.07351.78000.31701.145AR AR做正交相似變換后得到kk雅可比方法是一個(gè)迭代過程，它生成的是一個(gè)矩陣的序列A，當(dāng)k越大時(shí)A 就越接近于對角矩陣，從而得到A特征值更好的近似。第17頁/共32頁 11cossin1R1sincos11 ()pqqppq定定義義n n階階正正交交矩矩陣陣第18頁/共32頁 T(1)1ccos ,sin=ijn nsARARa記，做正交相似變換，得(1)(1)(1)(1)22(1)22(1)2

13、2( ,)(,)(,)22()()ijijpjpjqjqjpjqjpppppqqqqqpppqqqpqpqqqppaai jp qacasajp qasacajp qac acsas aac acsas aacsacs aa 22122()()=010pqqqpppqqqpppqcsacs aaaaasscac（ ）令，則=0，上述方程等價(jià)于 第19頁/共32頁2sin10cosqqpppqaastttca令， =代入則有 2,11tcsc tt 解二次方程可以求出 容易得到22122()()=010pqqqpppqqqpppqcsacs aaaaasscac令，則=0，上述方程等價(jià)于 第20

14、頁/共32頁21()( )2pqD AD Aa2(1)22112nniiiipqiiaaa1TARARJacobi算法的基本思想算法的基本思想: +12112TTTkkkRR RR RRA=A12TnddR Rd=A212D(A)S(A)niiiijijaa記=（對角元的平方和）=（非對角元的平方和）T21kRRR RR記，的每個(gè)列向量是對應(yīng)的特征向量。21()( )2pqS AS Aa第21頁/共32頁二、二、 雅可比過關(guān)法雅可比過關(guān)法（1）循環(huán)）循環(huán)Jacobi方法：方法： （2）Jacobi過關(guān)法：過關(guān)法： (,)(1,2)(1,3),(),(2,3),(2,),(),(,)()2p q

15、nnnnp qn n選擇依次為1,1,對每個(gè)做雅可比變換，完成上述1次變換稱做了一次掃描。( )S A 逐次掃描，直到為止。( )11( )( )qkkkpanJacobS AAinS 如果小于某個(gè)小參數(shù)，就可以讓它過關(guān)，不做使它零化的變換了，這樣可以節(jié)約些計(jì)算量。每次掃描所取的小參數(shù)是一個(gè)界限，一般第一個(gè)界限取為=，其余取為=。直到這為稱止。為過關(guān)法。第22頁/共32頁多項(xiàng)式運(yùn)算函數(shù)r=roots(p)：求多項(xiàng)式的零點(diǎn)p=poly(r) : 以r為零點(diǎn)的多項(xiàng)式p=poly(A): A的特征多項(xiàng)式PA=polyval(p,S):按數(shù)組運(yùn)算規(guī)則，計(jì)算多項(xiàng)式的值 其中S，PA為矩陣PM=polyv

16、alm(p,S):按矩陣運(yùn)算規(guī)則，計(jì)算多項(xiàng)式的值, 其中S，PM為矩陣 p=conv(p1,p2)：多項(xiàng)式的乘積q,r=deconv(p1,p2)：多項(xiàng)式的除法，p1/p2 p1(x)=p2(x)q(x)+r(x)第23頁/共32頁【例】由給定根向量求多項(xiàng)式系數(shù)向量。R=-0.5,-0.3+0.4*i,-0.3-0.4*i;P=poly(R)PPR=poly2str(P,x) P = 1.0000 1.1000 0.5500 0.1250PPR = x3 + 1.1 x2 + 0.55 x + 0.125 第24頁/共32頁【例】求多項(xiàng)式 的零點(diǎn)。 r=roots(1 -6 15 -20 15

17、 -6 1)r = 1.0042 + 0.0025i 1.0042 - 0.0025i 1.0000 + 0.0049i 1.0000 - 0.0049i 0.9958 + 0.0024i 0.9958 - 0.0024i665432(1)615201561yxxxxxxx注：盡管利用注：盡管利用MATLAB使得從系數(shù)轉(zhuǎn)換到零點(diǎn)或從零使得從系數(shù)轉(zhuǎn)換到零點(diǎn)或從零點(diǎn)轉(zhuǎn)換到系數(shù)都非常容易，但是使用時(shí)一定要注意計(jì)點(diǎn)轉(zhuǎn)換到系數(shù)都非常容易，但是使用時(shí)一定要注意計(jì)算的精度。如果存在重根，這種轉(zhuǎn)換可能會降低精度。算的精度。如果存在重根，這種轉(zhuǎn)換可能會降低精度。對于數(shù)值計(jì)算，計(jì)算重根是最困難的問題之一。對于數(shù)值

18、計(jì)算，計(jì)算重根是最困難的問題之一。第25頁/共32頁【例】求3階方陣A的特征多項(xiàng)式。 A=11 12 13;14 15 16;17 18 19;PA=poly(A) PPA=poly2str(PA,x) PA = 1.0000 -45.0000 -18.0000 -0.0000PPA = x3 - 45 x2 - 18 x - 2.8387e-015 第26頁/共32頁【例】求 的“商”及“余”多項(xiàng)式。 p1=conv(1,0,2,conv(1,4,1,1);p2=1 0 1 1;q,r=deconv(p1,p2);cq=商多項(xiàng)式為 ; cr=余多項(xiàng)式為 ;disp(cq,poly2str(q

19、,x)disp(cr,poly2str(r,x) 商多項(xiàng)式為 x + 5余多項(xiàng)式為 5 x2 + 4 x + 3 1) 1)(4)(2(32sssss第27頁/共32頁n dot(x,y) 向量的內(nèi)積nnorm ： 矩陣或向量范數(shù)n det(A) 方陣的行列式；nrank(A) 矩陣的秩；ntrace(A) 矩陣的跡；nrref(A) 初等變換化矩陣A為階梯矩陣ninv(A) 矩陣的逆；即 A-1npinv(A) 矩陣的廣義逆A+north(A) 將A標(biāo)準(zhǔn)正交化n cond(A,flag) 矩陣的條件數(shù), flag=2, 1, inf, fro;線性代數(shù)常用函數(shù)第28頁/共32頁nd=eig(A) ： 方陣的特征值； V,D=eig(A) : A*V=V*Dn c=condeig(A) ： 向量c中包含矩陣A關(guān)于各 特征值的條件數(shù)n V,D,c=condeig(A)：例:nA=1 0 0;1 2 0;1 2 3, nd=eig(A), nV,D=eig(A),nC=condeig(A), V,D,C=condeig(A),第29頁/共32頁例：例：觀察觀察7 7階隨機(jī)矩陣特征值的分布階隨機(jī)矩陣特征值的分布a=rands(7,7) %a=ra