数值分析-第8-9讲-QR方法.ppt

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

1、数值分析数值分析朱立永朱立永北京航空航天大学 数学与系统科学学院Password:beihang答疑时间：星期四下午2:305:30答疑地点：主216数值分析数值分析第八讲矩阵特征值与特征向量的计算（2）-Jacobi方法和QR方法第三章 矩阵特征值与特征向量的计算数值分析数值分析常用的求特征值的方法有幂法与反幂法 Jacobi法 QR方法数值分析数值分析上次课内容回顾 幂法可以用来求矩阵模最大的特征值和特征向量；幂法可以用来求矩阵模最大的特征值和特征向量；反幂法可以用来求矩阵模最小的特征值和特征向量；反幂法可以用来求矩阵模最小的特征值和特征向量；理论上可以用带原点平移的反幂法求得矩阵所有特征

2、理论上可以用带原点平移的反幂法求得矩阵所有特征值和特征向量；值和特征向量；在用在用幂幂法与反法与反幂幂法求矩法求矩阵阵特征特征值值和特征向量和特征向量时时，初始，初始值值u0的第一个分量不要的第一个分量不要为为零；零；当当|1|=|2|，但，但1=-2 时时，直接，直接幂幂法失法失败败；当；当|n-1|=|n|，但，但n-1=-n 时时，直接反，直接反幂幂法失法失败败；当是多重特征当是多重特征值时值时，幂幂法和反法和反幂幂法仍有效。法仍有效。数值分析数值分析Jacobi法 只适用于实对称方阵可以求出所有特征值和特征向量 数值分析数值分析矩阵的两个重要的基本性质：矩阵的两个重要的基本性质：（1）

3、如）如 A 为实对称矩阵，则一定存在正交矩阵为实对称矩阵，则一定存在正交矩阵 Q，使之相似，使之相似于一个对角矩阵，而该对角矩阵的对角元正是于一个对角矩阵，而该对角矩阵的对角元正是 A 的特征值。的特征值。（2）一个矩阵左乘一个正交矩阵或右乘一个正交矩阵，其）一个矩阵左乘一个正交矩阵或右乘一个正交矩阵，其F范范数数(Frobenius)不变。不变。数值分析数值分析Jacobi法的基本原理Jacobi法基于的原理是：对一个实对称矩阵法基于的原理是：对一个实对称矩阵 A一定存在一个正交矩阵一定存在一个正交矩阵 R(R-1=RT)使得使得 RTAR=D，其中，其中 Ddiagd1,d2,dn。我。我

