1、數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析 第三節(jié)第三節(jié) 求矩陣全部特征值的求矩陣全部特征值的QR方法方法一、求矩陣全部特征值的一、求矩陣全部特征值的QR方法方法 6060年代出現(xiàn)的年代出現(xiàn)的QRQR算法是目前計算中小型矩陣的算法是目前計算中小型矩陣的全部特征值與特征向量的最有效方法。全部特征值與特征向量的最有效方法。 理論依據(jù)：理論依據(jù)：任一非奇異實矩陣都可分解成一個正交矩陣任一非奇異實矩陣都可分解成一個正交矩陣Q Q和一個和一個上三角矩陣上三角矩陣R R的乘積，而且當?shù)某朔e，而且當R R的對角元符號取定時，的對角元符號取定時，分解是唯一的。分解是唯一的。 11 QRQR (1,2,). kkkkkk

2、AQ RkAR QAAA 方方法法的的基基本本思思想想是是利利用用矩矩陣陣的的分分解解通通過過迭迭代代格格式式將將化化成成相相似似的的上上三三角角陣陣（或或分分塊塊上上三三角角陣陣），從從而而求求出出矩矩陣陣的的全全部部特特征征值值與與特特征征向向量量。數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析111111121112, (2 ,3, ) kAAQ RQARAR QQAQAAAAk 由由即即。于于是是即即與與相相似似。同同理理可可得得，。故故它它們們有有相相同同的的特特征征值值。 可證，在一定條件下，基本可證，在一定條件下，基本QRQR方法產(chǎn)生的矩方法產(chǎn)生的矩陣序列陣序列A Ak k “ “基本基本”收

3、斂于一個上三角陣（或收斂于一個上三角陣（或分塊上三角陣）。即主對角線（或主對角線子塊）分塊上三角陣）。即主對角線（或主對角線子塊）及其以下元素均收斂，主對角線（或主對角線子及其以下元素均收斂，主對角線（或主對角線子塊）以上元素可以不收斂。特別的，如果塊）以上元素可以不收斂。特別的，如果A A是實對是實對稱陣，則稱陣，則A Ak k “ “基本基本”收斂于對角矩陣。收斂于對角矩陣。數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析QR方法的實際計算步驟方法的實際計算步驟HouseholderAHessenbergB 用用陣陣作作正正交交相相似似變變換換上上第第陣陣一一步步.*:* 1kkkGivenkkkBQ R

4、BBR Q 用用變變換換產(chǎn)產(chǎn)生生迭迭代代序序列列第第二二步步12*n 數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析HouseholderAB 用陣用陣作正交相似變換作正交相似變換（對稱陣）三對角陣（對稱陣）三對角陣* 數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析二、化一般矩陣為上二、化一般矩陣為上Hessenberg陣陣111211121222123233311 (2,3,), Househ old e rnnnnnnnnniihhhhhhhhhhhHhhhinA 稱稱形形如如 的的矩矩陣陣為為上上海海森森堡堡（H H e es ss se en nb be er rg g) )陣陣。如如果果此此對對角角線線元元全全

5、不不為為零零 則則稱稱該該矩矩陣陣為為不不可可約約的的上上H H e es ss se en nb be er rg g矩矩陣陣。討討論論用用變變換換將將一一般般矩矩陣陣相相似似變變換換成成H H e es ss se en nb be er rg g陣陣數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析11111111 ,1000 01 HouseholderHHH AHHHHHnHouseholder 首首先先，選選取取矩矩陣陣使使得得經(jīng)經(jīng)相相似似變變換換后后的的矩矩陣陣的的第第一一列列中中有有盡盡可可能能多多的的零零元元素素。為為此此，應應取取為為如如下下形形式式其其中中為為階階矩矩陣陣。11121111

