1、上頁(yè)上頁(yè)下頁(yè)下頁(yè)第第8章章 矩陣特征問(wèn)題的計(jì)算矩陣特征問(wèn)題的計(jì)算 8.1 引言引言 8.2 冪法及反冪法冪法及反冪法 8.3 豪斯霍爾德方法豪斯霍爾德方法 8.4 QR方法方法上頁(yè)上頁(yè)下頁(yè)下頁(yè)8.1 引引 言言 工程技術(shù)中有多種振動(dòng)問(wèn)題，如橋梁或建筑物的工程技術(shù)中有多種振動(dòng)問(wèn)題，如橋梁或建筑物的振動(dòng)，機(jī)械零件、飛機(jī)機(jī)翼的振動(dòng)，及一些穩(wěn)定性分振動(dòng)，機(jī)械零件、飛機(jī)機(jī)翼的振動(dòng)，及一些穩(wěn)定性分析和相關(guān)分析在數(shù)學(xué)上都可轉(zhuǎn)化為求矩陣特征值與特析和相關(guān)分析在數(shù)學(xué)上都可轉(zhuǎn)化為求矩陣特征值與特征向量的問(wèn)題征向量的問(wèn)題. 下面先復(fù)習(xí)一些矩陣的特征值和特征向量的基礎(chǔ)下面先復(fù)習(xí)一些矩陣的特征值和特征向量的基礎(chǔ)知識(shí)知識(shí)

