數(shù)值計算方法（南京大學）第8章矩陣特征值問題

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

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

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

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

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

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

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

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

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

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

11、()( )( , , ) ,. ( , , ) , ( ,) , ( ,. , ) , ( . ,. ) , TTTTTAyZyyAZCyZCyAZC用用 冪冪 法法 求求 矩矩 陣陣的的 按按 模模最最 大大 的的 特特 征征 值值 和和 相相 應應 的的 特特 征征 向向 量量 。取取例例 ：解解 ： 2 5. , 數(shù)值計算方法【第二版】電子教案數(shù)值計算方法【第二版】電子教案 南京大學林成森南京大學林成森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 由由故故相相應應特特(1)123121 (2.8436517, 2.9993946,2.9996973) 3,2,11 -1,1 2 .3TxA 征征向向量量為為。事事實實上上， 的的特特征征值值，與與對對應應的的特特征征向向量量為為（，）。此此例例中中比比值值為為數(shù)值計算方法【第二版】電子教案數(shù)值計算方法【第二版】電子教案 南京大學林成森南京大學林成森17兩種特殊情況兩種特殊情況:12121112()(1)()11(1)( )1111. 1,

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

14、方法【第二版】電子教案數(shù)值計算方法【第二版】電子教案 南京大學林成森南京大學林成森18 1213( )(1)(2)(3)( )3112311( )(21)21(1)(2)(2 )2(1)(2)112112(2)211,2( )2, ( 1)()() ()()kkkkknnnkkkkkkikiAnyxxxxykxxxxxxyy （ ）且且矩矩陣陣 有有 個個線線性性無無關關的的特特征征向向量量。由由上上式式可可知知，是是個個擺擺動動序序列列，當當 充充分分大大時時，有有(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ù)值計算方法【第二版】電子教案數(shù)值計算方法【第二版】電子教案 南京大學林成森南京大學林成森19 12121(1)( )1( )12 nmmnkkkAyAyyAn 綜綜上上可可知知，當當 的的特特征征值值分分布布為為或或時時，用用冪冪法法可可以以計計算算出出 及及相相應應的的特特征征向向量量。如如果果按按迭迭代代所所得得向向量量序序列列呈呈有有規(guī)規(guī)律律的的擺擺動動，則則可可能能為為的的情情況況。否否則則應應考考慮慮用用別別的

16、的方方法法求求解解。此此外外，當當矩矩陣陣無無 個個線線性性無無關關的的特特征征量量時時，冪冪法法收收斂斂很很慢慢，亦亦應應考考慮慮改改用用其其他他方方法法。冪冪法法計計算算簡簡便便易易行行，它它是是求求大大型型稀稀疏疏矩矩陣陣按按模模最最大大特特征征值值的的常常用用方方法法。冪法小結冪法小結數(shù)值計算方法【第二版】電子教案數(shù)值計算方法【第二版】電子教案 南京大學林成森南京大學林成森20二、冪法的加速 因為冪法的收斂速度是線性的，而且依賴于比值因為冪法的收斂速度是線性的，而且依賴于比值 ,當比值接近于當比值接近于1時，冪法收斂很慢。冪法時，冪法收斂很慢。冪法加速有多種，介紹兩種加速有多種，介紹兩

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

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

19、pp 原原點點平平移移法法使使用用簡簡便便，但但 的的選選取取困困難難。在在一一些些簡簡單單情情形形， 可可估估計計。如如當當矩矩陣陣 的的特特征征值值滿滿足足（或或時時，取取則則有有且且 11 因因此此，用用原原點點平平移移法法求求可可使使收收斂斂速速度度加加快快。數(shù)值計算方法【第二版】電子教案數(shù)值計算方法【第二版】電子教案 南京大學林成森南京大學林成森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、原點點平平移移法法求求矩矩陣陣 的的按按模模最最大大的的特特征征值值，要要求求誤誤差差不不超超過過1 10 0 。取取一一按按進進行行計計解解算算： 例例：4(5)54541) 3.1000568(3.0999984,2.2142846, 0.9687501) 3.09999840.000058410y 數(shù)值計算方法【第二版】電子教案數(shù)值計算方法【第二版】電子教案 南京大學林成森南京大學林成森2511232121 3.09999842.95.9999984 (3.0999984,2.2142846, 0.9687501) . 6,3,2.8,1,20.11 3.131TAxAApp 所所以以，

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

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

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

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

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

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

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