6、1221121311212131(,) ,(,) ,TTTnnaa HH AHH aH A Haaaaaaaa 于于是是有有 其其中中數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析222222111111.(, 0) 0,2nnnnTaaAaaHH aH AHn 只只要要取取使使得得就就會會使使得得變變換換后后的的矩矩陣陣的的第第一一列列出出現(xiàn)現(xiàn)個個零零元元。數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析2211221222211221000*0100*00*0022, .nnnHouseholderHH H AH HHnnHouseholderHHHHH H AH HHHHHessenberg 同同理理，可可構構造造如

7、如下下列列形形式式矩矩陣陣使使得得* *如如此此進進行行次次，可可以以構構造造個個矩矩陣陣使使得得其其中中為為上上矩矩陣陣AH。特特別別地地，當當 為為實實對對稱稱矩矩陣陣，則則經(jīng)經(jīng)過過上上述述正正交交變變換換后后，變變?yōu)闉槿龑墙顷囮嚒?shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析1221522 23 2105 2 22 2 021002412,022, (2,2)2(1,0)(22,2) :TTTHouseholderAAHouseholderHHu 用用變變換換將將矩矩陣陣 化化成成上上H H e es ss se e例例解解n nb be er rg g陣陣。求求矩矩陣陣滿滿：足足，數(shù)值分析數(shù)值

8、分析數(shù)值分析數(shù)值分析22 22222210442220122222442210000100220022220022TTuuHIu uH 數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析2112 100052223201001052 22 222002202102202410022100052510100103222 000223220012220022HH H AH H 于于 是是 有有數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析用用Household方法對矩陣方法對矩陣A作正交相似變換作正交相似變換, 使使A相似與上相似與上Hessenberg陣，算法如下：陣，算法如下：(1)(1)111221111111(1)112

9、,1,2,.,21(1)()()() ) ,()(0,.,0,.,)kkTkknkkkiki kkkkkkkkkkkknkknHIUUsign aaaUaaa ，計算計算1(2)kHAA計計算算 (1)11(1),1,11()21,nkjlljlkkkijijjijk kntuaiknaat u （ ）（ ）數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析(1)11(1)1,.,1(1)(2)1,.,nkiilll kkkijijijinta ujknaat u 1(3)kAHA計計算算 數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析三、上三、上Hessenberg陣的陣的QR分解分解對對上上Hessenberg陣陣只需要

10、將其次對角線上的只需要將其次對角線上的元素約化為零，用元素約化為零，用Given變換比用變換比用Householder變變換更節(jié)省計算量。為此先介紹換更節(jié)省計算量。為此先介紹Given變換。變換。數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析,11cossin11sincos11 ()i jiRjjin n階階方方陣陣稱稱為為平平面面旋旋轉轉陣陣，或或稱稱為為G Gi iv ve en ns s變變換換陣陣。定定義義 、平面旋轉陣、平面旋轉陣(Givens(Givens變換陣變換陣) )數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析1,1,TTi ji ji ji jRRIRRRi i, ,j j平平面面旋旋轉轉陣陣的的

11、（ ）平平面面旋旋轉轉陣陣是是非非對對稱稱交交質質：陣陣性性的的正正。,2Ti ji jRR（ ）也也是是平平面面旋旋轉轉陣陣。( (3 3) )d de et t( () )= =1 1數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析1,.,Rxxxxi i, ,j jT T1 12 2n n平平面面旋旋轉轉陣陣的的作作用用：（ ）將將向向量量 = =的的第第j j個個分分量量約約化化為為零零。,cossinsincos1,., ;,i jiijjijkkyRxyxxyxxyxkn ki j, ,若若令令，有有 111,222121212cossinsincoscossinsincosyxRyxxxxxxx

12、 jy調調整整 ，可可將將 約約化化為為零零。0tanjjixyx令令，得得,.,i jRxx xxxT T12n12n左左乘乘向向量量 = =只只改改變變 的的第第i i個個分分量量和和第第j j個個分分量量。jxix 數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析0tanjjixyx令令，得得2222cossiniiijjjijxxCrxxxxSrxx 所所以以，取取22,0iijijjyCxSxrxxy于于是是 ,., ,.,0,.,.i jRxxxr xxxxT T1 1i i- -1 1i i+ +1 1j j- -1 1j j+ +1 1n n= =jxix 數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析2,

