第九章矩阵特征值和特征向量优秀PPT.ppt

《第九章矩阵特征值和特征向量优秀PPT.ppt》由会员分享，可在线阅读，更多相关《第九章矩阵特征值和特征向量优秀PPT.ppt（90页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第九章矩阵特征值和特征向量第一页，本课件共有90页特征向量特征向量:已知已知A的特征值的特征值，求齐次线性方，求齐次线性方程组程组 的非零解的非零解x,（,所以有非零解。）为所以有非零解。）为A对应于对应于 的特征向量。的特征向量。如何求解如何求解?特征值特征值：已知：已知A=(aij)nn，求，求A的的特征多项式特征多项式的根的根有有n个零点（实或复，计重数）：个零点（实或复，计重数）：即求解代数方程即求解代数方程A的特征值第二页，本课件共有90页从理论上讲，可利用代数方程求根求出特征值，再利用线从理论上讲，可利用代数方程求根求出特征值，再利用线性方程组的解法，求出特征向量。性方程组的解法，

2、求出特征向量。缺点：工作量大且特征向量对矩阵的依赖很高；当矩缺点：工作量大且特征向量对矩阵的依赖很高；当矩阵阶数较高时，高次代数方程求根的计算稳定性较差。阵阶数较高时，高次代数方程求根的计算稳定性较差。另外，实际问题中的具体要求不同，有时只要求另外，实际问题中的具体要求不同，有时只要求A的绝对值最大的特征值（主特征值）及相应的特征的绝对值最大的特征值（主特征值）及相应的特征向量；有时又要求全部的特征值及特征向量。根据向量；有时又要求全部的特征值及特征向量。根据这两种不同要求，求矩阵的特征值与特征向量的方这两种不同要求，求矩阵的特征值与特征向量的方法也大致分为两类：迭代法（幂法反幂法）、变换法也

3、大致分为两类：迭代法（幂法反幂法）、变换法。法。第三页，本课件共有90页关于矩阵特征值及特征向量的一些结论：关于矩阵特征值及特征向量的一些结论：Th1.（i=1,n）为）为A的特征值，则有的特征值，则有 1.2.det(A)=第四页，本课件共有90页Th2、A B(相似相似)，即存在可逆阵，即存在可逆阵T，使，使B=T-1AT,则则 1.A与与B有相同的特征值。有相同的特征值。2.设设x是是B的关于的关于 的特征向量的特征向量,则则Tx是是A的关于的关于 的特征向量。的特征向量。Th3、（、（Gershgorins定理定理,园盘定理）：园盘定理）：A=(aij),则则A的每个特征值必在下述某个

4、园盘中：的每个特征值必在下述某个园盘中：A的每行元素确定一个圆盘，共的每行元素确定一个圆盘，共n个。个。Th3 表明表明A的任一特征值必在这的任一特征值必在这n个圆盘中的某一个内。个圆盘中的某一个内。第五页，本课件共有90页证明：设证明：设 为为A的任一特征值，的任一特征值，x0为对应特征向为对应特征向 量，则有量，则有(I-A)x=0,设设|xi|=max|xj|,显然显然xi0,第第i个方程：个方程：Th3 的证明过程表明的证明过程表明A的任一特征值必在其对应的任一特征值必在其对应特征向量模最大的分量的指标所对应的圆盘中。特征向量模最大的分量的指标所对应的圆盘中。第六页，本课件共有90页

5、称为称为A对应于向量对应于向量x的的Rayleigh商商。Def1.Ann 实对称阵实对称阵，0 xRn,Th4.Ann 实对称阵，其特征值依次排序为实对称阵，其特征值依次排序为 ,对应特征向量对应特征向量 组成组成规范正交系，即规范正交系，即 ，则，则 1.0 xRn,第七页，本课件共有90页2.3.Proof.1.0 xRn,forms an orthogonal basis of Rn,so it is possible to write x as2.where not all could be zero.Thus we have 第八页，本课件共有90页=第九页，本课件共有90页2.F

