1、第9章 矩陣特征值問題的數(shù)值方法 9.1 特征值與特征向量9.1 特征值與特征向量 設(shè)A是n階矩陣，x是非零列向量. 如果有數(shù)存在，滿足 ， (1)那么，稱x是矩陣A關(guān)于特征值的特征向量. Axx如果把(1)式右端寫為 ，那么(1)式又可寫為:x()0IA x| 0IA即1110( ) |.nnnfIAaaa記它是關(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的特征根. ( )0f( )0f矩陣特

2、征值和特征向量有如下主要性質(zhì)： 定理階矩陣A是降秩矩陣的充分必要 條件是A有零特征值. 定理設(shè)矩陣A與矩陣B相似，那么它們 有相同的特征值. 定理階矩陣A與AT有相同的特征值. 定理設(shè)ij是n階矩陣A的兩個(gè)互異特 征值，x、y分別是其相應(yīng)的右特征向 量和左特征向量，那么，xTy=0 . 9.2 Hermite矩陣特征值問題 設(shè)A為n階矩陣，其共軛轉(zhuǎn)置矩陣記為AH. 如果A=AH，那么，A稱為Hermite矩陣.Hermite矩陣的有關(guān)性質(zhì) 設(shè) 是Hermite矩陣A的n個(gè)特征值. 有以下性質(zhì): 全是實(shí)數(shù).12,.,n12,.,n 有相應(yīng)的n個(gè)線性無關(guān)的特征向量，它們可以化為一組標(biāo)準(zhǔn)酉交的特征向

3、量組 ,即 12,.,n 12,.,nu uuHiju uij 是酉空間中的一組標(biāo)準(zhǔn)酉交基. 12,.,nu uu 記U=( ),它是一個(gè)酉陣，即UHU=UUH=I，那么即A與以 為對(duì)角元的對(duì)角陣相似.12,.,nu uu1HnUAUD12,.,n A為正定矩陣的充分必要條件是 全為正數(shù). 12,.,n定理設(shè) 是Hermite矩陣A的n個(gè)特征值，那么證:12,.,n21maxiinA 21niFiA2222()()( ( )HAA AAA由21maxiinA 因此2221()()nHiFiAtr A Atr A又由21niFiA得 設(shè)x是一個(gè)非零向量，A是Hermite矩陣，稱 為矩陣A關(guān)于向

4、量x的Rayleigh商，記為R(x). HHxAxxx定理如果A的n個(gè)特征值為 其相應(yīng)的標(biāo)準(zhǔn)酉交的特征向量為 那么有 12.n12,.,nu uu1( )nR x定理設(shè)A是Hermite矩陣 ，那么100min( )min( )kn kkkx Cxx CxR xR x 且且或極值定理 定理極值定理) 設(shè)Hermite矩陣的n個(gè)特征值為 ，其相應(yīng)的標(biāo)準(zhǔn)酉交特征向量為 . 用Ck表示酉空間Cn中任意的k維子空間，那么12.n12,.,nu uu1100max min( )maxmin( )kkn kn kkCx CxkCx CxR xR x 且且或Hermite矩陣特征值問題的性態(tài) 矩陣特征值問

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

6、向量x,由極值定理,有12n12n12n1inii1n iC 1n iC 111000()maxmaxmaxn in in iHiHx CxHHHHx Cxx CxxAE xx xx Axx Exx xx x 且且且由定理，又由定理，對(duì)任意x0，有從而有另一方面, A=(A+E)-E. 記 為矩陣-E的特征值，那么，重復(fù)上面的過程,可得從而有10maxn iHiHx Cxx Axx x 且110maxn iHnHx CxxExxx 且1ii12n1in i 1iiiin定理通常又稱為Hermite矩陣特征值的擾動(dòng)定理 定理設(shè)矩陣A和A=A+E都是n階Hermite矩 陣，其特征值分別為 和 ，

7、那么 這個(gè)定理表明，擾動(dòng)矩陣E使A的特征值的變化不會(huì)超過 E2. 一般E2小，因此，Hermite矩陣特征值是良態(tài)的. 12n12n222iiEE9.3 Jacobi方法理論上，實(shí)對(duì)稱矩陣A正交相似于以A的特征值為對(duì)角元 的 對(duì)角陣. 問題是如何構(gòu)造這樣的正交矩陣呢? Jacobi方法就是通過構(gòu)造特殊的正交矩陣 序列，通過相似變換使A的非對(duì)角線元素逐次零化來實(shí)現(xiàn)對(duì)角化的. 平面旋轉(zhuǎn)矩陣與相似約化先看一個(gè)簡(jiǎn)單的例子. 設(shè) 是二階實(shí)對(duì)稱矩陣，即a21=a12，其特征值為1，2. 令 使得 記 容易驗(yàn)證BT=B, 且11122122aaAaacossinsincosR11TR AR11122122T

8、bbBR ARbb22111112222212212211122222111222cos2sincossin()sincos(cossin)sin2sincoscosbaaabbaaabaaa解之得:當(dāng) 時(shí)當(dāng) 時(shí) 并規(guī)定1122aa12112221arctan2aaa1122aa21arctan2pqppqqaaa4經(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(k)pq=a(k)qp=0 或按

9、列依次使A的非對(duì)角元 零化來確定. 定理設(shè)A是n階實(shí)對(duì)稱矩陣，那么由Jacobi方法產(chǎn)生的相似矩陣序列Ak的非對(duì)角元收斂于0. 也就是說，Ak收斂于以A的特征值為對(duì)角元的對(duì)角陣. 記 其中Ek是Ak除主對(duì)角元外的矩陣.由平面旋轉(zhuǎn)矩陣的性質(zhì) 中,對(duì)于 ,有因此,( )()kkiikAdiag aE1TkpqkpqAR A R,ip q(1)2(1)2( )2( )2()()()()kkkkipiqipiqaaaa22( )212()kkkpqFFEEa又由假設(shè),因此,這樣,便有從而,當(dāng)22( )( )( )( )1,1max(1)nkkkkpqijpqpqi j niji jijaaan na且

10、且且22( )(1)kkpqFEn na222112222(1)(1)kkkFFFEEEnnnn1,0kFkE 實(shí)用的Jacobi方法 循環(huán)Jacobi方法必須一次又一次掃描，才能使Ak收斂于對(duì)角陣 ，計(jì)算量很大. 在實(shí)際計(jì)算中，往往用一些特殊方法來控制掃描次數(shù)，減少計(jì)算量. 下面介 紹一種應(yīng)用最為廣泛的特殊循環(huán)Jacobi方法閾Jacobi方法. 閾Jacobi方法首先確定一個(gè)閾值，在對(duì)非對(duì)角元零化的一次掃描中，只對(duì)其中絕對(duì)值 超過閾值的非對(duì)角元進(jìn)行零化. 當(dāng)所有非對(duì)角元素的絕對(duì)值都不超過閾值后，將閾值減少， 再重復(fù)下一輪掃描，直至閾值充分小為止. 減少閾值的方法通常是先固定一個(gè)正整數(shù)Mn，

11、掃描一次后，讓 . 而閾值的下界是根據(jù)實(shí)際問題的精度要求選定的. M用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+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ì)算：( )(1)(1)(

12、)(1)(1)( )(1)cossin,sincos, ,1,2,kkkipipkipkkkkiqipkiqkkkijijqqqqqqqqjp qin 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ì) 分法. 相似約化為實(shí)對(duì)稱三對(duì)角矩陣 將一個(gè)實(shí)對(duì)稱矩陣正交相似約化為一個(gè)實(shí)對(duì)稱三對(duì)角矩陣的算法，可歸納如下： 記A(1)=A,對(duì)k