2、.上頁(yè)上頁(yè)下頁(yè)下頁(yè) 定義定義1 已知已知n階矩陣階矩陣A=(aij)，則，則)2()(det)det()(12211212222111211的項(xiàng)的項(xiàng)次數(shù)次數(shù) naaaaaaaaaaaaAInnnnnnnnnn 稱為稱為A的的特征多項(xiàng)式特征多項(xiàng)式. 一般有一般有n個(gè)根個(gè)根(實(shí)的或復(fù)的，復(fù)根按重?cái)?shù)計(jì)算實(shí)的或復(fù)的，復(fù)根按重?cái)?shù)計(jì)算)稱為稱為A的的特征值特征值. 用用(A)表示表示A的所有特征值的集合的所有特征值的集合. A的特征方程的特征方程)1 . 1(0)det()( AI 上頁(yè)上頁(yè)下頁(yè)下頁(yè) 設(shè)設(shè)為為A的特征值，相應(yīng)的齊次方程組的特征值，相應(yīng)的齊次方程組 注：注：當(dāng)當(dāng)A為實(shí)矩陣時(shí)，為實(shí)矩陣時(shí)， (

3、)=0為實(shí)系數(shù)為實(shí)系數(shù)n次代數(shù)次代數(shù)方程，其復(fù)根是共軛成對(duì)出現(xiàn)方程，其復(fù)根是共軛成對(duì)出現(xiàn).)2 . 1(0)( xAI 的的非零解非零解x稱為矩陣稱為矩陣A的對(duì)應(yīng)于的對(duì)應(yīng)于的的特征向量特征向量. 210131012A 例例1 求求A的特征值及特征向量，其中的特征值及特征向量，其中上頁(yè)上頁(yè)下頁(yè)下頁(yè). 0)4)(2)(1(8147210131012)det()(23 AI 解解 矩陣矩陣A的特征方程為的特征方程為求得矩陣求得矩陣A的特征值為：的特征值為：. 4, 2, 1 對(duì)應(yīng)于各特征值矩陣對(duì)應(yīng)于各特征值矩陣A的特征向量分別為：的特征向量分別為：.121,101,111321 xxx上頁(yè)上頁(yè)下頁(yè)下

4、頁(yè) 定理定理1 設(shè)設(shè)為為ARnn的特征值的特征值, 且且Ax=x (x 0)，則有則有 - -p為為A- -pI的特征值，即的特征值，即(A- -pI)x=(- -p)x ； c為的為的cA特征值特征值(c0為常數(shù)為常數(shù))； 下面敘述有關(guān)特征值的一些下面敘述有關(guān)特征值的一些結(jié)論結(jié)論： k為為Ak的特征值，即的特征值，即Akx=kx ； 設(shè)設(shè)A為非奇異矩陣，那么為非奇異矩陣，那么0 , 且且- -1為為A- -1的特的特征值，即征值，即A- -1x=- -1x .上頁(yè)上頁(yè)下頁(yè)下頁(yè) 定理定理2 設(shè)設(shè)i(i=1,2,n)為為n階矩陣階矩陣A=(aij)的特征值，的特征值，則有則有)(Atraniii

5、nii 11 稱為稱為A的的跡跡； .nA21 定理定理3 設(shè)設(shè)ARnn，則有，則有. )()(AAT 定理定理4 設(shè)設(shè)A 為分塊上三角矩陣，即為分塊上三角矩陣，即, mmmmAAAAAAA22211211其中每個(gè)對(duì)角塊其中每個(gè)對(duì)角塊Aii均為方陣，則均為方陣，則. )()(iiniAA1 上頁(yè)上頁(yè)下頁(yè)下頁(yè) 定理定理5 設(shè)設(shè)A與與B為相似矩陣（即存在非奇異矩陣為相似矩陣（即存在非奇異矩陣P使使B=P- -1AP），則），則 定理定理5說(shuō)明，一個(gè)矩陣說(shuō)明，一個(gè)矩陣A經(jīng)過(guò)相似變換，其特征經(jīng)過(guò)相似變換，其特征值不變值不變. 一個(gè)虧損矩陣是一個(gè)沒(méi)有足夠特征向量的矩陣，一個(gè)虧損矩陣是一個(gè)沒(méi)有足夠特征向量

6、的矩陣，虧損矩陣在理論上和計(jì)算上都存在困難虧損矩陣在理論上和計(jì)算上都存在困難. A與與B有相同的特征值；有相同的特征值； 如果如果y是是B的特征向量，則的特征向量，則Py是是A的特征向量的特征向量. 定義定義2 如果實(shí)矩陣如果實(shí)矩陣A有一個(gè)重?cái)?shù)為有一個(gè)重?cái)?shù)為k的特征值的特征值, 且對(duì)應(yīng)于且對(duì)應(yīng)于的的A的線性無(wú)關(guān)的特征向量個(gè)數(shù)的線性無(wú)關(guān)的特征向量個(gè)數(shù)|2|n|，則對(duì)任何非零向量則對(duì)任何非零向量v0(a1 0)，冪法的算式成立，冪法的算式成立.又設(shè)又設(shè)A有有n個(gè)線性無(wú)關(guān)的特征向量，個(gè)線性無(wú)關(guān)的特征向量，1對(duì)應(yīng)的對(duì)應(yīng)的r個(gè)線性個(gè)線性無(wú)關(guān)的特征向量為無(wú)關(guān)的特征向量為x1,x2,xr，則由，則由(2.2

7、)式有式有 如果如果A的主特征值為實(shí)的重根的主特征值為實(shí)的重根, 即即1=2=r, 且且 |r|r+1|n|，,)/(11110 nriikiiriiikkkxaxavAv 上頁(yè)上頁(yè)下頁(yè)下頁(yè)).0(lim111 riiiriiikkkxaxav設(shè)設(shè) 為為A的特征向量，這說(shuō)明當(dāng)?shù)奶卣飨蛄?，這說(shuō)明當(dāng)A的主特征值是實(shí)的重根的主特征值是實(shí)的重根時(shí)，定理時(shí)，定理5的結(jié)論還是正確的的結(jié)論還是正確的. 應(yīng)用應(yīng)用冪法冪法計(jì)算計(jì)算A的主特征值的主特征值1及其對(duì)應(yīng)的特征向及其對(duì)應(yīng)的特征向量時(shí)，如果量時(shí)，如果|1|1(或或|1|2|n|，則對(duì)任意非零初始，則對(duì)任意非零初始向量向量v0=u0(a1 0)，有冪法計(jì)算公

8、式為，有冪法計(jì)算公式為則有則有 ,)max(lim11xxukk .lim1 kk上頁(yè)上頁(yè)下頁(yè)下頁(yè)例例1 用冪法計(jì)算矩陣用冪法計(jì)算矩陣 1634310232A的主特征值與其對(duì)應(yīng)的特征向量的主特征值與其對(duì)應(yīng)的特征向量.解解取取 v0=u0=(0,0,1)T , 則則 TTvuv25. 0 , 1, 5 . 01, 4,1 , 4 , 211111 ), 2 , 1(max1 k/vuvAuvkkkkkkk 上頁(yè)上頁(yè)下頁(yè)下頁(yè)直到直到k=8 時(shí)的計(jì)算結(jié)果見(jiàn)下表時(shí)的計(jì)算結(jié)果見(jiàn)下表k1 2, 4, 1, 4 0.5, 1, 0.252 4.5, 9, 7.75 90.5, 1, 0.86113 5.72

9、22, 11.4444, 8.36111.44440.5, 1, 0.73604 5.4621, 10.9223, 8.2306 10.92230.5, 1, 0.75365 5.5075, 11.0142, 8.2576 11.01420.5, 1, 0.74946 5.4987, 10.9974, 8.2494 10.99740.5, 1, 0.75017 5.5002, 11.0005, 8.2501 11.00050.5, 1, 0.75008 5.5000, 11.0000, 8.2500 11.00000.5, 1, 0.7500TkvTku Tx7500. 0,0 . 1,5 .

10、 0,0000.1111 從而從而k 見(jiàn)書(shū)見(jiàn)書(shū)p303- -例例3.上頁(yè)上頁(yè)下頁(yè)下頁(yè)8.2.2 冪法的加速方法冪法的加速方法1、原點(diǎn)平移法、原點(diǎn)平移法 由前面討論知道，應(yīng)用冪法計(jì)算由前面討論知道，應(yīng)用冪法計(jì)算A的主特征值的的主特征值的收斂速度主要由比值收斂速度主要由比值 r=|2/1|來(lái)決定，但當(dāng)來(lái)決定，但當(dāng)r 接近于接近于1時(shí)，收斂可能很慢時(shí)，收斂可能很慢. 這時(shí)，一個(gè)補(bǔ)救辦法是采用加速這時(shí)，一個(gè)補(bǔ)救辦法是采用加速收斂的方法收斂的方法.其中其中p為參數(shù)，設(shè)為參數(shù)，設(shè)A的特征值為的特征值為 i，則對(duì)矩陣，則對(duì)矩陣B的特征的特征值為值為 i- -p ，而且，而且A, B的特征向量相同的特征向量相

11、同. 引進(jìn)矩陣引進(jìn)矩陣 B=A- -pI .上頁(yè)上頁(yè)下頁(yè)下頁(yè) 如果要計(jì)算如果要計(jì)算A的主特征值的主特征值 1, 只要只要選擇合適的數(shù)選擇合適的數(shù)p，使使 1- -p為矩陣為矩陣B=A- -pI 的主特征值，且的主特征值，且 1212max ppini那么，對(duì)矩陣那么，對(duì)矩陣B=A- -pI應(yīng)用冪法求其主特征值應(yīng)用冪法求其主特征值 1- -p, 收收斂速度將會(huì)加快斂速度將會(huì)加快. 這種通過(guò)求這種通過(guò)求B=A- -pI的主特征值和特的主特征值和特征向量，而得到征向量，而得到A的主特征值和特征向量的方法叫的主特征值和特征向量的方法叫原原點(diǎn)平移法點(diǎn)平移法. 對(duì)于對(duì)于A的特征值的某種分布，它是十分有的特

12、征值的某種分布，它是十分有效的效的.上頁(yè)上頁(yè)下頁(yè)下頁(yè)例例4 設(shè)設(shè)AR44有特征值有特征值),4 , 3 , 2 , 1(15 jji 比值比值r=|2/1|0.9. 做變換做變換B=A- -12I (p=12),則則B的特征值為的特征值為. 1, 0, 1, 24321 應(yīng)用冪法計(jì)算應(yīng)用冪法計(jì)算B的主特征值的主特征值1的收斂速度的比值為的收斂速度的比值為. 9 . 021121212 pp 雖然常常能夠選擇有利的雖然常常能夠選擇有利的p值值, 使冪法得到加速使冪法得到加速, 但設(shè)計(jì)一個(gè)自動(dòng)選擇適當(dāng)參數(shù)但設(shè)計(jì)一個(gè)自動(dòng)選擇適當(dāng)參數(shù)p的過(guò)程是困難的的過(guò)程是困難的.上頁(yè)上頁(yè)下頁(yè)下頁(yè) 下面考慮當(dāng)下面考慮

13、當(dāng)A的特征值是實(shí)數(shù)時(shí)，怎樣選擇的特征值是實(shí)數(shù)時(shí)，怎樣選擇p使采使采用冪法計(jì)算用冪法計(jì)算1得到加速得到加速.ppn 1且使且使收斂速度的比值收斂速度的比值.min,max112 ppppn 設(shè)設(shè)A的特征值都是實(shí)數(shù)，且滿足的特征值都是實(shí)數(shù)，且滿足)10. 2(,121nn 則對(duì)實(shí)數(shù)則對(duì)實(shí)數(shù)p，使矩陣，使矩陣A- -pI的主特征值為的主特征值為 1- -p或或 n- -p時(shí)，時(shí)，當(dāng)當(dāng)我們計(jì)算我們計(jì)算 1及及x1時(shí)，首先應(yīng)選取時(shí)，首先應(yīng)選取p使使上頁(yè)上頁(yè)下頁(yè)下頁(yè)顯然，當(dāng)顯然，當(dāng) 2- -p=- -( n- -p )時(shí)，即時(shí)，即 P=( 2+ n)/2P* 時(shí)時(shí)為最小值，這時(shí)為最小值，這時(shí)收斂速度的比值

14、收斂速度的比值為為.2212112nnnpppp 當(dāng)希望計(jì)算當(dāng)希望計(jì)算 n時(shí)，應(yīng)選取時(shí)，應(yīng)選取 p=( 1+ n-1)/2P* 使得應(yīng)用冪法計(jì)算使得應(yīng)用冪法計(jì)算 n得到加速得到加速. 當(dāng)當(dāng)A的特征值都是實(shí)數(shù)，滿足的特征值都是實(shí)數(shù)，滿足且且 2, n能初步估計(jì)出來(lái)，我們就能確定能初步估計(jì)出來(lái)，我們就能確定P*的近似值的近似值.nn 121上頁(yè)上頁(yè)下頁(yè)下頁(yè) 例例2 用原點(diǎn)平移加速法求用原點(diǎn)平移加速法求例例1中矩陣中矩陣A的主特征值的主特征值與其對(duì)應(yīng)的特征向量與其對(duì)應(yīng)的特征向量.5 . 36345 . 510235 . 4 B,1634310232 A對(duì)對(duì)B應(yīng)用冪法，仍應(yīng)用冪法，仍取取 v0=(0,

15、0,1)T , 則則 .875. 0 , 1, 5 . 01, 4,5 . 3 , 4 , 211111TTvuu ), 2 , 1(max1 k/vuvBuvkkkkkkk 解解 取取p=- -2.5, 做平移變換做平移變換B=A- -pI，則，則上頁(yè)上頁(yè)下頁(yè)下頁(yè)迭代迭代5步的計(jì)算結(jié)果見(jiàn)下表步的計(jì)算結(jié)果見(jiàn)下表k1 2, 4, 3.54 0.5, 1, 0.8752 7, 14, 10.5625 140.5, 1, 0.75453 6.76, 13.5179, 10.1406 13.51790.5, 1, 0.75074 6.7503, 13.5007, 10.1256 13.50070.5,

16、 1, 0.75005 6.7500, 13.5000, 10.1250 13.50000.5, 1, 0.7500TkuTkv可得到可得到B的主特征值為的主特征值為 1 13.5000, 主特征向量為主特征向量為 v1 (0.5 ,1.0, 0.7500)T ,因此，因此，A的主特征值為的主特征值為 1 = 1 +p 11.0000, 主特征向量仍為主特征向量仍為 x1 =(0.5,1,0.7500)T .k 上頁(yè)上頁(yè)下頁(yè)下頁(yè) 原點(diǎn)位移的加速方法，是一個(gè)矩陣變換方法原點(diǎn)位移的加速方法，是一個(gè)矩陣變換方法. 這這種變換容易計(jì)算，又不破壞矩陣種變換容易計(jì)算，又不破壞矩陣A的稀疏性，但的稀疏性，但

17、p的的選擇依賴對(duì)選擇依賴對(duì)A的特征值分布的大致了解的特征值分布的大致了解. 見(jiàn)書(shū)見(jiàn)書(shū)p306- -例例5.上頁(yè)上頁(yè)下頁(yè)下頁(yè) 設(shè)設(shè)ARnn為為對(duì)稱矩陣對(duì)稱矩陣，稱，稱.),(),()(xxxAxxR 為向量為向量x的的瑞利商瑞利商，其中，其中(x, x)=xTx為內(nèi)積為內(nèi)積. 由定理由定理11知道，實(shí)對(duì)稱矩陣知道，實(shí)對(duì)稱矩陣A的特征值的特征值 1及及 n可用可用瑞利商瑞利商的的極限值表示極限值表示. 下面我們將下面我們將瑞利商瑞利商應(yīng)用到用冪法計(jì)算應(yīng)用到用冪法計(jì)算實(shí)對(duì)稱矩陣實(shí)對(duì)稱矩陣A的主特征值的加速上來(lái)的主特征值的加速上來(lái).2、瑞利商、瑞利商(Rayleigh)加速加速上頁(yè)上頁(yè)下頁(yè)下頁(yè) 定理定

18、理14 設(shè)設(shè)ARnn為為對(duì)稱矩陣對(duì)稱矩陣，特征值滿足，特征值滿足對(duì)應(yīng)的特征向量對(duì)應(yīng)的特征向量xi滿足滿足(xi, xj)=ij (單位正交向量單位正交向量) ，應(yīng)用冪法公式應(yīng)用冪法公式(2.9)計(jì)算計(jì)算A的主特征值的主特征值 1，則規(guī)范化，則規(guī)范化向量向量uk的的瑞利商瑞利商給出給出 1的較好的近似值為的較好的近似值為,121nn kkkkkkuuuAuuR2121, 由此可見(jiàn)，由此可見(jiàn)，R(uk)比比k更快的收斂于更快的收斂于 1.上頁(yè)上頁(yè)下頁(yè)下頁(yè) 證明證明 由由(2.8)式及式及,)max(,)max(00100uAuAAuvuAuAukkkkkkk )11. 2(.),(),(),(),

