数值分析QR方法.pptx

《数值分析QR方法.pptx》由会员分享，可在线阅读，更多相关《数值分析QR方法.pptx（50页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第八讲矩阵特征值与特征向量的计算（2）-Jacobi方法和QR方法第三章 矩阵特征值与特征向量的计算第1页/共50页常用的求特征值的方法有 幂法与反幂法幂法与反幂法 JacobiJacobi法法 QRQR方法方法第2页/共50页上次课内容回顾 幂法可以用来求矩阵模最大的特征值和特征向量；反幂法可以用来求矩阵模最小的特征值和特征向量；理论上可以用带原点平移的反幂法求得矩阵所有特征值和特征向量；在用幂法与反幂法求矩阵特征值和特征向量时，初始值u0的第一个分量不要为零；当|1|=|2|，但1=-2 时，直接幂法失败；当|n-1|=|n|，但n-1=-n 时，直接反幂法失败；当是多重特征值时，幂法和反

2、幂法仍有效。第3页/共50页Jacobi法 只适用于只适用于实对称方阵实对称方阵 可以求出可以求出所有特征值和特征向量所有特征值和特征向量 第4页/共50页矩阵的两个重要的基本性质：（1）如 A 为实对称矩阵，则一定存在正交矩阵 Q，使之相似于一个对角矩阵，而该对角矩阵的对角元正是 A 的特征值。（2）一个矩阵左乘一个正交矩阵或右乘一个正交矩阵，其F范数(Frobenius)不变。第5页/共50页Jacobi法的基本原理 JacobiJacobi法基于的原理是：对一个实对称矩阵法基于的原理是：对一个实对称矩阵 A A一定存在一个正交矩阵一定存在一个正交矩阵 R(RR(R-1-1=R=RT T)

3、使得使得 R RT TAR=DAR=D，其中，其中 DDdiagddiagd1 1,d,d2 2,d,dn n。我们有。我们有 D D 的对角元素即为的对角元素即为 A A 的的特征值，对应的特征值，对应的 R R 的行向量即为相应的特征向量的行向量即为相应的特征向量 。思路：通过一系列的思路：通过一系列的旋转变换（正交变换）旋转变换（正交变换）把把A A中非对角线上的非零元变为零中非对角线上的非零元变为零 。第6页/共50页下面的矩阵是一个 n 阶正交矩阵：(p)(q)第7页/共50页旋转变换旋转变换 U Upqpq其元素特点：其元素特点：如果如果a apqpq00那么我们可以选取一个那么我

4、们可以选取一个，(A A(1)(1)仍为实对称矩阵）使得仍为实对称矩阵）使得 第8页/共50页A A(1)(1)的元素为：的元素为：选取选取满足满足我们就有我们就有 第9页/共50页JacobiJacobi法的算法法的算法 1.令令k1，R（1）I，给定矩阵，给定矩阵A（A（1），收敛条件），收敛条件2.找绝对值最大的找绝对值最大的3.计算计算，sinsin 和和 coscos，其中，其中满足满足4.4.计算计算A A（k k1 1）5.5.计算计算R R（k+1)k+1)6.6.如果如果 则停止，否则返回第则停止，否则返回第 2 2 步步第10页/共50页JacobiJacobi算法的收敛性

5、算法的收敛性定理定理：设：设A A是实对称矩阵，由是实对称矩阵，由JacobiJacobi方法第方法第k k次迭代得到的次迭代得到的矩阵记为矩阵记为A A（k k），记，记则有则有成立。成立。第11页/共50页QRQR方法方法 cf:矩阵计算矩阵计算，G.H.Golub&F.Van Loan 袁亚湘等译，第五章袁亚湘等译，第五章（5.1、5.2节）节）第12页/共50页QR方法是计算中小型矩阵特征值和特征向量的有效方法之一；QR方法最重要的一步是对A进行正交分解使得AQR，其中Q为一特殊正交矩阵；理论上，QR方法可以应用于任何矩阵，但对以下几类矩阵效率很高：1）对称三对角矩阵；2）Hessen

6、berg矩阵；3）对称带状矩阵第13页/共50页QRQR方法的理论依据方法的理论依据 定理（定理（实Schur分解定理）：设：设A A是一个是一个n n阶实方阵，那么存在一阶实方阵，那么存在一个正交矩阵个正交矩阵QQ使得使得A A相似于相似于 其中对角块为一阶或二阶方阵，每一个一阶对角块对应于其中对角块为一阶或二阶方阵，每一个一阶对角块对应于A A的一个实特征值，每一个二阶对角块的两个特征值是的一个实特征值，每一个二阶对角块的两个特征值是A A的一的一对共轭复特征值。对共轭复特征值。第14页/共50页QRQR方法的一般形式方法的一般形式由于由于 产生的矩阵序列产生的矩阵序列AAk k 中的每一

7、个中的每一个 矩阵都与矩阵都与A A有相同的特征值。有相同的特征值。要解决的问题是上述算法的要解决的问题是上述算法的工作量和工作量和QQ的选择的选择！定理定理：对任意实方阵：对任意实方阵A A，由，由QRQR方法产生的方法产生的矩阵序列矩阵序列AAk k 本质上收敛于分块上三角矩本质上收敛于分块上三角矩阵（对角块以上的元素可能不收敛！），阵（对角块以上的元素可能不收敛！），其中对角块为一阶或二阶方阵，每一个一其中对角块为一阶或二阶方阵，每一个一阶对角块对应于阶对角块对应于A A的一个实特征值，每一的一个实特征值，每一个二阶对角块的两个特征值是个二阶对角块的两个特征值是A A的一对共的一对共轭复

