計(jì)算方法6-矩陣特征值和特征向量

矩陣特征值和特征向量EigenvaluesandEigenvectors整理課件問題的提出矩陣特征值計(jì)算非常重要，在很多方面應(yīng)用數(shù)值分析中，和矩陣有關(guān)的迭代序列的收斂取決于迭代矩陣的特征值大小動(dòng)態(tài)系統(tǒng)中，特征值標(biāo)志著系統(tǒng)是否是穩(wěn)定的振動(dòng)系統(tǒng)中，微分方程的特征值或者有限元模型的矩陣系數(shù)和系統(tǒng)的固有頻率直接相關(guān)數(shù)學(xué)中方陣的對(duì)角化、微分方程組的解等等整理課件6.1基本概念回顧DEF6.1設(shè)A是n階方陣，如果數(shù)λ和一維非零向量χ使關(guān)系式Aχ=λχ成立，則稱數(shù)λ為方陣A的特征值，非零向量χ稱為A的屬于特征值λ的特征向量.推論：如果χ是矩陣A的屬于特征值λ0的特征向量，那么χ的任何一個(gè)非零倍數(shù)kχ也是A的屬于λ的特征向量。這是因?yàn)锳χ=λ0χ所以A(kχ)=λ0(kχ)，這說明屬于同一個(gè)特征值的特征向量不是唯一的，但一個(gè)特征向量只能屬于一個(gè)特征值。整理課件可以寫成齊次線性方程組方程組有解即上式是以為未知量的一元n次方程，稱為方陣A的特征方程，是的n次多項(xiàng)式，記為稱為方陣A的特征多項(xiàng)式。整理課件顯然，方陣A的特征值就是其特征方程的解。特征方程在復(fù)數(shù)范圍內(nèi)恒有解，其解的個(gè)數(shù)為方程的次數(shù)（重跟按重?cái)?shù)計(jì)算），因此n階方陣有n個(gè)特征值。顯然，n階單位矩陣E的特征值都是1。設(shè)n階方陣的特征值為則有（1）（2）整理課件如果是方陣A的一個(gè)特征值，求得非零解則就是A的對(duì)應(yīng)于特征值的特征向量。由以上分析知：求方陣的特征值和特征向量實(shí)際上就是求行列式和方程組的解。程組由線性方整理課件例6.1求矩陣的特征值與特征向量。解A的特征多項(xiàng)式為故A的特征值為當(dāng)時(shí),由即方程組解得基礎(chǔ)解系為整理課件就是A的一個(gè)屬于特征值的特征向量，A的屬于特征值的所有特征向量為當(dāng)由即方程組解得基礎(chǔ)解系A(chǔ)的屬于特征值的所有特征向量為就是A的一個(gè)屬于特征值的特征向量，整理課件對(duì)于一階矩陣A，如果是A的k重特征根，個(gè)數(shù)不大于k，所含向量的個(gè)數(shù)不大于k.定理的線性無關(guān)特征向量的則A對(duì)應(yīng)于的基礎(chǔ)解系也就是說，定理屬于不同特征值的特征向量是線性無關(guān)的。事實(shí)方陣在復(fù)數(shù)域內(nèi)總有特征根，但不一定有實(shí)特征根。例矩陣的特征值。A的特征多項(xiàng)式為其有復(fù)特征根整理課件方程一般形式整理課件注意：上面用定義闡述了如何求解矩陣A的特征值λ和特征向量X。但眾所周知，高次多項(xiàng)式求根是相當(dāng)困難的，而且重根的計(jì)算精度較低。同時(shí)，矩陣A求特征多項(xiàng)式系數(shù)的過程對(duì)舍入誤差十分敏感，這對(duì)最后計(jì)算結(jié)果影響很大。因此，從數(shù)值計(jì)算角度來看，上述方法缺乏實(shí)用價(jià)值。問題的解決：目前，求矩陣特征值問題實(shí)際采用的是迭代法和變換法。整理課件6.2冪法（PowerMethod）整理課件整理課件整理課件在很多問題中，矩陣的按模最大特征值往往起重要的作用。例如矩陣的譜半徑即按模最大特征值，決定了迭代矩陣是否收斂。因此矩陣的按模最大的特征值比其余特征值更重要。冪法是計(jì)算按模最大特征值及相應(yīng)的特征向量的數(shù)值方法。簡(jiǎn)單地說，任取初始向量X(0),迭代計(jì)算X(k+1)=AX(k)得到迭代序列X(k+1)，k＝0,1,…；再分析X(k+1)與X(k)之間的關(guān)系，就可得到A的按模最大特征值及特征向量的近似解整理課件冪法分析整理課件以下考慮兩種簡(jiǎn)單情況。整理課件整理課件整理課件整理課件整理課件整理課件從上述過程可得出計(jì)算矩陣A的按模最大特征值的方法,具體步驟如下：任取一非零向量X0,一般可取X0=(1,1,…,1)T

X(k+1)=AX(k)

當(dāng)k足夠大時(shí),即可得到：λ1＝X(k+1)/X(k)

整理課件6.3反冪法(InversePowerMethod)整理課件整理課件6.4規(guī)范化冪法若按6.2中計(jì)算過程，有一嚴(yán)重缺點(diǎn)，當(dāng)|λ1|>1時(shí)，X(k)中不為零的分量將隨K的增大而無限增大，計(jì)算機(jī)就可能出現(xiàn)上溢（或隨K的增大而很快出現(xiàn)下溢），因此，在實(shí)際計(jì)算時(shí)，須按規(guī)范法計(jì)算，每步先對(duì)向量進(jìn)行“規(guī)范化”，即用X(k)中絕對(duì)值最大的一個(gè)分量記作max|xik|，用max|xik|

遍除X(k)

