最新数值分析--第8-9讲-QR方法教学讲义PPT课件.ppt

《最新数值分析--第8-9讲-QR方法教学讲义PPT课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数值分析--第8-9讲-QR方法第八讲矩阵特征值与特征向量的计算（2）----Jacobi方法和QR方法第三章矩阵特征值与特征向量的计算常用的求特征值的方法有幂法与反幂法Jacobi法QR方法Jacobi法的基本原理Jacobi法基于的原理是：对一个实对称矩阵A一定存在一个正交矩阵R(R-1=RT)使得RTAR=D，其中D＝diag[d1,d2,…,dn]。我们有D的对角元素即为A的特征值，对应的R的行向量即为相应的特征向量。思路：通过一系列的旋转变换（正交变换）把A中非对角线上的非零元变为零。下面的矩阵是一个n阶正交矩阵：

2、(p)(q)旋转变换Upq其元素特点：如果apq≠0那么我们可以选取一个φ，(A(1)仍为实对称矩阵）使得A(1)的元素为：选取φ满足我们就有Jacobi法的算法令k＝1，R（1）＝I，给定矩阵A（＝A（1）），收敛条件ε找绝对值最大的计算φ，sinφ和cosφ，其中φ满足计算A（k＋1）计算R（k+1)如果则停止，否则返回第2步Jacobi算法的收敛性定理：设A是实对称矩阵，由Jacobi方法第k次迭代得到的矩阵记为A（k），记则有成立。QR方法cf:《矩阵计算》，G.H.Golub&F.VanLoan袁亚湘等译，第五章（

3、5.1、5.2节）QR方法是计算中小型矩阵特征值和特征向量的有效方法之一；QR方法最重要的一步是对A进行正交分解使得A＝QR，其中Q为一特殊正交矩阵；理论上，QR方法可以应用于任何矩阵，但对以下几类矩阵效率很高：1）对称三对角矩阵；2）Hessenberg矩阵；3）对称带状矩阵QR方法的理论依据定理（实Schur分解定理）：设A是一个n阶实方阵，那么存在一个正交矩阵Q使得A相似于其中对角块为一阶或二阶方阵，每一个一阶对角块对应于A的一个实特征值，每一个二阶对角块的两个特征值是A的一对共轭复特征值。QR方法的一般形式由于产生的

4、矩阵序列{Ak}中的每一个矩阵都与A有相同的特征值。要解决的问题是上述算法的工作量和Q的选择！定理：对任意实方阵A，由QR方法产生的矩阵序列{Ak}本质上收敛于分块上三角矩阵（对角块以上的元素可能不收敛！），其中对角块为一阶或二阶方阵，每一个一阶对角块对应于A的一个实特征值，每一个二阶对角块的两个特征值是A的一对共轭复特征值。Q的选择－Householder矩阵（镜面映象变换）定义：设υ为n维单位向量，即υTυ=1；H=I-2υυTHouseholder变换（矩阵）（1）Householder矩阵是正交矩阵(2)(3)记S为

5、与w垂直的平面,则几何上x与y=Hx关于平面S对称。事实上,由几何意义xwyx-y上式表明向量x-y与w平行，注意到y与x的长度相等，于是x经变换后的象y=Hx是x关于s对称的向量，如图所示。引理3.1：设有非零向量s和单位向量e，则必存在Householder矩阵H使得Hs＝±αe，其中α是实数且与平面旋转不同的是，镜面反射变换可成批的消去向量的非零元。定理：设A是一个n阶实方阵，那么A可分解为一个正交矩阵Q和一个上三角矩阵R的乘积，A＝QR减少QR算法的工作量－－矩阵的拟上三角化把A变成Hessenberg矩阵（拟上三角

6、矩阵）的目是减少QR方法的计算量；把A变成Hessenberg矩阵（拟上三角矩阵）能够减少QR方法计算量的主要原因是对拟上三角矩阵的QR分解时，Q一定是拟上三角矩阵；RQ（＝Ak＋1）的乘积为拟上三角矩阵。QR方法定理：对任意实方阵A，由QR方法产生的矩阵序列{Ak}本质上收敛于分块上三角矩阵（对角块以上的元素可能不收敛！），其中对角块为一阶或二阶方阵，每一个一阶对角块对应于A的一个实特征值，每一个二阶对角块的两个特征值是A的一对共轭复特征值。QR方法的加速－带原点位移的QR方法尽管通过Householder矩阵已把矩阵A相

7、似地变成为Hessenberg矩阵从而已减少了QR方法的不少工作量，但上述方法工作量仍太大，其中主要工作量在第二步的QR分解和收敛速度问题！带原点位移的QR方法为加速收敛，每次选取位移，作该矩阵序列有如下性质：（1）（2）如为拟上三角，则也为拟上三角矩阵（拟上三角矩阵指的是次对角线下的元素为零的矩阵）（3）如取位移为，则最后一行非对角元二阶收敛于零（特别对于对称矩阵，能达到三阶收敛），其余次对角元收敛于零的速度会慢一些。加速技术下的算法：（1）确定计算精度10E-m（2）对矩阵取加速因子进行加速（3）判断矩阵的最后一行非对角

8、元素是否小于要求的精度，如果不小于，继续加速迭代，如已经小于精度，停止计算，并划掉矩阵的最后一行和最后一列，产生一个子矩阵（4）对子矩阵重复进行上面的加速计算带原点位移的QR方法的总结：（1）利用Householder矩阵，将矩阵A相似于拟上三角矩阵（尤其，对于对称矩阵可以化为三对角矩阵）