6、rom 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.第十页，本课件共有90页1 幂法与反幂法幂法与反幂法（按模最大与最小特征值的求法）（按模最大与最小特征值的求法）F幂法幂法：求模最大的特征值求模最大的特征值主特征值及相应特征主特征值及相应特征 向量向量的的迭代法迭代法。用用A的乘幂构造迭代序列，因此称为幂法。的乘幂构造迭代序列，因此称为幂法。条件：条件：A Rnn具有具有线性初等因子线性初等因子 A有有n个线性无关的特征向量个

7、线性无关的特征向量。优点：简单，适合稀疏矩阵。优点：简单，适合稀疏矩阵。缺点：有时收敛速度很慢。缺点：有时收敛速度很慢。第十一页，本课件共有90页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 第十二页，本课件共有90页Convergence anal

8、ysis of Algorithm 1.第十三页，本课件共有90页 is an eigen-vector of A,and is also an eigen-vector corresponding to of A.The same is Eigen-vector第十四页，本课件共有90页Eigen value 1第十五页，本课件共有90页Th5.A Rnn有有n个线性无关特征向量个线性无关特征向量 主特征值主特征值 1满足满足则则做迭代做迭代有有 第十六页，本课件共有90页Principal eigen value 1summaryiteration systemeigen-vector c

9、orresponding to 1第十七页，本课件共有90页1.收敛速度：主要由来收敛速度：主要由来 确定，确定，r 越小，收越小，收2.敛越快。敛越快。时收敛可能很慢。时收敛可能很慢。3.2.若有若有 ，说明，说明10，4.以及以及 都不能作为近似特征都不能作为近似特征向量，需要重新取初始向量再迭代。向量，需要重新取初始向量再迭代。5.3.用幂法进行计算时，若用幂法进行计算时，若 在计算机中会产生在计算机中会产生“溢出溢出”或或 “机器零机器零”的情况（超的情况（超过计算机字长所能表示的精度）过计算机字长所能表示的精度）note第十八页，本课件共有90页Algorithm 2(improve

10、ment of A.1).第十九页，本课件共有90页Convergence analysis of A.2.Max(x)取出向量取出向量x中中模最大的分量模最大的分量第二十页，本课件共有90页对应对应 1的特征向量的特征向量x1的的规范化向量规范化向量第二十一页，本课件共有90页第二十二页，本课件共有90页Th6.A Rnn有有n个线性无关特征向量个线性无关特征向量 主特征值主特征值 1满足满足 则则做迭代做迭代有有 第二十三页，本课件共有90页第二十四页，本课件共有90页第二十五页，本课件共有90页第二十六页，本课件共有90页第二十七页，本课件共有90页第二十八页，本课件共有90页第二十九页

11、，本课件共有90页第三十页，本课件共有90页第三十一页，本课件共有90页第三十二页，本课件共有90页第三十三页，本课件共有90页2第三十四页，本课件共有90页平面旋转矩阵平面旋转矩阵第三十五页，本课件共有90页第三十六页，本课件共有90页雅可比法的基本思想雅可比法的基本思想:设法用一系列简单的正角阵设法用一系列简单的正角阵Rk,逐步地将逐步地将 A 化为近化为近似对角阵似对角阵(非对角元近似化为非对角元近似化为0)。即选择。即选择Rk,令令 A的全部特征值的全部特征值问题的关键问题的关键：如何构造正交阵：如何构造正交阵Rk？第三十七页，本课件共有90页 平面旋转变换平面旋转变换第三十八页，本课

12、件共有90页第三十九页，本课件共有90页第四十页，本课件共有90页第四十一页，本课件共有90页第四十二页，本课件共有90页第四十三页，本课件共有90页第四十四页，本课件共有90页第四十五页，本课件共有90页第四十六页，本课件共有90页第四十七页，本课件共有90页第四十八页，本课件共有90页雅可比算法雅可比算法:设设Ak-1(k1,A0=A)未对角化，即非对角元中有较大的元素，设未对角化，即非对角元中有较大的元素，设非对角元中按模最大的元素是非对角元中按模最大的元素是引入平面旋转矩阵引入平面旋转矩阵第四十九页，本课件共有90页利用利用Rk(p,q)对对Ak-1作旋转变换，使作旋转变换，使 中的非

