Chapter特征值和乘冪法方法

會計學(xué)1Chapter特征值和乘冪法方法引言/*Introduction*/工程實踐中有多種振動問題，如橋梁或建筑物的振動，機械機件、飛機機翼的振動，工程實踐中有多種振動問題，如橋梁或建筑物的振動，機械機件、飛機機翼的振動，及一些穩(wěn)定性分析和相關(guān)分析可轉(zhuǎn)化為求矩陣特征值與特征向量的問題。第1頁/共40頁G:GoogleMatrix,“theworld’slargestmatrixcomputation”.4,300,000,000x:PageRank（網(wǎng)頁級別）vector“The$25,000,000,000Eigenvector”搜索引擎第2頁/共40頁設(shè)A是n階矩陣,x是非零列向量.如果有數(shù)λ存在,滿足Ax=λx,那么,稱x是矩陣A關(guān)于特征值λ的特征向量.§1特征值與特征向量/*Eigenvalueandeigenvector*/如果把右端寫為λIx，那么又可寫為:

(λI-A)x=0

即|λI-A|=0

記它是關(guān)于參數(shù)λ的n次多項式，稱為矩陣A的特征多項式，其中a0=(-1)n|A|.齊次線性方程組定義1第3頁/共40頁A的特征值也稱為A的特征根.顯然,當λ是A的一個特征值時,它必然是f(λ)=0的根.反之,如果λ是f(λ)=0的根,那么齊次方程組(λI-A)x=0有非零解向量x,使Ax=λx成立.從而，λ是A的一個特征值.矩陣特征值和特征向量有如下主要性質(zhì)：n階矩陣A是降秩矩陣的充分必要條件是A有零特征值.

設(shè)矩陣A與矩陣B相似，那么它們有相同的特征值.

n階矩陣A與AT有相同的特征值.

設(shè)λi≠λj是n階矩陣A的兩個互異特征值，x、

y分別是其相應(yīng)的右特征向量和左特征向量，那么，xTy=0.定理1定理2定理3定理4第4頁/共40頁§2Hermite矩陣特征值問題設(shè)A為n階矩陣，其共軛轉(zhuǎn)置矩陣記為AH.如果A=AH，那么，A稱為Hermite矩陣一、Hermite矩陣的有關(guān)性質(zhì)設(shè)是Hermite矩陣A的n個特征值.有以下性質(zhì):全是實數(shù).有相應(yīng)的n個線性無關(guān)的特征向量，它們可以化為一組標準酉交的特征向量組,即第5頁/共40頁

是酉空間中的一組標準酉交基.記U=(),它是一個酉陣，即UHU=UUH=I，那么即A與以為對角元的對角陣相似A為正定矩陣的充分必要條件是全為正數(shù).第6頁/共40頁設(shè)是Hermite矩陣A的n個特征值，那么因此又由得定理5證明第7頁/共40頁

如果A的n個特征值為其相應(yīng)的標準酉交的特征向量為那么有

設(shè)A是Hermite矩陣，那么設(shè)x是一個非零向量,A是Hermite矩陣,稱為矩陣A關(guān)于向量x的Rayleigh商，記為R(x).或定理6定理7第8頁/共40頁二、極值定理

(極值定理)

設(shè)Hermite矩陣的n個特征值為，其相應(yīng)的標準酉交特征向量為用Ck表示酉空間Cn中任意的k維子空間，那么或定理8第9頁/共40頁矩陣特征值問題的性態(tài)是很復(fù)雜的，通常分別就單個特征值或整體特征值給出條件數(shù)進行分析.對于Hermite矩陣，由于其特征值問題的特殊性質(zhì)，其特征值都是良態(tài)的.下面先證明Hermite矩陣特征值的擾動定理.三、Hermite矩陣特征值問題的性態(tài)矩陣特征值問題與求解線性方程組問題一樣，都存在當矩陣A的原始數(shù)據(jù)有小變化(小擾動)時，引起特征值問題的變化有大有小的問題，如果引起的變化小，稱該特征值問題是良態(tài)的.反之，稱為病態(tài)的.第10頁/共40頁(擾動定理

)