19、()(2121122112200001 knjkjjnjkjjkkkkkkkkkaauAuAuAuAuuuAuuR 得得上頁(yè)上頁(yè)下頁(yè)下頁(yè) 冪法的冪法的瑞利商加速迭代公式瑞利商加速迭代公式可以寫為可以寫為 kkkkkkkkkkvukuuuvAuv /), 2 , 1(),(),(1111其中其中A為為n階實(shí)對(duì)稱矩陣階實(shí)對(duì)稱矩陣.,11kkux 對(duì)給定的誤差限對(duì)給定的誤差限 ，當(dāng)，當(dāng)| kk- -1| 時(shí)，取近似值時(shí)，取近似值上頁(yè)上頁(yè)下頁(yè)下頁(yè)8.2.3 反冪法反冪法 反冪法是用于求非奇異矩陣反冪法是用于求非奇異矩陣A的的按模最小的特征按模最小的特征值和對(duì)應(yīng)特征向量值和對(duì)應(yīng)特征向量的方法的方法. 而

20、結(jié)合原點(diǎn)平移法的反冪而結(jié)合原點(diǎn)平移法的反冪法則可以求矩陣法則可以求矩陣A的任何一個(gè)的任何一個(gè)具有先了解的特征值和具有先了解的特征值和對(duì)應(yīng)的特征向量對(duì)應(yīng)的特征向量。設(shè)矩陣設(shè)矩陣A非奇異非奇異,其特征值其特征值 i (i=1,2,n) ,滿足滿足0121 nn 其相應(yīng)的特征向量其相應(yīng)的特征向量x1,x2,xn線性無(wú)關(guān)，則線性無(wú)關(guān)，則 A- -1 的特征的特征值為值為1/ i ，對(duì)應(yīng)的特征向量仍為，對(duì)應(yīng)的特征向量仍為xi (i=1,2,n).iiiiiixxAxAx11 上頁(yè)上頁(yè)下頁(yè)下頁(yè)此時(shí)此時(shí), A- -1的特征值滿足的特征值滿足11111 nn因此因此, 對(duì)對(duì)A- -1應(yīng)用冪法應(yīng)用冪法,可求出其

21、可求出其主特征值主特征值1/ n k 和和特征向量特征向量 xn uk .從而求得從而求得A的的按模最小按模最小特征值特征值 n 1/k 和對(duì)應(yīng)的和對(duì)應(yīng)的特征向量特征向量 xn uk ，這種求這種求A- -1的方法就稱的方法就稱為為反冪法反冪法.上頁(yè)上頁(yè)下頁(yè)下頁(yè)為了避免求為了避免求A- -1, 可通過(guò)解線性方程組可通過(guò)解線性方程組Avk=uk- -1得到得到vk，采用采用LU分解法，即先對(duì)分解法，即先對(duì)A進(jìn)行進(jìn)行LU分解分解A=LU, 此時(shí)此時(shí)反冪反冪法的迭代公式法的迭代公式為為 , 2 , 1/max,1 kvuvvzUvzuLzkkkkkkkkkkk 求出求出解解求出求出解解 ), 2 ,

