數(shù)值計(jì)算方法（南京大學(xué)）第8章矩陣特征值問(wèn)題

1、數(shù)值計(jì)算方法數(shù)值計(jì)算方法【第二版】電子教案【第二版】電子教案科學(xué)出版社科學(xué)出版社2121世紀(jì)高等院校教材電子教案系列世紀(jì)高等院校教材電子教案系列南京大學(xué)數(shù)學(xué)系南京大學(xué)數(shù)學(xué)系 林成森教授林成森教授授課教材授課教材數(shù)值計(jì)算方法【第二版】電子教案數(shù)值計(jì)算方法【第二版】電子教案 南京大學(xué)林成森南京大學(xué)林成森3 第第8 8章章 矩陣特征值問(wèn)題矩陣特征值問(wèn)題 工程實(shí)踐中有多種振動(dòng)問(wèn)題，如橋梁工程實(shí)踐中有多種振動(dòng)問(wèn)題，如橋梁 或建筑物或建筑物的振動(dòng)，機(jī)械機(jī)件、飛機(jī)機(jī)翼的振動(dòng)，及的振動(dòng)，機(jī)械機(jī)件、飛機(jī)機(jī)翼的振動(dòng)，及 一些穩(wěn)定一些穩(wěn)定性分析和相關(guān)分析可轉(zhuǎn)性分析和相關(guān)分析可轉(zhuǎn) 化為求矩陣特征值與特征向化為求矩陣特

2、征值與特征向量的問(wèn)題。量的問(wèn)題。 但高次多項(xiàng)式求根精度低但高次多項(xiàng)式求根精度低 , 一般不作為求解方一般不作為求解方法法. 目前的方法是針對(duì)矩陣不同的特點(diǎn)給出不同的目前的方法是針對(duì)矩陣不同的特點(diǎn)給出不同的有效方法有效方法. ()ijAaAfIAn n nn n矩矩 陣陣的的 特特 征征 值值 是是的的 特特 征征 多多 項(xiàng)項(xiàng) 式式的的個(gè)個(gè) 零零 點(diǎn)點(diǎn) . .數(shù)值計(jì)算方法【第二版】電子教案數(shù)值計(jì)算方法【第二版】電子教案 南京大學(xué)林成森南京大學(xué)林成森4本章主要內(nèi)容：本章主要內(nèi)容：第一節(jié)第一節(jié) 特征值的估計(jì)和數(shù)值穩(wěn)定性特征值的估計(jì)和數(shù)值穩(wěn)定性第二節(jié)第二節(jié) 冪法和反冪法冪法和反冪法第三節(jié)第三節(jié) 求矩陣

3、全部特征值的求矩陣全部特征值的QR方法方法數(shù)值計(jì)算方法【第二版】電子教案數(shù)值計(jì)算方法【第二版】電子教案 南京大學(xué)林成森南京大學(xué)林成森5第一節(jié)第一節(jié) 特征值的估計(jì)和數(shù)值穩(wěn)定性特征值的估計(jì)和數(shù)值穩(wěn)定性 為為格格希希格格林林圓圓盤盤。則則稱稱，令令階階矩矩陣陣對(duì)對(duì)定定義義iiiinijjijinnijraZCZZniaraAn ), 2 , 1( ,)(1一、格希格林圓盤一、格希格林圓盤(Gerschgorin(Gerschgorin) )數(shù)值計(jì)算方法【第二版】電子教案數(shù)值計(jì)算方法【第二版】電子教案 南京大學(xué)林成森南京大學(xué)林成森6 nnnnnniniinixxxxaaaaaaaaaxAxAx1111

4、1212111211 ，則則有有最最大大元元為為的的特特征征向向量量規(guī)規(guī)范范化化使使其其，將將設(shè)設(shè)有有數(shù)值計(jì)算方法【第二版】電子教案數(shù)值計(jì)算方法【第二版】電子教案 南京大學(xué)林成森南京大學(xué)林成森7二、特征值問(wèn)題的穩(wěn)定性二、特征值問(wèn)題的穩(wěn)定性內(nèi)內(nèi)。為為中中心心的的格格希希格格林林圓圓盤盤必必須須在在以以此此式式說(shuō)說(shuō)明明，得得到到因因?yàn)闉閭€(gè)個(gè)方方程程是是其其第第iiinijjijiijnijjjijiiaraanjxxaai 11), 2 , 1( , 1,數(shù)值計(jì)算方法【第二版】電子教案數(shù)值計(jì)算方法【第二版】電子教案 南京大學(xué)林成森南京大學(xué)林成森8第二節(jié)第二節(jié) 冪法和反冪法冪法和反冪法 求矩陣的按模

5、最大的特征值與相應(yīng)的特征向量。求矩陣的按模最大的特征值與相應(yīng)的特征向量。它是通過(guò)迭代產(chǎn)生向量序列，由此計(jì)算特征值和特它是通過(guò)迭代產(chǎn)生向量序列，由此計(jì)算特征值和特征向量。征向量。一、冪法一、冪法數(shù)值計(jì)算方法【第二版】電子教案數(shù)值計(jì)算方法【第二版】電子教案 南京大學(xué)林成森南京大學(xué)林成森9 12(1)(2)( )(0)(1)( )( )(1)( )(1)1(1,2, )(1,2, ), ,(1 ,2,),/,ininkkkkkkiinnAininxxxyAykykyyy 設(shè)設(shè)階階實(shí)實(shí)矩矩陣陣 的的特特征征值值滿滿足足且且與與相相應(yīng)應(yīng)的的特特征征向向量量線線性性無(wú)無(wú)關(guān)關(guān)。給給定定初初始始向向量量y由y

6、由迭迭代代公公式式產(chǎn)產(chǎn)生生向向量量序序列列可可以以證證明明，當(dāng)當(dāng) 充充分分大大時(shí)時(shí)，有有相相應(yīng)應(yīng)的的特特征征向向量量為為。數(shù)值計(jì)算方法【第二版】電子教案數(shù)值計(jì)算方法【第二版】電子教案 南京大學(xué)林成森南京大學(xué)林成森10 ( )(0)( )11 (1,2, )(1,2, , ) , iiiniiixinuninyx 為為簡(jiǎn)簡(jiǎn)便便，不不妨妨設(shè)設(shè)。因因?yàn)闉榫€線性性無(wú)無(wú)關(guān)關(guān)，故故必必存存在在 個(gè)個(gè)不不全全為為零零的的數(shù)數(shù)使使得得。()(1)(0)( )( )11()(1)(2)()211211 () ()()nnkkkkikiiiiiikkkknnnyAyA yAxxyxxx 由由數(shù)值計(jì)算方法【第二版】

