特征值和Jacobi方法

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

2、ociates),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, Greenwich (pronounced green-ich) is suppos

3、ed 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 across Westminster, which becomes so

4、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 university. On the very first day that the bri

5、dge 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 opening ceremony ended up in an embarrassi

6、ng 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 writing about this wobbly bridge? Next

7、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!,G: Google Matrix, “the worlds largest matrix computation”. 4,300,000,000 x: PageRank（網(wǎng)頁級別） vector “The $25,000,000,000 Eigenvector”,搜索引擎,9.1

8、特征值與特征向量,設(shè)A是n階矩陣，x是非零列向量. 如果有數(shù)存在，滿足 ， (1) 那么，稱x是矩陣A關(guān)于特征值的特征向量.,如果把(1)式右端寫為 ，那么(1)式又可寫為:,記,它是關(guān)于參數(shù)的n次多項式，稱為矩陣A的特征多項式， 其中a0=(-1)nA.,(2),顯然，當(dāng)是A的一個特征值時，它必然是 的根. 反之，如果是 的根，那么齊次方程組(2)有非零解向量x，使(1)式成立. 從而，是A的一個特征值. A的特征值也稱為A的特征根.,矩陣特征值和特征向量有如下主要性質(zhì)：,定理9.1.1 n階矩陣A是降秩矩陣的充分必要條件是A有零特征值.,定理9.1.2 設(shè)矩陣A與矩陣B相似，那么它們 有相

9、同的特征值.,定理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ì):,全是實數(shù).,有相應(yīng)的n個線性無關(guān)的特征向量，它們可以化為一組標(biāo)準(zhǔn)酉交的特征向量組 ,即,是酉空間中的一組標(biāo)準(zhǔn)酉交基.,記U=( ),它是一個酉陣，即UHU=UUH=I，那么 即A與以 為對角元的

10、對角陣相似.,A為正定矩陣的充分必要條件是 全為正數(shù).,定理9.2.1 設(shè) 是Hermite矩陣A的n個特征值，那么,證:,設(shè)x是一個非零向量，A是Hermite矩陣，稱 為矩陣A關(guān)于向量x的Rayleigh商，記為R(x).,定理9.2.2 如果A的n個特征值為 其相應(yīng)的標(biāo)準(zhǔn)酉交的特征向量為 那么有,定理9.2.3 設(shè)A是Hermite矩陣 ，那么,9.2.2 極值定理,定理9.2.4(極值定理) 設(shè)Hermite矩陣的n個特征值為 ，其相應(yīng)的標(biāo)準(zhǔn)酉交特征向量為 . 用Ck表示酉空間Cn中任意的k維子空間，那么,9.2.3 Hermite矩陣特征值問題的性態(tài),矩陣特征值問題與求解線性方程組問

11、題一樣，都存在當(dāng)矩陣A的原始 數(shù)據(jù)有小變化(小擾動)時，引起特征值問題的變化有大有小的問題，如果引起的變化小，稱 該特征值問題是良態(tài)的. 反之，稱為病態(tài)的. 矩陣特征值問題的性態(tài)是很復(fù)雜的，通常分別就單個特征值或整體特征值給出條件數(shù)進行分 析. 對于Hermite矩陣，由于其特征值問題的特殊性質(zhì)，其特征值都是良態(tài)的.下面先證明Hermite矩陣特征值的擾動定理.,定理9.2.5 設(shè)矩陣A，E，A+E都是n階Hermite矩陣，其特征值分別為 那么,證 設(shè)矩陣A關(guān)于特征值1，2，n 的標(biāo)準(zhǔn)酉交特征向量為u1，u2，un， 是由ui，ui+1，un生成的n-i+1維子空間. 對 中任意非零向量x,

12、由極值定理,有,由定理9.2.3， 又由定理9.2.2，對任意x0，有 從而有 另一方面, A=(A+E)-E. 記 為矩陣-E的特征值，那么， 重復(fù)上面的過程,可得 從而有,定理9.2.5通常又稱為Hermite矩陣特征值的擾動定理,定理9.2.6 設(shè)矩陣A和A=A+E都是n階Hermite矩 陣，其特征值分別為 和 ，那么,這個定理表明，擾動矩陣E使A的特征值的變化 不會超過 E2. 一般E2小，因此， Hermite矩陣特征值是良態(tài)的.,9.3 Jacobi方法,理論上，實對稱矩陣A正交相似于以A的特征值為對角元 的 對角陣. 問題是如何構(gòu)造這樣的正交矩陣呢? Jacobi方法就是通過構(gòu)

