特征值和Jacobi方法

1、第9章 矩陣特征值問題的數(shù)值方法,9.1 特征值與特征向量 9.2 Hermite矩陣特征值問題 9.3 Jacobi方法 9.4 對(duì)分法 9.5 乘冪法 9.6 反冪法 9.7 QR方法,引言,工程實(shí)踐中有多種振動(dòng)問題，如橋梁或建筑物的振動(dòng)，機(jī)械機(jī)件、飛機(jī)機(jī)翼的振動(dòng)，工程實(shí)踐中有多種振動(dòng)問題，如橋梁或建筑物的振動(dòng)，機(jī)械機(jī)件、飛機(jī)機(jī)翼的振動(dòng)，及一些穩(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)頁(yè)級(jí)別） 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次多項(xiàng)式，稱為矩陣A的特征多項(xiàng)式， 其中a0=(-1)nA.,(2),顯然，當(dāng)是A的一個(gè)特征值時(shí)，它必然是 的根. 反之，如果是 的根，那么齊次方程組(2)有非零解向量x，使(1)式成立. 從而，是A的一個(gè)特征值. 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的兩個(gè)互異特征值，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個(gè)特征值.有以下性質(zhì):,全是實(shí)數(shù).,有相應(yīng)的n個(gè)線性無關(guān)的特征向量，它們可以化為一組標(biāo)準(zhǔn)酉交的特征向量組 ,即,是酉空間中的一組標(biāo)準(zhǔn)酉交基.,記U=( ),它是一個(gè)酉陣，即UHU=UUH=I，那么 即A與以 為對(duì)角元的

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

11、題一樣，都存在當(dāng)矩陣A的原始 數(shù)據(jù)有小變化(小擾動(dòng))時(shí)，引起特征值問題的變化有大有小的問題，如果引起的變化小，稱 該特征值問題是良態(tài)的. 反之，稱為病態(tài)的. 矩陣特征值問題的性態(tài)是很復(fù)雜的，通常分別就單個(gè)特征值或整體特征值給出條件數(shù)進(jìn)行分 析. 對(duì)于Hermite矩陣，由于其特征值問題的特殊性質(zhì)，其特征值都是良態(tài)的.下面先證明Hermite矩陣特征值的擾動(dòng)定理.,定理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維子空間. 對(duì) 中任意非零向量x,

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

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

14、k)pq=a(k)qp=0 或按列依次使A的非對(duì)角元 零化來確定.,定理9.3.1 設(shè)A是n階實(shí)對(duì)稱矩陣，那么由Jacobi方法產(chǎn)生的相似矩陣序列Ak的非對(duì)角元收斂于0. 也就是說，Ak收斂于以A的特征值為對(duì)角元的對(duì)角陣.,記 其中Ek是Ak除主對(duì)角元外的矩陣.由平面旋轉(zhuǎn)矩陣的性質(zhì) 中,對(duì)于 ,有 因此,又由假設(shè), 因此, 這樣,便有 從而,當(dāng),9.3.3 實(shí)用的Jacobi方法,循環(huán)Jacobi方法必須一次又一次掃描，才能使Ak收斂于對(duì)角陣 ，計(jì)算量很大. 在實(shí)際計(jì)算中，往往用一些特殊方法來控制掃描次數(shù)，減少計(jì)算量. 下面介 紹一種應(yīng)用最為廣泛的特殊循環(huán)Jacobi方法閾Jacobi方法.

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

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

17、矩陣,將一個(gè)實(shí)對(duì)稱矩陣正交相似約化為一個(gè)實(shí)對(duì)稱三對(duì)角矩陣的算法，可歸納如下： 記A(1)=A,對(duì)k=1,2,n-2 按(4)式、(5)式和(8)式計(jì)算 ； 按(9)(12)式，計(jì)算A(k+1).,9.4.2 Sturm序列的性質(zhì),設(shè)實(shí)對(duì)稱三對(duì)角矩陣為 其中i0 (i=1,2,，n-1) 其特征矩陣為T-I. 記T-I的第i階主子式為,這是關(guān)于的i次多項(xiàng)式，當(dāng)i=n時(shí)， pn()=T-I是矩陣T的特征多項(xiàng)式. 令p0()1，則有p1()=1-，pi()=(i-)pi-1()-2i-1pi-2()，i=2,3，n.(15) 多項(xiàng)式序列pi() (i=0,1,，n)稱為Sturm序列,定理9.4.1

18、pi() (i=1,2,，n)的根都是 實(shí)根. 證 由(14)式，pi()是i階實(shí)對(duì)稱矩陣的特征多項(xiàng)式，因此，pi() (i=1,2,，n)的根全是實(shí)根.,定理9.4.2 定理9.4.2 設(shè)是pi()的一個(gè)根，那么 pi-1()pi+1()0，即相鄰的兩個(gè)多項(xiàng)式無公共根； pi-1()pi+1()0，即pi-1()與pi+1( )反號(hào).,定理9.4.4 pi()的根都是單根，并且將pi+1()的根嚴(yán)格隔離.,9.4.3 同號(hào)數(shù)和它的應(yīng)用,定義1 設(shè)p0()1，pi()(i=1,2,，n) 是一個(gè)Sturm序列，稱相鄰的兩個(gè)數(shù)中符號(hào)一致的數(shù)目為同號(hào)數(shù)，記為ai(). 若某個(gè)pi()=0，規(guī)定與p

19、i-1()反號(hào). 定理9.4.5 設(shè)兩個(gè)實(shí)數(shù)xy，那么，形如(13)式的實(shí)對(duì)稱 三對(duì)角矩陣T的特征多項(xiàng)式在區(qū)間(x,y上根的數(shù)目為a(x)-a(y).,9.4.4 求Hermite矩陣特征值的對(duì)分法,對(duì)分法的計(jì)算可歸納為以下4個(gè)部分 確定(13)式的矩陣T的全部特征值的分布區(qū)間. 在區(qū)間a,b中，用區(qū)間對(duì)分的方法找出只含T的一個(gè)特征值的子區(qū)間. 在只含一個(gè)特征值的子區(qū)間上的對(duì)分法. 同號(hào)數(shù)的計(jì)算.,9.5 乘冪法,設(shè)A是n階矩陣，其n個(gè)特征值按模從大到小排序?yà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的乘冪法的計(jì)算公式：,9.5.2 收縮方法,設(shè)矩陣A的n個(gè)特征值按模從大到小排序?yàn)?，其相應(yīng)的n個(gè)線性無關(guān)特征向量為v1，v 2，vn. 在計(jì)算A的最大特征值1及相應(yīng)特征向量v1后，可以通過收縮方法，繼續(xù)用乘冪法計(jì)算2及其相應(yīng)的特征向量v2.,定義n階矩陣 把去掉A1的第1行和第1列的n-1階矩陣記為,那么，B有與A1除1外的相同的n-1個(gè)特征值 23n，可以用乘冪法計(jì)算2及其相應(yīng)的 特征向量. 在計(jì)算1和v后，按(15)式形成n-1階矩陣B的計(jì)算過程稱為收縮方法.,9.6 反冪法,反冪法可以求一個(gè)非奇異矩陣A的逆矩陣A-1的按模最小的特征值及相應(yīng)的特征向量，又可以求A的一個(gè)近似特征值相應(yīng)的特征向量. 9.6.1 求按模最小特征值及相應(yīng)特征