7、電子教案數(shù)值計(jì)算方法【第二版】電子教案 南京大學(xué)林成森南京大學(xué)林成森1111( )( )211()(1)( )(1)1111210,(2,3, ) lim() lim() ( )inkikiiiiikkinkkkikiiiinxxkyxxx 設(shè)設(shè)由由得得故故只只要要 充充分分大大，就就有有( )(1)1(1)( )(1)1111(1)1( )( )( ) , (1,2,) kikkkkkikikkiyyxyxyinyyyi 因因此此，可可把把作作為為與與相相應(yīng)應(yīng)的的特特征征向向量量的的近近似似。由由為為的的第第 個(gè)個(gè)分分量量。數(shù)值計(jì)算方法【第二版】電子教案數(shù)值計(jì)算方法【第二版】電子教案 南京大

8、學(xué)林成森南京大學(xué)林成森1221 A 按按上上面面式式子子計(jì)計(jì)算算矩矩陣陣 按按模模最最大大的的特特征征值值與與相相應(yīng)應(yīng)的的特特征征向向量量的的方方法法稱稱為為冪冪法法。 冪冪法法的的收收斂斂速速度度依依賴賴于于比比值值，比比值值越越小小，收收斂斂越越快快。數(shù)值計(jì)算方法【第二版】電子教案數(shù)值計(jì)算方法【第二版】電子教案 南京大學(xué)林成森南京大學(xué)林成森13(0)1()(1)()(1)1111 10, 2,(1)0(1 ) kkkyyxyx 兩兩點(diǎn)點(diǎn)說(shuō)說(shuō)明明：）如如果果的的選選取取恰恰恰恰使使得得冪冪法法計(jì)計(jì)算算仍仍能能進(jìn)進(jìn)行行。因因?yàn)闉橛?jì)計(jì)算算過(guò)過(guò)程程中中舍舍入入誤誤差差的的影影響響，迭迭代代若若干干

9、次次后后，必必然然會(huì)會(huì)產(chǎn)產(chǎn)生生一一個(gè)個(gè)向向量量它它在在方方向向上上的的分分量量不不為為零零，這這樣樣，以以后后的的計(jì)計(jì)算算就就滿滿足足所所設(shè)設(shè)條條件件。）因因計(jì)計(jì)算算過(guò)過(guò)程程中中可可能能會(huì)會(huì)出出現(xiàn)現(xiàn)溢溢出出或或成成為為的的情情形形。解解決決方方法法：每每次次迭迭代代所所求求的的向向量量都都要要?dú)w歸范范化化。因因此此，冪冪法法實(shí)實(shí)際際使使用用的的計(jì)計(jì)算算公公式式是是0012 1( )( )( )()( )( )( )max()(, ,.)kkkkkkkZyyAZCyZyCk數(shù)值計(jì)算方法【第二版】電子教案數(shù)值計(jì)算方法【第二版】電子教案 南京大學(xué)林成森南京大學(xué)林成森141( )( )1 1.(),(

10、,),2 .1,03.max4. 5., ,66.,1, 3ijnkkkriri nAayyyNkryyCyZyAZCCykNkk ( ( ) )算算法法：輸輸入入初初始始向向量量誤誤差差限限 ， 最最大大迭迭代代次次數(shù)數(shù) 。置置求求整整數(shù)數(shù) ，使使， y y計(jì)計(jì)算算置置若若輸輸出出停停機(jī)機(jī)；否否則則，轉(zhuǎn)轉(zhuǎn)若若置置轉(zhuǎn)轉(zhuǎn) ；否否則則，輸輸出出失失敗敗 信信息息，停停機(jī)機(jī)。數(shù)值計(jì)算方法【第二版】電子教案數(shù)值計(jì)算方法【第二版】電子教案 南京大學(xué)林成森南京大學(xué)林成森1503001011212100210120 0 1100 0 101 2200 5 10 52 2 5()()()( )()( )( )

11、()( )( , , ) ,. ( , , ) , ( ,) , ( ,. , ) , ( . ,. ) , TTTTTAyZyyAZCyZCyAZC用用 冪冪 法法 求求 矩矩 陣陣的的 按按 模模最最 大大 的的 特特 征征 值值 和和 相相 應(yīng)應(yīng) 的的 特特 征征 向向 量量 。取取例例 ：解解 ： 2 5. , 數(shù)值計(jì)算方法【第二版】電子教案數(shù)值計(jì)算方法【第二版】電子教案 南京大學(xué)林成森南京大學(xué)林成森16(8)(7)(8)(9)(8)31(2.7650948, 2.9981848,2.9990924) 2.9990924(0.9219772, 0.9996973,1)(2.843651

12、7, 2.9993946,2.9996973). 2.99969732.99909240.000604910 .2.9996973. yAZCZyAZ 由由故故相相應(yīng)應(yīng)特特(1)123121 (2.8436517, 2.9993946,2.9996973) 3,2,11 -1,1 2 .3TxA 征征向向量量為為。事事實(shí)實(shí)上上， 的的特特征征值值，與與對(duì)對(duì)應(yīng)應(yīng)的的特特征征向向量量為為（，）。此此例例中中比比值值為為數(shù)值計(jì)算方法【第二版】電子教案數(shù)值計(jì)算方法【第二版】電子教案 南京大學(xué)林成森南京大學(xué)林成森17兩種特殊情況兩種特殊情況:12121112()(1)()11(1)( )1111. 1,

