数值分析第8章——矩阵特征值问题计算.ppt

用正交变换化对称矩阵为对称三对角阵 带原点位移的QR算法 用单步QR方法计算上Hessenberg特征值 设A为n阶实对称矩阵，称 为向量 x 的瑞利商，其中 ( x, x)= xT x 为内积。不难证明，对实对称矩阵A，如果其特征值满足 2、瑞利商加速 由幂法公式生成的 xk 的瑞利商满足 由此可见，R(xk) 比 mk 更快的收敛于?1 。 幂法的瑞利商加速迭代公式为 其中A为n阶实对称矩阵。 对给定的误差限 ? ，当 | mk – mk-1 | ? 时，取 三、反幂法 反幂法是用于求非奇异矩阵A的按模最小的特征值和对应特征向量的方法. 而结合原点平移法的反幂法则可以求矩阵A的任何一个具有先验了解的特征值和对应的特征向量。 设矩阵A非奇异,其特征值?i (i=1,2,…,n) ,满足 其相应的特征向量 x1 , x2, …, xn 线性无关,则 A-1 的特征值为1/ ?i ，对应的特征向量仍为 xi (i=1,2, …,n). 此时,A-1 的特征值满足 因此,对 A-1 应用幂法,可求出其主特征值 1/ ?n ? 和特征向量 xn ? uk , 从而求得A的按模最小特征值 ?n ? 1/ 和对应的特征向量 xn ? uk ， 这种方法称为反幂法。 为了避免求 A-1 ,可通过解线性方程组A vk= uk-1 得到yk ，采用LU分解,即先对 A 进行LU分解 A=LU , 此时反幂法的迭代公式为 对给定的误差 ? ，当 | – | ? 时，得 显然，反幂法的收敛速度取决于比值 ，比值越小，收敛越快。 例3 用反幂法求矩阵 的对应于特征值 的特征向量 解 取 解方程组 得 解方程组 得 与 的对应分向量大体上成正比, 所以对应于 的特征向量为 QR 算法也是一种迭代算法,是目前计算任意实的非奇异矩阵全部特征值问题的最有效的方法之一.该方法的基础是构造矩阵序列 ,并对它进行QR 分解. 由线性代数知识知道,若A 为非奇异方阵,则A 可以分解为正交矩阵Q 与三角形矩阵R 的乘积,即A=QR ,而且当R的对角线元素符号取定时,分解式是唯一的. 8.4 QR算法 若A为奇异方阵,则零为A的特征值.任取一数 p 不是A 的特征值,则 A-pI 为非奇异方阵.只要求出 A-pI 的特征值,就很容易求出A的特征值, 所以假设A 为非奇异方阵,并不防碍讨论的一般性. 设A 为非奇异方阵,令 , 对 进行QR 分解, 即把 分解为正交矩阵 与上三角形矩阵 的乘积 作矩阵 继续对 进行QR分解 并定义 一般地,递推公式为 QR 算法就是利用矩阵的QR 分解,按上述递推公 式构造矩阵序列 .只要A 为非奇异方阵,则由QR算 法就完全确定 这个矩阵序列 具有如下性质. 性质1 所有都相似,它们具有相同的特征值. 证明 因为 若令 , 则 为正交阵,且有 因此 与A 相似,他们具有相同的 特征值. 性质2 的 QR 分解式为 其中 证明 用归纳法. 显然当 k=1 时,有 假设 有分解式 于是 因为 , 所以 定理 1 如果 收敛于非奇异矩阵 , 为上三 角形矩阵,则 存在并