22、 1(max11 k/vuvuAvkkkkkkk knknux ,1 反冪法的迭代公式反冪法的迭代公式為為上頁(yè)上頁(yè)下頁(yè)下頁(yè)對(duì)給定的誤差對(duì)給定的誤差 ，當(dāng)，當(dāng)|kk- -1| n|0，則對(duì)任意非零初始向量則對(duì)任意非零初始向量u0(an 0) ，由反冪法計(jì)算公，由反冪法計(jì)算公式構(gòu)造的向量序列式構(gòu)造的向量序列vk，uk滿足滿足 ,)max(limnnkkxxu .1)max(limnkkv 上頁(yè)上頁(yè)下頁(yè)下頁(yè) 在反冪法中也可以用在反冪法中也可以用原點(diǎn)平移法原點(diǎn)平移法加速迭代過(guò)程加速迭代過(guò)程，或或求其它特征值與其對(duì)應(yīng)的特征向量求其它特征值與其對(duì)應(yīng)的特征向量. 如果矩陣如果矩陣(A- -pI)- -1存在

23、，顯然其特征值為存在，顯然其特征值為,1,1,121pppn 對(duì)應(yīng)的特征向量仍然是對(duì)應(yīng)的特征向量仍然是x1,x2,xn，現(xiàn)對(duì)矩陣，現(xiàn)對(duì)矩陣(A- -pI)- -1應(yīng)用冪法，得到反冪法的迭代公式應(yīng)用冪法，得到反冪法的迭代公式)12. 2()., 2 , 1()max(/.,)(, 01100 kvuupIAvvukkkkk 初始向量初始向量上頁(yè)上頁(yè)下頁(yè)下頁(yè) 如果如果p是是A的特征值的特征值 j的一個(gè)近似值，且設(shè)的一個(gè)近似值，且設(shè) j與其它與其它特征值是分離的，即特征值是分離的，即),(jippij 就是說(shuō)就是說(shuō)1/( j- -p)是矩陣是矩陣 (A- -pI)- -1的主特征值，可用反冪的主特征

24、值，可用反冪法法(2.12)計(jì)算特征值及特征向量計(jì)算特征值及特征向量. 設(shè)設(shè)ARnn有有 n個(gè)線性無(wú)關(guān)的特征向量個(gè)線性無(wú)關(guān)的特征向量 x1,x2, xn，則則),0(10 jniiiaxau,)max()(0)1(0upIAupIAvkkk 上頁(yè)上頁(yè)下頁(yè)下頁(yè),)max()(00upIAupIAukkk 其中其中.)()(10 niikiikxpaupIA 同理可得：同理可得：上頁(yè)上頁(yè)下頁(yè)下頁(yè) 定理定理16 設(shè)設(shè)ARnn有有n個(gè)線性無(wú)關(guān)的特征向量，個(gè)線性無(wú)關(guān)的特征向量， 矩陣矩陣A的特征值及對(duì)應(yīng)的特征向量分別記為的特征值及對(duì)應(yīng)的特征向量分別記為 i 及及xi (i=1,2,n)，而，而p為為 j

25、的近似值，的近似值，(A- -pI)- -1存在，且存在，且 ,)max(limjjkkxxu jkjkkvppv )max(1,1)max(lim即即則對(duì)任意非零初始向量則對(duì)任意非零初始向量u0(aj 0) ，由反冪法計(jì)算公式，由反冪法計(jì)算公式(2.12)構(gòu)造的向量序列構(gòu)造的向量序列vk，uk滿足滿足. )( |jippij . |min/ |pprijij 且收斂速度為且收斂速度為上頁(yè)上頁(yè)下頁(yè)下頁(yè) 由該定理知，對(duì)由該定理知，對(duì)A- -pI(其中其中p j)應(yīng)用反冪法，可應(yīng)用反冪法，可用來(lái)計(jì)算特征向量用來(lái)計(jì)算特征向量xj，只要選擇，只要選擇p是是 j的一個(gè)較好的近的一個(gè)較好的近似且特征值分離

26、情況較好，一般似且特征值分離情況較好，一般r很小，常常只要迭很小，常常只要迭代一二次就可完成特征向量的計(jì)算代一二次就可完成特征向量的計(jì)算.反冪法迭代公式中的反冪法迭代公式中的vk是通過(guò)解方程組是通過(guò)解方程組.)(1 kkuvpIA求得的求得的, 為了節(jié)省工作量為了節(jié)省工作量, 可以先將可以先將A- -pI進(jìn)行三角分解進(jìn)行三角分解.)(LUpIAP 于是求于是求vk相對(duì)于解兩個(gè)三角形方程組相對(duì)于解兩個(gè)三角形方程組.,1kkkkyUvPuLy 上頁(yè)上頁(yè)下頁(yè)下頁(yè)實(shí)驗(yàn)表明實(shí)驗(yàn)表明, 按下述方法選擇按下述方法選擇u0是較好的是較好的: 選選u0使使)13. 2()1 , 1 , 1(011 PuLUv用

27、回代求解用回代求解(2.13)即得即得v1,然后再按公式然后再按公式(2.12)進(jìn)行迭代進(jìn)行迭代.反冪法計(jì)算公式見(jiàn)書(shū)反冪法計(jì)算公式見(jiàn)書(shū)p311.前面已提到前面已提到.見(jiàn)書(shū)見(jiàn)書(shū)p311- -例例6.上頁(yè)上頁(yè)下頁(yè)下頁(yè)8.3 豪斯霍爾德方法豪斯霍爾德方法 (1)用用初等反射矩陣作正交相似變換初等反射矩陣作正交相似變換約化一般約化一般實(shí)矩陣實(shí)矩陣A為為上海森伯格矩陣上海森伯格矩陣.8.3.1 引言引言 本節(jié)討論本節(jié)討論兩個(gè)問(wèn)題兩個(gè)問(wèn)題 (2)用用初等反射矩陣作正交相似變換初等反射矩陣作正交相似變換約化對(duì)稱約化對(duì)稱矩陣矩陣A為為對(duì)稱三對(duì)角矩陣對(duì)稱三對(duì)角矩陣. 于是，于是，求原矩陣特征值問(wèn)題求原矩陣特征值

28、問(wèn)題，就，就轉(zhuǎn)化為轉(zhuǎn)化為求上求上海森伯格矩陣海森伯格矩陣或或?qū)ΨQ三對(duì)角矩陣的特征值對(duì)稱三對(duì)角矩陣的特征值問(wèn)題問(wèn)題.上頁(yè)上頁(yè)下頁(yè)下頁(yè)8.3.2 用正交相似變換用正交相似變換 約化一般實(shí)矩陣為上海森伯格矩陣約化一般實(shí)矩陣為上海森伯格矩陣 設(shè)設(shè)ARnn，下面來(lái)說(shuō)明，可選擇初等反射矩，下面來(lái)說(shuō)明，可選擇初等反射矩陣陣U1,U2,Un- -2使使A經(jīng)正交相似變換約化為一個(gè)上海經(jīng)正交相似變換約化為一個(gè)上海森伯格陣森伯格陣.(1) 設(shè)設(shè),)1(221)1(1211212222111211 AcAaaaaaaaaaaAnnnnnn上頁(yè)上頁(yè)下頁(yè)下頁(yè))1 . 3().(,)(sgn(2111111112/1221

29、211 aecuaanii 其中其中c1=(a21,an1)TRn- -1 ,不妨設(shè)不妨設(shè)c10，否則這一步不，否則這一步不需要約化需要約化. 于是于是, 可選擇初等反射陣可選擇初等反射陣 使使 ，其中，其中TuuIR11111 1111ecR 令令,111 RU上頁(yè)上頁(yè)下頁(yè)下頁(yè)則則 1)1(221111)1(12111112RARcRRAaUAUA,000)2(221)2(12)2(11)2()2(3)2(2)2(3)2(33)2(32)2(2)2(23)2(221)2(1)2(13)2(1211 AcAAaaaaaaaaaaaaannnnnnn 其中其中.,),()2()2()2(222)

30、2(2)2(322 nnnTnRARaac上頁(yè)上頁(yè)下頁(yè)下頁(yè)(2) 第第k步約化：重復(fù)上述過(guò)程，設(shè)對(duì)步約化：重復(fù)上述過(guò)程，設(shè)對(duì)A已完成第已完成第1步步,第第k- -1步正交相似變換，即有步正交相似變換，即有,111 kkkkUAUA或或,11111 kkkUUAUUA且且 )()(1,)()(, 1)(1, 1)(, 1)()(1,)(1)(2)(1,2)(2)1(1,2)2(221)(1)(1, 1)(1)1(1, 1)2(12)1(11knnkknknkknkkkkkkkkknkkkkkkkknkkkkkkknkkkkkkkaaaaaaaaaaaaaaaaaaaaA 上頁(yè)上頁(yè)下頁(yè)下頁(yè),0)(

31、22)(12)(11knkAcAAknkkkkk 其中其中 為為k階上海森階上海森伯格陣，伯格陣，)(11)()(, 1,),(kknTknkkkkkARaac .)()()(22knknkRA 設(shè)設(shè)ck0, 于是可選擇初等反射陣于是可選擇初等反射陣Rk使使 其中，其中，Rk計(jì)算公式為計(jì)算公式為,1ecRkkk 上頁(yè)上頁(yè)下頁(yè)下頁(yè))2 . 3(.),(,)()(sgn(1)(, 112/112)()(, 1 TkkkkkkkkkkkkknkikikkkkkuuIRaecuaa 令令, kkRIU則則)3 . 3(00)1(221)1(12)1(11)(22)(12)1(111 kkkkkkkkk

32、kkkkkkkAcAARARcRRAAUAUA上頁(yè)上頁(yè)下頁(yè)下頁(yè)221122 nnUUAUUUU其中其中 為為k+1階上海森伯格陣，第階上海森伯格陣，第k步約化只需計(jì)步約化只需計(jì)算算 及及 (當(dāng)當(dāng)A為對(duì)稱矩陣時(shí)，只需要計(jì)為對(duì)稱矩陣時(shí)，只需要計(jì)算算 ).)1(11 kAkkRA)(12kkkRAR)(22kkkRAR)(22(3) 重復(fù)上述過(guò)程，則有重復(fù)上述過(guò)程，則有.1)(1)1(1, 12)3(332)2(22111 nnnnnnnnnAaaaaa 上頁(yè)上頁(yè)下頁(yè)下頁(yè) 定理定理17 (豪斯霍爾德約化矩陣為上海森伯格陣豪斯霍爾德約化矩陣為上海森伯格陣) 設(shè)設(shè)ARnn則存在初等反射矩陣則存在初等反射

33、矩陣U1,U2,Un- -2 使使.00221122HAUUUUAUUUUTnn 為為上海森伯格矩陣上海森伯格矩陣.總結(jié)上述結(jié)論，有總結(jié)上述結(jié)論，有 算法算法1 (豪斯霍爾德約化矩陣為上海森伯格陣豪斯霍爾德約化矩陣為上海森伯格陣) 設(shè)設(shè)ARnn，本算法計(jì)算，本算法計(jì)算U0TAU0=H(上海森伯格型上海森伯格型)，其，其中中U0=U1U2Un- -2為初等反射陣的乘積為初等反射陣的乘積.1. U0I上頁(yè)上頁(yè)下頁(yè)下頁(yè)2. 對(duì)于對(duì)于k=1,2,n- -2(1) 計(jì)算初等反射陣計(jì)算初等反射陣Rk使使本算法約需要本算法約需要5n3/3次乘法運(yùn)算，要明顯形成次乘法運(yùn)算，要明顯形成U0還需要附加還需要附加2

34、n3/3次乘法次乘法.,1ecRkkk (2) 約化計(jì)算約化計(jì)算, kkkkRIUAUUA(3) U0U0Uk上頁(yè)上頁(yè)下頁(yè)下頁(yè)例例7 用用豪斯霍爾德方法豪斯霍爾德方法將矩陣將矩陣 7242327341AA約化為約化為上海森伯格陣上海森伯格陣. 解解 選取初等反射陣選取初等反射陣R1使使 , 其中其中c1=(2,4)T.1111ecR (1) 計(jì)算計(jì)算R1:)() 1 , 5 . 0(, 4) 4 , 2max(11規(guī)范化規(guī)范化Tcc .,472136. 4,809017. 1)5 . 0(,)1,618034. 1(,118034. 125. 11111111111TTuuIRecu 上頁(yè)上頁(yè)

35、下頁(yè)下頁(yè).1111ecR 則有則有(2) 約化計(jì)算約化計(jì)算:,111 RU則得到則得到上海森伯格陣上海森伯格陣為為.200000. 2399999. 00400000. 0799999. 7472136. 4447214. 0602631. 74112HAUUA 上頁(yè)上頁(yè)下頁(yè)下頁(yè)8.3.3 用正交相似變換用正交相似變換 約化對(duì)稱矩陣為對(duì)稱三對(duì)角矩陣約化對(duì)稱矩陣為對(duì)稱三對(duì)角矩陣 定理定理18 (豪斯霍爾德約化對(duì)稱矩陣為對(duì)稱三對(duì)豪斯霍爾德約化對(duì)稱矩陣為對(duì)稱三對(duì)角矩陣角矩陣) 設(shè)設(shè)ARnn為對(duì)稱矩陣，則存在初等反射矩為對(duì)稱矩陣，則存在初等反射矩陣陣U1,U2,Un- -2使使.11122211122

36、1122CcbbcbbcbbcUUAUUUUnnnnnn 為為對(duì)稱三對(duì)角矩陣對(duì)稱三對(duì)角矩陣.上頁(yè)上頁(yè)下頁(yè)下頁(yè) 證明證明 由定理由定理17, 存在初等反射矩陣存在初等反射矩陣U1,U2,Un- -2 使使 為上海森伯格為上海森伯格陣，且陣，且An- -1亦是對(duì)稱陣，因此，亦是對(duì)稱陣，因此，An- -1為對(duì)稱三對(duì)角陣為對(duì)稱三對(duì)角陣.1221122 nnnAHUUAUUUU 由上面討論可知，當(dāng)由上面討論可知，當(dāng)A為對(duì)稱陣時(shí)，由為對(duì)稱陣時(shí)，由AkAk+1 =Ak Uk Ak一步約化計(jì)算中只需計(jì)算一步約化計(jì)算中只需計(jì)算Rk及及Rk A22(k)Rk . 又又由于由于A的對(duì)稱性，故只需計(jì)算的對(duì)稱性，故只需

37、計(jì)算Rk A22(k)Rk的對(duì)角線以下的對(duì)角線以下元素元素. 注意到注意到).)()(221)(221)(22TkkkkkTkkkkkkuuAAuuIRAR 上頁(yè)上頁(yè)下頁(yè)下頁(yè)引進(jìn)記號(hào)引進(jìn)記號(hào))., 1;, 1()(22)(22ikjnkiuttuARARTkkTkkkkkk ,)(221knkkkkRuAr ,)(21knkkTkkkkRururt 則有則有對(duì)對(duì)稱陣對(duì)對(duì)稱陣A用初等反射陣正交相似約化為對(duì)角三用初等反射陣正交相似約化為對(duì)角三對(duì)角陣大約需要對(duì)角陣大約需要2n3/3次乘法次乘法.用正交矩陣進(jìn)行相似約化有一些特點(diǎn)，如構(gòu)造的，用正交矩陣進(jìn)行相似約化有一些特點(diǎn)，如構(gòu)造的， Uk容易求逆，且

38、容易求逆，且Uk的元素?cái)?shù)量級(jí)不大，這個(gè)算法是十的元素?cái)?shù)量級(jí)不大，這個(gè)算法是十分穩(wěn)定的分穩(wěn)定的.算法算法2見(jiàn)書(shū)見(jiàn)書(shū)p318.上頁(yè)上頁(yè)下頁(yè)下頁(yè)8.4 QR 方方 法法8.4.1 QR算法算法Rutishauser(1958)利用矩陣的三角分解提出了計(jì)利用矩陣的三角分解提出了計(jì)算矩陣特征值的算矩陣特征值的LR算法，算法，F(xiàn)rancis(1961,1962)利用矩利用矩陣的陣的QR分解建立了分解建立了計(jì)算矩陣特征值計(jì)算矩陣特征值的的QR算法算法.QR方法是一種變換方法，是計(jì)算一般矩陣方法是一種變換方法，是計(jì)算一般矩陣(中小中小型矩陣型矩陣)全部特征值全部特征值問(wèn)題的問(wèn)題的最有效方法之一最有效方法之一.