13、 ( ( ) )mmnmkkmmkmknmnmnmAnyxxxx 前前面面假假定定如如果果按按模模最最大大的的特特征征值值有有多多個(gè)個(gè)，即即冪冪法法是是否否有有效效？（ ）是是重重根根，即即矩矩陣陣 仍仍有有 個(gè)個(gè)線線性性無(wú)無(wú)關(guān)關(guān)的的特特征征向向量量。此此時(shí)時(shí)有有 顯顯然然，只只要要1()(1)()11(1)()11(1)12()(), y() mkkmmmmkimkikkxxxxAyyy 不不全全為為零零，當(dāng)當(dāng) 充充分分大大時(shí)時(shí)，就就有有因因也也是是矩矩陣陣 相相應(yīng)應(yīng)于于的的特特征征向向量量，故故有有為為相相應(yīng)應(yīng)的的特特征征向向量量，即即對(duì)對(duì)這這種種情情況況冪冪法法仍仍然然有有效效。數(shù)值計(jì)算

14、方法【第二版】電子教案數(shù)值計(jì)算方法【第二版】電子教案 南京大學(xué)林成森南京大學(xué)林成森18 1213( )(1)(2)(3)( )3112311( )(21)21(1)(2)(2 )2(1)(2)112112(2)211,2( )2, ( 1)()() ()()kkkkknnnkkkkkkikiAnyxxxxykxxxxxxyy （ ）且且矩矩陣陣 有有 個(gè)個(gè)線線性性無(wú)無(wú)關(guān)關(guān)的的特特征征向向量量。由由上上式式可可知知，是是個(gè)個(gè)擺擺動(dòng)動(dòng)序序列列，當(dāng)當(dāng) 充充分分大大時(shí)時(shí)，有有(2)( )(1)1(1)1(2)112( )(1)(2)112(1)( )1(1)111(1)( )11(2)112/ ( 1

15、) ( 1)2 2( 1)kkiikkkkkkkkkkkkkyyyxxyxxyyxyyx 又又由由故故在在這這種種情情況況下下，仍仍可可按按冪冪法法產(chǎn)產(chǎn)生生向向量量序序列列。數(shù)值計(jì)算方法【第二版】電子教案數(shù)值計(jì)算方法【第二版】電子教案 南京大學(xué)林成森南京大學(xué)林成森19 12121(1)( )1( )12 nmmnkkkAyAyyAn 綜綜上上可可知知，當(dāng)當(dāng) 的的特特征征值值分分布布為為或或時(shí)時(shí)，用用冪冪法法可可以以計(jì)計(jì)算算出出 及及相相應(yīng)應(yīng)的的特特征征向向量量。如如果果按按迭迭代代所所得得向向量量序序列列呈呈有有規(guī)規(guī)律律的的擺擺動(dòng)動(dòng)，則則可可能能為為的的情情況況。否否則則應(yīng)應(yīng)考考慮慮用用別別的

16、的方方法法求求解解。此此外外，當(dāng)當(dāng)矩矩陣陣無(wú)無(wú) 個(gè)個(gè)線線性性無(wú)無(wú)關(guān)關(guān)的的特特征征量量時(shí)時(shí)，冪冪法法收收斂斂很很慢慢，亦亦應(yīng)應(yīng)考考慮慮改改用用其其他他方方法法。冪冪法法計(jì)計(jì)算算簡(jiǎn)簡(jiǎn)便便易易行行，它它是是求求大大型型稀稀疏疏矩矩陣陣按按模模最最大大特特征征值值的的常常用用方方法法。冪法小結(jié)冪法小結(jié)數(shù)值計(jì)算方法【第二版】電子教案數(shù)值計(jì)算方法【第二版】電子教案 南京大學(xué)林成森南京大學(xué)林成森20二、冪法的加速 因?yàn)閮绶ǖ氖諗克俣仁蔷€性的，而且依賴于比值因?yàn)閮绶ǖ氖諗克俣仁蔷€性的，而且依賴于比值 ,當(dāng)比值接近于當(dāng)比值接近于1時(shí)，冪法收斂很慢。冪法時(shí)，冪法收斂很慢。冪法加速有多種，介紹兩種加速有多種，介紹兩

17、種。12 數(shù)值計(jì)算方法【第二版】電子教案數(shù)值計(jì)算方法【第二版】電子教案 南京大學(xué)林成森南京大學(xué)林成森21( )(1)( )(1)(1)(2)( )211211 ()() ()() iikkkkkkknnnAApIApApIApIyAyyApI ypppxxxpp 1. 原1. 原點(diǎn)點(diǎn)移移位位法法矩矩陣陣 與與的的特特征征值值有有以以下下關(guān)關(guān)系系：若若是是 的的特特征征值值，則則就就是是的的特特征征值值，而而且且相相應(yīng)應(yīng)的的特特征征向向量量不不變變。如如果果對(duì)對(duì)矩矩陣陣按按計(jì)計(jì)算算，則則有有數(shù)值計(jì)算方法【第二版】電子教案數(shù)值計(jì)算方法【第二版】電子教案 南京大學(xué)林成森南京大學(xué)林成森22()(1)2

18、11122111211 ()() ()() (2,3, )kkkkknnniiyApI ypppuuuppppppinp 適適當(dāng)當(dāng)?shù)氐剡x選取取 ，使使得得且且1ApIpA 這這樣樣，用用冪冪法法計(jì)計(jì)算算的的最最大大模模特特征征值值及及相相應(yīng)應(yīng)特特征征向向量量的的收收斂斂速速度度比比對(duì)對(duì) 用用冪冪法法計(jì)計(jì)算算要要快快。這這種種加加速速收收斂斂的的方方法法稱稱為為原原點(diǎn)點(diǎn) 平平移移法法。數(shù)值計(jì)算方法【第二版】電子教案數(shù)值計(jì)算方法【第二版】電子教案 南京大學(xué)林成森南京大學(xué)林成森23123123221222221121121 00)1(), 2 (2,3,2 ) nnninnnnnnppAppppin