的所有分量，得到規(guī)范化向量Y(k)

，并令X(k+1)=AY(k)

實(shí)際計(jì)算公式Y(jié)(k)＝X(k)/||X(k)||∞X(k+1)=AY(k)整理課件整理課件整理課件反冪法的規(guī)范算法實(shí)際計(jì)算公式Y(jié)(k)＝X(k)/||X(k)||∞AX(k+1)=Y(k)整理課件6.5冪法的加速和降階冪法的收斂速率依賴于次大和最大特征值之比，當(dāng)比值很小時(shí)，收斂快先對(duì)矩陣進(jìn)行變換，使得有很大的特征值原點(diǎn)移位法：用A－λ0I來代替A進(jìn)行迭代整理課件原點(diǎn)移位法：A－λ0I和A的特征值λ0，相應(yīng)的特征向量不變?yōu)榱思铀偈諗浚m當(dāng)選取λ0，使得整理課件從理論上講，冪法可以采取降階的方法求出矩陣A的全部特征值。當(dāng)求出λ1和對(duì)應(yīng)的特征向量x1后，按同樣的思想可以依次求出λ2,λ3,…,λn以及相應(yīng)的特征向量x2,x3,…,xn。在冪法中，求出矩陣A的主特征值λ1及對(duì)應(yīng)的特征向量x1后，可用壓縮方法求出n-1階矩陣B使它的特征值為λ2,從而把求A次特征值λ2的問題轉(zhuǎn)化為求B的主特征值，等等。整理課件冪法小結(jié)：冪法適用范圍為求矩陣的按模最大特征值及相應(yīng)的特征向量，其優(yōu)點(diǎn)是算法簡(jiǎn)單，容易編寫程序在計(jì)算機(jī)上實(shí)現(xiàn)，缺點(diǎn)是收斂速度慢，其有效性依賴與矩陣特征值的分布情況反冪法的適用范圍是求矩陣A的按模最小特征值及對(duì)應(yīng)的特征向量。整理課件6.6其它方法平行迭代法：可求出前幾個(gè)較大的特征值和特征測(cè)量，適用于高階對(duì)稱稀疏矩陣QR算法：基于任何實(shí)非奇異矩陣都可分解為正交矩陣和上三角矩陣的乘積，適用于任意實(shí)非奇異矩陣的全部特征值Jacobi法：用平面旋轉(zhuǎn)矩陣構(gòu)成的正交相似變換將對(duì)稱矩陣化為對(duì)角形，適用于實(shí)對(duì)稱矩陣整理課件PowerMethodThebasiccomputationofthepowermethodissummarizedasTheequationcanbewrittenas:整理課件PowerMethodThebasiccomputationofthepowermethodissummarizedasTheequationcanbewrittenas:整理課件ShiftmethodItispossibletoobtainanothereigenvaluefromthesetequationsbyusingatechniqueknownasshiftingthematrix.Subtracttheavectorfromeachside,therebychangingthemaximumeigenvalue整理課件ShiftmethodTheeigenvalue,s,isthemaximumvalueofthematrixA.Thematrixisrewritteninaform.UsethePowermethodtoobtainthelargesteigenvalueof[B].整理課件InversePowerMethodTheinversemethodissimilartothepowermethod,exceptthatitfindsthesmallesteigenvalue.Usingthefollowingtechnique.整理課件InversePowerMethodThealgorithmisthesameasthePowermethodandthe“eigenvector”isnottheeigenvectorforthesmallesteigenvalue.Toobtainthesmallesteigenvaluefromthepowermethod.整理課件AcceleratedPowerMethodThePowermethodcanbeacceleratedbyusingtheRayleighQuotientinsteadofthelargestwkvalue.TheRayeighQuotientisdefinedas:整理課件AcceleratedPowerMethodThevaluesofthenextztermisdefinedas:ThePowermethodisadaptedtousethenewvalue.整理課件

QRfactorizationAnotherformoffactorization

A=Q*RProducesanorthogonalmatrix(“Q”)andarightuppertriangularmatrix(“R”)Orthogonalmatrix-inverseistranspose整理課件Whydowecare?WecanuseQandRtofindeigenvalues1.GetQandR(A=Q*R)2.LetA=R*Q3.DiagonalelementsofAareeigenvalueapproximations4.IterateuntilconvergedQR

factorizationNote:

QReigenvaluemethodgivesalleigenvaluessimultaneously,notjustthedominant整理課件HouseholderMatrixHouseholdermatrixreduceszk+1,…,zntozeroToachievetheaboveoperation,vmustbealinearcombinationofxandek整理課件對(duì)象雙曲型方程:(5.1)整理課件建立差分格式將xt平面分割成矩形網(wǎng)格用(k,j)表示網(wǎng)格節(jié)點(diǎn)(xk,tj)，網(wǎng)格節(jié)點(diǎn)上的函數(shù)值為u(k,j)整理課件用差商表示導(dǎo)數(shù)整理課件方程(5.1)式變?yōu)?5.2)略去誤差項(xiàng)，得到差分方程加上初始條件，構(gòu)成差分格式整理課件差分格式的收斂性和穩(wěn)定性差分格式的依賴區(qū)域庫朗條件：差分格式收斂的必要條件是差分格式的依賴區(qū)域應(yīng)包含微分方程的依賴區(qū)域穩(wěn)定性整理課件對(duì)象拋物型方程:(5.3)整理課件建立差分格式將xt平面分割成矩形網(wǎng)格用(k,j)表示網(wǎng)格節(jié)點(diǎn)(xk,tj)，網(wǎng)格節(jié)點(diǎn)上的函數(shù)值為u(k,j)整理課件用差商表示導(dǎo)數(shù)方程(5.3)式變?yōu)檎碚n件