39、上頁(yè)上頁(yè)下頁(yè)下頁(yè) (1) 上海森伯格矩陣上海森伯格矩陣的的全部特征值全部特征值問(wèn)題；問(wèn)題； (2) 計(jì)算計(jì)算對(duì)稱三對(duì)角矩陣對(duì)稱三對(duì)角矩陣的的全部特征值全部特征值問(wèn)題，問(wèn)題， 目前目前QR方法方法主要主要用來(lái)計(jì)算：用來(lái)計(jì)算：且且QR方法具有收斂快，算法穩(wěn)定等特點(diǎn)方法具有收斂快，算法穩(wěn)定等特點(diǎn). 對(duì)于一般矩陣對(duì)于一般矩陣ARnn (或?qū)ΨQ矩陣或?qū)ΨQ矩陣)，則首先用，則首先用豪斯霍爾德方法將豪斯霍爾德方法將A化為上海森伯格陣化為上海森伯格陣B(或?qū)ΨQ三對(duì)或?qū)ΨQ三對(duì)角陣角陣)，然后再用，然后再用QR方法計(jì)算方法計(jì)算B的全部特征值的全部特征值. 設(shè)設(shè)ARnn，且，且A對(duì)進(jìn)行對(duì)進(jìn)行QR分解，即分解，即A=