19、pp 原原點(diǎn)點(diǎn)平平移移法法使使用用簡(jiǎn)簡(jiǎn)便便，但但 的的選選取取困困難難。在在一一些些簡(jiǎn)簡(jiǎn)單單情情形形， 可可估估計(jì)計(jì)。如如當(dāng)當(dāng)矩矩陣陣 的的特特征征值值滿滿足足（或或時(shí)時(shí)，取取則則有有且且 11 因因此此，用用原原點(diǎn)點(diǎn)平平移移法法求求可可使使收收斂斂速速度度加加快快。數(shù)值計(jì)算方法【第二版】電子教案數(shù)值計(jì)算方法【第二版】電子教案 南京大學(xué)林成森南京大學(xué)林成森24(0)( )(1)(4)4140 51302.9,102.8(1,1,1) ,()6.9140 510.10100.1(3.1000568,2.214326, 0.968766 TkkApAyyApI yApIy - -4 4, ,用用原

20、原點(diǎn)點(diǎn)平平移移法法求求矩矩陣陣 的的按按模模最最大大的的特特征征值值，要要求求誤誤差差不不超超過(guò)過(guò)1 10 0 。取取一一按按進(jìn)進(jìn)行行計(jì)計(jì)解解算算： 例例：4(5)54541) 3.1000568(3.0999984,2.2142846, 0.9687501) 3.09999840.000058410y 數(shù)值計(jì)算方法【第二版】電子教案數(shù)值計(jì)算方法【第二版】電子教案 南京大學(xué)林成森南京大學(xué)林成森2511232121 3.09999842.95.9999984 (3.0999984,2.2142846, 0.9687501) . 6,3,2.8,1,20.11 3.131TAxAApp 所所以以，

21、矩矩陣陣 的的按按模模最最大大的的特特征征值值為為相相應(yīng)應(yīng)的的特特征征向向量量為為 不不難難求求出出， 的的特特征征值值為為若若對(duì)對(duì) 直直接接用用冪冪法法，則則比比值值而而用用原原點(diǎn)點(diǎn)平平移移法法，則則有有因因此此收收斂斂速速度度明明顯顯加加快快。數(shù)值計(jì)算方法【第二版】電子教案數(shù)值計(jì)算方法【第二版】電子教案 南京大學(xué)林成森南京大學(xué)林成森26 1211222112121 lim 0 ()22kkkkkkkkkkkkkkkkkkkkkkkaaaacaaaaaakaaaaaaaaaaaaaaaaaaaaaAitken 2 2. . A A i i t tk ke en n加加速速如如果果序序列列線線

22、性性收收斂斂到到 ，即即則則當(dāng)當(dāng) 充充分分大大時(shí)時(shí)，有有序序列列比比更更快快地地收收斂斂到到 ，這這就就是是加加速速法法。將將這這一一方方 kC法法用用于于冪冪法法所所產(chǎn)產(chǎn)生生的的序序列列，可可加加快快冪冪法法的的收收斂斂速速度度。數(shù)值計(jì)算方法【第二版】電子教案數(shù)值計(jì)算方法【第二版】電子教案 南京大學(xué)林成森南京大學(xué)林成森2710101221002101021 1.(),(,),2 .1,0,0,13.max4. ()5. 26.,77. , ijnririnrAayyyNkryyyCyZyAZyCaaaaaapykN 算算 法法 ：輸輸 入入初初 始始 向向 量量誤誤 差差 限限 ， 最最 大

23、大 迭迭 代代 次次 數(shù)數(shù)。置置求求 整整 數(shù)數(shù) ， 使使，計(jì)計(jì) 算算置置計(jì)計(jì) 算算若若輸輸 出出停停 機(jī)機(jī) ； 否否 則則 ， 轉(zhuǎn)轉(zhuǎn)若若置置,1,3p kk 轉(zhuǎn)轉(zhuǎn)； 否否 則則 ， 輸輸 出出 失失 敗敗 信信 息息 ， 停停 機(jī)機(jī) 。( (也也 可可 采采 用用 冪冪 法法 迭迭 代代 兩兩 步步 或或 三三 步步 ， 加加 速速 一一 次次 的的 方方 法法 ）數(shù)值計(jì)算方法【第二版】電子教案數(shù)值計(jì)算方法【第二版】電子教案 南京大學(xué)林成森南京大學(xué)林成森28三、反冪法三、反冪法 反冪法是計(jì)算矩陣按模最小的特征值及特征向反冪法是計(jì)算矩陣按模最小的特征值及特征向量的方法，也是修正特征值、求相應(yīng)特

24、征向量的最量的方法，也是修正特征值、求相應(yīng)特征向量的最有效的方法。有效的方法。數(shù)值計(jì)算方法【第二版】電子教案數(shù)值計(jì)算方法【第二版】電子教案 南京大學(xué)林成森南京大學(xué)林成森2911111 , 1 AnnuAAxxxA xA xxAAAAA 設(shè)設(shè) 為為階階非非奇奇異異矩矩陣陣，為為 的的特特征征值值與與相相應(yīng)應(yīng)的的特特征征向向量量，即即此此式式表表明明，的的特特征征值值是是 的的特特征征值值的的倒倒數(shù)數(shù)，而而相相應(yīng)應(yīng)的的特特征征向向量量不不變變。因因此此，若若對(duì)對(duì)矩矩陣陣用用冪冪法法，即即可可計(jì)計(jì)算算出出的的按按模模最最大大的的特特征征值值，其其倒倒數(shù)數(shù)恰恰為為的的按按模模最最小小的的特特征征值值。

25、 這這就就是是反反冪冪法法的的基基本本思思想想。數(shù)值計(jì)算方法【第二版】電子教案數(shù)值計(jì)算方法【第二版】電子教案 南京大學(xué)林成森南京大學(xué)林成森301( )(1)( )1(1)( ) kkkkkAAAyyyA yyA 因因?yàn)闉榈牡挠?jì)計(jì)算算比比較較麻麻煩煩，而而且且往往往往不不能能保保持持矩矩陣陣 的的一一些些好好性性質(zhì)質(zhì)（如如稀稀疏疏性性），因因此此，反反冪冪法法在在實(shí)實(shí)際際運(yùn)運(yùn)算算時(shí)時(shí)以以求求解解方方程程組組 代代替替冪冪法法迭迭代代求求得得，每每迭迭代代一一次次要要解解一一個(gè)個(gè)線線性性方方程程組組。由由于于矩矩陣陣在在迭迭代代過(guò)過(guò)程程中中不不變變，故故可可對(duì)對(duì) 先先進(jìn)進(jìn)行行三三角角分分解解，每每