13、.,xxxxT T1 12 2n n（ ）將將向向量量 = =的的第第i i+ +1 1個個分分量量到到第第n n個個分分量量約約化化為為零零。22,11,., ,0,.,i iiiRxxxrxxrxxT T1 1i i- -1 1i i+ +2 2n n= =,2,122212,., ,0,0,.,i ii iiiiRRxxxrxxrxxxT T1 1i i- -1 1i i+ +3 3n n= =,2,122,., ,0,.,0,i ni ii iinRRRxxxrrxxT T1 1i i- -1 1= =,(3)i ji jiiji jjRAARAARRARAAT TT T左左乘乘 只只

14、改改變變 的的第第i i，j j行行。右右乘乘 只只改改用用對對矩矩陣陣 作作變變換換得得變變 的的第第i i，j j列列。只只改改變變 的的第第i i，j j行行和和到到的的結結第第論論i i，j j列列。數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析2,1,4,0,0.xxrT TT T已已知知向向量量 = =，試試用用G Gi iv ve en ns s變變換換將將 約約化化為為例例(1)(1)2,1,4x xxT T：記記 = =，對對計計解解算算C C和和S S。122222121221,55xxCSxxxx1,2(1)(2)1,221055120550015,0,4TRRxx 數(shù)值分析數(shù)值分析數(shù)

15、值分析數(shù)值分析(2)4,21xS 5 5對對計計算算C C和和S,C=S,C=2121 (1)1,31,34021010,21,0,04021TRRx 5 52 21 15 52 21 1(2)5,0,4Tx數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析、用、用 GivensGivens變換對變換對上上Hessenberg陣作陣作QR分解分解(1)(1)(1)11121(1)(1)(1)21222(1)(1)1 1 nnnnnnbbbbbbBbbnGivensBQR 對對上上H H e es ss se en nb be er rg g陣陣, ,通通常常用用個個變變換換陣陣可可將將它它化化成成上上三三角角矩