28、16 .,77.,1,ijnririnrAaxxxNkuP AILUryyyCyZLWZUyWyCyukNkk 算算 法法 ：輸輸 入入近近 似似 值值 ， 初初 始始 向向 量量誤誤 差差 限限 ， 最最 大大 迭迭 代代 次次 數(shù)數(shù)。置置作作 三三 角角 分分 解解 4 4. .求求 整整 數(shù)數(shù) ， 使使，計計 算算置置若若則則 置置, ,輸輸 出出停停 機機 ； 否否 則則 ， 轉(zhuǎn)轉(zhuǎn)若若置置,4u 轉(zhuǎn)轉(zhuǎn)； 否否 則則 ， 輸輸 出出 失失 敗敗 信信 息息 ， 停停 機機 。數(shù)值計算方法【第二版】電子教案數(shù)值計算方法【第二版】電子教案 南京大學林成森南京大學林成森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的的特特征征值值，并并求求相相應應的的特特征征向向量量，取取對對作作三三角角：分分解解得得例例解解：4931000.931/ 0.9333.0000954,310(1, 0.9992431,0.9991478)(1,-1,1)0.001.TTxr 按按算算法法迭迭代代 次次，與與準準確確值值 的的誤誤差差小小于于，與與準準確確值值比比較較，殘殘差差數(shù)值計算方法【第二版】電子教案數(shù)

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

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

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

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

34、森40二、化一般矩陣為上二、化一般矩陣為上Hessenberg陣陣111211121222123233311 (2,3,), Househ old e rnnnnnnnnniihhhhhhhhhhhHhhhinA 稱稱形形如如 的的矩矩陣陣為為上上海海森森堡堡（H H e es ss se en nb be er rg g) )陣陣。如如果果此此對對角角線線元元全全不不為為零零 則則稱稱該該矩矩陣陣為為不不可可約約的的上上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ù)值計算方法【第二版】電子教案數(shù)值計算方法【第二版】電子教案 南京大學林成森南京大學林成森4111111111 ,1000 01 HouseholderHHH AHHHHHnHouseholder 首首先先，選選取取矩矩陣陣使使得得經(jīng)經(jīng)相相似似變變換換后后的的矩矩陣陣的的第第一一列列中中有有盡盡可可能能多多的的零零元元素素。為為此此，應應取取為為如如下下形形式式其其中中為為階階矩矩陣陣。數(shù)值計算方法【第二版】電子教案數(shù)值計算方法【第二版】電子教案 南京大學林成森南京大學林成森42111211111221121311212131(,) ,(,) ,TTTnnaa HH A

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

37、此進進行行次次，可可以以構構造造個個矩矩陣陣使使得得其其中中為為上上矩矩陣陣AH。特特別別地地，當當 為為實實對對稱稱矩矩陣陣，則則經(jīng)經(jīng)過過上上述述正正交交變變換換后后，變變?yōu)闉槿龑墙顷囮嚒?shù)值計算方法【第二版】電子教案數(shù)值計算方法【第二版】電子教案 南京大學林成森南京大學林成森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ù)值計算方法【第二版】電子教案數(shù)值計算方法【第二版】電子教案 南京大學林成森南京大學林成森4522 22222210442220122222442210000100220022220022TTuuHIu uH 數(shù)值計算方法【第二版】電子教案數(shù)值計算方法【第二版】電子教案 南京大學林成森南京大學林成森462112 100052223201001052 22 222002202102202410022100052510100103222 000223220012220022HH H AH H 于于 是是 有有數(shù)值計算方法【第二版】電子教案數(shù)值計算方法【第二版】電子教案 南京大學林成森南京大學林

39、成森47用用Household方法對矩陣方法對矩陣A作正交相似變換作正交相似變換, 使使A相似與上相似與上Hessenberg陣，算法如下：陣，算法如下：(1)(1)111221111111(1)112,1,2,.,21(1)()()() ) ,()(0,.,0,.,)kkTkknkkkiki kkkkkkkkkkkknkknHIUUsign aaaUaaa ，計算計算數(shù)值計算方法【第二版】電子教案數(shù)值計算方法【第二版】電子教案 南京大學林成森南京大學林成森481(2)kHAA計計算算 (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計計算算 數(shù)值計算方法【第二版】電子教案數(shù)值計算方法【第二版】電子教案 南京大學林成森南京大學林成森49三、上三、上Hessenberg陣的陣的QR分解分解對對上上Hessenberg陣陣只需要將其次對角線上的只需要將其次對角線上的元素約化為零，用元素約化為零，用Given變換比用變換比用Householder變變換更節(jié)省計算量。為此先介紹換更節(jié)省計算量。為此先介紹Given變換。變換。數(shù)值計算方法【第二版】電子教案數(shù)值計算方法【第二版】電子教案 南京大學林成森南

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

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

43、第第i i個個分分量量和和第第j j個個分分量量。數(shù)值計算方法【第二版】電子教案數(shù)值計算方法【第二版】電子教案 南京大學林成森南京大學林成森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ù)值計算方法【第二版】電子教案數(shù)值計算方法【第二版】電子教案 南京大學林成森南京大學林成森542,.