26、次次迭迭代代只只要要解解兩兩個(gè)個(gè)三三角角形形方方程程組組。數(shù)值計(jì)算方法【第二版】電子教案數(shù)值計(jì)算方法【第二版】電子教案 南京大學(xué)林成森南京大學(xué)林成森31( )( )( )1( )( )( )(1)( )1.2.max, 3. kkkriri nkkkkkAPALUryyCyyZCLWPZUyW 反反冪冪法法計(jì)計(jì)算算的的主主要要步步驟驟：對(duì)對(duì) 進(jìn)進(jìn)行行三三角角分分解解求求整整數(shù)數(shù) ，使使得得計(jì)計(jì)算算解解方方程程組組數(shù)值計(jì)算方法【第二版】電子教案數(shù)值計(jì)算方法【第二版】電子教案 南京大學(xué)林成森南京大學(xué)林成森32 0 () ()iiijjiiijjiiAAIAI 用用帶帶原原點(diǎn)點(diǎn)平平移移的的反反冪冪法

27、法來(lái)來(lái)修修正正特特征征值值，并并求求相相應(yīng)應(yīng)的的特特征征向向量量是是非非常常有有效效的的。設(shè)設(shè)已已知知的的一一個(gè)個(gè)特特征征值值的的近近似似值值為為，因因接接近近，一一般般有有故故是是矩矩陣陣的的按按模模最最小小的的特特征征值值，且且由由上上式式可可知知，比比值值較較小小。因因此此，對(duì)對(duì)用用反反冪冪法法求求一一般般收收斂斂很很快快，通通常常只只要要經(jīng)經(jīng)過(guò)過(guò)二二、三三次次迭迭代代就就能能達(dá)達(dá)到到較較高高的的精精度度。反冪法的一個(gè)應(yīng)用反冪法的一個(gè)應(yīng)用數(shù)值計(jì)算方法【第二版】電子教案數(shù)值計(jì)算方法【第二版】電子教案 南京大學(xué)林成森南京大學(xué)林成森33111.(),(,),2 .1,13.()max5. 11

28、16 .,77.,1,ijnririnrAaxxxNkuP AILUryyyCyZLWZUyWyCyukNkk 算算 法法 ：輸輸 入入近近 似似 值值 ， 初初 始始 向向 量量誤誤 差差 限限 ， 最最 大大 迭迭 代代 次次 數(shù)數(shù)。置置作作 三三 角角 分分 解解 4 4. .求求 整整 數(shù)數(shù) ， 使使，計(jì)計(jì) 算算置置若若則則 置置, ,輸輸 出出停停 機(jī)機(jī) ； 否否 則則 ， 轉(zhuǎn)轉(zhuǎn)若若置置,4u 轉(zhuǎn)轉(zhuǎn)； 否否 則則 ， 輸輸 出出 失失 敗敗 信信 息息 ， 停停 機(jī)機(jī) 。數(shù)值計(jì)算方法【第二版】電子教案數(shù)值計(jì)算方法【第二版】電子教案 南京大學(xué)林成森南京大學(xué)林成森34(0)2100210

29、12(0,0,1) . 2.930.9310 2.9300.931010.931000.9310 01000.01/ 0.9 3 1 TAAyAIAI ，用用反反冪冪法法求求矩矩陣陣 接接近近2 2. . 9 93 3的的特特征征值值，并并求求相相應(yīng)應(yīng)的的特特征征向向量量，取取對(duì)對(duì)作作三三角角：分分解解得得例例解解：4931000.931/ 0.9333.0000954,310(1, 0.9992431,0.9991478)(1,-1,1)0.001.TTxr 按按算算法法迭迭代代 次次，與與準(zhǔn)準(zhǔn)確確值值 的的誤誤差差小小于于，與與準(zhǔn)準(zhǔn)確確值值比比較較，殘殘差差數(shù)值計(jì)算方法【第二版】電子教案數(shù)

30、值計(jì)算方法【第二版】電子教案 南京大學(xué)林成森南京大學(xué)林成森35 第三節(jié)第三節(jié) 求矩陣全部特征值的求矩陣全部特征值的QR方法方法 6060年代出現(xiàn)的年代出現(xiàn)的QRQR算法是目前計(jì)算中小型矩陣的算法是目前計(jì)算中小型矩陣的全部特征值與特征向量的最有效方法。全部特征值與特征向量的最有效方法。 理論依據(jù)：理論依據(jù)：任一非奇異實(shí)矩陣都可分解成一個(gè)正交矩陣任一非奇異實(shí)矩陣都可分解成一個(gè)正交矩陣Q Q和一個(gè)和一個(gè)上三角矩陣上三角矩陣R R的乘積，而且當(dāng)?shù)某朔e，而且當(dāng)R R的對(duì)角元符號(hào)取定時(shí)，的對(duì)角元符號(hào)取定時(shí)，分解是唯一的。分解是唯一的。 一、求矩陣全部特征值的一、求矩陣全部特征值的QR方法方法數(shù)值計(jì)算方法【

31、第二版】電子教案數(shù)值計(jì)算方法【第二版】電子教案 南京大學(xué)林成森南京大學(xué)林成森3611 QRQR (1,2,). kkkkkkAQ RkAR QAAA 方方法法的的基基本本思思想想是是利利用用矩矩陣陣的的分分解解通通過(guò)過(guò)迭迭代代格格式式將將化化成成相相似似的的上上三三角角陣陣（或或分分塊塊上上三三角角陣陣），從從而而求求出出矩矩陣陣的的全全部部特特征征值值與與特特征征向向量量。111111121112, (2 ,3, ) kAAQ RQARAR QQAQAAAAk 由由即即。于于是是即即與與相相似似。同同理理可可得得，。故故它它們們有有相相同同的的特特征征值值。數(shù)值計(jì)算方法【第二版】電子教案數(shù)值

