正交变换与QR 迭代 矩阵特征值计算

1第八章矩阵特征值计算计算方法——正交变换与QR迭代2本讲内容正交变换QR迭代Householder变换Givens变换QR分解Schur分解Hessenberg矩阵3Householder变换性质(1)对称：(2)正交：(3)对合：(4)保模：(5)TwwHH定义：设且，称矩阵2TwHIww为Householder变换，或初等反射矩阵。Rnw1Tww1T2wHI22wHxxdet()1wH4Householder变换定理：设x,yRn,xy且||x||2=||y||2，则存在n阶Householder变换H，使得y=Hx证：取2()||||xywxy5Householder变换定理：对任意的非零向量xRn，存在Householder变换H，使得Hx=e1其中=sgn(x1)||x||2,e1=(1,0,...,0)T，1THIuu1uxe2121()2ux的选取是为了防止在实际计算中与x1互相抵消若x1=0,则取=||x||26Givens变换定义：称矩阵为Givens变换，或旋转变换。ij7Givens变换性质(1)只有四个元素与单位矩阵不同(2)正交：(3)用G左乘一个矩阵时，只改变该矩阵中两行的值(4)用G右乘一个矩阵时，只改变该矩阵中两列的值1GG8Givens变换定理：设x=(x1,...,xi,...,xj,...,xn)T，且xi,xj不全为零，则存在Givens变换G=G(i,j,)，使得1(,...,,...,,.0..,)iTnGxxxx9QR分解定理：（QR分解）设n阶实矩阵A非奇异，则存在正交分解A=QR其中Q是正交矩阵，R是非奇异上三角矩阵。若限定R的对角线元素为正数，则此分解唯一。10QR分解算法设1212[,,,],[,,,]TnjjjnjAaaaaaaa(j=1,...,n)(1)构造H1使得H1a1=1e1，令(2)(2)1121(2)(2)22221112(2)(2)20[,,,]0nnnnnnaaaaAHAHaaaaa(2)2a(2)构造使得，令2H(2)2122Hae22100HH(2)(2)(2)112131(3)(3)2232(3)(3)322333(3)(3)300000nnnnnnaaaaaAHAaaaa算法（QR分解）11QR分解算法以此类推，经过n-1步，可得Householder矩阵H1,H2,...,Hn-1，使得(2)(2)1121(3)22121000nnnnnaaaHHHAR令，即得1121nnQHHHAQR12QR分解举例例：用Householder变换计算的QR分解020212021A2212TuuHIu1uxe2122()ux12sgn()xx解：(板书)13Schur分解定理：（Schur分解）设A为n阶实矩阵，则存在正交矩阵Q，使得其中Rii是一阶或二阶方阵。11121222mmTmmRRRRRQAQRR若Rii是一阶方阵，则它就是A的特征值；若Rii是二阶方阵，则其特征值为A的两个共轭复特征值。拟上三角矩阵14QR迭代QR迭代算法计算矩阵的所有特征值和特征向量计算过程(1)令A1＝A(2)对k=1,2,...，计算Ak的QR分解计算直到Ak+1收敛到一个拟上三角阵1kkkARQkkkAQR15作业教材277页，习题10