13、对角元中的非对角元 应满足应满足常将常将限制在限制在第五十页，本课件共有90页对对Jacobi算法有几点说明：算法有几点说明：1.构造旋转矩阵时只需计算构造旋转矩阵时只需计算sin,cos,为了防止为了防止舍入误差扩大，舍入误差扩大，sin,cos按下面公式计算：按下面公式计算：否则，否则，第五十一页，本课件共有90页第五十二页，本课件共有90页 2.由于由于Ak 是对称阵，因此只要计算上三角（或下三角）元素是对称阵，因此只要计算上三角（或下三角）元素即可，既节省计算量，有能保证即可，既节省计算量，有能保证Ak 严格对称。严格对称。3.的计算过程如下：的计算过程如下：第五十三页，本课件共有90

14、页 4.Ak 中经旋转变换化为零的元素，可能在中经旋转变换化为零的元素，可能在Ak+1中又成为非零中又成为非零元素，因此不能期望通过有限次旋转变换将原矩阵元素，因此不能期望通过有限次旋转变换将原矩阵A对角化，对角化，但可证但可证 证明证明Jacobi法的收敛性法的收敛性第五十四页，本课件共有90页由前面推论知由前面推论知第五十五页，本课件共有90页 5.实际计算时，当实际计算时，当k充分大或者当充分大或者当 时迭代终止，时迭代终止，A的全部近似特征值的全部近似特征值 6.特征向量的计算：设经过特征向量的计算：设经过m次旋转变换迭代结束，则次旋转变换迭代结束，则说明说明Pm的第的第j列就是列就是

15、 j的标准正交特征向量的近似值。的标准正交特征向量的近似值。第五十六页，本课件共有90页实际计算时，并不是保留实际计算时，并不是保留 到最后才形成到最后才形成Pm，而，而是逐步形成的。是逐步形成的。令令 每一步的计算公式为每一步的计算公式为第五十七页，本课件共有90页 7.对经典对经典Jacobi法的改进法的改进-避免每次在非对角元中选主避免每次在非对角元中选主元素花费太多时间：元素花费太多时间：循环雅可比法和雅可比过关法循环雅可比法和雅可比过关法。雅可比过关法雅可比过关法：1.设阈值设阈值T0(一般取为一般取为 )，在，在A的非对角的非对角 元中按行元中按行（或列）扫描（只需扫描上（或下）三

16、角元素），即按如下顺（或列）扫描（只需扫描上（或下）三角元素），即按如下顺序与阈值序与阈值T0作比作比 较：较：若若|aij|j+1时，时，bij=0,则称则称B为上为上Hessenberg阵阵(或准上三角阵或准上三角阵)，即，即i=j+1i j+1第六十四页，本课件共有90页理论基础：理论基础：A是是n阶实矩阵，存在阶实矩阵，存在正交阵正交阵P，s.t.是是1阶或阶或2阶方阵。若阶方阵。若Aii 是是1阶的，阶的，则它是则它是A的一个实特征值；若的一个实特征值；若Aii 是是2阶的，则它的两个阶的，则它的两个特征值是特征值是A的一对共轭复特征值。的一对共轭复特征值。第六十五页，本课件共有90

17、页定理说明：定理说明：用正交阵相似变换可将一般实矩阵约化为上用正交阵相似变换可将一般实矩阵约化为上Hessenberg阵，将实对称阵约化为对称三对角阵。阵，将实对称阵约化为对称三对角阵。正交相似变换不改变特征值和特征向量，因此求原矩阵的特征正交相似变换不改变特征值和特征向量，因此求原矩阵的特征值问题就转化为求上值问题就转化为求上Hessenberg阵或对称三对角阵的特征值问阵或对称三对角阵的特征值问题。题。问题的关键问题的关键：如何将一般实矩阵正交约化为上：如何将一般实矩阵正交约化为上Hessenberg阵，将实对称阵约化为对称三对角阵？阵，将实对称阵约化为对称三对角阵？初等反射阵初等反射阵D