32、計(jì)算方法【第二版】電子教案 南京大學(xué)林成森南京大學(xué)林成森37 可證，在一定條件下，基本可證，在一定條件下，基本QRQR方法產(chǎn)生的矩方法產(chǎn)生的矩陣序列陣序列A Ak k “ “基本基本”收斂于一個(gè)上三角陣（或收斂于一個(gè)上三角陣（或分塊上三角陣）。即主對(duì)角線（或主對(duì)角線子塊）分塊上三角陣）。即主對(duì)角線（或主對(duì)角線子塊）及其以下元素均收斂，主對(duì)角線（或主對(duì)角線子及其以下元素均收斂，主對(duì)角線（或主對(duì)角線子塊）以上元素可以不收斂。特別的，如果塊）以上元素可以不收斂。特別的，如果A A是實(shí)對(duì)是實(shí)對(duì)稱陣，則稱陣，則A Ak k “ “基本基本”收斂于對(duì)角矩陣。收斂于對(duì)角矩陣。數(shù)值計(jì)算方法【第二版】電子教案數(shù)

33、值計(jì)算方法【第二版】電子教案 南京大學(xué)林成森南京大學(xué)林成森38QR方法的實(shí)際計(jì)算步驟方法的實(shí)際計(jì)算步驟HouseholderAHessenbergB 用用陣陣作作正正交交相相似似變變換換上上第第陣陣一一步步.*:* 1kkkGivenkkkBQ RBBR Q 用變換產(chǎn)生迭代序列用變換產(chǎn)生迭代序列第二步第二步12*n 數(shù)值計(jì)算方法【第二版】電子教案數(shù)值計(jì)算方法【第二版】電子教案 南京大學(xué)林成森南京大學(xué)林成森39HouseholderAB 用用陣陣作作正正交交相相似似變變換換（對(duì)對(duì)稱稱陣陣）三三對(duì)對(duì)角角陣陣* 數(shù)值計(jì)算方法【第二版】電子教案數(shù)值計(jì)算方法【第二版】電子教案 南京大學(xué)林成森南京大學(xué)林成

34、森40二、化一般矩陣為上二、化一般矩陣為上Hessenberg陣陣111211121222123233311 (2,3,), Househ old e rnnnnnnnnniihhhhhhhhhhhHhhhinA 稱稱形形如如 的的矩矩陣陣為為上上海海森森堡堡（H H e es ss se en nb be er rg g) )陣陣。如如果果此此對(duì)對(duì)角角線線元元全全不不為為零零 則則稱稱該該矩矩陣陣為為不不可可約約的的上上H H e es ss se en nb be er rg g矩矩陣陣。討討論論用用變變換換將將一一般般矩矩陣陣相相似似變變換換成成H H e es ss se en nb

35、be er rg g陣陣數(shù)值計(jì)算方法【第二版】電子教案數(shù)值計(jì)算方法【第二版】電子教案 南京大學(xué)林成森南京大學(xué)林成森4111111111 ,1000 01 HouseholderHHH AHHHHHnHouseholder 首首先先，選選取取矩矩陣陣使使得得經(jīng)經(jīng)相相似似變變換換后后的的矩矩陣陣的的第第一一列列中中有有盡盡可可能能多多的的零零元元素素。為為此此，應(yīng)應(yīng)取取為為如如下下形形式式其其中中為為階階矩矩陣陣。數(shù)值計(jì)算方法【第二版】電子教案數(shù)值計(jì)算方法【第二版】電子教案 南京大學(xué)林成森南京大學(xué)林成森42111211111221121311212131(,) ,(,) ,TTTnnaa HH A

36、HH aH A Haaaaaaaa 于于是是有有 其其中中222222111111.(, 0) 0,2nnnnTaaAaaHH aH AHn 只只要要取取使使得得就就會(huì)會(huì)使使得得變變換換后后的的矩矩陣陣的的第第一一列列出出現(xiàn)現(xiàn)個(gè)個(gè)零零元元。數(shù)值計(jì)算方法【第二版】電子教案數(shù)值計(jì)算方法【第二版】電子教案 南京大學(xué)林成森南京大學(xué)林成森432211221222211221000*0100*00*0022, .nnnHouseholderHH H AH HHnnHouseholderHHHHH H AH HHHHHessenberg 同同理理，可可構(gòu)構(gòu)造造如如下下列列形形式式矩矩陣陣使使得得* *如如此

37、此進(jìn)進(jìn)行行次次，可可以以構(gòu)構(gòu)造造個(gè)個(gè)矩矩陣陣使使得得其其中中為為上上矩矩陣陣AH。特特別別地地，當(dāng)當(dāng) 為為實(shí)實(shí)對(duì)對(duì)稱稱矩矩陣陣，則則經(jīng)經(jīng)過(guò)過(guò)上上述述正正交交變變換換后后，變變?yōu)闉槿龑?duì)對(duì)角角陣陣。數(shù)值計(jì)算方法【第二版】電子教案數(shù)值計(jì)算方法【第二版】電子教案 南京大學(xué)林成森南京大學(xué)林成森441221522 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陣陣。求求矩矩陣陣滿滿：足

38、足，數(shù)值計(jì)算方法【第二版】電子教案數(shù)值計(jì)算方法【第二版】電子教案 南京大學(xué)林成森南京大學(xué)林成森4522 22222210442220122222442210000100220022220022TTuuHIu uH 數(shù)值計(jì)算方法【第二版】電子教案數(shù)值計(jì)算方法【第二版】電子教案 南京大學(xué)林成森南京大學(xué)林成森462112 100052223201001052 22 222002202102202410022100052510100103222 000223220012220022HH H AH H 于于 是是 有有數(shù)值計(jì)算方法【第二版】電子教案數(shù)值計(jì)算方法【第二版】電子教案 南京大學(xué)林成森南京大學(xué)林