8、特征值。轭复特征值。第15页/共50页QQ的选择的选择HouseholderHouseholder矩阵（镜面映象变换）矩阵（镜面映象变换）定义定义：设：设 为为n n维单位向量，即维单位向量，即 T T =1=1 ；H H=I-2=I-2T T HouseholderHouseholder变换（矩阵）变换（矩阵）（1 1）HouseholderHouseholder矩阵是正交矩阵矩阵是正交矩阵(2)(3)记S为与w垂直的平面,则几何上x与y=Hx关于平面S对称。事实上,由第16页/共50页几何意义xwyx-y上式表明向量x-y与w平行，注意到y与x的长度相等，于是x经变换后的象y=Hx是x关于

9、s对称的向量，如图所示。第17页/共50页 引理引理3.13.1：设有非零向量：设有非零向量s s和单位向量和单位向量e e，则必存在，则必存在HouseholderHouseholder矩阵矩阵H H使得使得HsHs e e，其中，其中 是实数是实数且且第18页/共50页与平面旋转不同的是，镜面反射变换可成批的消去向量的非零元。第19页/共50页 定理定理：设：设A A是一个是一个n n阶实方阵，那么阶实方阵，那么A A可分解为一个正交矩阵可分解为一个正交矩阵QQ和一个上三角矩阵和一个上三角矩阵R R的乘积，的乘积，A AQRQR第20页/共50页第21页/共50页第22页/共50页第23页

10、/共50页第24页/共50页第25页/共50页第26页/共50页第27页/共50页第28页/共50页减少减少QRQR算法的工作量矩阵的拟上三角化算法的工作量矩阵的拟上三角化第29页/共50页第30页/共50页第31页/共50页第32页/共50页第33页/共50页第34页/共50页第35页/共50页 把把A A变成变成HessenbergHessenberg矩阵（拟上三角矩阵）的目是减少矩阵（拟上三角矩阵）的目是减少QRQR方法的计算量；方法的计算量；把把A A变成变成HessenbergHessenberg矩阵（拟上三角矩阵）能够减少矩阵（拟上三角矩阵）能够减少QRQR方法计算量的主方法计算量

11、的主要原因是要原因是1.1.对拟上三角矩阵的对拟上三角矩阵的QRQR分解时，分解时，QQ一定是拟上三角矩阵；一定是拟上三角矩阵；2.2.RQRQ（A Ak k 1 1）的乘积为拟上三角矩阵。）的乘积为拟上三角矩阵。第36页/共50页QRQR方法方法定理定理：对任意实方阵：对任意实方阵A A，由，由QRQR方法产生的矩阵序列方法产生的矩阵序列AAk k 本本质上收敛于分块上三角矩阵（对角块以上的元素可能不收质上收敛于分块上三角矩阵（对角块以上的元素可能不收敛！），其中对角块为一阶或二阶方阵，每一个一阶对角敛！），其中对角块为一阶或二阶方阵，每一个一阶对角块对应于块对应于A A的一个实特征值，每一

12、个二阶对角块的两个特的一个实特征值，每一个二阶对角块的两个特征值是征值是A A的一对共轭复特征值。的一对共轭复特征值。第37页/共50页QRQR方法的加速方法的加速带原点位移的QR 方法尽管通过尽管通过HouseholderHouseholder矩阵已把矩阵矩阵已把矩阵A A相似地变成为相似地变成为HessenbergHessenberg矩阵从而已减少了矩阵从而已减少了QRQR方法的不少工作量，但上述方法的不少工作量，但上述方法工作量仍太大，其中主要工作量在第二步的方法工作量仍太大，其中主要工作量在第二步的QRQR分解和收分解和收敛速度问题！敛速度问题！第38页/共50页带原点位移的QR 方法

13、为加速收敛，每次选取位移 ，作该矩阵序列有如下性质：（1）（2）如 为拟上三角，则 也为拟上三角矩阵（拟上三角矩阵指的是次对角线下的元素为零的矩阵）（3）如取位移 为 ，则 最后一行非对角元二阶收敛于零（特别对于对称矩阵，能达到三阶收敛），其余次对角元收敛于零的速度会慢一些。第39页/共50页加速技术下的算法：（1）确定计算精度10E-m（2）对矩阵 取加速因子 进行加速（3）判断矩阵 的最后一行非对角元素是否小于要求的精度，如果不小于，继续加速迭代，如已经小于精度，停止计算，并划掉矩阵的最后一行和最后一列，产生一个子矩阵（4）对子矩阵重复进行上面的加速计算第40页/共50页带原点位移的QR

14、方法的总结：（1）利用Householder矩阵，将矩阵 A 相似于拟上三角矩阵（尤其，对于对称矩阵可以化为三对角矩阵）（2）利用带原点位移的QR 方法构造矩阵序列（3）对矩阵 取加速因子 进行加速（4）判断矩阵 的最后一行非对角元素（由于是拟上三角矩阵，只有一个元素 ）是否小于要求的精度（5）如已经小于精度，停止计算，并划掉矩阵的最后一行和最后一列，产生一个子矩阵，对子矩阵重复进行上面的加速计算。第41页/共50页QRQR方法的加速方法的加速2 2带双步位移的带双步位移的QRQR方法方法尽管通过尽管通过HouseholderHouseholder矩阵已把矩阵矩阵已把矩阵A A相似地变成为相似地变成为HessenbergHessenberg矩阵从而已减少了矩阵从而已减少了QRQR方法的不少工作量，但上述方法的不少工作量，但上述方法工作量仍太大，其中主要工作量在第二步的方法工作量仍太大，其中主要工作量在第二步的QRQR分解和收分解和收敛速度问题！敛速度问题！第42页/共50页第43页/共50页第44页/共50页第45页/共50页第46页/共50页第47页/共50页作业教材第66页习题8、10、12课外阅读第48页/共50页第49页/共50页感谢您的观看！第50页/共50页