计算方法_矩阵特征值和特征向量.ppt

矩阵特征值和特征向量EigenvaluesandEigenvectors,问题的提出,矩阵特征值计算非常重要，在很多方面应用数值分析中，和矩阵有关的迭代序列的收敛取决于迭代矩阵的特征值大小动态系统中，特征值标志着系统是否是稳定的振动系统中，微分方程的特征值或者有限元模型的矩阵系数和系统的固有频率直接相关数学中方阵的对角化、微分方程组的解等等,6.1基本概念回顾,DEF6.1设A是n阶方阵，如果数和一维非零向量使关系式A=成立，则称数为方阵A的特征值，非零向量称为A的属于特征值的特征向量.,推论：如果是矩阵A的属于特征值0的特征向量，那么的任何一个非零倍数k也是A的属于的特征向量。这是因为A=0所以A(k)=0(k)，这说明属于同一个特征值的特征向量不是唯一的，但一个特征向量只能属于一个特征值。,可以写成齐次线性方程组,方程组有解,即,的特征方程，,称为方阵A的特征多项式。,显然，方阵A的特征值就是其特征方程的解。特征方程在复数范围内恒有解，其解的个数为方程的次数（重跟按重数计算），因此n阶方阵有n个特征值。显然，n阶单位矩阵E的特征值都是1。,则有,（1）,（2）,求得非零解,由以上分析知：,求方阵的特征值和特征向量实际上就是求行列式和方程组的解。,程组,由线性方,例6.1,解,A的特征多项式为,故A的特征值为,即方程组,解得基础解系为,当,由,即方程组,解得基础解系,例,A的特征多项式为,其有复特征根,方程一般形式,注意：上面用定义阐述了如何求解矩阵A的特征值和特征向量X。但众所周知，高次多项式求根是相当困难的，而且重根的计算精度较低。同时，矩阵A求特征多项式系数的过程对舍入误差十分敏感，这对最后计算结果影响很大。因此，从数值计算角度来看，上述方法缺乏实用价值。,问题的解决：目前，求矩阵特征值问题实际采用的是迭代法和变换法。,6.2幂法（PowerMethod）,在很多问题中，矩阵的按模最大特征值往往起重要的作用。例如矩阵的谱半径即按模最大特征值，决定了迭代矩阵是否收敛。因此矩阵的按模最大的特征值比其余特征值更重要。幂法是计算按模最大特征值及相应的特征向量的数值方法。简单地说，任取初始向量X(0),迭代计算X(k+1)=AX(k)得到迭代序列X(k+1)，k0,1,；再分析X(k+1)与X(k)之间的关系，就可得到A的按模最大特征值及特征向量的近似解,幂法分析,以下考虑两种简单情况。,从上述过程可得出计算矩阵A的按模最大特征值的方法,具体步骤如下：任取一非零向量X0,一般可取X0=(1,1,1)TX(k+1)=AX(k)当k足够大时,即可得到：1X(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),实际计算公式,反幂法的规范算法,实际计算公式,6.5幂法的加速和降阶,幂法的收敛速率依赖于次大和最大特征值之比，当比值很小时，收敛快,先对矩阵进行变换，使得有很大的特征值,原点移位法：用A0I来代替A进行迭代,原点移位法：A0I和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法：用平面旋转矩阵构成的正交相似变换将对称矩阵化为对角形，适用于实对称矩阵,PowerMethod,Thebasiccomputationofthepowermethodissummarizedas,Theequationcanbewrittenas:,PowerMethod,Thebasiccomputationofthepowermethodissummarizedas,Theequationcanbewrittenas:,Shiftmethod,Itispossibletoobtainanothereigenvaluefromthesetequationsbyusingatechniqueknownasshiftingthematrix.,Subtracttheavectorfromeachside,therebychangingthemaximumeigenvalue,Shiftmethod,Theeigenvalue,s,isthemaximumvalueofthematrixA.Thematrixisrewritteninaform.,UsethePowermethodtoobtainthelargesteigenvalueofB.,InversePowerMethod,Theinversemethodissimilartothepowermethod,exceptthatitfindsthesmallesteigenvalue.Usingthefollowingtechnique.,InversePowerMethod,ThealgorithmisthesameasthePowermethodandthe“eigenvector”isnottheeigenvectorforthesmallesteigenvalue.Toobtainthesmallesteigenvaluefromthepowermethod.,AcceleratedPowerMethod,ThePowermethodcanbeacceleratedbyusingtheRayleighQuotientinsteadofthelargestwkvalue.TheRayeighQuotientisdefinedas:,AcceleratedPowerMethod,Thevaluesofthenextztermisdefinedas:ThePowermethodisadaptedtousethenewvalue.,QRfactorization,AnotherformoffactorizationA=Q*RProducesanorthogonalmatrix(“Q”)andarightuppertriangularmatrix(“R”)Orthogonalmatrix-inverseistranspose,Whydowecare?WecanuseQandRtofindeigenvalues1.GetQandR(A=Q*R)2.LetA=R*Q3.DiagonalelementsofAareeigenvalueapproximations4.Iterateuntilconverged,QRfactorization,Note:QReigenvaluemethodgivesalleigenvaluessimultaneously,notjustthedominant,HouseholderMatrix,Householdermatrixreduceszk+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)式变为,(5.4),略去误差项，并令s/h2得到差分方程,边界条件差分化（第二、三类边界条件）,常用的差分格式,显式格式,