计算方法6-矩阵特征值和特征向量

矩阵特征值和特征向量EigenvaluesandEigenvectors整理课件问题的提出矩阵特征值计算非常重要，在很多方面应用数值分析中，和矩阵有关的迭代序列的收敛取决于迭代矩阵的特征值大小动态系统中，特征值标志着系统是否是稳定的振动系统中，微分方程的特征值或者有限元模型的矩阵系数和系统的固有频率直接相关数学中方阵的对角化、微分方程组的解等等整理课件6.1基本概念回顾DEF6.1设A是n阶方阵，如果数λ和一维非零向量χ使关系式Aχ=λχ成立，则称数λ为方阵A的特征值，非零向量χ称为A的属于特征值λ的特征向量.推论：如果χ是矩阵A的属于特征值λ0的特征向量，那么χ的任何一个非零倍数kχ也是A的属于λ的特征向量。这是因为Aχ=λ0χ所以A(kχ)=λ0(kχ)，这说明属于同一个特征值的特征向量不是唯一的，但一个特征向量只能属于一个特征值。整理课件可以写成齐次线性方程组方程组有解即上式是以为未知量的一元n次方程，称为方阵A的特征方程，是的n次多项式，记为称为方阵A的特征多项式。整理课件显然，方阵A的特征值就是其特征方程的解。特征方程在复数范围内恒有解，其解的个数为方程的次数（重跟按重数计算），因此n阶方阵有n个特征值。显然，n阶单位矩阵E的特征值都是1。设n阶方阵的特征值为则有（1）（2）整理课件如果是方阵A的一个特征值，求得非零解则就是A的对应于特征值的特征向量。由以上分析知：求方阵的特征值和特征向量实际上就是求行列式和方程组的解。程组由线性方整理课件例6.1求矩阵的特征值与特征向量。解A的特征多项式为故A的特征值为当时,由即方程组解得基础解系为整理课件就是A的一个属于特征值的特征向量，A的属于特征值的所有特征向量为当由即方程组解得基础解系A的属于特征值的所有特征向量为就是A的一个属于特征值的特征向量，整理课件对于一阶矩阵A，如果是A的k重特征根，个数不大于k，所含向量的个数不大于k.定理的线性无关特征向量的则A对应于的基础解系也就是说，定理属于不同特征值的特征向量是线性无关的。事实方阵在复数域内总有特征根，但不一定有实特征根。例矩阵的特征值。A的特征多项式为其有复特征根整理课件方程一般形式整理课件注意：上面用定义阐述了如何求解矩阵A的特征值λ和特征向量X。但众所周知，高次多项式求根是相当困难的，而且重根的计算精度较低。同时，矩阵A求特征多项式系数的过程对舍入误差十分敏感，这对最后计算结果影响很大。因此，从数值计算角度来看，上述方法缺乏实用价值。问题的解决：目前，求矩阵特征值问题实际采用的是迭代法和变换法。整理课件6.2幂法（PowerMethod）整理课件整理课件整理课件在很多问题中，矩阵的按模最大特征值往往起重要的作用。例如矩阵的谱半径即按模最大特征值，决定了迭代矩阵是否收敛。因此矩阵的按模最大的特征值比其余特征值更重要。幂法是计算按模最大特征值及相应的特征向量的数值方法。简单地说，任取初始向量X(0),迭代计算X(k+1)=AX(k)得到迭代序列X(k+1)，k＝0,1,…；再分析X(k+1)与X(k)之间的关系，就可得到A的按模最大特征值及特征向量的近似解整理课件幂法分析整理课件以下考虑两种简单情况。整理课件整理课件整理课件整理课件整理课件整理课件从上述过程可得出计算矩阵A的按模最大特征值的方法,具体步骤如下：任取一非零向量X0,一般可取X0=(1,1,…,1)T

X(k+1)=AX(k)

当k足够大时,即可得到：λ1＝X(k+1)/X(k)

整理课件6.3反幂法(InversePowerMethod)整理课件整理课件6.4规范化幂法若按6.2中计算过程，有一严重缺点，当|λ1|>1时，X(k)中不为零的分量将随K的增大而无限增大，计算机就可能出现上溢（或随K的增大而很快出现下溢），因此，在实际计算时，须按规范法计算，每步先对向量进行“规范化”，即用X(k)中绝对值最大的一个分量记作max|xik|，用max|xik|

遍除X(k)

的所有分量，得到规范化向量Y(k)

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

实际计算公式Y(k)＝X(k)/||X(k)||∞X(k+1)=AY(k)整理课件整理课件整理课件反幂法的规范算法实际计算公式Y(k)＝X(k)/||X(k)||∞AX(k+1)=Y(k)整理课件6.5幂法的加速和降阶幂法的收敛速率依赖于次大和最大特征值之比，当比值很小时，收敛快先对矩阵进行变换，使得有很大的特征值原点移位法：用A－λ0I来代替A进行迭代整理课件原点移位法：A－λ0I和A的特征值λ0，相应的特征向量不变为了加速收敛，适当选取λ0，使得整理课件从理论上讲，幂法可以采取降阶的方法求出矩阵A的全部特征值。当求出λ1和对应的特征向量x1后，按同样的思想可以依次求出λ2,λ3,…,λn以及相应的特征向量x2,x3,…,xn。在幂法中，求出矩阵A的主特征值λ1及对应的特征向量x1后，可用压缩方法求出n-1阶矩阵B使它的特征值为λ2,从而把求A次特征值λ2的问题转化为求B的主特征值，等等。整理课件幂法小结：幂法适用范围为求矩阵的按模最大特征值及相应的特征向量，其优点是算法简单，容易编写程序在计算机上实现，缺点是收敛速度慢，其有效性依赖与矩阵特征值的分布情况反幂法的适用范围是求矩阵A的按模最小特征值及对应的特征向量。整理课件6.6其它方法平行迭代法：可求出前几个较大的特征值和特征测量，适用于高阶对称稀疏矩阵QR算法：基于任何实非奇异矩阵都可分解为正交矩阵和上三角矩阵的乘积，适用于任意实非奇异矩阵的全部特征值Jacobi法：用平面旋转矩阵构成的正交相似变换将对称矩阵化为对角形，适用于实对称矩阵整理课件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整理课件对象双曲型方程:(5.1)整理课件建立差分格式将xt平面分割成矩形网格用(k,j)表示网格节点(xk,tj)，网格节点上的函数值为u(k,j)整理课件用差商表示导数整理课件方程(5.1)式变为(5.2)略去误差项，得到差分方程加上初始条件，构成差分格式整理课件差分格式的收敛性和稳定性差分格式的依赖区域库朗条件：差分格式收敛的必要条件是差分格式的依赖区域应包含微分方程的依赖区域稳定性整理课件对象抛物型方程:(5.3)整理课件建立差分格式将xt平面分割成矩形网格用(k,j)表示网格节点(xk,tj)，网格节点上的函数值为u(k,j)整理课件用差商表示导数方程(5.3)式变为整理课件