數(shù)值分析特征值和Jacobi方法

1、第9章 矩陣特征值問題的數(shù)值方法 9.1 特征值與特征向量引言工程實踐中有多種工程實踐中有多種振動問題振動問題，如橋梁或建，如橋梁或建筑物的振動，機械機件、飛機機翼的振筑物的振動，機械機件、飛機機翼的振動，工程實踐中有多種振動問題，如橋動，工程實踐中有多種振動問題，如橋梁或建筑物的振動，機械機件、飛機機梁或建筑物的振動，機械機件、飛機機翼的振動，及一些翼的振動，及一些穩(wěn)定性分析穩(wěn)定性分析和相關(guān)分和相關(guān)分析可轉(zhuǎn)化為求矩陣特征值與特征向量的析可轉(zhuǎn)化為求矩陣特征值與特征向量的問題。問題。London, England: Millennium (Wobbly) Bridge (1998-2002, N

2、orman Foster and Partners and Arup Associates) I decide that I have to write something today, otherwise I would not know how to speak English here. This is a very quick story about a bridge. London launched three major construction projects to celebrate the arrival of the Millennium. After all, Gree

3、nwich (pronounced green-ich) is supposed to be (supposed to be?!) where the prime meridian lies, and the place where the Millennium officially starts in the world. The three projects are the Millennium Dome in North Greenwich, so far the largest single roofed structure in the world, London Eye right

4、 across Westminster, which becomes so far the largest observation wheel in the world, and the Millennium Bridge that links Southeast London with St. Pauls Cathedral, which is currentlywell.not swinging any more, it is said. The bridge was designed by Imperial College, a college of my former universi

5、ty. On the very first day that the bridge was open to public, there were simply so many people going there to walk from the south bank to St. Pauls that the weight completely exceeded the architects expectation. The slender steel truss bridge began to vibrate with a million people on there. The open

6、ing ceremony ended up in an embarrassing vertigo. Millennium left Londoners a happy adage about swinging bridge, meaning fancy technology that looks good but functions in a funny fashion. Am I using too many Fs here? Or is it simply because my tongue starts to swing in the same direction when I am w

7、riting about this wobbly bridge? Next time you visit London, I strongly recommend this place. After all, with a little swing, this is a shortcut to dash into St. Pauls directly from the southeast! xxGT1exTG: Google Matrix, “the worlds largest matrix computation”. 4,300,000,000 x: PageRank（網(wǎng)頁級別）（網(wǎng)頁級別

8、） vector “The $25,000,000,000 Eigenvector”搜索引擎搜索引擎9.1 特征值與特征向量 設(shè)A是n階矩陣，x是非零列向量. 如果有數(shù)存在，滿足 ， (1)那么，稱x是矩陣A關(guān)于特征值的特征向量. Axx如果把(1)式右端寫為 ，那么(1)式又可寫為:Ix()0IA x| 0IA即1110( ) |.nnnfIAaaa記它是關(guān)于參數(shù)的n次多項式，稱為矩陣A的特征多項式， 其中a0=(-1)nA. (2) 顯然，當是A的一個特征值時，它必然是 的根. 反之，如果是 的根，那么齊次方程組(2)有非零解向量x，使(1)式成立. 從而，是A的一個特征值. A的特征值也

9、稱為A的特征根. ( )0f( )0f矩陣特征值和特征向量有如下主要性質(zhì)： 定理9.1.1 n階矩陣A是降秩矩陣的充分必要條件是A有零特征值. 定理9.1.2 設(shè)矩陣A與矩陣B相似，那么它們 有相同的特征值. 定理9.1.3 n階矩陣A與AT有相同的特征值. 定理9.1.4 設(shè)ij是n階矩陣A的兩個互異特征值，x、y分別是其相應(yīng)的右特征向量和左特征向量，那么，xTy=0 . 9.2 Hermite矩陣特征值問題 設(shè)A為n階矩陣，其共軛轉(zhuǎn)置矩陣記為AH. 如果A=AH，那么，A稱為Hermite矩陣.9.2.1 Hermite矩陣的有關(guān)性質(zhì) 設(shè) 是Hermite矩陣A的n個特征值.有以下性質(zhì):

