數(shù)值分析第四章矩陣特征值與特征向量的計算.ppt

1,第四章 特征值與特征向量的計算, 冪法和反冪法,2,冪法 用于計算矩陣按模最大的特征值及其相應(yīng)的特征向量, 特別適用于大型稀疏矩陣.,1 冪法和反冪法,反冪法 用于計算矩陣按模最小的特征值及其特征向量, 也可用來計算對應(yīng)于一個給定近似特征值的特征向量.,3,設(shè)A為n階實矩陣, 其特征值為1, 2, , n, 相應(yīng)的特征向量為u1, u2, , un. 且滿足條件,u1, u2, , un線性無關(guān)., 冪法, 冪法: 求1及其相應(yīng)的特征向量.,此時1一定是實數(shù)!, 1通常稱為主特征值.,4, 冪法基本思想, 給定初始非零向量x(0), 由矩陣A構(gòu)造一向量序列, 在一定條件下, 當(dāng)k充分大時:, 相應(yīng)的特征向量為:,5,設(shè)t1不為零., x(k+1)為1的特征向量的近似向量(除一個因子外).,對任意向量x(0), 有, 冪法的理論依據(jù),故,6, 如果x(0)的選取恰恰使得t1=0, 冪法仍能進(jìn)行. 因為計算過程中會有舍入誤差, 迭代若干次后, 必然會產(chǎn)生一個向量x(k), 它在u1方向上的分量不為零, 這樣以后的計算就滿足所設(shè)條件., 因為 計算過程中可能會出現(xiàn)上溢(|1|1)或下溢成為0 (|1|1). 為避免出現(xiàn)這一情形, 實際計算時每次迭代所求的向量都要歸一化.,7, 歸一化過程,設(shè)有一向量x0, 將其歸一化得到向量,其中max(x)表示向量x的絕對值最大的分量, 即如果有,例 x=(1, 8, 7)T,則 max(x)=8 ,歸一化向量為,8, 冪法的計算公式, 任取初始向量x(0)=y(0)0, 對k=1, 2, , 構(gòu)造向量序列 x(k), y(k), 當(dāng)k充分大時,9,定理 設(shè)n階實矩陣A有n個線性無關(guān)的特征向量u1, u2, , un, 主特征值1滿足| 1 | |2 | |3 | | n |, 則對任取非零初始向量x(0)=y(0)0 (t10), 按下述方法構(gòu)造向量序列 x(k), y(k),則有,10, 冪法特別適用于求大型稀疏矩陣的主特征值和相應(yīng)的特征向量., 若A的主特征值1為實的m重根, 即1= 2= m, 且 | 1 | |m+1 | |m+2 | | n |, 又設(shè)A有n個線性無關(guān)的特征向量, 此時冪法仍然適用., 冪法的收斂速度取決于比值 即 比值越接近1, 收斂速度越慢, 比值越接近0, 收斂越快.,11,例 用冪法求矩陣,的按模最大的特征值和相應(yīng)的特征向量.,取 x(0)=(0, 0, 1)T, 要求誤差不超過103.,解,12,13, 應(yīng)用冪法計算矩陣A的主特征值的收斂速度主要由比值 r=|2/1|來決定, 但當(dāng)r接近于1時, 收斂可能很慢. 這時可以采用加速收斂的方法., 冪法的加速原點移位法,引進(jìn)矩陣 B=A0I 其中0為代選擇參數(shù). 設(shè)A的特征值為1, 2, , n, 則B的特征值為10, 20, , n0, 而且A, B的特征向量相同.,14, 仍設(shè)A有主特征值1, 且,取0使得,且, 用冪法求矩陣B=A0I的按模最大的特征值1*, 則1= 1*+0.,10是B=A0I的主特征值,對B應(yīng)用冪法比對A應(yīng)用冪法收斂速度快,原點移位法,15,例,矩陣A的特征值為,直接應(yīng)用冪法求矩陣A的主特征值其收斂速度為,用原點移位法求主特征值, 取0=2.9, 此時收斂速度為,16, 原點移位法使用簡便, 不足之處在于0的選取十分困難, 通常需要對特征值的分布有一大概的了解, 才能粗略地估計0, 并通過計算不斷進(jìn)行修改.,17,若 ak 線性收斂于a, 即,當(dāng) k 充分大時，有, 冪法的加速Aitken加速法,18,可以證明, 用 逼近a, 這就是Aitken加速法.,把上式右端記為,即 比 快., 將Aitken方法用于冪法產(chǎn)生的序列k, 可加快冪法的收斂速度.,19,例 用Aitken加速法求矩陣,的按模最大的特征值和相應(yīng)的特征向量, 取 x(0)=(0, 0, 1)T.,解,20,反冪法 用于計算矩陣按模最小的特征值及其特征向量, 也可用來計算對應(yīng)于一個給定近似特征值的特征向量, 是目前求特征向量最有效的方法., 反冪法,21,設(shè)A為n階實可逆矩陣，其特征值滿足,對應(yīng)的特征向量分別 u1, u2, , un, 則A1的特征值滿足,對應(yīng)的特征向量分別 un, un-1, , u2, u1., 反冪法：計算n以及相應(yīng)的特征向量., 反冪法,22, 對于A1應(yīng)用冪法迭代，可求得矩陣A1的主特征值1/ n, 從而求得A的按模最小的特征值n., 反冪法基本思想,23, 反冪法迭代公式為, 任取初始向量x(0)=y(0)0, 構(gòu)造向量序列, 迭代向量x(k+1)可以通過解方程組求得, 當(dāng)k充分大時,24,定理 設(shè)A為非奇異矩陣且有n個線性無關(guān)的特征向量，其對應(yīng)的特征值滿足,則對任何初始非零向量x(0) (tn0), 由反冪法構(gòu)造的向量序列x(k), y(k)滿足, 收斂速度比值為,25, 在反冪法中也可用原點移位法來加速迭代過程或求其他特征值及特征向量., 設(shè)已知A的一個特征值 的近似值 *, 因為* 接近, 一般應(yīng)有 0| * | i* | (i ) 故*是矩陣A*I的按模最小的特征值，比值 |(* )/(i* )|較小. 因此對A*I用反冪法 求*一般收斂很快，通常只要迭代二、三次就能達(dá)到較高的精度., 帶原點移位的反冪法,26, 原點移位反冪法,任取初始向量x(0)=y(0)0,迭代向量x(k+1)可以通過解方程組求得,27,為了節(jié)省計算量，可以先對A*I 作三角分解,已知 y(k) 求 x(k+1) 可通過下列方式進(jìn)行,28, 原點移位反冪法計算公式,任取初始向量x(0)=y(0)0, 先對A*I作三角分解,已知y(k