16、矩陣陣，從從而而得得到到 的的分分解解式式。數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析(1)211111(2)(2)(2)112131(2)(2)(2)22232(2)(2)(2)1232333(2)(2)1 0(cossin00sincos00(1,2)0011(1,2) nnnnnnnbRrbbbbbbRBBbbbbb 具具體體步步驟驟為為：設設否否則則進進行行下下一一步步），取取旋旋轉轉矩矩陣陣則則(1)(1)(1)(1)1121111112111 cos, sin, .bbrbbrr 其其中中數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析2322222( 3 )( 3 )( 3 )( 3 )11213111(

17、 3 )( 3 )( 3 )223212( 3 )( 3 )( 3 )333132( 3 )( 3 )4341 0(10cossinsincos (3, 2)11 (3 , 2)nnnnnnnbRrbbbbrbbbbbbRBbb （）設設否否 則則 進進 行行 下下 一一 步步 ） ， 再再 取取 旋旋 轉轉 矩矩 陣陣 則則3( 3 )4( 3 )( 3 )1( 2 )( 2 )( 2 )2( 2 )23222222223222 cos, sin, ()() .nnnnnBbbbbbrbbrr 其其 中中數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析1( )( )( )( )1111111( )( )(

18、)11111( )( )( )1( )( )( )1111( )( )1 (1, ) kkkkkkkknnkkkkkkknknkkkkkknknkkkkkknknkknnnnBR kk Brbbbbrbbbbhhbbbbb 1k 假假設設上上述述過過程程已已進進行行了了步步，有有數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析()1()()1()2()21 0,11 (1,)cossinsincos1 cos, sin, ()() .kkkkkkkkkkkkkkkkkkkkkkkkbR kkbbrrrbb 設設取取其其中中數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析(1)(1)(1)11111(1)(1)1(1)(1)(

19、1)111111(1)(1)(1)21212(1)(1)1 (1, )1kkkkknkkkkkknkkkkkkkknknkkkkkknknkknnnnrbbbrbbR kk BBbhbbhhbbn 于于是是因因此此，最最多多做做次次旋旋轉轉變變換換，即即( )( )( )( )112131( )( )2232( )33 ( ,1) (2,1)(1,2)nnnnnnnnnnnHR n nR nnRBrbbbrbbRrbr 得得數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析213212132123( ,1),(2,3, ) 4,() TTTnnTTTnnR i iinHR RRRQRQR RRnQRO nHRQ

20、QRQR 因因為為均均為為正正交交矩矩陣陣，故故其其中中仍仍為為正正交交矩矩陣陣?？煽伤闼愠龀鐾晖瓿沙蛇@這一一過過程程的的運運算算量量約約為為比比一一般般矩矩陣陣的的分分解解的的運運算算量量少少一一個個數(shù)數(shù)量量級級。可可證證明明仍仍是是上上H H e es ss se en nb be er rg g陣陣，于于是是可可按按上上述述步步驟驟一一直直迭迭代代下下去去，這這樣樣得得到到的的方方法法的的運運算算量量比比基基本本QR方方法法大大為為減減少少。需需要要說說明明的的是是，通通常常用用方方法法計計算算特特征征值值，然然后后用用反反冪冪法法求求其其相相應應的的特特征征向向量量。數(shù)值分析數(shù)值分析數(shù)

21、值分析數(shù)值分析22532644445 (6,4)64 (1,0)(652,4)10 2010.9160250.2773500.8320500.55470020.2773500.08397470.5547000.832050TTTTTQRAAuuuIu u 用用方方法法求求矩矩陣陣的的全全部部特特征征值值。首首先先將將 化化成成上上H H e es ss se en nb be e例例：r rg g：陣陣，取取解解110000.8320500.55470000.5547000.832050H 于于是是 數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析11221111151.3867503.3282007.211

22、1021.2307688.15384000.1538462.230767, 5( 7.21102)8.774964 cos50.56980. sin0.821781 HH AHHAHQRBHrr 即即為為與與 相相似似的的上上H H e es ss se en nb be er rg g陣陣。將將進進行行分分解解，記記取取0.5698030.8217810(2,1)0.8217810.5698030001R 數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析122222228.7749641.8015968.597089(2,1)00.4383101.91103000.1538462.230767 (0.438

23、310)( 0.153846)0.464526, cos0.4383100.943564, sin0.1538460.331189 RBrrr 于于 是是再再 取取11100 (3, 2)00.9435640.33118900.3311890.943564 (3, 2)(2,1)8.7749641.8015968.59708900.4645262.541982001.471953RRRBR 于于 是是數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析12110.5698030.7754030.272165(2,1)(3,2)0.8217810.5376430.18871200.3311890.9435643.5

24、194824.92549110.8401170.3817391.0916272.31065300.4874951.388883,11TTQRRBRQ 第第一一次次迭迭代代得得重重復復上上述述過過程程 迭迭代代次次121232.9920321.0003853 12.013392 0.0074962.0046951.94197100.0003250.9998952.992032,2.004695,0.999895 3,2,1.0.007496BQR 得得精精確確值值下下三三角角非非對對角角元元的的最最大大模模為為。方方法法“基基本本”收收斂斂較較慢慢。數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析算法：用算法：用Givens方法對上方法對上Hessenberg陣陣A作作 正交分解正交分解,A=QR。,1,22,1,1,1,1,1,1,1,1,1Hessenberg,1,2,.,1(1),(2)1,2.,(3)1,2.,i iiii iiii ii ki kikiki kikTi ik ik ik ik ik ik iA QIinaaraacsrrRAAknacasaasacaQRQknqcqsqqsacqA 輸入上陣輸入上陣計算計算計算計算輸出 為輸出 為,Q上三角陣為正交陣。上三角陣為正交陣。數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析算法：用算法：用Givens方法對上方法對上Hessenberg陣