設(shè)矩陣A,E,A+E都是n階Hermite矩陣，其特征值分別為,,,那么,設(shè)矩陣A關(guān)于特征值λ1,λ2,…,λn

的標準酉交特征向量為u1,u2,…,un，是由ui,ui+1,…,un生成的n-i+1維子空間.對中任意非零向量x,由極值定理,有定理9證明第11頁/共40頁由定理又由定理，對任意x≠0，有從而有另一方面,A=(A+E)-E.那么，重復(fù)上面的過程,可得從而有為矩陣-E的特征值記，第12頁/共40頁設(shè)矩陣A和A’=A+E都是n階Hermite矩陣，其特征值分別為和，那么

這個定理表明，擾動矩陣E使A的特征值的變化不會超過‖E‖2.一般‖E‖2小，因此，Hermite矩陣特征值是良態(tài)的.定理10第13頁/共40頁乘冪法是適用于求一般矩陣按模最大特征值及相應(yīng)特征向量的算法.§3乘冪法設(shè)A是n階矩陣,其n個特征值按模從大到小排序為又假設(shè)關(guān)于λ1,λ2,…,λn的特征向量v1,v2,…,vn線性無關(guān)一、乘冪法第14頁/共40頁任意取定初始向量x0建立迭代公式：第15頁/共40頁故當k→∞時，xk→λ1ka1v1.因此，xk可看成是關(guān)于特征值λ1的近似特征向量有一嚴重缺點，當|1|>1（或|1|<1時）{vk}中不為零的分量將隨k的增大而無限增大，計算機就可能出現(xiàn)上溢（或隨k的增大而很快出現(xiàn)下溢）因此，在實際計算時，須按規(guī)范法計算，每步先對向量xk進行“規(guī)范化”。迭代格式改為:因為第16頁/共40頁對任意給定的初始向量x0類似地當1>0時第17頁/共40頁按模最大特征值λ1及其相應(yīng)的特征向量v1的乘冪法的計算公式：當1<0時若λ1為A的實重根,冪法仍然有效.第18頁/共40頁試用冪法求按模最大的特征值和相應(yīng)的特征向量例1第19頁/共40頁通過B求λ1-p的速度快于通過A求λ1的速度二、加速方法冪法計算A的特征值λ1的收斂速度主要由決定有特征值λ1-p,λ2-p,…,λn-p選擇p使λ1-p仍為B的主特征值,且滿足第20頁/共40頁求按模最小特征值及相應(yīng)特征向量的反冪法,又稱為反迭代法.§4反冪法反冪法可以求一個非奇異矩陣A的逆矩陣A-1的按模最小的特征值及相應(yīng)的特征向量，又可以求A的某個近似特征值相應(yīng)的特征向量.若A非奇異,且Ax=λx,則A-1x=λ-1x因此,求A按模最小特征值就是求A-1按模最大特征值第21頁/共40頁一、λi的近似求法若A有特征值λi,λi有近似值:先對矩陣進行LU分解記第22頁/共40頁

“半迭代法”的命名也由此而得.二、半迭代法一種選取特殊的初始向量x0的反冪法選取初始向量x0滿足‖x0‖∞=1，這時z0=x0對照上頁中的第二個式子.可把z0看成滿足Le=z0這里，e=(1,1,…,1)T,而z0的各個分量的取值多少是無關(guān)重要的這樣,在第一個迭代步的計算中,只需求解上頁中的上三角方程組Ux1=e.假設(shè)第23頁/共40頁例2試用反冪法求矩陣A最接近于的特征值和相應(yīng)的特征向量取作半迭代，計算結(jié)果如表第24頁/共40頁由于A是對稱矩陣，做一次Rayleigh商加速與精確值λs=2相比，這次加速有較好效果第25頁/共40頁理論上，實對稱矩陣A正交相似于以A的特征值為對角元的對角陣.問題是如何構(gòu)造這樣的正交矩陣呢?Jacobi方法就是通過構(gòu)造特殊的正交矩陣序列，通過相似變換使A的非對角線元素逐次零化來實現(xiàn)對角化的.§5Jacobi方法第26頁/共40頁一、平面旋轉(zhuǎn)矩陣與相似約化先看一個簡單的例子.設(shè)是二階實對稱矩陣,即a21=a12,其特征值為λ1,λ2.容易驗證BT=B,且令使得第27頁/共40頁當時為使RTAR為對角陣，要求b12=b21=0解之得:當時可選取一般的n階平面旋轉(zhuǎn)矩陣第28頁/共40頁構(gòu)造一個相似矩陣序列，使{Ak}收斂于一個對角陣.其中Qk為平面旋轉(zhuǎn)矩陣，其旋轉(zhuǎn)角θk由使Ak的絕對值最大元a(k)pq=a(k)qp=0或按列依次使A的非對角元零化來確定.二、經(jīng)典的Jacobi方法設(shè)A是實對稱矩陣，記A1=A.Jacobi方法的基本思想是用迭代格式Ak+1=QTkAkQk,k=1,2,…第29頁/共40頁

