矩阵特征值和特征向量Eigenvalues and Eigenvectors2021/3/91问题的提出问题的提出矩阵特征值计算非常重要，在很多方面应用矩阵特征值计算非常重要，在很多方面应用数值分析中，和矩阵有关的迭代序列的收敛数值分析中，和矩阵有关的迭代序列的收敛取决于迭代矩阵的特征值大小取决于迭代矩阵的特征值大小动态系统中，特征值标志着系统是否是稳定动态系统中，特征值标志着系统是否是稳定的的振动系统中，微分方程的特征值或者有限元振动系统中，微分方程的特征值或者有限元模型的矩阵系数和系统的固有频率直接相关模型的矩阵系数和系统的固有频率直接相关数学中方阵的对角化、微分方程组的解等等数学中方阵的对角化、微分方程组的解等等2021/3/926.1 基本概念回顾基本概念回顾DEF6.1 设设A是是n阶方阵，如果数阶方阵，如果数和一维非零向量和一维非零向量使关系式使关系式A=成立，则称数成立，则称数为方阵为方阵A的的特征值特征值，非零向量非零向量称为称为A的属于特征值的属于特征值的的特征向量特征向量.推论：推论：如果如果是矩阵是矩阵A的属于特征值的属于特征值0的特征向量，的特征向量，那么那么的任何一个非零倍数的任何一个非零倍数k也是也是A的属于的属于的特征向的特征向量。这是因为量。这是因为A=0所以所以A(k)= 0(k)，这说明属这说明属于同一个特征值的特征向量不是唯一的，但一个特征于同一个特征值的特征向量不是唯一的，但一个特征向量只能属于一个特征值。向量只能属于一个特征值。2021/3/93可以写成齐次线性方程组可以写成齐次线性方程组方程组有解方程组有解即即上式是以上式是以为未知量的一元为未知量的一元n n次方程，称为方阵次方程，称为方阵A A的的特征方程特征方程，是是的的n n次多项式，记为次多项式，记为称为方阵称为方阵A A的的特征多项式特征多项式。2021/3/94显然，方阵显然，方阵A的特征值就是其特征方程的解。特征的特征值就是其特征方程的解。特征方程在复数范围内恒有解，其解的个数为方程的方程在复数范围内恒有解，其解的个数为方程的次数（重跟按重数计算），因此次数（重跟按重数计算），因此n阶方阵有阶方阵有n个特个特征值。显然，征值。显然，n阶单位矩阵阶单位矩阵E的特征值都是的特征值都是1。设设n n阶方阵阶方阵的特征值为的特征值为则有则有（1 1）（2 2）2021/3/95如果如果是方阵是方阵A A的一个特征值，的一个特征值，求得非零解求得非零解则则就是就是A A的对应于特征值的对应于特征值的特征向量。的特征向量。由以上分析知：由以上分析知：求方阵的特征值和特征向量实际上就是求行列式和求方阵的特征值和特征向量实际上就是求行列式和方程组的解。方程组的解。程组程组由线性方由线性方2021/3/96例例6.1求矩阵求矩阵的特征值与特征向量。的特征值与特征向量。解解A A的特征多项式为的特征多项式为故故A A的特征值为的特征值为当当时时, ,由由即方程组即方程组解得基础解系为解得基础解系为2021/3/97就是就是A A的一个属于特征值的一个属于特征值的特征向量，的特征向量，A A的属于特征值的属于特征值的所有特征向量为的所有特征向量为当当由由即方程组即方程组解得基础解系解得基础解系A A的属于特征值的属于特征值的所有特征向量为的所有特征向量为就是就是A A的一个属于特征值的一个属于特征值的特征向量，的特征向量，2021/3/98对于一阶矩阵对于一阶矩阵A A，如果，如果是是A A的的k k重特征根，重特征根，个数不大于个数不大于k k， 所含向量的个数不大于所含向量的个数不大于k.k.定理定理的线性无关特征向量的的线性无关特征向量的则则A A对应于对应于的基础解系的基础解系也就是说，也就是说，定理定理 属于不同特征值的特征向量是线性无关的。属于不同特征值的特征向量是线性无关的。事实事实 方阵在复数域内总有特征根，但不一定有实方阵在复数域内总有特征根，但不一定有实特征根。特征根。例例矩阵矩阵的特征值。的特征值。A A的特征多项式为的特征多项式为其有复特征根其有复特征根2021/3/99方程一般形式方程一般形式2021/3/910注意：上面用定义阐述了如何求解矩阵注意：上面用定义阐述了如何求解矩阵A A的特征值的特征值和特征向量和特征向量X X。但众所周知，高次多项式求根是。但众所周知，高次多项式求根是相当困难的，而且重根的计算精度较低。同时，相当困难的，而且重根的计算精度较低。同时，矩阵矩阵A A求特征多项式系数的过程对舍入误差十分敏求特征多项式系数的过程对舍入误差十分敏感，这对最后计算结果影响很大。因此，从数值感，这对最后计算结果影响很大。因此，从数值计算角度来看，上述方法缺乏实用价值。计算角度来看，上述方法缺乏实用价值。问题的解决：问题的解决：目前，求矩阵特征值问题实际采用目前，求矩阵特征值问题实际采用的是迭代法和变换法。的是迭代法和变换法。2021/3/9116.2 幂法（幂法（Power Method）2021/3/9122021/3/9132021/3/914在很多问题中，矩阵的按模最大特征值往往起重要在很多问题中，矩阵的按模最大特征值往往起重要的作用。例如矩阵的谱半径即按模最大特征值，决的作用。例如矩阵的谱半径即按模最大特征值，决定了迭代矩阵是否收敛。因此矩阵的按模最大的特定了迭代矩阵是否收敛。因此矩阵的按模最大的特征值比其余特征值更重要。征值比其余特征值更重要。幂法是计算按模最大特征值及相应的特征向量的数幂法是计算按模最大特征值及相应的特征向量的数值方法值方法。简单地说，任取初始向量。简单地说，任取初始向量X(0),迭代计算迭代计算X(k+1)=A X(k)得到迭代序列得到迭代序列X(k+1)，k0,1,；再分析；再分析X(k+1)与与X(k)之间的关系，就可得到之间的关系，就可得到A的按模最大特征值及的按模最大特征值及特征向量的近似解特征向量的近似解2021/3/915幂法分析幂法分析2021/3/916以下考虑两种简单情况。以下考虑两种简单情况。2021/3/9172021/3/9182021/3/9192021/3/9202021/3/9212021/3/922从上述过程可得出计算矩阵从上述过程可得出计算矩阵A的按模最大特征值的方的按模最大特征值的方法法,具体步骤如下：具体步骤如下：任取一非零向量任取一非零向量X0,一般可取一般可取 X0=(1,1,1)T X(k+1)=A X(k) 当当k足够大时足够大时,即可得到：即可得到：1 X(k+1)/ X(k) 2021/3/9236.3 反幂法反幂法( Inverse Power Method)2021/3/9242021/3/9256.4 规范化幂法规范化幂法若按若按6.2中计算过程，有一严重缺点，当中计算过程，有一严重缺点，当|1|1时，时， X(k)中不为零的分量将随中不为零的分量将随K的增大的增大而无限增大，计算机就可能出现上溢（或随而无限增大，计算机就可能出现上溢（或随K的的增大而很快出现下溢），因此，在实际计算时，增大而很快出现下溢），因此，在实际计算时，须按规范法计算，每步先对向量须按规范法计算，每步先对向量 进行进行“规范化规范化”，即用，即用X(k)中绝对值最大的一个分量记作中绝对值最大的一个分量记作max|xik| ，用用max|xik| 遍除遍除X(k) 的所有分的所有分量，得到规范化向量量，得到规范化向量Y(k) ，并令，并令X(k+1)=A Y(k) 实际计算公式实际计算公式Y(k) X(k) /| X(k) |X(k+1)=A Y(k)2021/3/9262021/3/9272021/3/928反幂法的规范算法反幂法的规范算法实际计算公式实际计算公式Y(k) X(k) /| X(k) |AX(k+1)= Y(k)2021/3/9296.5 幂法的加速和降阶幂法的加速和降阶幂法的收敛速率依赖于次大和最大特征值之比，幂法的收敛速率依赖于次大和最大特征值之比，当比值很小时，收敛快当比值很小时，收敛快先对先对矩阵进行变换，使得有很大的特征值矩阵进行变换，使得有很大的特征值原点移位法原点移位法：用：用A0I来代替来代替A进行迭代进行迭代2021/3/930原点移位法原点移位法：A0I和和A的特征值的特征值0，相应的特征向量不变相应的特征向量不变为了加速收敛，适当选取为了加速收敛，适当选取0，使得，使得2021/3/931从理论上讲，幂法可以采取从理论上讲，幂法可以采取降阶降阶的方法求出矩阵的方法求出矩阵A A的全部特征值。当求出的全部特征值。当求出1和对应的特征向量和对应的特征向量x1后，后，按同样的思想可以依次求出按同样的思想可以依次求出2,3,n以及相应以及相应的特征向量的特征向量x2,x3,xn 。在幂法中，求出矩阵。在幂法中，求出矩阵A A的的主特征值主特征值1及对应的特征向量及对应的特征向量x1后，可用后，可用压缩方压缩方法法求出求出n-1n-1阶矩阵阶矩阵B B使它的特征值为使它的特征值为2, ,从而把求从而把求A次特征值次特征值2的问题转化为求的问题转化为求B B的主特征值，等等。的主特征值，等等。2021/3/932幂法小结：幂法小结：幂法适用范围幂法适用范围 为求矩阵的按模最大特征值及相应为求矩阵的按模最大特征值及相应的特征向量，其优点是算法简单，容易编写程序的特征向量，其优点是算法简单，容易编写程序在计算机上实现，缺点是收敛速度慢，其有效性在计算机上实现，缺点是收敛速度慢，其有效性依赖与矩阵特征值的分布情况依赖与矩阵特征值的分布情况反幂法的适用范围是求矩阵反幂法的适用范围是求矩阵A A的按模最小特征值及的按模最小特征值及对应的特征向量。对应的特征向量。2021/3/9336.6 其它方法其它方法 平行迭代法：可求出前几个较大的特征值和特平行迭代法：可求出前几个较大的特征值和特征测量，适用于高阶对称稀疏矩阵征测量，适用于高阶对称稀疏矩阵 QR算法：基于任何实非奇异矩阵都可分解为正算法：基于任何实非奇异矩阵都可分解为正交矩阵和上三角矩阵的乘积，适用于任意实非奇交矩阵和上三角矩阵的乘积，适用于任意实非奇异矩阵的全部特征值异矩阵的全部特征值 Jacobi法：用平面旋转矩阵构成的正交相似变法：用平面旋转矩阵构成的正交相似变换将对称矩阵化为对角形，适用于实对称矩阵换将对称矩阵化为对角形，适用于实对称矩阵2021/3/934Power MethodThe basic computation of the power method is summarized asThe equation can be written as:2021/3/935Power MethodThe basic computation of the power method is summarized asThe equation can be written as:2021/3/936Shift methodIt is possible to obtain another eigenvalue from the set equations by using a technique known as shifting the matrix.Subtract the a vector from each side, thereby changing the maximum eigenvalue2021/3/937Shift methodThe eigenvalue, s, is the maximum value of the matrix A. The matrix is rewritten in a form.Use the Power method to obtain the largest eigenvalue of B.2021/3/938Inverse Power MethodThe inverse method is similar to the power method, except that it finds the smallest eigenvalue. Using the following technique.2021/3/939Inverse Power MethodThe algorithm is the same as the Power method and the “eigenvector” is not the eigenvector for the smallest eigenvalue. To obtain the smallest eigenvalue from the power method.2021/3/940Accelerated Power MethodThe Power method can be accelerated by using the Rayleigh Quotient instead of the largest wk value.The Rayeigh Quotient is defined as:2021/3/941Accelerated Power MethodThe values of the next z term is defined as:The Power method is adapted to use the new value.2021/3/942 QR factorizationAnother form of factorization A = Q*R Produces an orthogonal matrix (“Q”) and a right upper triangular matrix (“R”) Orthogonal matrix - inverse is transpose2021/3/943Why do we care?We can use Q and R to find eigenvalues1. Get Q and R (A = Q*R)2. Let A = R*Q3. Diagonal elements of A are eigenvalue approximations 4. Iterate until convergedQR factorizationNote: QR eigenvalue method gives all eigenvalues simultaneously, not just the dominant 2021/3/944Householder MatrixHouseholder matrix reduces zk+1 ,zn to zeroTo achieve the above operation, v must be a linear combination of x and ek2021/3/945对象对象双曲型方程双曲型方程:(5.1)2021/3/946建立差分格式建立差分格式将将xt平面分割成矩形网格平面分割成矩形网格用用(k,j)表示网格节点表示网格节点(xk,tj)，网格节点上的函数，网格节点上的函数值为值为u(k,j)2021/3/947用差商表示导数用差商表示导数2021/3/948方程方程(5.1)式变为式变为(5.2)略去误差项，得到差分方程略去误差项，得到差分方程加上初始条件，构成差分格式加上初始条件，构成差分格式2021/3/949差分格式的收敛性和稳定性差分格式的收敛性和稳定性差分格式的依赖区域差分格式的依赖区域库库朗朗条条件件：差差分分格格式式收收敛敛的的必必要要条条件件是是差差分分格格式式的的依依赖区域应包含微分方程的依赖区域赖区域应包含微分方程的依赖区域稳定性稳定性2021/3/950对象对象抛物型方程抛物型方程:(5.3)2021/3/951建立差分格式建立差分格式将将xt平面分割成矩形网格平面分割成矩形网格用用(k,j)表示网格节点表示网格节点(xk,tj)，网格节点上的函数，网格节点上的函数值为值为u(k,j)2021/3/952用差商表示导数用差商表示导数方程方程(5.3)式变为式变为2021/3/953(5.4)略去误差项，并令略去误差项，并令s/h2 得到差分方程得到差分方程边界条件差分化（第二、三类边界条件）边界条件差分化（第二、三类边界条件）2021/3/954常用的差分格式显式格式显式格式2021/3/955隐式格式隐式格式Richardson格式格式2021/3/956菱形格式菱形格式六点格式六点格式2021/3/957对象对象椭圆型方程椭圆型方程:(5.5)2021/3/958建立差分格式建立差分格式将将xy平面分割成矩形网格平面分割成矩形网格用用(k,j)表示网格节点表示网格节点(xk,yj)，网格节点上的函数，网格节点上的函数值为值为u(k,j)2021/3/959用差商表示导数用差商表示导数方程方程(5.5)式变为式变为2021/3/960(5.6)略去误差项，得到差分方程略去误差项，得到差分方程边界条件处理边界条件处理直接转移直接转移线性插值线性插值2021/3/961放映结束 感谢各位的批评指导！ 谢谢 谢！谢！让我们共同进步2021/3/962