13、造特殊的正交矩陣 序列，通過相似變換使A的非對角線元素逐次零化來實現(xiàn)對角化的.,9.3.1 平面旋轉(zhuǎn)矩陣與相似約化 先看一個簡單的例子.,設(shè) 是二階實對稱矩陣，即a21=a12，其特征值為1，2. 令 使得 記 容易驗證BT=B, 且,解之得: 當(dāng) 時 當(dāng) 時可選取,為使RTAR為對角陣，要求b12=b21=0,一般的n階平面旋轉(zhuǎn)矩陣,9.3.2 經(jīng)典的Jacobi方法,設(shè)A是實對稱矩陣，記A1=A.Jacobi方法的基本思想是用迭代格式 Ak+1=QTkAkQk , k=1,2, 構(gòu)造一個相似矩陣序列，使Ak收斂于一個對角陣. 其中 Qk為平面旋轉(zhuǎn)矩陣，其旋轉(zhuǎn)角k由使Ak的絕對值 最大元a(

14、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ì) 中,對于 ,有 因此,又由假設(shè), 因此, 這樣,便有 從而,當(dāng),9.3.3 實用的Jacobi方法,循環(huán)Jacobi方法必須一次又一次掃描，才能使Ak收斂于對角陣 ，計算量很大. 在實際計算中，往往用一些特殊方法來控制掃描次數(shù)，減少計算量. 下面介 紹一種應(yīng)用最為廣泛的特殊循環(huán)Jacobi方法閾Jacobi方法.

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

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

17、矩陣,將一個實對稱矩陣正交相似約化為一個實對稱三對角矩陣的算法，可歸納如下： 記A(1)=A,對k=1,2,n-2 按(4)式、(5)式和(8)式計算 ； 按(9)(12)式，計算A(k+1).,9.4.2 Sturm序列的性質(zhì),設(shè)實對稱三對角矩陣為 其中i0 (i=1,2,，n-1) 其特征矩陣為T-I. 記T-I的第i階主子式為,這是關(guān)于的i次多項式，當(dāng)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序列,定理9.4.1

18、pi() (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( )反號.,定理9.4.4 pi()的根都是單根，并且將pi+1()的根嚴(yán)格隔離.,9.4.3 同號數(shù)和它的應(yīng)用,定義1 設(shè)p0()1，pi()(i=1,2,，n) 是一個Sturm序列，稱相鄰的兩個數(shù)中符號一致的數(shù)目為同號數(shù)，記為ai(). 若某個pi()=0，規(guī)定與p

19、i-1()反號. 定理9.4.5 設(shè)兩個實數(shù)xy，那么，形如(13)式的實對稱 三對角矩陣T的特征多項式在區(qū)間(x,y上根的數(shù)目為a(x)-a(y).,9.4.4 求Hermite矩陣特征值的對分法,對分法的計算可歸納為以下4個部分 確定(13)式的矩陣T的全部特征值的分布區(qū)間. 在區(qū)間a,b中，用區(qū)間對分的方法找出只含T的一個特征值的子區(qū)間. 在只含一個特征值的子區(qū)間上的對分法. 同號數(shù)的計算.,9.5 乘冪法,設(shè)A是n階矩陣，其n個特征值按模從大到小排序為 又假設(shè)關(guān)于1，2，n的特征向量v1，v2，vn線性無關(guān).,乘冪法是適用于求一般矩陣按模最大特征值及 相應(yīng)特征向量的算法.,xkk1a1

20、v1 (k). 因此，xk可看成是關(guān)于特征值1的近似特征向量.,迭代格式為,按模最大特征值1及其相應(yīng)的特征向量v1的乘冪法的計算公式：,9.5.2 收縮方法,設(shè)矩陣A的n個特征值按模從大到小排序為 ，其相應(yīng)的n個線性無關(guān)特征向量為v1，v 2，vn. 在計算A的最大特征值1及相應(yīng)特征向量v1后，可以通過收縮方法，繼續(xù)用乘冪法計算2及其相應(yīng)的特征向量v2.,定義n階矩陣 把去掉A1的第1行和第1列的n-1階矩陣記為,那么，B有與A1除1外的相同的n-1個特征值 23n，可以用乘冪法計算2及其相應(yīng)的 特征向量. 在計算1和v后，按(15)式形成n-1階矩陣B的計算過程稱為收縮方法.,9.6 反冪法,反冪法可以求一個非奇異矩陣A的逆矩陣A-1的按模最小的特征值及相應(yīng)的特征向量，又可以求A的一個近似特征值相應(yīng)的特征向量. 9.6.1 求按模最小特征值及相應(yīng)特征