4、们有们有 D 的对角元素即为的对角元素即为 A 的特征值，对应的的特征值，对应的 R 的行向量即为相应的特征向量的行向量即为相应的特征向量。思路：通过一系列的思路：通过一系列的旋转变换（正交变换）旋转变换（正交变换）把把A中非对角线上的非零元变为零中非对角线上的非零元变为零。数值分析数值分析下面的矩阵是下面的矩阵是一个一个 n 阶正交矩阵：阶正交矩阵：(p)(q)数值分析数值分析旋转变换旋转变换旋转变换旋转变换 U Upqpq其元素特点：其元素特点：其元素特点：其元素特点：如果如果如果如果a apqpq00那么我那么我那么我那么我们们们们可以可以可以可以选选选选取一个取一个取一个取一个，(A

5、A(1)(1)仍仍仍仍为实对为实对为实对为实对称矩称矩称矩称矩阵阵阵阵）使得）使得）使得）使得 数值分析数值分析A A(1)(1)的元素为：的元素为：的元素为：的元素为：选选选选取取取取满足满足满足满足我们就有我们就有我们就有我们就有 数值分析数值分析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.如果如果 则停止，否停止，否则返回第返回第

6、 2 2 步步数值分析数值分析JacobiJacobi算法的收敛性算法的收敛性算法的收敛性算法的收敛性定理定理定理定理：设：设：设：设A A是实对称矩阵，由是实对称矩阵，由是实对称矩阵，由是实对称矩阵，由JacobiJacobi方法第方法第方法第方法第k k次迭代得到次迭代得到次迭代得到次迭代得到的矩阵记为的矩阵记为的矩阵记为的矩阵记为A A（k k），记，记，记，记则有则有则有则有成立。成立。成立。成立。数值分析数值分析QR方法方法 cf:矩阵计算矩阵计算，G.H.Golub&F.Van Loan 袁亚湘等译，第五章袁亚湘等译，第五章（5.1、5.2节）节）数值分析数值分析QR方法是计算中小

7、型矩阵特征值和特征向方法是计算中小型矩阵特征值和特征向量的有效方法之一；量的有效方法之一；QR方法最重要的一步是对方法最重要的一步是对A进行正交分解进行正交分解使得使得AQR，其中，其中Q为一特殊正交矩阵；为一特殊正交矩阵；理论上，理论上，QR方法可以应用于任何矩阵，但方法可以应用于任何矩阵，但对以下几类矩阵效率很高：对以下几类矩阵效率很高：1）对称三对角）对称三对角矩阵；矩阵；2）Hessenberg矩阵；矩阵；3）对称带状）对称带状矩阵矩阵数值分析数值分析QRQR方法的理论依据方法的理论依据方法的理论依据方法的理论依据 定理（定理（定理（定理（实实Schur分解定理分解定理）：设：设：设：

8、设A A是一个是一个是一个是一个n n阶实方阵，那么阶实方阵，那么阶实方阵，那么阶实方阵，那么存在一个正交矩阵存在一个正交矩阵存在一个正交矩阵存在一个正交矩阵QQ使得使得使得使得A A相似于相似于相似于相似于 其中对角块为一阶或二阶方阵，每一个一阶对角块对应于其中对角块为一阶或二阶方阵，每一个一阶对角块对应于其中对角块为一阶或二阶方阵，每一个一阶对角块对应于其中对角块为一阶或二阶方阵，每一个一阶对角块对应于A A的一个实特征值，每一个二阶对角块的两个特征值是的一个实特征值，每一个二阶对角块的两个特征值是的一个实特征值，每一个二阶对角块的两个特征值是的一个实特征值，每一个二阶对角块的两个特征值是

9、A A的的的的一对共轭复特征值。一对共轭复特征值。一对共轭复特征值。一对共轭复特征值。数值分析数值分析QRQR方法的一般形式方法的一般形式方法的一般形式方法的一般形式由于由于由于由于 产生的矩阵序列产生的矩阵序列产生的矩阵序列产生的矩阵序列AAk k 中的每一个中的每一个中的每一个中的每一个 矩阵都与矩阵都与矩阵都与矩阵都与A A有相同的特征值。有相同的特征值。有相同的特征值。有相同的特征值。要解决的问题是上述算法的要解决的问题是上述算法的要解决的问题是上述算法的要解决的问题是上述算法的工作量和工作量和工作量和工作量和QQ的选择的选择的选择的选择！定理定理定理定理：对任意实方阵：对任意实方阵：

10、对任意实方阵：对任意实方阵A A，由，由，由，由QRQR方法产生的方法产生的方法产生的方法产生的矩阵序列矩阵序列矩阵序列矩阵序列AAk k 本质上收敛于分块上三角矩本质上收敛于分块上三角矩本质上收敛于分块上三角矩本质上收敛于分块上三角矩阵（对角块以上的元素可能不收敛！），阵（对角块以上的元素可能不收敛！），阵（对角块以上的元素可能不收敛！），阵（对角块以上的元素可能不收敛！），其中对角块为一阶或二阶方阵，每一个一其中对角块为一阶或二阶方阵，每一个一其中对角块为一阶或二阶方阵，每一个一其中对角块为一阶或二阶方阵，每一个一阶对角块对应于阶对角块对应于阶对角块对应于阶对角块对应于A A的一个实特征值

11、，每一的一个实特征值，每一的一个实特征值，每一的一个实特征值，每一个二阶对角块的两个特征值是个二阶对角块的两个特征值是个二阶对角块的两个特征值是个二阶对角块的两个特征值是A A的一对共的一对共的一对共的一对共轭复特征值。轭复特征值。轭复特征值。轭复特征值。数值分析数值分析QQ的选择的选择的选择的选择HouseholderHouseholder矩阵（镜面映象变换）矩阵（镜面映象变换）矩阵（镜面映象变换）矩阵（镜面映象变换）定义定义定义定义：设：设：设：设 为为为为n n n n维单位向量，即维单位向量，即维单位向量，即维单位向量，即 T T =1=1 ；H H=I-2=I-2T T Househ

12、olderHouseholder变换（矩阵）变换（矩阵）变换（矩阵）变换（矩阵）（1 1）HouseholderHouseholder矩阵是正交矩阵矩阵是正交矩阵矩阵是正交矩阵矩阵是正交矩阵(2)(3)记S为与w垂直的平面,则几何上x与y=Hx关于平面S对称。事实上,由数值分析数值分析几何意义xwyx-y上式表明向量x-y与w平行，注意到y与x的长度相等，于是x经变换后的象y=Hx是x关于s对称的向量，如图所示。数值分析数值分析 引理引理引理引理3.13.1：设有非零向量：设有非零向量：设有非零向量：设有非零向量s s和单位向量和单位向量和单位向量和单位向量e e，则必存在，则必存在，则必存在

13、，则必存在HouseholderHouseholder矩阵矩阵矩阵矩阵H H使得使得使得使得HsHs e e e e，其中，其中，其中，其中 是实数是实数是实数是实数且且且且数值分析数值分析与平面旋转不同的是，镜面反射变换可成批的消去向量的非零元。数值分析数值分析 定理定理定理定理：设：设：设：设A A是一个是一个是一个是一个n n阶实方阵，那么阶实方阵，那么阶实方阵，那么阶实方阵，那么A A可分解为一个正交矩阵可分解为一个正交矩阵可分解为一个正交矩阵可分解为一个正交矩阵QQ和一个上三角矩阵和一个上三角矩阵和一个上三角矩阵和一个上三角矩阵R R的乘积，的乘积，的乘积，的乘积，A AQRQR数值

14、分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析减少减少减少减少QRQR算法的工作量矩阵的拟上三角化算法的工作量矩阵的拟上三角化算法的工作量矩阵的拟上三角化算法的工作量矩阵的拟上三角化数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析把把A变成变成Hessenberg矩阵（拟上三角矩矩阵（拟上三角矩阵）的目是减少阵）的目是减少QR方法的计算量；方法的计算量；把把A变成变成Hessenberg矩阵（拟上三角矩矩阵（拟上三角矩阵）能够减少阵）能够

15、减少QR方法计算量的主要原因方法计算量的主要原因是是1.对拟上三角矩阵的对拟上三角矩阵的对拟上三角矩阵的对拟上三角矩阵的QRQR分解时，分解时，分解时，分解时，QQ一定是拟上一定是拟上一定是拟上一定是拟上三角矩阵；三角矩阵；三角矩阵；三角矩阵；2.RQRQ（A Ak k1 1）的乘积为拟上三角矩阵。）的乘积为拟上三角矩阵。）的乘积为拟上三角矩阵。）的乘积为拟上三角矩阵。数值分析数值分析QRQR方法方法方法方法定理定理定理定理：对任意实方阵：对任意实方阵：对任意实方阵：对任意实方阵A A，由，由，由，由QRQR方法产生的矩阵序列方法产生的矩阵序列方法产生的矩阵序列方法产生的矩阵序列AAk k 本

16、本本本质上收敛于分块上三角矩阵（对角块以上的元素可能不收质上收敛于分块上三角矩阵（对角块以上的元素可能不收质上收敛于分块上三角矩阵（对角块以上的元素可能不收质上收敛于分块上三角矩阵（对角块以上的元素可能不收敛！），其中对角块为一阶或二阶方阵，每一个一阶对角敛！），其中对角块为一阶或二阶方阵，每一个一阶对角敛！），其中对角块为一阶或二阶方阵，每一个一阶对角敛！），其中对角块为一阶或二阶方阵，每一个一阶对角块对应于块对应于块对应于块对应于A A的一个实特征值，每一个二阶对角块的两个特的一个实特征值，每一个二阶对角块的两个特的一个实特征值，每一个二阶对角块的两个特的一个实特征值，每一个二阶对角块的两

17、个特征值是征值是征值是征值是A A的一对共轭复特征值。的一对共轭复特征值。的一对共轭复特征值。的一对共轭复特征值。数值分析数值分析QRQR方法的加速方法的加速方法的加速方法的加速带原点位移的带原点位移的QR 方法方法尽管通过尽管通过尽管通过尽管通过HouseholderHouseholder矩阵已把矩阵矩阵已把矩阵矩阵已把矩阵矩阵已把矩阵A A相似地变成为相似地变成为相似地变成为相似地变成为HessenbergHessenberg矩阵从而已减少了矩阵从而已减少了矩阵从而已减少了矩阵从而已减少了QRQR方法的不少工作量，但上述方法的不少工作量，但上述方法的不少工作量，但上述方法的不少工作量，但上

18、述方法工作量仍太大，其中主要工作量在第二步的方法工作量仍太大，其中主要工作量在第二步的方法工作量仍太大，其中主要工作量在第二步的方法工作量仍太大，其中主要工作量在第二步的QRQR分解和收分解和收分解和收分解和收敛速度问题！敛速度问题！敛速度问题！敛速度问题！数值分析数值分析带原点位移的带原点位移的QR 方法方法为加速收敛，每次选取位移为加速收敛，每次选取位移 ，作，作该矩阵序列有如下性质：该矩阵序列有如下性质：（1）（2）如）如 为拟上三角，则为拟上三角，则 也为拟上三角矩阵（拟上三角也为拟上三角矩阵（拟上三角矩阵指的是次对角线下的元素为零的矩阵）矩阵指的是次对角线下的元素为零的矩阵）（3）如

19、取位移）如取位移 为为 ，则，则 最后一行非对角元二阶收最后一行非对角元二阶收敛于零（特别对于对称矩阵，能达到三阶收敛），其余次对敛于零（特别对于对称矩阵，能达到三阶收敛），其余次对角元收敛于零的速度会慢一些。角元收敛于零的速度会慢一些。数值分析数值分析加速技术下的算法：加速技术下的算法：（1）确定计算精度）确定计算精度10E-m（2）对矩阵）对矩阵 取加速因子取加速因子 进行加速进行加速（3）判断矩阵）判断矩阵 的最后一行非对角元素是否小于要求的精的最后一行非对角元素是否小于要求的精度，如果不小于，继续加速迭代，如已经小于精度，停止计度，如果不小于，继续加速迭代，如已经小于精度，停止计算，并

20、划掉矩阵的最后一行和最后一列，产生一个子矩阵算，并划掉矩阵的最后一行和最后一列，产生一个子矩阵（4）对子矩阵重复进行上面的加速计算）对子矩阵重复进行上面的加速计算数值分析数值分析带原点位移的带原点位移的QR 方法的总结：方法的总结：（1）利用）利用Householder矩阵，将矩阵矩阵，将矩阵 A 相似于拟上三角矩阵相似于拟上三角矩阵（尤其，对于对称矩阵可以化为三对角矩阵）（尤其，对于对称矩阵可以化为三对角矩阵）（2）利用）利用带原点位移的带原点位移的QR 方法构造矩阵序列方法构造矩阵序列（3）对矩阵对矩阵 取加速因子取加速因子 进行加速进行加速（4）判断矩阵）判断矩阵 的最后一行非对角元素（

21、由于是拟上三角的最后一行非对角元素（由于是拟上三角矩阵，只有一个元素矩阵，只有一个元素 ）是否小于要求的精度）是否小于要求的精度（5）如已经小于精度，停止计算，并划掉矩阵的最后一行和）如已经小于精度，停止计算，并划掉矩阵的最后一行和最后一列，产生一个子矩阵，对子矩阵重复进行上面的加最后一列，产生一个子矩阵，对子矩阵重复进行上面的加速计算。速计算。数值分析数值分析QRQR方法的加速方法的加速方法的加速方法的加速2 2带双步位移的带双步位移的带双步位移的带双步位移的QRQR方法方法方法方法尽管通过尽管通过尽管通过尽管通过HouseholderHouseholder矩阵已把矩阵矩阵已把矩阵矩阵已把矩

22、阵矩阵已把矩阵A A相似地变成为相似地变成为相似地变成为相似地变成为HessenbergHessenberg矩阵从而已减少了矩阵从而已减少了矩阵从而已减少了矩阵从而已减少了QRQR方法的不少工作量，但上述方法的不少工作量，但上述方法的不少工作量，但上述方法的不少工作量，但上述方法工作量仍太大，其中主要工作量在第二步的方法工作量仍太大，其中主要工作量在第二步的方法工作量仍太大，其中主要工作量在第二步的方法工作量仍太大，其中主要工作量在第二步的QRQR分解和收分解和收分解和收分解和收敛速度问题！敛速度问题！敛速度问题！敛速度问题！数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析数值分析作业教材第66页习题8、10、12课外阅读数值分析数值分析