特征值和特征向量的数值算法.pptx

《特征值和特征向量的数值算法.pptx》由会员分享，可在线阅读，更多相关《特征值和特征向量的数值算法.pptx（24页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、我们称这种分块上三交阵为矩阵A的Schur分块上三角阵，上三角阵和对角阵是它的特殊情形。定理7.9并没有解决如何计算全部特征的问题。7.4.1 化矩阵为化矩阵为Hessenberg形形对于实对称矩阵，可通过正交相似变换约化为对角矩阵。那么，对于一般的实矩阵，通过正交相似变换可约化到什么程度呢？线性代数中有如下结果。定理定理7.9（实实Schur分解定理分解定理）第1页/共24页定义定义7.2(ij+1),则称B为上Hessenberg矩阵，简称Hessenberg形，即B的形状为可以用平面旋转变换化矩阵为Hessenberg形,下面介绍另一种正交变换。为了节省运算工作量，实用的方法是先将矩阵约

2、化为与Schur分块上三角阵很近似的Hessenberg形。第2页/共24页定义定义7.3（7.4.1）为为（初等）镜面反射矩阵（初等）镜面反射矩阵，或，或Householder变换矩阵变换矩阵。Houholder矩阵H=H（w）有如下性质：(1)(2)(3)记S为与w垂直的平面,则几何上x与y=Hx关于平面S对称。事实上,由上式表明向量x-y与w平行，注意到y与x的长度相等，于是x经变换后的象y=Hx是x关于s对称的向量，如图7-1所示。第3页/共24页xwyx-y图图7-1对应于性质（2），有下面的定理。定理定理7.10得Hx=y。证证第4页/共24页由此可得定理得证。（7.4.2）（7.

3、4.3）第5页/共24页稳定性。（7.4.2）的意义是对向量作消元运算。与平面旋转不同的是，镜面反射变换可成批的消去向量的非零元。例例7.4 解解第6页/共24页（7.4.4）定理定理7.11为为Hessenberg形形。证证第7页/共24页变换，有如此类推，经n-2步对称正交相似变换，得到Hessenberg形矩阵。第8页/共24页推论7.1对称三对角阵。上述定理7.11的证明是构造的，即可以用镜面反射化矩阵Hessenberg形。此定理可用平面旋转变换来证明，即也可用平面旋转变换化矩阵为Hessenberg如此类推，最后得到的正交矩阵Q，是平面旋转矩阵的乘积。7.4.2 QR算法及其收敛性

4、算法及其收敛性 QR算法可以用来求任意的非奇异矩阵的全部特征值，是目前计算这类问题最有效的方法之一。它基于对任何实的非奇异矩阵都可以分解为正交阵Q和上三角矩阵R的乘积。第9页/共24页 定理7.2 (QR分定理)上三角阵R,使得A=QR,且当R的对角元素均取正时,分解是唯一的。证类似于定理7.11的证明，对矩阵A的左乘一系列正交变换矩阵，可以将A化为上三角形矩阵，因此，可得A的QR分解。下面证明分解的唯一性。设有两种分解上式左边为正交阵，即这个式子左边是下三角阵，则右边是上三角阵，所以只能是对角阵。设定理得证。第10页/共24页一般按平面旋转变换或镜面反射变换作出的分解A=QR，R的对角元不定

5、理7.12的唯一QR分解。如下的算法：（7.4.5）或称为基本QR算法。QR算法，第11页/共24页证证 容易证容易证(1)从它递推从它递推得得定理定理7.13QR算法产生的序列算法产生的序列 满足满足:（1）（2）一般情形下，QR算法的收敛性比较复杂。若矩阵序列 对角元均收敛，且严格下三角部分元素均收敛到零，则对求A的特征值而言已经足够了。此时，我们称 基本收敛到上三角阵。下面对最简单的情性给出收敛性定理。第12页/共24页设矩阵 的特征值满足定理7.14=LU，其中L为单位下三角阵U为上三角阵，则QR算法产生的序列 基本收敛到上三角阵，其对角极限为更一般地，在一定条件下，由QR算法生成的序

6、列 收敛为Schur分块上三角形，对角块按特征值的模从大到小排列，上述定理是它的特殊情形。当收敛结果为Schur分块上三角形时，序列 的对角块以上的元素以及2阶块的元素不一定收敛，但不影响求全部特征值。例7.5 用QR方法求下列矩阵的全部特征值。第13页/共24页解先用镜面反射变换化矩阵A为Hessenberg形矩阵 ，然后用平面旋转变换作QR分解进行迭代，生成序列 。（1）的计算结果为第14页/共24页该矩阵A非对称，从计算结果看，收敛于上三角阵。（2）的计算结果为第15页/共24页 从计算结果来看，迭代收敛于Schur分块上三角形，对角块分别是1阶和2阶子 一般在实际使用QR方法之前，先用

7、镜面反射变换将A化为Hessenberg形矩阵H，然后对H作QR迭代，这样可以大大节省运算工作量。因为上 Hessenberg阵H的 次对角线以下元素均为零，所以用平面旋转变换作QR分解较为方便。对i=1,2,.n-1,依次用平面旋转矩阵J（i,i+1）左乘H，使J（i,i+1）H的第i+1行第i列元素为零。左乘J(i,i+1)后，矩阵H的第i行与第i+1行零元素位置上仍为零，其他行不变。这样，共n-1次左乘正交矩阵后得到上三角阵R。即 =R，=J（n-1,n）J(n-2,n-1)J(1,2)。可以验证 是一个下Hessenberg阵，即U是一个上Hessenberg阵。这样，得到H的QR分解

8、H=UR。在作QR迭代时，下一步计算RU，容易验证RU是一个上Hessenberg阵。以上说明了QR算法保持了H的上Hessenberg结构形式。例 7.6求Hessenberg形矩阵 的特征值。第16页/共24页解解重复上面的过程，计算11次得至此，不难看出，一个特征值是4，另一个特征值是-1，其他两个特征值是方程第17页/共24页上述用QR方法求得的特征值是该特征方程的准确解。7.4.3 带原点位移的带原点位移的QR算法算法 前面我们介绍了在反幂法中应用原点位移的策略，这种思想方法也可用于QR算法。一般我们针对上Hessenberg矩阵讨论QR算法，并且假设每次QR迭代中产生的 都是不可约的，否则，可以将问题分解为较小型的问题。这样，带原点位移的QR算法可以描述为：第18页/共24页第19页/共24页根据QR算法的收敛性质，位移量有下列两种取法：例7.7 用带原点位移的QR算法求下列矩阵的特征值：第20页/共24页解 先用镜面反射变换把A化为上Hessenberg矩阵。按（7.4.3）式有第21页/共24页第22页/共24页 该问题如果不用带原点位移的QR算法，而是用基本QR算法，则收敛速度很慢，计算结果为第23页/共24页感谢您的观看！第24页/共24页