资源描述：
《矩阵分析与计算-QR算法.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、4.4QR算法4.4QR算法QR方法是求矩阵全部特征值的一种有效方法．一般都先把A变换为Hessenberg形式，然后用基于QR分解的QR迭代运算．在某些条件下，迭代产生的矩阵序列趋于一种实Schur分解的形式．4.4.4.4.11QR算法的基本思想QR算法的基本思想从QR分解定理可知实矩阵A有A=QR，其中Q为正交阵，R为上三角阵．若规定R的主对角元为正数,则分解有唯一性．如果令B=RQ，则有B=QTAQ，说明B与A有相同的特征值．对B继续作QR分解，可得到如下的算法⎧令A1=A⎪⎨Ak=QkRk(Ak的QR分解))7.
2、4(⎪A=RQk=,2,1?⎩k+1kk由(4.7)得到{A}的方法称为QR算法，或基本QR算k法．命题4.1QR算法产生的序列{Ak}满足：)1(A=QTAQTk+1kkk)2(Ak+1=QkAQk,其中Qk=Q1Q2?Qkk)3(A=QR,其中R=R?RRkkkk21证明易证(1)．从它递推得TTA=QAQ=(QQ?Q)A(QQ?Q)k+1kkk12k12k即得(2)，并知A与A相似，再由k+1QR=Q?QR?RR=QARkk1kk21k−1kk−1T以及A=QAQ可得到k+1kkTQR=QQAQR=AQRkkk−1k
3、−1k−1k−1k−1k−1由此递推，以及Q1R1=Q1R1=A1=A,即证3().关于QR算法的收敛性有各种情况，这里给出一种简单情况的收敛定理．定义4.1矩阵序列{Ak}当k→∞时，若其主对角元均收敛，且严格下三角部分元素收敛到零，则称{A}基本收敛到上三角阵．k基本收敛的概念并未指出{A}严格上三角部分k元素是否收敛．但对求A的特征值而言，基本收敛已足够了．定理4.3设矩阵A∈Rn×n，其特征值满足
4、λ
5、>
6、λ
7、>…>
8、λ
9、>0(4.7)′12nλ对应特征向量x，i=1,2,…,n．以x为列的方阵iii记为X=(x,
10、x,…,x)．设X−1可分解为X−1=LU,12n其中L为单位下三角阵，U为上三角阵．则QR算法产生的序列{A}基本收敛到上三角阵．其对角元k极限为(k)lima=λi=,2,1?,niiik→∞⎛82⎞例4.6A=⎜⎟有特征值λ1=9,λ2=4，可验⎝25⎠证满足定理4.3条件，且A对称，所以QR算法产生的序列应收敛到一个对角阵．用Givens变换的方法作A=A的QR分解，得到11⎛8−2⎞1⎛6826⎞Q=⎜⎟,R=⎜⎟1168⎝28⎠68⎝036⎠1⎛59672⎞⎛.87647.10588⎞A=RQ=⎜⎟≈⎜⎟211
11、68⎝72288⎠⎝.10588.42353⎠1⎛.87647−.10588⎞Q=⎜⎟277.9410⎝.10588.87647⎠1⎛77.941013.7644⎞R=⎜⎟277.9410⎝036.0001⎠⎛.89517.04890⎞A=RQ≈⎜⎟322⎝.04890.40483⎠可看到A仍为对称阵，而且其非对角元绝对值比A31对应数值要小，对角元则比A对应数值更接近特征1值，即A比A更接近对角形．继续算下去，作10次31QR迭代可以求出有7位数字的特征值．一般情形QR算法的收敛性较为复杂．在有等模特征值(包括实的重特征
12、值，单的或重的共轭复特征值及其他情形)时，如果X−1仍有LU分解，则{A}基本k收敛到块上三角阵．若同一模的特征值有p个，则在对角线上出现一个p阶子阵，其元素不一定收敛，但p阶子阵的特征值收敛于A的等模特征值．对于一种重要的情况，即等模特征值中只有实的重特征值和多重复共轭特征值的情况，可以证明{A}基本收敛k到分块上三角阵，对角块是1阶或2阶的，其中2阶子阵给出一对复共轭特征值．4.4.4.4.22Hessenberg矩阵的QR方法Hessenberg矩阵的QR方法一般实际使用QR方法之前，先将A通过正交相似变换化为上He
13、ssenberg矩阵H，然后对H作QR迭代,这样可以大大节省运算工作量．因为上Hessenberg矩阵H的次对角线以下元素均为零，所以用Givens变换作QR分解较为方便．例如用Givens矩阵G(i,i+1,θ)左乘H，有iG,(ii+,1θ)H=i⎛h11h12?h1i?h,1n−1h1n⎞⎜⎟⎛1⎞⎜hh?h?hh⎟⎜⎟21222i,2n−1,2n⎜B⎟⎜BB@@@⎟⎜cs⎟⎜⎟ii⎜hh?hh⎟⎜⎟,ii−1iii,n−1i,n⎜−sici⎟⎜h?hh⎟i+,1ii+,1n−1i+,1n⎜B⎟⎜⎟⎜⎟⎜B@@⎟⎜⎟
14、⎝1⎠⎜⎟hh⎝n,n−1nn⎠选择θ，使G(i,i+1,θ)H的第i+1行第i列元素为0，而ii矩阵H的第i与i+1行零元素位置上左乘G(i,i+1,θ)后i仍为0，其他行则不变．这样i=1,…,n−1，共n−1次左乘正交矩阵后得到上三角阵R，即1TTQH=R,Q=G(n−,1n,θ)?G,2,1(θ