13、=1,2,n-2 按(4)式、(5)式和(8)式計(jì)算 ； 按(9)(12)式，計(jì)算A(k+1). ,kkku和( )1,( )2,( )(4)kkkkkkkkknkaaua ( )( )21,1()() (5)nkkkkkiki ksignaa ( )1,()(8)kkkkkka1( )1(1)( ),(9),(10)1,(11)2(),(12)kkkkTkkkkkkkkkkTTkkkkgA uu gyguAAu yy u序列的性質(zhì) 設(shè)實(shí)對(duì)稱三對(duì)角矩陣為 其中i0 (i=1,2,，n-1) 其特征矩陣為T-I. 記T-I的第i階主子式為 111221nnaTaa111211( )iiiiaap

14、a 這是關(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序列 111211( )iiiiaapa定理pi() (i=1,2,，n)的根都是 實(shí)根. 證 由(14)式，pi()是i階實(shí)對(duì)稱矩陣的特征多項(xiàng)式，因此，pi() (i=1,2,，n)的根全是實(shí)根. 定理定理設(shè)是pi()的一個(gè)根，那么 pi-1()pi+1()0，即相鄰的兩個(gè)多項(xiàng)式無公共根； pi-1()pi+1()0，即pi-1()與pi+1( )

15、反號(hào). lim( )0,iplim( )0,lim( )0,iipp當(dāng)i為奇數(shù)當(dāng)i為偶數(shù)定理pi()的根都是單根，并且將pi+1()的根嚴(yán)格隔離. 同號(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ī)定與pi-1()反號(hào). 定理設(shè)兩個(gè)實(shí)數(shù)x3n，可以用乘冪法計(jì)算2及其相應(yīng)的 特征向量. 在計(jì)算1和v后，按(15)式形成n-1階矩陣B的計(jì)算過程稱為收縮方法. 9.6 反冪法 反冪法可以求一個(gè)非奇異矩陣A的逆矩陣A-1的按模最小的特征值及相應(yīng)的特征向量，又可以求A的一個(gè)近似特征值相

16、應(yīng)的特征向量. 求按模最小特征值及相應(yīng)特征向量的反冪法,又稱為反迭代法.1(1)1,0,1,kkkkkTkkkTkkxzxLUxzz xkz z求近似特征值的特征向量的反冪法 先對(duì)矩陣 進(jìn)行LU分解，記 那么， (7) 下面介紹一種選取特殊的初始向量x0的反冪法半迭代法. lIAlIALU1,0,1,kkkkkkkxzxLyzUxy k 假設(shè) ,選取初始向量x0滿足x0=1，這時(shí)z0=x0.對(duì)照(7)式中的第二個(gè)式子.可把z0看成滿足Le=z0.(8) 這里，e=(1,1，1)T，而z0的各個(gè)分量的取值多少是無關(guān)重要的.這樣，在第一個(gè)迭代步的計(jì)算中，只需求解(7)式中的上三角方程組Ux1=e.

17、 “半迭代法”的命名也由此而得.lIA9.7 QR方法 定理設(shè)A是n階矩陣，其n個(gè) 特征值為 .那么存在一個(gè)酉矩陣U，使UAU是以為 對(duì)角元的上三角矩陣. 12,n 12,n 兩個(gè)基本定理定理設(shè)A是n階實(shí)矩 陣，那么，存在一個(gè)正交矩陣Q，使QAQ為一個(gè)準(zhǔn)上三角矩陣，它的對(duì)角元是A的一個(gè)特征值，對(duì)角元上的二階塊矩陣的兩個(gè)特征值是A的一對(duì)共軛復(fù)特征值. 相似約化為上Hessenberg矩陣 對(duì)一般n階矩陣，QR算法的每一個(gè)迭代步需要O(n)次乘法運(yùn)算.如果矩 陣階數(shù)稍大，這個(gè)算法幾乎沒有實(shí)際的應(yīng)用價(jià)值.通常采用的方法是先將矩陣相似約化為上Hessenberg形式的矩陣，在此基礎(chǔ)上應(yīng)用QR迭代.這時(shí)

18、，一個(gè)QR迭代步的乘法運(yùn)算次數(shù)只需O(n）次. 所謂上Hessenberg矩陣是指一個(gè)n階矩陣A，如果當(dāng)ij+1時(shí)，aij=0，稱A為上Hessenberg矩陣.例如：一個(gè)5階的上Hessenberg矩陣具有如下的形式： *0*00*000*A下面介紹QR方法時(shí)，都假設(shè)矩陣A是一個(gè)上Hessenberg矩陣. 算法 設(shè)A是n階矩陣且有QR分解AQR，(2) 這里，Q是酉矩陣，R是上三角矩陣.如果A是滿秩并規(guī)定R有正對(duì)角元，這個(gè)分解是惟一的. 一、QR算法的基本思想 記AA且有AQ 1R1.將等號(hào)右邊兩個(gè)矩陣因子的次序交換，得ARQ，且 ，(3) 即AA.不難證明:即Ak+1AkA，矩陣序列Ak

19、有相同的特征值. 記12111AQ AQ111111kkkkkkkAQ A QQQ A QQ12kkQQQQ12kkRR RR容易得到 是Ak的一個(gè)QR分解kkkAQ R 如果A是一個(gè)滿秩的上Hessenberg矩陣，可以證明，經(jīng)過一個(gè)QR迭代步得到的A2QA1Q仍然是上Hessenberg矩陣. 因?yàn)樯螲essenberg矩陣次對(duì)角線以下的元素全為0，因此，只要證明，當(dāng)k時(shí)，由迭 代格式(4)產(chǎn)生的矩陣Ak的次對(duì)角元趨向于零就可以了. 二、 QR算法的收斂性 定理設(shè)n階矩陣A的n個(gè)特征值滿足|n|0，其相應(yīng)的n個(gè)線性無關(guān)特征向量為x1，x2，xn. 記X(x1,x2,xn), Y= X.如果Y存在LU分解，那么，由(4) 式產(chǎn)生的矩陣Ak基本收斂于上三角矩陣R.這里，基本收斂的含義指Ak的元素中除對(duì)角線以下的元素趨于零外，可以不收斂于R的元素. 三、 QR算