10、全是實數(shù).12,.,n 12,.,n 有相應(yīng)的n個線性無關(guān)的特征向量，它們可以化為一組標準酉交的特征向量組 ,即 12,.,n 12,.,nu uuHiju uij 是酉空間中的一組標準酉交基. 12,.,nu uu 記U=( ),它是一個酉陣，即UHU=UUH=I，那么即A與以 為對角元的對角陣相似.12,.,nu uu1HnUAUD12,.,n A為正定矩陣的充分必要條件是 全為正數(shù). 12,.,n 定理9.2.1 設(shè) 是Hermite矩陣A的n個特征值，那么證:12,.,n 21maxii nA 21niFiA2222()()( ( )HAA AAA由21maxii nA 因此2221(

11、)()nHiFiAtr A Atr A又由21niFiA得 設(shè)x是一個非零向量，A是Hermite矩陣，稱 為矩陣A關(guān)于向量x的Rayleigh商，記為R(x). HHx Axx x定理9.2.2 如果A的n個特征值為 其相應(yīng)的標準酉交的特征向量為 那么有 12.n12,.,nu uu1( )nR x定理9.2.3 設(shè)A是Hermite矩陣 ，那么100min( )min( )kn kkkx Cxx CxR xR x 且且或9.2.2 極值定理 定理9.2.4(極值定理) 設(shè)Hermite矩陣的n個特征值為 ，其相應(yīng)的標準酉交特征向量為 . 用Ck表示酉空間Cn中任意的k維子空間，那么12.n

12、12,.,nu uu1100max min( )minmax( )kkn kn kkx CxCkCx CxR xR x 且且或9.2.3 Hermite矩陣特征值問題的性態(tài) 矩陣特征值問題與求解線性方程組問題一樣，都存在當矩陣A的原始 數(shù)據(jù)有小變化(小擾動)時，引起特征值問題的變化有大有小的問題，如果引起的變化小，稱 該特征值問題是良態(tài)的. 反之，稱為病態(tài)的. 矩陣特征值問題的性態(tài)是很復(fù)雜的，通常分別就單個特征值或整體特征值給出條件數(shù)進行分 析. 對于Hermite矩陣，由于其特征值問題的特殊性質(zhì)，其特征值都是良態(tài)的.下面先證明Hermite矩陣特征值的擾動定理. 定理9.2.5 設(shè)矩陣A，E

13、，A+E都是n階Hermite矩陣，其特征值分別為 那么,證 設(shè)矩陣A關(guān)于特征值1，2，n 的標準酉交特征向量為u1，u2，un， 是由ui，ui+1，un生成的n-i+1維子空間. 對 中任意非零向量x,由極值定理,有12n12n12n1inii1n iC 1n iC 111000()maxmaxmaxn in in iHiHx CxHHHHx Cxx CxxAE xx xx Axx Exx xx x 且且且由定理9.2.3，又由定理9.2.2，對任意x0，有從而有另一方面, A=(A+E)-E. 記 為矩陣-E的特征值，那么，重復(fù)上面的過程,可得從而有10maxn iHiHx Cxx Ax

14、x x 且110maxn iHnHx Cxx Exx x 且1ii12n1in i 1iiiin定理9.2.5通常又稱為Hermite矩陣特征值的擾動定理 定理9.2.6 設(shè)矩陣A和A=A+E都是n階Hermite矩 陣，其特征值分別為 和 ，那么 12n12n222iiEE9.3 Jacobi方法 理論上，實對稱矩陣A正交相似于以A的特征值為對角元 的 對角陣. 問題是如何構(gòu)造這樣的正交矩陣呢? Jacobi方法就是通過構(gòu)造特殊的正交矩陣 序列，通過相似變換使A的非對角線元素逐次零化來實現(xiàn)對角化的. 9.3.1 平面旋轉(zhuǎn)矩陣與相似約化先看一個簡單的例子. 設(shè) 是二階實對稱矩陣，即a21=a1

15、2，其特征值為1，2. 令 使得 記 容易驗證BT=B, 且11122122aaAaacossinsincosR11TR AR11122122TbbBR ARbb22111112222212212211122222111222cos2sincossin()sincos(cossin)sin2sincoscosbaaabbaaabaaa解之得:當 時當 時可選取 1122aa12112221arctan2aaa1122aa4為使RTAR為對角陣，要求b12=b21=0一般的n階平面旋轉(zhuǎn)矩陣21arctan2pqppqqaaa49.3.2 經(jīng)典的Jacobi方法 設(shè)A是實對稱矩陣，記A1=A.Ja

16、cobi方法的基本思想是用迭代格式 Ak+1=QTkAkQk , k=1,2, 構(gòu)造一個相似矩陣序列，使Ak收斂于一個對角陣. 其中 Qk為平面旋轉(zhuǎn)矩陣，其旋轉(zhuǎn)角k由使Ak的絕對值 最大元a(k)pq=a(k)qp=0 或按列依次使A的非對角元 零化來確定. 定理9.3.1 設(shè)A是n階實對稱矩陣，那么由Jacobi方法產(chǎn)生的相似矩陣序列Ak的非對角元收斂于0. 也就是說，Ak收斂于以A的特征值為對角元的對角陣. 記 其中Ek是Ak除主對角元外的矩陣.由平面旋轉(zhuǎn)矩陣的性質(zhì) 中,對于 ,有因此,( )()kkiikAdiag aE1TkpqkpqAR A R,ip q(1)2(1)2( )2( )

17、2()()()()kkkkipiqipiqaaaa22( )212()kkkpqFFEEa又由假設(shè),因此,這樣,便有從而,當22( )( )( )( )1,1max(1)nkkkkpqijpqpqi j niji jijaaan na且且且22( )(1)kkpqFEn na222112222(1)(1)kkkFFFEEEnnnn1,0kFkE9.3.3 實用的Jacobi方法 循環(huán)Jacobi方法必須一次又一次掃描，才能使Ak收斂于對角陣 ，計算量很大. 在實際計算中，往往用一些特殊方法來控制掃描次數(shù)，減少計算量. 下面介 紹一種應(yīng)用最為廣泛的特殊循環(huán)Jacobi方法閾Jacobi方法. 閾

18、Jacobi方法首先確定一個閾值，在對非對角元零化的一次掃描中，只對其中絕對值 超過閾值的非對角元進行零化. 當所有非對角元素的絕對值都不超過閾值后，將閾值減少， 再重復(fù)下一輪掃描，直至閾值充分小為止. 減少閾值的方法通常是先固定一個正整數(shù)Mn，掃描一次后，讓 . 而閾值的下界是根據(jù)實際問題的精度要求選定的. M9.3.4 用Jacobi方法計算特征向量 假定經(jīng)過k次迭代得到Ak+1=RTkRT1AR1Rk，(15) 這時Ak+1是滿足精度要求的一個近似的對角陣. 如果記Qk=R1R2Rk=Qk-1Rk，(16) 那么，Qk是一個正交矩陣，且(15)式又可表示為Ak+1=QTkAQk.當Ak+

19、1的非對角元素充分小，Qk的第 j列qj可以看成是近似特征值a(k+1)jj相應(yīng)的特征向量了. 在實際計算中，可以按(16)式在迭代過程中形成Qk，把Qk看成是Qk-1右乘一個平面旋轉(zhuǎn)矩陣得到. 不妨記 Q0=I，Qk的元素按下式計算：( )(1)(1)( )(1)(1)( )(1)cossin,sincos, ,1,2,kkkipipkipkkkkiqipkiqkkkijijqqqqqqqqjp qin 9.4 對分法 理論上，一個實對稱矩陣正交相似于一個以其特征值為對角元的 對角陣. 但是，經(jīng)典的結(jié)果告訴我們，一個大于4次的多項式方程不可能用有限次四則運算 求根. 因此，我們不可能期望只用

20、有限次相似變換將一個實對稱矩陣約化為一個對角陣.下面先介紹將一個實對稱矩陣相似約化為實對稱三對角矩陣的方法，再討論求其特征值的對 分法. 9.4.1 相似約化為實對稱三對角矩陣 將一個實對稱矩陣正交相似約化為一個實對稱三對角矩陣的算法，可歸納如下： 記A(1)=A,對k=1,2,n-2 按(4)式、(5)式和(8)式計算 ； 按(9)(12)式，計算A(k+1). ,kkku和( )1,( )2,( )(4)kkkkkkkkknkaaua ( )( )21,1()() (5)nkkkkkiki ksignaa ( )1,()(8)kkkkkka 1( )1(1)( ),(9),(10)1,(1

21、1)2(),(12)kkkkTkkkkkkkkkkTTkkkkgA uu gyguAAu yy u9.4.2 Sturm序列的性質(zhì) 設(shè)實對稱三對角矩陣為 其中i0 (i=1,2,，n-1) 其特征矩陣為T-I. 記T-I的第i階主子式為 111221nnaTaa111211( )iiiiaapa 這是關(guān)于的i次多項式，當i=n時， pn()=T-I是矩陣T的特征多項式. 令p0()1，則有p1()=1-，pi()=(i-)pi-1()-2i-1pi-2()，i=2,3，n.(15) 多項式序列pi() (i=0,1,，n)稱為Sturm序列 111211( )iiiiaapa定理9.4.1pi

22、() (i=1,2,，n)的根都是 實根. 證 由(14)式，pi()是i階實對稱矩陣的特征多項式，因此，pi() (i=1,2,，n)的根全是實根. 定理9.4.2定理9.4.2 設(shè)是pi()的一個根，那么 pi-1()pi+1()0，即相鄰的兩個多項式無公共根； pi-1()pi+1()0，即pi-1()與pi+1( )反號. lim( )0,iplim( )0,lim( )0,iipp當i為奇數(shù)當i為偶數(shù)定理9.4.4 pi()的根都是單根，并且將pi+1()的根嚴格隔離. 9.4.3 同號數(shù)和它的應(yīng)用 定義1 設(shè)p0()1，pi()(i=1,2,，n) 是一個Sturm序列，稱相鄰的兩個數(shù)中符號一致的數(shù)目為同號數(shù)，記為ai(). 若某個pi()=0，規(guī)定與pi-1()反號. 定理9.4.5 設(shè)兩個實數(shù)x3n，可以用乘冪法計算2及其相應(yīng)的 特征向量. 在計算1和v后，按(15)式形成n-1階矩陣B的計算過程稱為收縮方法. 9.6 反冪法 反冪法可以求一個非奇異矩陣A的逆矩陣A-1的按模最小的特征值及相應(yīng)的特征向量，又可以求A的一個近似特征值相應(yīng)的特征向量. 9.6.1 求按模最小特征值及相應(yīng)特征向量的反冪