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

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,*,第八章,矩阵特征值计算,正交变换与,QR,迭代,1,本讲内容,正交变换,QR,迭代,Householder,变换,Givens,变换,QR,分解,Schur,分解,Hessenberg,矩阵,2,Householder,变换,性质,(1),对称：,(2),正交：,(3),对合：,(4),保模：,(5),定义,：,设 且 ，称矩阵,为,Householder,变换,，或,初等反射矩阵,。,3,Householder,变换,定理,：,设,x,y,R,n,x,y,且,|,x|,2,= |,y|,2,，则存在,n,阶,Householder,变换,H,，使得,y,=,Hx,证：,取,4,Householder,变换,定理,：,对任意的非零向量,x,R,n,，存在,Householder,变换,H,，使得,Hx,=,e,1,其中,= sgn(,x,1,)|,x,|,2,e,1,= (1, 0, ., 0),T,，,的选取是为了,防止在实际计算中,与,x,1,互相抵消,若,x,1,=0,则取,= |,x,|,2,5,Givens,变换,定义,：,称矩阵,为,Givens,变换,，或,旋转变换,。,i,j,6,Givens,变换,性质,(1),只有四个元素与单位矩阵不同,(2),正交：,(3),用,G,左乘一个矩阵时，只改变该矩阵中两行的值,(4),用,G,右乘一个矩阵时，只改变该矩阵中两列的值,7,Givens,变换,定理,：,设,x,= (,x,1, .,x,i, . ,x,j, . ,x,n,),T,，且,x,i,x,j,不全为零，则存在,Givens,变换,G,=,G,(,i,j,),，使得,8,QR,分解,定理：（,QR,分解）,设,n,阶实矩阵,A,非奇异，则存在正交分解,A,=,QR,其中,Q,是正交矩阵 ，,R,是非奇异上三角矩阵 。,若限定,R,的对角线元素为正数，则此分解唯一 。,9,QR,分解算法,设,(,j,= 1, . ,n,),(1),构造,H,1,使得,H,1,a,1,=,1,e,1,，令,(2),构造,使得,，令,算法（,QR,分解）,10,QR,分解算法,以此类推，经过,n,-,1,步，可得,Householder,矩阵,H,1,H,2, . ,H,n,-1,，使得,令 ，即得,11,QR,分解举例,例：,用,Householder,变换计算 的,QR,分解,解：,(,板书,),12,Schur,分解,定理：（,Schur,分解）,设,A,为,n,阶实矩阵，则存在正交矩阵,Q,，使得,其中,R,ii,是一阶或二阶方阵。,若,R,ii,是一阶方阵，则它就是,A,的,特征值,；,若,R,ii,是二阶方阵，则其特征值为,A,的两个,共轭复特征值,。,拟上三角矩阵,13,QR,迭代,QR,迭代算法,计算矩阵的所有特征值和特征向量,计算过程,(1),令,A,1,A,(2),对,k,= 1, 2, .,，,计算,A,k,的,QR,分解,计算,直到,A,k,+1,收敛到一个,拟上三角阵,14,作业,教材,277,页，习题,10,15,