設(shè)A是n階實對稱矩陣，那么由Jacobi方法產(chǎn)

生的相似矩陣序列{Ak}的非對角元收斂于0.也就

是說，{Ak}收斂于以A的特征值為對角元的對角記其中Ek是Ak除主對角元外的矩陣.由平面旋轉(zhuǎn)矩陣的性質(zhì)中,對于,有因此,定理11第30頁/共40頁又由假設(shè),因此,這樣,便有從而,當?shù)?1頁/共40頁循環(huán)Jacobi方法必須一次又一次掃描,才能使{Ak}收斂于對角陣，計算量很大.在實際計算中，往往用一些特殊方法來控制掃描次數(shù),減少計算量.減少閾值的方法通常是先固定一個正整數(shù)M≥n，掃描一次后，讓.而閾值的下界是根據(jù)實際問題的精度要求選定的.三、實用的Jacobi方法下面介紹一種應(yīng)用最為廣泛的特殊循環(huán)Jacobi方法——閾Jacobi方法.閾Jacobi方法首先確定一個閾值δ，在對非對角元零化的一次掃描中，只對其中絕對值超過閾值的非對角元進行零化.當所有非對角元素的絕對值都不超過閾值后，將閾值減少，再重復(fù)下一輪掃描，直至閾值充分小為止.第32頁/共40頁當Ak+1的非對角元素充分小，Qk的第j列qj可以看成是近似特征值a(k+1)jj相應(yīng)的特征向量了.四、用Jacobi方法計算特征向量假定經(jīng)過k次迭代得到Ak+1=RTk…RT1AR1…Rk，這時Ak+1是滿足精度要求的一個近似的對角陣.記Qk=R1R2…Rk=Qk-1Rk，則，Qk是一個正交矩陣，Ak+1=QTkAQk.在實際計算中，把Qk看成是Qk-1右乘一個平面旋轉(zhuǎn)矩陣得到.不妨記Q0=I，Qk的元素按下式計算：第33頁/共40頁理論上，一個實對稱矩陣正交相似于一個以其特征值為對角元的對角陣.但是，經(jīng)典的結(jié)果告訴我們，一個大于4次的多項式方程不可能用有限次四則運算求根.因此，我們不可能期望只用有限次相似變換將一個實對稱矩陣約化為一個對角陣.下面先介紹將一個實對稱矩陣相似約化為實對稱三對角矩陣的方法，再討論求其特征值的對分法.§6對分法第34頁/共40頁一、相似約化為實對稱三對角矩陣將一個實對稱矩陣正交相似約化為一個實對稱三對角矩陣的算法，可歸納如下：記A(1)=A,對k=1,2,…,n-2第35頁/共40頁二、Sturm序列的性質(zhì)設(shè)實對稱三對角矩陣為其中βi≠0(i=1,2,…,n-1)多項式序列{pi(λ)}(i=0,1,…,n)稱為Sturm序列

記T-λI的第i階主子式為:其特征矩陣為T-λI.定義2令p0(λ)≡1，p1(λ)=α1-λ，pi(λ)=(αi-λ)pi-1(λ)-β2i-1pi-2(λ)，i=2,3,…,n第36頁/共40頁pi(λ)是i階實對稱矩陣的特征多項式，因此,{pi(λ)}(i=1,2,…,n)的根全是實根.設(shè)α是pi(λ)的一個根，那么