矩陣特征值計算

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

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

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

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

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

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

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

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

9、對任何非零初始向量其特征值個線性無關(guān)的特征向量有設(shè)定理定理.lim ,)max(lim 111kkkkxxu則 ,)max()max( , 對于任0011100100AvAvvvuAvAuvvu，給非零向量事實上，,)max()max( ,)max( 020222200212vAvAvvuAvvAAuv.)max()max( ,)max( , 00010vAvAvvuvAvAvkkkkkkkk,121221110nknnkkkaaaxxxvA)( )max( max)max(111212211121221100kaaaaaanknnknknnkkkkxxxxxxxxvAvAu)( maxmax

10、 )max(max)max(111211221112122111010kaaaaaanknnknknnkkkkxxxxxxvAvAv.12確定收斂速度由比值r.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/v1二、二、加速方法加速方法 原點位移法原點位移法1.1. IABp.5,3,1A)( 量的收斂速度最大特征值及其特征向的按模法求，考察帶原點平移的冪設(shè)A例4例4，若n21 .2*2np則.225. 05 . 025. 0115 . 0

11、11 特征向量的按模最大特征值及其用帶原點平移的冪法求A例5例5.75. 0p取 瑞雷商加速法瑞雷商加速法2.2.),(),( )9 . 2( , , 142121121kkkkkknnnORuuuAuuA的較好近似的瑞利商給出，則應(yīng)用冪法其特征值滿足為對稱矩陣設(shè)定理定理).( 1 ,333aP：作作業(yè)業(yè)三、反冪三、反冪法法反冪法可求非奇異實矩陣的按模最小特征值及特征向量。 .)max( ),max( , 2 , 1 ,)max(, ,11100kkknknkkkkknkRvvuxvvvuuAvuv計算任取非零向量. , , 11kkkkkkkyUvuLyLUuAvv求解即分解求得利用經(jīng)常來求

12、得求解可通過主元高斯消去法 ).1,2,( ,)max( , )0( , 0 , 151100121kanRkkkkknnnnnvvuuAvvuA計算，對任何非零初始向量其特征值滿足向量個線性無關(guān)的特征為非奇異矩陣且有設(shè)定理定理.1)max(lim ,)max(lim nkknnkkvxxu則特征值.移來加速迭代或求其他在反冪法中可用原點位.,1 ,1 ,1 )(21211nnppppxxxIA對應(yīng)的特征向量仍然為存在，則特征值為若(2.12) ).1,2,( ,)max( ,)( 1100kpkkkkkvvuuIAvvu，計算對任何非零初始向量)( , 0 ijpppijj的近似，并且滿足的

13、特征值是如果A.)()()(111及其對應(yīng)的特征向量特征值法可求的主特征值，用上述算是則pppjjIA).( , 0 , ), 2 , 1( , 16ijpppninRijjiinn且的近似是而和值和特征向量記為的特征個線性無關(guān)的特征向量有設(shè)xAA定定理理(2.12) ).1,2,( ,)max( ,)( ),0(110kpakkkkkjvvuuIAvu計算對任何非零初始向量.)max(1,1)max( ,)max( jkjkjjkppvvxxu則 .min確定收斂速度由比值pprijij.算迭代一兩次就可完成計很小，離較好，一般的較好近似且特征值分是只要rpj. ) 1 , 1 , 1 (:

14、10110vPuLUvu，即得使得實際選取T. )( :.)( 11kkkkkkppyUvPuLyLUIAPLUuvIA，組：，需解兩個三角形方程分解借助反冪法需要解方程組：反冪法計算公式反冪法計算公式: .)max( )( 1kkkkkpvvuuvIA., 3 , 2 ,/ ),max( , (2) ;/),max( , ) 1 , 1 , 1 (1 . 2.,)( : . 111111111kpkkkkkkkkkTvuvyUvPuLyvuvvUvULPLUIAPLU得）解（反冪法迭代，保存分解.2679. 133410131012 3的特征向量的特征值求A例例6 6format long;

15、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/mu3 Householder3 Householder方法方法一、引言一、引言本節(jié)討論兩個問題:. ) 1 ( 伯格矩陣海森似變換約化實矩陣為上用初等反射陣作正交相. )2( 對角矩陣的問題對稱似變換約化對稱矩陣為用初等反射陣作正交相. 值問題或?qū)ΨQ對角矩陣的特征格矩陣題就轉(zhuǎn)化為求上海森伯于是，原矩陣特征值問已經(jīng)學(xué)過的知識：階矩陣則且設(shè)nRTn

