4.5QR方法.ppt

4.5 QR方法方法 QR方法是一种变换方法，是计算一般矩阵全部特征方法是一种变换方法，是计算一般矩阵全部特征值以及特征向量的最有效的方法之一。主要用来计算值以及特征向量的最有效的方法之一。主要用来计算Hessenberg阵的全部特征值和对称三角阵的全部特征值阵的全部特征值和对称三角阵的全部特征值.对于一般矩阵对于一般矩阵A，先用，先用household变换将其约化为变换将其约化为Hessenberg矩阵或是对称三对角矩阵矩阵或是对称三对角矩阵B，然后用，然后用QR方法计算方法计算B的全部特征值。的全部特征值。理论依据：任一实矩阵都可分解成一个正交矩阵Q和一个上三角矩阵R的乘积，而且当R的对角元符号取定时，分解是唯一的。4.5.1 基本基本QR方法方法一个结论：一个结论：QR算法算法.什么时候停止迭代？什么时候停止迭代？迭代步数k充分大时，由迭代格式产生的Ak的次对角元趋于0.在 实 际计算中，控制迭代次数常用的一种办法是，预先给定一个小的正数在一个迭代步的计 算结束后，对i=n-1,n-2,，1，依次判别次对角元的绝对值是否满足 或更严格的准则是 或不太严格的准则是 如果上面三个不等式中有一个成立，把 看做实际上为零直到直到 Ak+1 收敛到一个收敛到一个 拟上三角阵拟上三角阵QR 迭代算法迭代算法l 计算矩阵的所有特征值和特征向量计算矩阵的所有特征值和特征向量l 计算过程计算过程(1)令令 A1A(2)对对 k=1,2,.，计算计算 Ak 的的 QR 分解分解 计算计算直到直到 Ak+1 收敛到一个收敛到一个 拟上三角阵拟上三角阵证明：Th4.11在在QR算算法中，有法中，有 4.5.2 QR方法的收敛性方法的收敛性引理继续这一过程继续这一过程定义定义4.5 由由QR算法产生算法产生如果当如果当时时收敛于分块三角矩阵，则算法收敛于分块三角矩阵，则算法QR是收敛的。是收敛的。趋于分块上三角形式，其对角块为一阶或者二阶趋于分块上三角形式，其对角块为一阶或者二阶若若子块，即子块，即的对角线下方趋于的对角线下方趋于0，则称算法是本质或者，则称算法是本质或者基本收敛基本收敛定理定理4.12 基本基本QR方法每次迭代都需作一次方法每次迭代都需作一次QR分解与矩分解与矩阵乘法，计算量大，而且收敛速度慢。因此实际阵乘法，计算量大，而且收敛速度慢。因此实际使用的使用的QR方法是先用一系列矩阵相似变换将方法是先用一系列矩阵相似变换将 A 约约化成拟上三角矩阵化成拟上三角矩阵(称为上称为上Hessenberg 矩阵矩阵)，然，然后对此矩阵用基本后对此矩阵用基本QR方法。因为拟上三角矩阵具方法。因为拟上三角矩阵具有较多零元素，故可减少运算量。化有较多零元素，故可减少运算量。化A为相似的拟为相似的拟上三角阵的方法有多种。上三角阵的方法有多种。4.5.3、带原点移位的、带原点移位的QR方法方法4.5.4.单步QR方法计算上Hessenberg矩阵特征值例例 试用带平移量的单步QR算法，计算的全部特征值。4.5.5 上Hessenberg矩阵双步QR算法