40、QR，上頁(yè)上頁(yè)下頁(yè)下頁(yè)其中其中R為上三角陣為上三角陣, Q為正交陣為正交陣, 于是可得到一新矩陣于是可得到一新矩陣B=RQ=QTAQ.顯然，顯然，B是由是由A經(jīng)過(guò)正交相似變換得到，因此經(jīng)過(guò)正交相似變換得到，因此B與與A的的特征值相同特征值相同. 再對(duì)再對(duì)B進(jìn)行進(jìn)行QR分解，又可得一新矩陣分解，又可得一新矩陣,重復(fù)這一過(guò)程可得到矩陣序列：重復(fù)這一過(guò)程可得到矩陣序列： 設(shè)設(shè)A=A1 將將A1進(jìn)行進(jìn)行QR分解分解A1=Q1R1 作矩陣作矩陣A2=R1Q1=Q1TR1Q1 QR算法，就是利用矩陣的算法，就是利用矩陣的QR分解，按上述遞分解，按上述遞推法則構(gòu)造矩陣序列推法則構(gòu)造矩陣序列Ak的過(guò)程的過(guò)程. 只要只要A為非奇異矩為非奇異矩陣，則由陣，則由QR算法就完全確定算法就完全確定Ak.上頁(yè)上頁(yè)下頁(yè)下頁(yè) 定理定理19 (基本基本QR方法方法) 設(shè)設(shè)A=A1Rnn, 構(gòu)造構(gòu)造QR算法算法:)1 . 4(), 2 , 1(),(1 kQRARIQQRQAkkkkkTkkkk為上三角陣為上三角陣其中其中則則有有記記,1221RRRRQQQQkkkk ;,111kTkkkkAQQAAA 即即相相似似于于）（;)()()2(1211211kTkkTkkQA