39、成森47用用Household方法對(duì)矩陣方法對(duì)矩陣A作正交相似變換作正交相似變換, 使使A相似與上相似與上Hessenberg陣，算法如下：陣，算法如下：(1)(1)111221111111(1)112,1,2,.,21(1)()()() ) ,()(0,.,0,.,)kkTkknkkkiki kkkkkkkkkkkknkknHIUUsign aaaUaaa ，計(jì)算計(jì)算數(shù)值計(jì)算方法【第二版】電子教案數(shù)值計(jì)算方法【第二版】電子教案 南京大學(xué)林成森南京大學(xué)林成森481(2)kHAA計(jì)計(jì)算算 (1)11(1),1,11()21,nkjlljlkkkijijjijk kntuaiknaat u （ ）

40、（ ）(1)11(1)1,.,1(1)(2)1,.,nkiilll kkkijijijinta ujknaat u 1(3)kAHA計(jì)計(jì)算算 數(shù)值計(jì)算方法【第二版】電子教案數(shù)值計(jì)算方法【第二版】電子教案 南京大學(xué)林成森南京大學(xué)林成森49三、上三、上Hessenberg陣的陣的QR分解分解對(duì)對(duì)上上Hessenberg陣陣只需要將其次對(duì)角線上的只需要將其次對(duì)角線上的元素約化為零，用元素約化為零，用Given變換比用變換比用Householder變變換更節(jié)省計(jì)算量。為此先介紹換更節(jié)省計(jì)算量。為此先介紹Given變換。變換。數(shù)值計(jì)算方法【第二版】電子教案數(shù)值計(jì)算方法【第二版】電子教案 南京大學(xué)林成森南

41、京大學(xué)林成森50,11cossin11sincos11 ()i jiRjjin n階階方方陣陣稱稱為為平平面面旋旋轉(zhuǎn)轉(zhuǎn)陣陣，或或稱稱為為G Gi iv ve en ns s變變換換陣陣。定定義義 、平面旋轉(zhuǎn)陣、平面旋轉(zhuǎn)陣(Givens(Givens變換陣變換陣) )數(shù)值計(jì)算方法【第二版】電子教案數(shù)值計(jì)算方法【第二版】電子教案 南京大學(xué)林成森南京大學(xué)林成森511,1,TTi ji ji ji jRRIRRRi i, ,j j平平面面旋旋轉(zhuǎn)轉(zhuǎn)陣陣的的（ ）平平面面旋旋轉(zhuǎn)轉(zhuǎn)陣陣是是非非對(duì)對(duì)稱稱交交質(zhì)質(zhì)：陣陣性性的的正正。,2Ti ji jRR（ ）也也是是平平面面旋旋轉(zhuǎn)轉(zhuǎn)陣陣。( (3 3) )d

42、de et t( () )= =1 1數(shù)值計(jì)算方法【第二版】電子教案數(shù)值計(jì)算方法【第二版】電子教案 南京大學(xué)林成森南京大學(xué)林成森521,.,Rxxxxi i, ,j jT T1 12 2n n平平面面旋旋轉(zhuǎn)轉(zhuǎn)陣陣的的作作用用：（ ）將將向向量量 = =的的第第j j個(gè)個(gè)分分量量約約化化為為零零。,cossinsincos1,., ;,i jiijjijkkyRxyxxyxxyxkn ki j, ,若若令令，有有 111,222121212cossinsincoscossinsincosyxRyxxxxxxx ,.,i jRxx xxxT T12n12n左左乘乘向向量量 = =只只改改變變 的的

43、第第i i個(gè)個(gè)分分量量和和第第j j個(gè)個(gè)分分量量。數(shù)值計(jì)算方法【第二版】電子教案數(shù)值計(jì)算方法【第二版】電子教案 南京大學(xué)林成森南京大學(xué)林成森530tanjjixyx令令，得得2222cossiniiijjjijxxCrxxxxSrxx 所所以以，取取22,0iijijjyCxSxrxxy 于于是是 ,., ,.,0,.,.i jRxxxr xxxxT T1 1i i- -1 1i i+ +1 1j j- -1 1j j+ +1 1n n= =jxix jy調(diào)調(diào)整整 ，可可將將 約約化化為為零零。數(shù)值計(jì)算方法【第二版】電子教案數(shù)值計(jì)算方法【第二版】電子教案 南京大學(xué)林成森南京大學(xué)林成森542,.

44、,xxxxT T1 12 2n n（ ）將將向向量量 = =的的第第i i+ +1 1個(gè)個(gè)分分量量到到第第n n個(gè)個(gè)分分量量約約化化為為零零。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= =數(shù)值計(jì)算方法【第二版】電子教案數(shù)值計(jì)算方法【第二版】電子教案 南京大學(xué)林成森南京大學(xué)林

45、成森55,(3)i ji jiiji jjRAARAARRARAAT TT T左左乘乘 只只改改變變 的的第第i i，j j行行。右右乘乘 只只改改用用對(duì)對(duì)矩矩陣陣 作作變變換換得得變變 的的第第i i，j j列列。只只改改變變 的的第第i i，j j行行和和到到的的結(jié)結(jié)第第論論i i，j j列列。數(shù)值計(jì)算方法【第二版】電子教案數(shù)值計(jì)算方法【第二版】電子教案 南京大學(xué)林成森南京大學(xué)林成森562,1,4,0,0.xxrT TT T已已知知向向量量 = =，試試用用G Gi iv ve en ns s變變換換將將 約約化化為為例例(1)(1)2,1,4x xxT T：記記 = =，對(duì)對(duì)計(jì)計(jì)解解算算

46、C C和和S S。122222121221,55xxCSxxxx1,2(1)(2)1,221055120550015,0,4TRRxx 數(shù)值計(jì)算方法【第二版】電子教案數(shù)值計(jì)算方法【第二版】電子教案 南京大學(xué)林成森南京大學(xué)林成森57(2)4,21xS 5 5對(duì)對(duì)計(jì)計(jì)算算C C和和S S, ,C C= =2 21 1 (1)1,31,34021010,21,0,04021TRRx 5 52 21 15 52 21 1(2)5,0,4Tx數(shù)值計(jì)算方法【第二版】電子教案數(shù)值計(jì)算方法【第二版】電子教案 南京大學(xué)林成森南京大學(xué)林成森58、用、用 GivensGivens變換對(duì)變換對(duì)上上Hessenberg

