1、上頁上頁下頁下頁第第8章章 矩陣特征問題的計算矩陣特征問題的計算 8.1 引言引言 8.2 冪法及反冪法冪法及反冪法 8.3 豪斯霍爾德方法豪斯霍爾德方法 8.4 QR方法方法上頁上頁下頁下頁8.1 引引 言言 工程技術中有多種振動問題，如橋梁或建筑物的工程技術中有多種振動問題，如橋梁或建筑物的振動，機械零件、飛機機翼的振動，及一些穩定性分振動，機械零件、飛機機翼的振動，及一些穩定性分析和相關分析在數學上都可轉化為求矩陣特征值與特析和相關分析在數學上都可轉化為求矩陣特征值與特征向量的問題征向量的問題. 下面先復習一些矩陣的特征值和特征向量的基礎下面先復習一些矩陣的特征值和特征向量的基礎知識知識

2、.上頁上頁下頁下頁 定義定義1 已知已知n階矩陣階矩陣A=(aij)，則，則)2()(det)det()(12211212222111211的項的項次數次數 naaaaaaaaaaaaAInnnnnnnnnn 稱為稱為A的的特征多項式特征多項式. 一般有一般有n個根個根(實的或復的，復根按重數計算實的或復的，復根按重數計算)稱為稱為A的的特征值特征值. 用用(A)表示表示A的所有特征值的集合的所有特征值的集合. A的特征方程的特征方程)1 . 1(0)det()( AI 上頁上頁下頁下頁 設設為為A的特征值，相應的齊次方程組的特征值，相應的齊次方程組 注：注：當當A為實矩陣時，為實矩陣時， (

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

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

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

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

7、)式有式有 如果如果A的主特征值為實的重根的主特征值為實的重根, 即即1=2=r, 且且 |r|r+1|n|，,)/(11110 nriikiiriiikkkxaxavAv 上頁上頁下頁下頁).0(lim111 riiiriiikkkxaxav設設 為為A的特征向量，這說明當的特征向量，這說明當A的主特征值是實的重根的主特征值是實的重根時，定理時，定理5的結論還是正確的的結論還是正確的. 應用應用冪法冪法計算計算A的主特征值的主特征值1及其對應的特征向及其對應的特征向量時，如果量時，如果|1|1(或或|1|2|n|，則對任意非零初始，則對任意非零初始向量向量v0=u0(a1 0)，有冪法計算公

8、式為，有冪法計算公式為則有則有 ,)max(lim11xxukk .lim1 kk上頁上頁下頁下頁例例1 用冪法計算矩陣用冪法計算矩陣 1634310232A的主特征值與其對應的特征向量的主特征值與其對應的特征向量.解解取取 v0=u0=(0,0,1)T , 則則 TTvuv25. 0 , 1, 5 . 01, 4,1 , 4 , 211111 ), 2 , 1(max1 k/vuvAuvkkkkkkk 上頁上頁下頁下頁直到直到k=8 時的計算結果見下表時的計算結果見下表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 見書見書p303- -例例3.上頁上頁下頁下頁8.2.2 冪法的加速方法冪法的加速方法1、原點平移法、原點平移法 由前面討論知道，應用冪法計算由前面討論知道，應用冪法計算A的主特征值的的主特征值的收斂速度主要由比值收斂速度主要由比值 r=|2/1|來決定，但當來決定，但當r 接近于接近于1時，收斂可能很慢時，收斂可能很慢. 這時，一個補救辦法是采用加速這時，一個補救辦法是采用加速收斂的方法收斂的方法.其中其中p為參數，設為參數，設A的特征值為的特征值為 i，則對矩陣，則對矩陣B的特征的特征值為值為 i- -p ，而且，而且A, B的特征向量相同的特征向量相

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

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

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

14、收斂速度的比值為為.2212112nnnpppp 當希望計算當希望計算 n時，應選取時，應選取 p=( 1+ n-1)/2P* 使得應用冪法計算使得應用冪法計算 n得到加速得到加速. 當當A的特征值都是實數，滿足的特征值都是實數，滿足且且 2, n能初步估計出來，我們就能確定能初步估計出來，我們就能確定P*的近似值的近似值.nn 121上頁上頁下頁下頁 例例2 用原點平移加速法求用原點平移加速法求例例1中矩陣中矩陣A的主特征值的主特征值與其對應的特征向量與其對應的特征向量.5 . 36345 . 510235 . 4 B,1634310232 A對對B應用冪法，仍應用冪法，仍取取 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，則，則上頁上頁下頁下頁迭代迭代5步的計算結果見下表步的計算結果見下表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 上頁上頁下頁下頁 原點位移的加速方法，是一個矩陣變換方法原點位移的加速方法，是一個矩陣變換方法. 這這種變換容易計算，又不破壞矩陣種變換容易計算，又不破壞矩陣A的稀疏性，但的稀疏性，但

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

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

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

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

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

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

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

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

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

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

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

28、問題，就，就轉化為轉化為求上求上海森伯格矩陣海森伯格矩陣或或對稱三對角矩陣的特征值對稱三對角矩陣的特征值問題問題.上頁上頁下頁下頁8.3.2 用正交相似變換用正交相似變換 約化一般實矩陣為上海森伯格矩陣約化一般實矩陣為上海森伯格矩陣 設設ARnn，下面來說明，可選擇初等反射矩，下面來說明，可選擇初等反射矩陣陣U1,U2,Un- -2使使A經正交相似變換約化為一個上海經正交相似變換約化為一個上海森伯格陣森伯格陣.(1) 設設,)1(221)1(1211212222111211 AcAaaaaaaaaaaAnnnnnn上頁上頁下頁下頁)1 . 3().(,)(sgn(2111111112/1221

29、211 aecuaanii 其中其中c1=(a21,an1)TRn- -1 ,不妨設不妨設c10，否則這一步不，否則這一步不需要約化需要約化. 于是于是, 可選擇初等反射陣可選擇初等反射陣 使使 ，其中，其中TuuIR11111 1111ecR 令令,111 RU上頁上頁下頁下頁則則 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上頁上頁下頁下頁(2) 第第k步約化：重復上述過程，設對步約化：重復上述過程，設對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 上頁上頁下頁下頁,0)(

31、22)(12)(11knkAcAAknkkkkk 其中其中 為為k階上海森階上海森伯格陣，伯格陣，)(11)()(, 1,),(kknTknkkkkkARaac .)()()(22knknkRA 設設ck0, 于是可選擇初等反射陣于是可選擇初等反射陣Rk使使 其中，其中，Rk計算公式為計算公式為,1ecRkkk 上頁上頁下頁下頁)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上頁上頁下頁下頁221122 nnUUAUUUU其中其中 為為k+1階上海森伯格陣，第階上海森伯格陣，第k步約化只需計步約化只需計算算 及及 (當當A為對稱矩陣時，只需要計為對稱矩陣時，只需要計算算 ).)1(11 kAkkRA)(12kkkRAR)(22kkkRAR)(22(3) 重復上述過程，則有重復上述過程，則有.1)(1)1(1, 12)3(332)2(22111 nnnnnnnnnAaaaaa 上頁上頁下頁下頁 定理定理17 (豪斯霍爾德約化矩陣為上海森伯格陣豪斯霍爾德約化矩陣為上海森伯格陣) 設設ARnn則存在初等反射矩陣則存在初等反射

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

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

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

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

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

38、容易求逆，且Uk的元素數量級不大，這個算法是十的元素數量級不大，這個算法是十分穩定的分穩定的.算法算法2見書見書p318.上頁上頁下頁下頁8.4 QR 方方 法法8.4.1 QR算法算法Rutishauser(1958)利用矩陣的三角分解提出了計利用矩陣的三角分解提出了計算矩陣特征值的算矩陣特征值的LR算法，算法，Francis(1961,1962)利用矩利用矩陣的陣的QR分解建立了分解建立了計算矩陣特征值計算矩陣特征值的的QR算法算法.QR方法是一種變換方法，是計算一般矩陣方法是一種變換方法，是計算一般矩陣(中小中小型矩陣型矩陣)全部特征值全部特征值問題的問題的最有效方法之一最有效方法之一.

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

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