矩陣特征值計算PPT

1、11 1 引引 言言第第8 8章章 矩陣特征值問題計算矩陣特征值問題計算物理、力學和工程技術中很多問題在數(shù)學上都歸結為求矩陣的特征值問題。例如，振動問題(大型橋梁或建筑物的振動、機械的振動、電磁震蕩等)，物理學中的某些臨界值的確定。它們都歸結為下述數(shù)學問題。nnnnnnnnijaaaaaaaaaa212222111211)det()( ,)( AIA則稱已知定定義義1 12.|) 1()( 12211特特征征多多項項式式的為AAaaannnnn.)( .(1.1) 0)det()( 的所有特征值的集合表示的的根稱為的特征方程AAAAIA特征值特征值.(1.2) 0)( ,特征值特征向量特征向量

2、的的對應于稱為的非零解相應的齊次方程組的為設AxxAIA3.210131012 的特征值及其特征向量求A例1例1.1 ,10 )4( , )3()( )( , )2()0( (1) , 11xxAAAxxAAxxIAIAAxA即的特征值為且非奇異，則設；即的特征值是；即的特征值為；常數(shù)的特征值是向量，則是對應的非零特征的特征值是矩陣設kkkknnppppcccR定理1定理14.)det( )2(,1)(tr1 (1) ,), 1( 1niiiinianiniAAA則的特征值是矩陣若定理2定理2).()( , 3AAATnnR則設定定理理5. )()( , , 122211211miiiiimm

3、mmAAAAAAAAAAA則均為方陣其中每個對角塊為分塊上三角陣設定理4定理4. , )2(; ) 1 (, , 1的特征向量是則的特征向量是若有相同的特征值與則使非奇異即為相似矩陣與若APyByBAPPPBABA定理5定理56. , 虧虧損損矩矩陣陣定定義義2 2為，則稱個數(shù)少于線性無關的特征向量的且其對應的重特征值有一個如果設AAAkkRnn., ,)( )2(. 1 2121211線性無關對應的特征向量則個不同的特征值有若個線性無關的特征向量具有的充要條件是使非奇異矩陣即可對角化，）（mmnnnnnxxxnmmRnRAAAPPPA定理6定理67則為對稱矩陣設對稱矩陣的正交約化, )7(n

4、nRA定理定理；個線性無關的特征向量有的特征值均為實數(shù)；nAA )2( (1).)(,), 2 , 1( )3(21211的特征向量為對應于向量的列而的特征值為且，使得存在正交矩陣jjnin,niuuuuPAAPPP8.), 1( ,| | )2( | 1,)( 圓盤為半徑的為圓心以為復平面上以稱，）（令設nGerschgoriraDnizrazzDnijaraiiiiiiiiijinnijCA定義3定義3. ), 1( |,| ,)( (1) )( nijniaaanGerschgoriijiinnij某個圓盤之中一個特征值必屬于下列的每則設圓盤定理AA定理8定理8.S ,S, 個特征值的中

5、恰有則個圓盤分離與其余且個圓盤構成一個連通域個圓盤中有如果上述的mmnSmnA(2)(2)9.), 2 , 1(. ),(diag11結果質獲得特征值的進一步改變，根據(jù)相似矩陣性和連通性有時可使某些圓盤半徑適當選取，得到選取非奇異對角矩陣niainnijijnADDD.411101014 的特征值的范圍估計A例例2 2.49 . 09 . 001014,119101910ADDD2|4| 2|1|4|2 . 28 . 55339192919110.), 2 , 1(, )(922211211的特征值為其中使則存在酉矩陣，設定理AnirrrrrrrRSchuriinnnnTnnRAUUUA定理定

6、理.), 2 , 1(, )(1022211211的兩個共軛復特征值的兩個特征值是二階時為的實特征值，當是為一階時其中當使則存在正交矩陣，設分解實ARRARRRRRRRRAQQQAiiiiiiiimmmmTnnmiRSchur定定理理11.)()(),()( , , 商商瑞瑞雷雷定定義義4 4RayleighRRnn的為關于向量稱對于任一非零向量階實對稱陣是設xxx,xAxxxA.)(),(min 3,)(),(max 2 ,)(),( 1 . , 11111xx,xAxxx,xAxxxx,xAxAAxxxx00nnRnRnnnRn）（）（對于任何非零向量）（則的特征值為階實對稱陣為設定定理理

7、122 2 冪法及反冪法冪法及反冪法一、一、冪法冪法冪法是一種求實矩陣A的按模最大的特征值1及其對應的特征向量x1的方法。特別適合于大型稀疏矩陣。 ., , ,)(2121nnnnnnijRaxxxA對應的特征向量為為其特征值有一個完全特征向量組設(2.1) , 21n滿足的主特征值是實根，且并設A.11的基本方法及現(xiàn)在討論求x13)0( ,122110aaaann設xxxv,22211101nnnaaaxxxAvv.121221111nknnkkkkaaaxxxAvv.lim , , 111111111xvvAvvvxvaakkkkkkkkkk，很大時，當.1的近似的特征向量是即kv .1)