18、ef第六十六页，本课件共有90页初等反射阵初等反射阵性质性质:对称、正交、对称、正交、对合对合第六十七页，本课件共有90页初等反射阵的初等反射阵的几何意义几何意义Swv=x+yyx-yv=x-yv是是v关于平面关于平面S的镜面反射。的镜面反射。初等反射阵将初等反射阵将 Rn 中任意向量关于以中任意向量关于以w为法向量且过原点的超平为法向量且过原点的超平面做镜面反射面做镜面反射。初等反射阵的作用：对向量作变换初等反射阵的作用：对向量作变换第六十八页，本课件共有90页Proposition证明：令第六十九页，本课件共有90页Corollary第七十页，本课件共有90页 第七十一页，本课件共有90页

19、结论结论推论说明：通过初等反射阵即可将任何非零向量推论说明：通过初等反射阵即可将任何非零向量约化成只有一个非约化成只有一个非0 0元素的向量。元素的向量。注意：计算注意：计算 时可能上溢或下溢，时可能上溢或下溢，为防止溢出，将为防止溢出，将x 规范化，规范化，第七十二页，本课件共有90页用正交相似变换用正交相似变换(初等反射阵初等反射阵)约化矩阵为约化矩阵为Hessenberg阵阵(n-1)(n-1)维维第七十三页，本课件共有90页令第七十四页，本课件共有90页第七十五页，本课件共有90页第七十六页，本课件共有90页重复这一过程直到 第七十七页，本课件共有90页结论结论第七十八页，本课件共有9

20、0页设x是c 的对应于的特征向量，则有 说明说明 P x 是是 A 对应于对应于 的特征向量。的特征向量。A的特征值和特征向量的特征值和特征向量第七十九页，本课件共有90页若若A是实对称阵，则是实对称阵，则C也是实对称阵也是实对称阵(CT=PTATP=PTAP=C),故故C为对称三对角阵，即为对称三对角阵，即关于实对称阵关于实对称阵第八十页，本课件共有90页4 QR方法方法是一种变换方法，计算一般中小型矩阵全部特征值的是一种变换方法，计算一般中小型矩阵全部特征值的最有效方法之一。最有效方法之一。主要用于计算：主要用于计算：1.1.上上Hessenberg阵的全部特征值阵的全部特征值;2.2.对

21、称三对角矩阵的全部特征值。对称三对角矩阵的全部特征值。对于一般矩阵或对称阵，先用对于一般矩阵或对称阵，先用Householder方法将其方法将其约化为上约化为上Hessenberg阵或对称三对角阵，再用阵或对称三对角阵，再用QR法法计算全部特征值。计算全部特征值。优点：算法稳定，收敛快。优点：算法稳定，收敛快。矩阵的矩阵的QR分解分解Lemma1（旋转对向量的作用）（旋转对向量的作用）第八十一页，本课件共有90页i行j行i列j列第八十二页，本课件共有90页证：证：P左乘左乘x只对的第只对的第i,j个元素有影响，其它元素不变。个元素有影响，其它元素不变。（旋转对矩阵的作用）（旋转对矩阵的作用）A

22、 A非奇异，则存在旋转阵非奇异，则存在旋转阵P1,P2,Pn,s.t.为上三角阵，且对角线元素为上三角阵，且对角线元素 Theorem2第八十三页，本课件共有90页证明：证明：A=A1非奇异，非奇异，A1的第一列一定存在的第一列一定存在ai10,1.若若ai10,由引理由引理1，存在旋转阵，存在旋转阵 ,s.t.2.同理，同理，若若 ,由引理由引理1,存在旋转阵存在旋转阵 ,s.t.第八十四页，本课件共有90页3.重复上述过程，得到重复上述过程，得到 ,s.t.矩阵的矩阵的QR分解分解Theorem3第八十五页，本课件共有90页下三角下三角正交阵正交阵上三角阵上三角阵证证(仅证唯一性，反正仅证唯一性，反正)：设：设第八十六页，本课件共有90页QR算法算法 第八十七页，本课件共有90页算法收敛性算法收敛性证明：Th4.在在QR算算法中，有法中，有 第八十八页，本课件共有90页Lemma5证证：第八十九页，本课件共有90页Theorem6(QR法的收敛性法的收敛性)A非奇异非奇异,且有且有n个不同的特征根：个不同的特征根：定理说明，定理说明，Ak收敛收敛于上三角阵，其对于上三角阵，其对角线上的元素就是角线上的元素就是A的特征值。的特征值。第九十页，本课件共有90页