资源描述：
《特征值和特征向量的数值算法.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、7.4QR算法7.4.3带原点位移的QR算法7.4.2QR算法及其收敛性7.4.1化矩阵为Hessenberg形我们称这种分块上三交阵为矩阵A的Schur分块上三角阵，上三角阵和对角阵是它的特殊情形。定理7.9并没有解决如何计算全部特征的问题。7.4.1化矩阵为Hessenberg形对于实对称矩阵，可通过正交相似变换约化为对角矩阵。那么，对于一般的实矩阵，通过正交相似变换可约化到什么程度呢？线性代数中有如下结果。定理7.9（实Schur分解定理）定义7.2(i>j+1),则称B为上Hessenberg矩阵，简称Hessenberg形，即B的形状为可
2、以用平面旋转变换化矩阵为Hessenberg形,下面介绍另一种正交变换。为了节省运算工作量，实用的方法是先将矩阵约化为与Schur分块上三角阵很近似的Hessenberg形。定义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所示。xwyx-y图7-1对应于性质（2），有下面的定理
3、。定理7.10得Hx=y。证由此可得定理得证。（7.4.2）（7.4.3）稳定性。（7.4.2）的意义是对向量作消元运算。与平面旋转不同的是，镜面反射变换可成批的消去向量的非零元。例7.4解（7.4.4）定理7.11为Hessenberg形。证变换，有如此类推，经n-2步对称正交相似变换，得到Hessenberg形矩阵。推论7.1对称三对角阵。上述定理7.11的证明是构造的，即可以用镜面反射化矩阵Hessenberg形。此定理可用平面旋转变换来证明，即也可用平面旋转变换化矩阵为Hessenberg如此类推，最后得到的正交矩阵Q，是平面旋转矩阵的乘积
4、。7.4.2QR算法及其收敛性QR算法可以用来求任意的非奇异矩阵的全部特征值，是目前计算这类问题最有效的方法之一。它基于对任何实的非奇异矩阵都可以分解为正交阵Q和上三角矩阵R的乘积。定理7.2(QR分定理)上三角阵R,使得A=QR,且当R的对角元素均取正时,分解是唯一的。证类似于定理7.11的证明，对矩阵A的左乘一系列正交变换矩阵，可以将A化为上三角形矩阵，因此，可得A的QR分解。下面证明分解的唯一性。设有两种分解上式左边为正交阵，即这个式子左边是下三角阵，则右边是上三角阵，所以只能是对角阵。设定理得证。一般按平面旋转变换或镜面反射变换作出的分解A
5、=QR，R的对角元不定理7.12的唯一QR分解。如下的算法：（7.4.5）或称为基本QR算法。QR算法，证容易证(1)从它递推得定理7.13QR算法产生的序列满足:（1）（2）一般情形下，QR算法的收敛性比较复杂。若矩阵序列对角元均收敛，且严格下三角部分元素均收敛到零，则对求A的特征值而言已经足够了。此时，我们称基本收敛到上三角阵。下面对最简单的情性给出收敛性定理。设矩阵的特征值满足定理7.14=LU，其中L为单位下三角阵U为上三角阵，则QR算法产生的序列基本收敛到上三角阵，其对角极限为更一般地，在一定条件下，由QR算法生成的序列收敛为Schur分
6、块上三角形，对角块按特征值的模从大到小排列，上述定理是它的特殊情形。当收敛结果为Schur分块上三角形时，序列的对角块以上的元素以及2阶块的元素不一定收敛，但不影响求全部特征值。例7.5用QR方法求下列矩阵的全部特征值。解先用镜面反射变换化矩阵A为Hessenberg形矩阵，然后用平面旋转变换作QR分解进行迭代，生成序列。（1）的计算结果为该矩阵A非对称，从计算结果看，收敛于上三角阵。（2）的计算结果为从计算结果来看，迭代收敛于Schur分块上三角形，对角块分别是1阶和2阶子一般在实际使用QR方法之前，先用镜面反射变换将A化为Hessenberg形
7、矩阵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的上Hes
