[理学]第九章 矩阵特征值与特征向量的计算.ppt

2019/3/29,1,第九章 矩阵特征值与特征向量的计算,包括求个别特征值和全部特征值。, 幂法,内容:, 反幂法, Jacobi方法, 原点平移方法, QR算法简介,2019/3/29,2,9.1 求按模最大特征值的幂法,下面讨论求 的幂法。,令,易见，当k充分大时,2019/3/29,3,幂法的算法描述,取,但是考虑到，,我们要对v(k)进行归一化，即规范化幂法！,2019/3/29,4,规范化的幂法：,取,转(1);,(1),(2), 按模最大特征值, 对应的特征向量,注:,2019/3/29,5,幂法的收敛性分析:,(1),(2),幂法对于按模最大的特征值是重根的情形也适用！,2019/3/29,6,9.2 求按模最小特征值的反幂法,反幂法用来求A的按模最小的特征值。,其特征值满足,所对应的n个线性无关的特征向量为,下面计算 按模最小的特征值 及其对应的特征向量 ：,所以对 应用幂法即可！,收敛因子为 。,2019/3/29,7,算法如下：, A按模最小特征值；, 对应的特征向量。,注：,取,转(1);,(1),(2),2019/3/29,8,关于幂法和反幂法的说明:,由于幂法和反幂法的迭代是否收敛，依赖于特征值的分布情况，因此实际使用很不方便，特别不适合自动计算。,通常只是在没有其他更有效的方法的情况下，才利用幂法计算按模最大的特征值，利用反幂法计算按模最小的特征值。,(1),(2),2019/3/29,9,9.3 原点平移加速,所以希望 | 2 / 1 | 越小越好。,不妨设 1 2 n ， 1为A按模最大的特征值， 2为A按模次大的特征值，且 | 2 | | n |。,p = ( 2 + n ) / 2,令 B = ApE ，则有 | AE | = | (B+pE)E| = | B(p)E | A p = B 。选择p使得1 p为B按模最大的特征值， 2 p为B按模次大的特征值，并且使得 ，从而用幂法求B按模最大的特征值收敛更快！,我们知道，| 2 / 1 |决定幂法的收敛速度！,思路：,2019/3/29,10,若知道某一特征值 i 的大致位置 p ，即对任意 j i 有 | i p | | j p | ，并且 (A pI)1存在，,求指定点附近的某个特征值和特征向量:,则可以用反幂法求(A pI)的按模最小特征值 (i p ) ，及相应的特征向量，从而得到矩阵A在点p附近的特征值和相应的特征向量！,注：,幂法的加速和用反幂法求任意点附近特征值算法的有效性，依赖于对矩阵特征值分布的估计！难以实现自动计算！,反幂法和原点平移相结合，可以计算指定点附近的特征值和相应的特征向量。,收敛非常快！,2019/3/29,11,幂法综述,幂法和反幂法适用于求解可对角化矩阵的实数特征值和特征向量，不能求解复特征值；,幂法和反幂法均为线性收敛，收敛速度由收敛因子决定，效率不高；,原点位移法可以加快收敛速度；,可用于求指定特征值，不适于求解全部特征值。,求矩阵全部特征值和特征向量的算法：, QR方法, Jacobi方法,2019/3/29,12,若P为n阶可逆阵，则A与P1AP相似，且有相同的特征值。,若A对称，则存在正交阵Q ( QTQ = E )，使得,由高等代数的知识我们知道:,(1),(2),其中1, 2 , n 为A的特征值！ Q的列向量为对应的特征向量。,直接找Q比较困难！,当非对角元小得无足轻重时，, Jacobi方法,若可以构造一系列正交阵Q1,.,Qn对A作正交相似变换，,使得非对角元的绝对值逐渐变小。,可以近似认为此时的对角元就是A的所有特征值。,9.4 Jacobi方法(求实对称矩阵的全部特征值),2019/3/29,13,Givens旋转变换,设矩阵,称之为平面旋转矩阵或Givens变换矩阵。,将R n中p、q轴在其所确定的平面内逆时针旋转 角。,注：,2019/3/29,14,性质：,2019/3/29,15,平面旋转变换的意义是：通过平面旋转变换可把向量中某一分量变为零。,2019/3/29,16,记：,则：,由于变换的目的是为了削减非对角元，故可以选择 使得,(*),Jacobi方法,2019/3/29,17,记,则,所以，,保证|t|1, 稳定性,计算出矩阵B中相关元素！,接下来，给出Jacobi方法的计算步骤，,2019/3/29,18,取p,q使,Jacobi方法的计算步骤：,(1),(2),(3),输入实对称矩阵A，令Q=E，,根据(*)式计算矩阵B中的元素以及正交矩阵Q=Q*Q1 (Q1为旋转矩阵)；,(4),否则，令A=B，转(1);,计算,2019/3/29,19,Jacobi方法的收敛性：,定理：,1、 旋转后矩阵全部元素的平方和不变。,2、 旋转后矩阵非主对角线元素的平方和减少了！,3、 旋转后矩阵主对角线元素趋向于矩阵的特征值！,Jacobi方法的特点：,(1) 总是收敛的，当矩阵阶数不高时收敛较快；,(2) 精度较高，且特征向量具有正交性；,(3) 有较好的数值稳定性。,2019/3/29,20,9.5 QR方法,QR算法简介：,QR算法是电子计算机问世以来，计算数学的重大进展之一，是计算中小型稠密矩阵全部特征值和特征向量的最有效的方法！在某种意义是它是幂法的一种自然推广！,运用QR方法可以计算出A的所有特征值，与反幂法相结合就可以计算出对应的特征向量！,可以参考：徐树方，矩阵计算的理论与方法，北京大学出版社，1995。（P237）,2019/3/29,21,一、镜面反射变换,2019/3/29,22,镜面反射矩阵的意义是“成批”消去向量的非零元素。,证明：,2019/3/29,23,例：,解:,#,2019/3/29,24,二、QR分解,定理：任何mn阶实矩阵存在QR分解，特别实方阵存在QR分解。,应用: (求解线性方程组),2019/3/29,25,2019/3/29,26,用Householder变换