8、()(1 ,)()( 1111njnjkjkjkjkvvvv或而主特征值14，則對任何非零初始向量其特征值個線性無關的特征向量有設)0( , , 121021anRnnnvA定理定理.)()(lim lim 11111jkjkkkkkavvxv，上述結果仍成立線性無關的特征向量時個有且，當nRnnnrrrA ,121.)()(lim ,lim 1111jkjkkriiikkkavvxv15就有得值最大的分量，規(guī)范化的絕對為向量記做改進為了避免“溢出”下面 ).()max( )max( .0 0vvvuvv(2.9) )1,2,( ./),max( , , )0( , , 131001021ka

9、nRkkkkkkknnnvuvAuvvuvA計算，對任何非零初始向量其特征值個線性無關的特征向量有設定理定理.lim ,)max(lim 111kkkkxxu則16 ,)max()max( , 對于任0011100100AvAvvvuAvAuvvu，給非零向量事實上，,)max()max( ,)max( 020222200212vAvAvvuAvvAAuv.)max()max( ,)max( , 00010vAvAvvuvAvAvkkkkkkkk17,121221110nknnkkkaaaxxxvA)( )max( max)max(111212211121221100kaaaaaanknnkn

10、knnkkkkxxxxxxxxvAvAu18)( maxmax )max(max)max(111211221112122111010kaaaaaanknnknknnkkkkxxxxxxvAvAv.12確定收斂速度由比值r19.225. 05 . 025. 0115 . 011 特征向量的按模最大特征值及其用冪法求A例3例3A=1 1 0.5;1 1 .25;.5 .25 2u=1,1,1v=A*u,v1=max(v),u=v/v120二、二、加速方法加速方法 原點位移法原點位移法1.1. IABp.5,3,1A)( 量的收斂速度最大特征值及其特征向的按模法求，考察帶原點平移的冪設A例例4 4，

11、若n21 .2*2np則.225. 05 . 025. 0115 . 011 特征向量的按模最大特征值及其用帶原點平移的冪法求A例5例5.75. 0p取21 瑞雷商加速法瑞雷商加速法2.2.),(),( )9 . 2( , , 142121121kkkkkknnnORuuuAuuA的較好近似的瑞利商給出，則應用冪法其特征值滿足為對稱矩陣設定理定理).( 1 ,333aP：作作業(yè)業(yè)22三、反冪三、反冪法法反冪法可求非奇異實矩陣的按模最小特征值及特征向量。 .)max( ),max( , 2 , 1 ,)max(, ,11100kkknknkkkkknkRvvuxvvvuuAvuv計算任取非零向量

12、. , , 11kkkkkkkyUvuLyLUuAvv求解即分解求得利用經常來求得求解可通過主元高斯消去法23 ).1,2,( ,)max( , )0( , 0 , 151100121kanRkkkkknnnnnvvuuAvvuA計算，對任何非零初始向量其特征值滿足向量個線性無關的特征為非奇異矩陣且有設定理定理.1)max(lim ,)max(lim nkknnkkvxxu則24特征值.移來加速迭代或求其他在反冪法中可用原點位.,1 ,1 ,1 )(21211nnppppxxxIA對應的特征向量仍然為存在，則特征值為若(2.12) ).1,2,( ,)max( ,)( 1100kpkkkkkv

13、vuuIAvvu，計算對任何非零初始向量)( , 0 ijpppijj的近似，并且滿足的特征值是如果A25.)()()(111及其對應的特征向量特征值法可求的主特征值，用上述算是則pppjjIA).( , 0 , ), 2 , 1( , 16ijpppninRijjiinn且的近似是而和值和特征向量記為的特征個線性無關的特征向量有設xAA定定理理(2.12) ).1,2,( ,)max( ,)( ),0(110kpakkkkkjvvuuIAvu計算對任何非零初始向量.)max(1,1)max( ,)max( jkjkjjkppvvxxu則26 .min確定收斂速度由比值pprijij.算迭代一

14、兩次就可完成計很小，離較好，一般的較好近似且特征值分是只要rpj. ) 1 , 1 , 1 (:10110vPuLUvu，即得使得實際選取T. )( :.)( 11kkkkkkppyUvPuLyLUIAPLUuvIA，組：，需解兩個三角形方程分解借助反冪法需要解方程組：27反冪法計算公式反冪法計算公式: .)max( )( 1kkkkkpvvuuvIA., 3 , 2 ,/ ),max( , (2) ;/),max( , ) 1 , 1 , 1 (1 . 2.,)( : . 111111111kpkkkkkkkkkTvuvyUvPuLyvuvvUvULPLUIAPLU得）解（反冪法迭代，保存分

15、解.2679. 133410131012 3的特征向量的特征值求A例例6 6format long;A=2 1 0;1 3 1;0 1 4,p=1.2679,B=A-p*eye(3);L U P=lu(B);L,U,P,v=U1 1 1, mu=max(v);u=v/mu,v=U(L(P*u), mu=max(v);u=v/mu,lamda=p+1/mu283 Householder3 Householder方法方法一、引言一、引言本節(jié)討論兩個問題:. ) 1 ( 伯格矩陣海森似變換約化實矩陣為上用初等反射陣作正交相. )2( 對角矩陣的問題對稱似變換約化對稱矩陣為用初等反射陣作正交相. 值問

16、題或對稱對角矩陣的特征格矩陣題就轉化為求上海森伯于是，原矩陣特征值問已經學過的知識：29階矩陣則且設nRTn , 1 , www定定義義TwwIH2 .rHouseholde,)(矩陣也稱矩陣或鏡面反射稱為初等反射都有初等反射陣對于因此 , 0u , ,.2)( 22uuuIuHT , ,)0 , 0 , 1 (0),( 11121，使得則總存在初等反射陣，設約化定理eHxuuIHexTTTnxxx) )定定理理( (其中 . )(,),( ,)sgn(1222121121xxxxxTnuexux30 般矩陣為上海森伯格陣用正交相似變換約化一二二、 .),(,1131211) 1 (221)

17、1 (12112122221112111TnnnnnnnaaaaaaaaaaaaacAcAAA其中步約化：設第 ),1否則這步不需做不妨0(c ,111111111，使得取初等反射陣ecRuuIRT其中 . )(,),( ,)sgn(2111221211131121111121211aaaaaTnuecuc31,00 )2(222)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(12111) 1 (221111) 1 (12111112AcAARARcRRAUAUA 0nnnnnnnaaaaaaaaaaaaaa，則令11

18、1RU.),()2(2)2(322Tnaac其中32)()(1,)(,)(, 1)(1, 1)(, 1)(,1) 1(1, 12)(2)(1, 2)(2) 1(1, 2)2(221)(1)(1, 1)(1) 1(1, 1)2(12) 1 (1111111111121 ,1, 1knnkknkknknkkkkkkkkkkkkkkknkkkkkkknkkkkkkkkkkkkkaaaaaaaaaaaaaaaaaaakkUUAUUUAUAUUU使得步，即有步約化：假定已完成第第, )(22)(12)(11knkkkkkAcAA 0.)(11階上海森伯格矩陣是其中kkA33 ,11，使取初等反射陣不妨e

19、cRuuIRckkkTkkkkk0其中 . )(,),( ,)sgn()(, 12221)(,)(, 2)(, 112)(, 1kkkkkkkTkknkkkkkkkkkkkkkkkaaaaauecuc. ) 1(221) 1(12) 1(11)(22)(12)(111kkkkkkkkkkkkkkkkkkkAcAARARcRRAAUAUARIU0000，則令.1) 1(11階上海森伯格矩陣是其中kkA. )(22)(22)(12）為對稱陣時只需計算（當及步約化只需計算第RARARARRAkkkkkkk34.* 2) 1(1)2(1, 1)3(332)2(221) 1 (1121121nnnnnn

20、nnnnaaaaanUAUUUA步約化：第).( , 002112221上海森伯格矩陣使得，則存在初等反射陣設HAUUUAUUUUUUATnnnnnR定定理理1 17 735.32 12,1, . 2; . 10010kkkkkkkkkknkIUUURIUAUUAecRRU）（；，其中）約化計算（；，使）計算初等反射陣（對：00算法1.724232734 1約化為上海森伯格矩陣用豪斯霍爾德方法將 AA例例7 7 ,)4 , 2(111111，使得，求初等反射陣解：ecRRcT36.0.4472 0.8944- 0.8944- 0.4472- 16)522(4)522(4)522()522(52

21、111 )522(52)( ,)4 , 522( , 5220)sgn(21111121111111121211TTaauuIRecuc，.2.2000 0.4000- 0.0000 0.4000- 7.8000 4.4721-0.4472- 7.6026 4.0000-1112HUAUA，111RU37 稱陣為對稱三對角陣用正交相似變換約化對三、. , 81112221112112221CUAUUUUUUAnnnnnnnnncbbcbbcbbcR使得反射陣為對稱陣，則存在初等設定定理理1 1.17知：由定理證明38, .11) 1(221) 1(12) 1(11)(22)(12)(111kn

22、kkkkkknkkkkkkkkkkkkkkAcAARARcRRAAUAUA00步約化中，在第下面考慮實現(xiàn)過程).()(22即可實際上對角線以下元素和對稱，故只需計算因kkkkRARRA,)(21,1)(221knkkTkkkkknkkkkRRururtuAr記)( )(221)(221)(22TkkkkkTkkkkkkuuAAuuIRAR則TkkTkkkTkkkTkkkTkkTkkkkkTkkTkkkTkkTkkkTkkTkkkkTkkkTkkkuttuAuururururuAuruuruurAuruuAuuurA)(2211)(221)(221)(221)(22 )(2)(2 )( 39)算

23、法2(略. 9 , 4 ,334P：作作業(yè)業(yè)404 QR4 QR方法方法Rutishauser(1958)利用矩陣的三角分解提出計算矩陣特征值的LR算法，F(xiàn)rancis(1961,1962)利用矩陣的QR分解建立計算矩陣特征值的QR方法.QR方法是一種變換方法，是計算一般(中小型)矩陣全部特征值問題的最有效方法之一.目前QR方法主要用來計算：（1）上海森伯格陣全部特征值問題；（2）對稱三對角陣全部特征值問題.下面先介紹求非奇異矩陣的全部特征值的基本QR方法，再討論上海森伯格陣和對稱三對角陣的全部特征值問題.41一、基本一、基本QR方法方法 , 30 ,111RQAAA知存在正交三角分解由第五章定理對非奇異矩陣).2(30,222. , , ,ThRQQRAApnRnn為上三角陣交陣階正為其中交三角分解則存在正為非奇異矩陣設交換乘法次序得, 111112QQQRAAT, 2222RQAA作正交三角分解得再對, 222223QAQQRAT再交換乘法次序得, ,kkkkRQAA作正交三角分解得對一般地, 1kkTkkkkQAQQRA交換乘法次序得42并且有如下結果：相似，有相同的特征值與可見 , ,1AAk. 111111kTkkTTkkkkTkTkkkTkkkkQAQQAQQQQQAQQQAQQRA分解：進行設方法基本QRRnn , )