16、 , 1 , www定義定義TwwIH2 .rHouseholde,)(矩陣也稱矩陣或鏡面反射稱為初等反射都有初等反射陣對于因此 , 0u , ,.2)( 22uuuIuHT , ,)0 , 0 , 1 (0),( 11121，使得則總存在初等反射陣，設(shè)約化定理eHxuuIHexTTTnxxx) )定定理理( (其中 . )(,),( ,)sgn(1222121121xxxxxTnuexux 般矩陣為上海森伯格陣用正交相似變換約化一二二、 .),(,1131211) 1 (221) 1 (12112122221112111TnnnnnnnaaaaaaaaaaaaacAcAAA其中步約化：設(shè)第

17、),1否則這步不需做不妨0(c ,111111111，使得取初等反射陣ecRuuIRT其中 . )(,),( ,)sgn(2111221211131121111121211aaaaaTnuecuc,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，則令111RU.),()2(2)2(322Tnaac其中)()(1,)(,)(, 1)(1, 1)(, 1)(,1) 1(1

18、, 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階上海森伯格矩陣是其中kkA ,11，使取初等反射陣不妨ecRuuIRckkkTkkkkk0其中 . )(,),( ,)sgn()(, 12221)(,)(, 2)(, 112)(,

19、 1kkkkkkkTkknkkkkkkkkkkkkkkkaaaaauecuc. ) 1(221) 1(12) 1(11)(22)(12)(111kkkkkkkkkkkkkkkkkkkAcAARARcRRAAUAUARIU0000，則令.1) 1(11階上海森伯格矩陣是其中kkA. )(22)(22)(12）為對稱陣時只需計算（當(dāng)及步約化只需計算第RARARARRAkkkkkkk.* 2) 1(1)2(1, 1)3(332)2(221) 1 (1121121nnnnnnnnnnaaaaanUAUUUA步約化：第).( , 002112221上海森伯格矩陣使得，則存在初等反射陣設(shè)HAUUUAUUU

20、UUUATnnnnnR定定理理1 17 7.32 12,1, . 2; . 10010kkkkkkkkkknkIUUURIUAUUAecRRU）（；，其中）約化計算（；，使）計算初等反射陣（對：00算法1.724232734 1約化為上海森伯格矩陣用豪斯霍爾德方法將 AA例例7 7 ,)4 , 2(111111，使得，求初等反射陣解：ecRRcT.0.4472 0.8944- 0.8944- 0.4472- 16)522(4)522(4)522()522(52111 )522(52)( ,)4 , 522( , 5220)sgn(21111121111111121211TTaauuIRecuc

21、，.2.2000 0.4000- 0.0000 0.4000- 7.8000 4.4721-0.4472- 7.6026 4.0000-1112HUAUA，111RU 稱陣為對稱三對角陣用正交相似變換約化對三、. , 81112221112112221CUAUUUUUUAnnnnnnnnncbbcbbcbbcR使得反射陣為對稱陣，則存在初等設(shè)定定理理1 1.17知：由定理證明, .11) 1(221) 1(12) 1(11)(22)(12)(111knkkkkkknkkkkkkkkkkkkkkAcAARARcRRAAUAUA00步約化中，在第下面考慮實現(xiàn)過程).()(22即可實際上對角線以下元

22、素和對稱，故只需計算因kkkkRARRA,)(21,1)(221knkkTkkkkknkkkkRRururtuAr記)( )(221)(221)(22TkkkkkTkkkkkkuuAAuuIRAR則TkkTkkkTkkkTkkkTkkTkkkkkTkkTkkkTkkTkkkTkkTkkkkTkkkTkkkuttuAuururururuAuruuruurAuruuAuuurA)(2211)(221)(221)(221)(22 )(2)(2 )( )算法2(略. 9 , 4 ,334P：作作業(yè)業(yè)4 QR4 QR方法方法Rutishauser(1958)利用矩陣的三角分解提出計算矩陣特征值的LR算法

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