47、陣作陣作QR分解分解(1)(1)(1)11121(1)(1)(1)21222(1)(1)1 1 nnnnnnbbbbbbBbbnGivensBQR 對(duì)對(duì)上上H essenberg陣H essenberg陣, ,通通常常用用個(gè)個(gè)變變換換陣陣可可將將它它化化成成上上三三角角矩矩陣陣，從從而而得得到到 的的分分解解式式。數(shù)值計(jì)算方法【第二版】電子教案數(shù)值計(jì)算方法【第二版】電子教案 南京大學(xué)林成森南京大學(xué)林成森59(1)211111(2)(2)(2)112131(2)(2)(2)22232(2)(2)(2)1232333(2)(2)1 0(cossin00sincos00(1,2)0011(1,2)

48、nnnnnnnbRrbbbbbbRBBbbbbb 具具體體步步驟驟為為：設(shè)設(shè)否否則則進(jìn)進(jìn)行行下下一一步步），取取旋旋轉(zhuǎn)轉(zhuǎn)矩矩陣陣則則(1)(1)(1)(1)1121111112111 cos, sin, .bbrbbrr 其其中中數(shù)值計(jì)算方法【第二版】電子教案數(shù)值計(jì)算方法【第二版】電子教案 南京大學(xué)林成森南京大學(xué)林成森602322222( 3 )( 3 )( 3 )( 3 )11213111( 3 )( 3 )( 3 )223212( 3 )( 3 )( 3 )333132( 3 )( 3 )4341 0(10cossinsincos (3, 2)11 (3 , 2)nnnnnnnbRrbbb

49、brbbbbbbRBbb （）設(shè)設(shè)否否 則則 進(jìn)進(jìn) 行行 下下 一一 步步 ） ， 再再 取取 旋旋 轉(zhuǎn)轉(zhuǎn) 矩矩 陣陣 則則3( 3 )4( 3 )( 3 )1( 2 )( 2 )( 2 )2( 2 )23222222223222 cos, sin, ()() .nnnnnBbbbbbrbbrr 其其 中中數(shù)值計(jì)算方法【第二版】電子教案數(shù)值計(jì)算方法【第二版】電子教案 南京大學(xué)林成森南京大學(xué)林成森611( )( )( )( )1111111( )( )( )11111( )( )( )1( )( )( )1111( )( )1 (1, ) kkkkkkkknnkkkkkkknknkkkkkknk

50、nkkkkkknknkknnnnBR kk Brbbbbrbbbbhhbbbbb 1k 假假設(shè)設(shè)上上述述過(guò)過(guò)程程已已進(jìn)進(jìn)行行了了步步，有有數(shù)值計(jì)算方法【第二版】電子教案數(shù)值計(jì)算方法【第二版】電子教案 南京大學(xué)林成森南京大學(xué)林成森62()1()()1()2()21 0,11 (1,)cossinsincos1 cos, sin, ()() .kkkkkkkkkkkkkkkkkkkkkkkkbR kkbbrrrbb 設(shè)設(shè)取取其其中中數(shù)值計(jì)算方法【第二版】電子教案數(shù)值計(jì)算方法【第二版】電子教案 南京大學(xué)林成森南京大學(xué)林成森63(1)(1)(1)11111(1)(1)1(1)(1)(1)111111(

51、1)(1)(1)21212(1)(1)1 (1, )1kkkkknkkkkkknkkkkkkkknknkkkkkknknkknnnnrbbbrbbR kk BBbhbbhhbbn 于于是是因因此此，最最多多做做次次旋旋轉(zhuǎn)轉(zhuǎn)變變換換，即即( )( )( )( )112131( )( )2232( )33 ( ,1) (2,1)(1,2)nnnnnnnnnnnHR n nR nnRBrbbbrbbRrbr 得得數(shù)值計(jì)算方法【第二版】電子教案數(shù)值計(jì)算方法【第二版】電子教案 南京大學(xué)林成森南京大學(xué)林成森64213212132123( ,1),(2,3, ) 4,() TTTnnTTTnnR i iin

52、HR RRRQRQR RRnQRO nHRQQRQR 因因?yàn)闉榫鶠闉檎唤痪鼐仃囮嚕使势淦渲兄腥匀詾闉檎唤痪鼐仃囮?。可可算算出出完完成成這這一一過(guò)過(guò)程程的的運(yùn)運(yùn)算算量量約約為為比比一一般般矩矩陣陣的的分分解解的的運(yùn)運(yùn)算算量量少少一一個(gè)個(gè)數(shù)數(shù)量量級(jí)級(jí)?？煽勺C證明明仍仍是是上上H H e es ss se en nb be er rg g陣陣，于于是是可可按按上上述述步步驟驟一一直直迭迭代代下下去去，這這樣樣得得到到的的方方法法的的運(yùn)運(yùn)算算量量比比基基本本QR方方法法大大為為減減少少。需需要要說(shuō)說(shuō)明明的的是是，通通常常用用方方法法計(jì)計(jì)算算特特征征值值，然然后后用用反反冪冪法法求求其其相相

53、應(yīng)應(yīng)的的特特征征向向量量。數(shù)值計(jì)算方法【第二版】電子教案數(shù)值計(jì)算方法【第二版】電子教案 南京大學(xué)林成森南京大學(xué)林成森6522532644445 (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

54、 于于是是 數(shù)值計(jì)算方法【第二版】電子教案數(shù)值計(jì)算方法【第二版】電子教案 南京大學(xué)林成森南京大學(xué)林成森6611221111151.3867503.3282007.2111021.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陣陣。將將進(jìn)進(jìn)行行分分解解，記記取取0.5698030.8217810(2,1)0.8217810.5698030001R 數(shù)值計(jì)算方法【第二版】電子教案數(shù)值計(jì)算方法【第二版】電子教案 南京大學(xué)林成森南京大學(xué)林成森67122222228.7749641.8015968.597089(2,1)00.4383101.91103000.1538462.230767 (0.438310)( 0.153846)0.464526, cos0.4383100.943564, sin0.1538460.