第九章 矩阵的特征值与特征向量 /* Eigen-values and Eigen-vectors of matrix */ 待求解的问题：矩阵的特征值和特征向量x 0 ，满足 :Ax=x or (I-A)x =0Eigen-valueEigen-vector工程技术中的许多问题例如电磁振荡、桥梁振动、机 械振动等，都归结为求矩阵的特征值 和特征向量问 题-代数计算中的重要课题。特征向量: 已知A的特征值，求齐次线性方程 组 的非零解x, （ ,所以有非零解。）为A对应于的特征向量。 如何求解?特征值：已知A=(aij)nn，求A的特征多项式的根有n个零点（实或复，计重数）：即求解代数方程A的特 征值从理论上讲，可利用代数方程求根求出特征值，再 利用线性方程组的解法，求出特征向量。缺点：工作量大且特征向量对矩阵的依赖很高； 当矩阵阶数较高时，高次代数方程求根的计算稳定 性较差。另外，实际问题中的具体要求不同，有时只要求A 的绝对值最大的特征值（主特征值）及相应的特征 向量；有时又要求全部的特征值及特征向量。根据 这两种不同要求，求矩阵的特征值与特征向量的方 法也大致分为两类：迭代法（幂法反幂法）、变换 法。关于矩阵特征值及特征向量的一些结论： Th1. （i=1,n）为A的特征值，则有1. 2. det(A)= Th2、AB(相似)，即存在可逆阵T，使B=T-1AT,则 1. A与B有相同的特征值。2. 设x是B的关于的特征向量, 则Tx是A的关于 的特征向量。Th3、（Gershgorins定理,园盘定理）：A=(aij),则 A的每个特征值必在下述某个园盘中： A的每行元素确定一个圆盘，共n个。 Th3 表明A的任一特征值必在这n个圆盘中的某一个内。证明：设为A的任一特征值，x0为对应特征向 量，则有(I-A)x=0,设|xi|=max|xj|,显然xi0,第i个方程：Th3 的证明过程表明A的任一特征值必在其对应 特征向量模最大的分量的指标所对应的圆盘中。称为A对应于向量x的Rayleigh商。 Def1. Ann 实对称阵，0 xRn,Th4. Ann 实对称阵，其特征值依次排序为 , 对应特征向量 组 成规范正交系，即 ，则 1. 0 xRn, 2.3.Proof.1. 0 xRn, forms an orthogonal basis of Rn , so it is possible to write x aswhere not all could be zero. Thus we have =2. From 1 we know so we only need to prove there exists an x0 such that Taking x=x1, we get3. Proof is similar to 2.1 幂法与反幂法（按模最大与最小特征值的求法） F幂法：求模最大的特征值主特征值及相应特征向量的迭代法。用A的乘幂构造迭代序列，因此称为幂法。条件：A Rnn具有线性初等因子A有n个线性无关的特征向量。 优点：简单，适合稀疏矩阵。 缺点：有时收敛速度很慢。Algorithm 1. suppose A has eigen-values (This implies is a single real root of the characteristic polynomial; else )，and n independent eigen-vectors . Take an initial vector start the iteration system Convergence analysis of Algorithm 1.is an eigen-vector of A, and is also an eigen-vector corresponding to of A. The same is Eigen-vectorEigen value 1Th5. A Rnn有n个线性无关特征向量 主特征值1满足则做迭代有 Principal eigen value 1summaryiteration systemeigen-vector corresponding to 11. 收敛速度：主要由来 确定，r 越小，收敛越快。 时收敛可能很慢。2. 若有 ，说明10，1. 以及 都不能作为近 似特征向量，需要重新取初始向量再迭代。2. 3. 用幂法进行计算时，若 在计算机中会产生“溢出”或 “机器零”的情况（ 超过计算机字长所能表示的精度） noteAlgorithm 2(improvement of A.1). Convergence analysis of A.2.Max(x)取出向量x 中模最大的分量对应1的特征向量x1 的规范化向量Th6. A Rnn有n个线性无关特征向量 主特征值1满足 则做迭代有 2平面旋转矩 阵雅可比法的基本思想:设法用一系列简单的正角阵Rk , 逐步地将 A 化为近 似对角阵(非对角元近似化为0)。即选择Rk , 令 A的全部特征值问题的关键：如何构造正交阵Rk ？ 平面旋转变换雅可比算法:设Ak-1 (k1, A0 =A)未对角化，即非对角元中有较大的元素 ，设非对角元中按模最大的元素是引入平面旋转矩阵利用Rk(p,q)对Ak-1作旋转变换，使 中的非对角元 应满 足常将限制在对Jacobi算法有几点说明 ： 1. 构造旋转矩阵时只需计算sin,cos,为了防 止舍入误差扩大，sin,cos按下面公式计算： 否则， 2. 由于Ak 是对称阵，因此只要计算上三角（或下三角 ）元素即可，既节省计算量，有能保证Ak 严格对称。 3. 的计算过程如下： 4. Ak 中经旋转变换化为零的元素，可能在Ak+1中又成为 非零元素，因此不能期望通过有限次旋转变换将原矩阵A 对角化，但可证 证明Jacobi法的收敛性由前面推论知 5. 实际计算时，当k充分大或者当 时迭代终止，A的全部近似特征值 6. 特征向量的计算：设经过m次旋转变换迭代结束，则说明Pm的第j列就是j的标准正交特征向量的近似值。实际计算时，并不是保留 到最后 才形成Pm，而是逐步形成的。令 每一步的计算公式为 7. 对经典Jacobi法的改进-避免每次在非对角元中选 主元素花费太多时间：循环雅可比法和雅可比过关法。雅可比过关法：1. 设阈值T0(一般取为 )，在A的非对角 元中按行（或列）扫描（只需扫描上（或下）三角元素 ），即按如下顺序与阈值T0作比 较：若 |aij|j+1时，bij=0,则称B为上 Hessenberg阵(或准上三角阵)，即i=j+1i j+1理论基础：A是n阶实矩阵，存在正交阵P，s.t.是1阶或2阶方阵。若Aii 是1阶的 ， 则它是A的一个实特征值；若Aii 是2阶的，则它的两 个特征值是A的一对共轭复特征值。 定理说明：用正交阵相似变换可将一般实矩阵约化为上 Hessenberg阵，将实对称阵约化为对称三对角阵。正交相似变换不改变特征值和特征向量，因此求原矩阵 的特征值问题就转化为求上Hessenberg阵或对称三对角 阵的特征值问题。问题的关键：如何将一般实矩阵正交约化为上 Hessenberg阵，将实对称阵约化为对称三对角阵？初等反射阵Def初等反射阵性质:对称、正交 、对合初等反射阵的几何意义Swv=x+y yx-yv=x-yv是v关于平面S 的镜面反射。初等反射阵将 Rn 中任意向量关于以w为法向量且过原点的超 平面做镜面反射。初等反射阵的作用：对向量作变换Proposition证明：令Corollary结论推论说明：通过初等反射阵即可将任何非零向量 约化成只有一个非0元素的向量。 注意：计算 时可能上溢或下 溢，为防止溢出，将x 规范化，用正交相似变换(初等反射阵)约化矩阵为 Hessenberg阵(n-1) (n-1)维令重复这一过程直到 结论设x是c 的对应于的特征向量，则有 说明 P x 是 A 对应于 的特征向量。A的特征值和特征向量若A是实对称阵，则C也是实对称阵(CT=PTATP=PTAP=C),故C为对称三对角阵，即关于实对称阵4 QR方法是一种变换方法，计算一般中小型矩阵全部特征值的 最有效方法之一。 主要用于计算：1.上Hessenberg阵的全部特征值; 2.对称三对角矩阵的全部特征值。 对于一般矩阵或对称阵，先用Householder方法将其 约化为上Hessenberg阵或对称三对角阵，再用QR法 计算全部特征值。 优点：算法稳定，收敛快。 矩阵的QR分解Lemma1 （旋转对向量的作用）i行j行i列j列证：P左乘x只对的第i,j个元素有影响，其它元素不变 。 （旋转对矩阵的作用）A非奇异，则存在旋转阵P1, P2, Pn,s.t.为上三角阵，且对角线元素 Theorem2证明：A=A1非奇异，A1的第一列一定存在ai10, 1. 若ai10, 由引理1，存在旋转阵 , s.t. 2. 同理， 若 ,由引理1, 存在旋转阵 , s.t.3. 重复上述过程，得到 , s.t.矩阵的QR 分解Theorem3下三 角正交阵上三角阵证(仅证唯一性，反正)：设QR算法 算法收敛性证明：Th4.在QR算 法中，有 Lemma5证 ：Theorem6(QR法的收敛性)A非奇异,且有n个不同的特征根 ： 定理说明，Ak收敛 于上三角阵，其对 角线上的元素就是 A的特征值。