资源描述
计算上Hessenberg阵的全部特征值,计算对称三对角阵的全部特征值,收敛快、算法稳定,利用正交相似变换（Householder变换）、QR分解将矩阵A化,QR算法的应用：,优点：,理论基础：,QR算法：变换法,4QR算法,特征值相同,思想方法：,为简单矩阵。如上Hessenberg阵、对称三对角阵。,A相似于B的定义：设矩阵，如果存在可逆矩阵X使,上Hessenberg阵的定义：,（2）若，称B为不可约上Hessenberg阵。,B=X-1AX，则称B相似于A，记为,时，bij=0,称B为上Hessenberg阵，即,（1）设，如果当ij+1,一、基本QR方法,二、带原点位移的QR方法,三、上Hessenberg阵的单步QR方法,本节内容：,（加速收敛的方法）,一、基本QR方法,B的构造如下：,（一）过程,（1）QR分解：,（2）逆序相乘（作矩阵）：B=RQ,Q-1=QT,显然，B是由A经过正交相似变换(Householder)得到。因此，,A=QR，R是上三角阵，Q为正交阵。,从而，B与A有相同的特征值。,构造序列Ak,设,先分解：A1=Q1R1，,再分解：A2=Q2R2，,Ak=QkRk,这样由矩阵的QR分解，按正交相似变换构造矩阵序列Ak的过程,称为QR算法。,=QTAQ，,R=Q-1A=QTA,Ak+1=RkQk=QkTAkQk；,作矩阵：A2=R1Q1=Q1TA1Q1；,作矩阵：A3=Q2TA2Q2；,Ak的性质：,（1）Ak+1相似于Ak，即Ak+1=QkTAkQk；,定理13QR序列Ak满足：,（2）Ak+1=(Q1Q2Qk)TA1(Q1Q2Qk),（3）Ak的QR分解式为：,分析:(1)因为AkAk1是正交相似变换，因此,（2）由记，及QR算法,Ak+1=RkQk=QkTAkQk,(k=1,2,)得,Ak+1=QkT(Qk-1TAk-1Qk-1)Qk,=QkTQk-1TQ1TA1Q1Q2Qk,=(Q1Q2Qk)TA1(Q1Q2Qk),矩阵的结合律,（3）要证,用归纳法证。,即要证Ak=(Q1Q2Qk)(RkR2R1),Ak=QkRk,，Ak+1=RkQk=QkTAkQk,（k=1,2,),又因为,证明：当k=1时，有,假设Ak-1,Ak的性质：,（1）Ak+1相似于Ak，即Ak+1=QTkAkQk；,定理13QR序列Ak满足：,（2）Ak+1=(Q1Q2Qk)TA1(Q1Q2Qk),（3）Ak的QR分解式为：,=(Q1Q2Qk-1)(Rk-1R2R1),则,=(Q1Q2Qk-1Qk)（RkRk-1R2R1),=(Q1Q2Qk-1)Ak(Rk-1R2R1),所以,#,Ak+1=(Q1Q2Qk)TA1(Q1Q2Qk),Ak,)(QkRk)(,QkRk,=(Q1Q2Qk-1Qk)（Rk),=(Q1Q2Qk-1)Ak,=A(Q1Q2Qk-1),QkTAk=Rk,从而Ak+1=QkTAkQk,方法：,（1）左变换：Pn-1P2P1AkRk（上三角阵）,（2）右变换：RkP1TP2TPn-1T=Ak+1,(k=1,2,),(二)由Ak计算Ak+1的方法,，将Ak进行QR分解，即是对Ak施行正交变换（左变换）,化为上三角阵Rk，即,QkT=Pn-1P2P1,Pi(i=1,2,n-1)为正交阵,k=1,2,=Pn-1P2P1AkP1TP2TPn-1T,上三角阵,定理14设,（1）A的特征值满足：；,（2）A有标准型，即存在非奇异阵X使A=XDX-1，其中,则由QR算法产生的序列Ak本,(三)QR方法的收敛性,本质收敛:设称本质上收敛于上三角阵R,当,收敛定理,L-单位下三角阵，U-上三角阵。,D=diag（对角阵），且设X-1有三角分解X-1=LU，,质上收敛于上三角阵，即,A的特征值满足：,定理15设为对称矩阵且满足定理14的条件(1),则由QR算法产生的矩阵,说明：QR算法收敛性进一步结果，若A的等模特征值中只有实,若A为对称矩阵，则由QR算法产生的序列Ak仍为对称矩阵。,序列Ak收敛于对角矩阵D=diag。,特征值或复的共轭特征值，则由QR算法产生的矩阵序列Ak本质,上收敛于分块上三角矩阵（对角块为一阶或二阶子块），且对角块,每一个22子块给出一对共轭复特征值，或每一个一阶对角块给出,实特征值。,二带原点位移的QR方法（加速收敛的方法）,设A的特征值满足：。由QR算法产生的,矩阵序列Ak元素,其收敛速度依赖于，,那么当|rn|很小时，收敛较快。若是一个估计，且对运,敛于0。此时，(n,n)元素将比在基本QR算法中收敛更快。因此，,用QR算法，则(n,n-1)元素将以收敛因子线性收,为了加速收敛，选择数列，从而有带原点位移的QR算法。,(一)带原点位移的QR算法,设,，QR分解：,作矩阵：,QR分解：,若已求得Ak，,QR分解：,作矩阵：,若已求得Ak，,结论：,(3)带位移QR算法变换一步的计算：,右变换：,先用正交变换（左变换）将化为上三角阵，即,左变换：,，其中,（二）矩阵A化为上Hessenberg阵的QR算法,(1)一般算法,设,有，为上Hessenberg阵,以下考虑上,QR算法:,Hk=QkRkQR分解,当k=1,2,时,(a)假设由（4.3）式产生的每一个Hessenberg阵Hk都是可约,pn-p,Pn-p,Hessenberg阵的QR算法。,Hk+1=RkQk,的,即若在某步有,问题就分离为H11与H22的两个较小的问题。特别当p=n-1或p=n-2,时，有,当p=n-1时，,当p=n-2时，,n-22,n-22,问题就分离为H11与H22的两个较小的问题。特别当p=n-1或p=n-2,H的特征值,，H的特征值可由,Hk+1下,这样，求H特征值问题可降阶求H11特征值。,角二阶矩阵的特征值得到。,pn-p,Pn-p,特别当p=n-1或p=n-2时，有,例如时，就把视为零，其中,(2)用位移加速收敛,当k=1,2,时,(QR分解),(作矩阵Hk+1),(b)假设由（4.3）式产生的每一个Hessenberg阵Hk都是不可,约的,计算时，每当Hk的次对角元适当小时，就进行分离。,为计算机的字长。,Hessenberg阵）,取H1=H,（为不可约上,三上Hessenberg阵的单步QR算法,单步QR方法：,取,当k=1,2,时,或计算,（上三角阵）,即,(QR分解),(作矩阵Hk+1),
展开阅读全文