44、,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= =數(shù)值計算方法【第二版】電子教案數(shù)值計算方法【第二版】電子教案 南京大學林成森南京大學林

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

46、C C和和S S。122222121221,55xxCSxxxx1,2(1)(2)1,221055120550015,0,4TRRxx 數(shù)值計算方法【第二版】電子教案數(shù)值計算方法【第二版】電子教案 南京大學林成森南京大學林成森57(2)4,21xS 5 5對對計計算算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ù)值計算方法【第二版】電子教案數(shù)值計算方法【第二版】電子教案 南京大學林成森南京大學林成森58、用、用 GivensGivens變換對變換對上上Hessenberg

47、陣作陣作QR分解分解(1)(1)(1)11121(1)(1)(1)21222(1)(1)1 1 nnnnnnbbbbbbBbbnGivensBQR 對對上上H essenberg陣H essenberg陣, ,通通常常用用個個變變換換陣陣可可將將它它化化成成上上三三角角矩矩陣陣，從從而而得得到到 的的分分解解式式。數(shù)值計算方法【第二版】電子教案數(shù)值計算方法【第二版】電子教案 南京大學林成森南京大學林成森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 具具體體步步驟驟為為：設設否否則則進進行行下下一一步步），取取旋旋轉(zhuǎn)轉(zhuǎn)矩矩陣陣則則(1)(1)(1)(1)1121111112111 cos, sin, .bbrbbrr 其其中中數(shù)值計算方法【第二版】電子教案數(shù)值計算方法【第二版】電子教案 南京大學林成森南京大學林成森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 （）設設否否 則則 進進 行行 下下 一一 步步 ） ， 再再 取取 旋旋 轉(zhuǎn)轉(zhuǎn) 矩矩 陣陣 則則3( 3 )4( 3 )( 3 )1( 2 )( 2 )( 2 )2( 2 )23222222223222 cos, sin, ()() .nnnnnBbbbbbrbbrr 其其 中中數(shù)值計算方法【第二版】電子教案數(shù)值計算方法【第二版】電子教案 南京大學林成森南京大學林成森611( )( )( )( )1111111( )( )( )11111( )( )( )1( )( )( )1111( )( )1 (1, ) kkkkkkkknnkkkkkkknknkkkkkknk

50、nkkkkkknknkknnnnBR kk Brbbbbrbbbbhhbbbbb 1k 假假設設上上述述過過程程已已進進行行了了步步，有有數(shù)值計算方法【第二版】電子教案數(shù)值計算方法【第二版】電子教案 南京大學林成森南京大學林成森62()1()()1()2()21 0,11 (1,)cossinsincos1 cos, sin, ()() .kkkkkkkkkkkkkkkkkkkkkkkkbR kkbbrrrbb 設設取取其其中中數(shù)值計算方法【第二版】電子教案數(shù)值計算方法【第二版】電子教案 南京大學林成森南京大學林成森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ù)值計算方法【第二版】電子教案數(shù)值計算方法【第二版】電子教案 南京大學林成森南京大學林成森64213212132123( ,1),(2,3, ) 4,() TTTnnTTTnnR i iin

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

53、應應的的特特征征向向量量。數(shù)值計算方法【第二版】電子教案數(shù)值計算方法【第二版】電子教案 南京大學林成森南京大學林成森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ù)值計算方法【第二版】電子教案數(shù)值計算方法【第二版】電子教案 南京大學林成森南京大學林成森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陣陣。將將進進行行分分解解，記記取取0.5698030.8217810(2,1)0.8217810.5698030001R 數(shù)值計算方法【第二版】電子教案數(shù)值計算方法【第二版】電子教案 南京大學林成森南京大學林成森67122222228.7749641.8015968.597089(2,1)00.4383101.91103000.1538462.230767 (0.438310)( 0.153846)0.464526, cos0.4383100.943564, sin0.1538460.