上海交通大学计算方法课件(宋宝瑞)CH.9

1第九章矩阵特征值与特征向量计算矩阵特征值问题有物理、工程背景特征值，对应的特征向量NAXX特征多项式DETIA特征值0特征向量的基础解系。IX定理1如果为A的特征值的集合，则1,NA112DET3NOIINIOATRABB若X是B对应于的特征向量，则TX是A对应于同一特征1,T值的特征向量。定理2GERSCHGORIN圆盘定理设，则得每一个特征值必属于下述某个圆盘之中IJNAA11,2,NIIJJAIN证设特征值，对应的特征向量X0IAX21,0MAXTNIKXX第个方程I1NIIJA/1JIIIJJXA有得证，且对应的特征向量第个分量绝对值最大，在第个圆盘中。IREYLEIGH商设实对称矩阵，的REYLEIGH商定义为A0X,AXR定理3设对称，特征值，对应特征向量N12N组成标准正交组则1,NX,IJIJX11,NAX2100MAINNXXRR幂法与反幂法设有完全特征向量组（N个线性无关的特征向量）IJAA1231N幂法任取初值10010,KKVVAVAV3，以后我们用符号表示向量的第I个分量。1LIMKIVKIVKV一般为避免溢出1KI表示向量绝对值最大的分量001112221MAXKKKVUVAVUV不会溢出KVKV此时，1MAXK收敛速度1MAXKKVOR21当时也可用121SS方法的证明设的特征向量为（线性无关），A,NXA1,NDIAGTX1122102,NNNAXXXTTVAAX410211212110KKKKNKKNKKKNKVAVAXAXXAXAX1LIMKIIKIKIV加速原点平移法BAPI12,N适当选，使P2211求的主特征值BRAYLEIGH加速设对称A123N则11,KKUO5反幂法，有完全特征向量系A1230NN的特征值为，且1,N11N通过求的主特征值来间接求1AN迭代公式01MAXKKKVUA1KKVVU通过求解方程求得。相似变换法方法的思想是找适当的P通过相对好算来计算A的特征1,AB值，如果对不加限制，则从求，很可能是病态方程，所以只能用酉相似变换法，即限制为酉阵（注意特征值一般是复的）。酉阵HIJNJINAAAHUI6酉相似变换的优点求逆容易11HU21MINCONDU酉变换能把任意矩阵变换成怎样的矩阵定理（SCHUR分解定理）设，则存在N阶酉阵，使NA，为上三角形矩阵。HAUT证明设的一个特征值为，对应的特征向量为，找11X2使得为酉阵。1N，,XU,AU1111,0HHHUAHXA21212210NAAUU121220HU为酉阵，如此进行下去，即得酉阵12U1HNUAT定理（实的SCHUR分解定理）,存在正交阵，使NR712120KTKTRA为一阶或二阶矩阵。I实际上，一阶对应实特征值，二阶矩阵对应一对共轭复特征值关键在于求或R，CHUR定理的证明中，有了特征值，特征向量才有，UU不能直接用于求特征值。求一般矩阵全部特征值的QR算法我们把算法分为5步讲解初等反射阵1问题给定中的向量X，Y，如何找正交阵使得由于正交变NHXY换保内积，给定的X，Y必须满足条件|XY给定单位向量，构造矩阵，这样定义的2,1NW2TIWH称为初等反射阵，易验证初等反射阵具有性质，是正1H交阵，对称阵，对合阵。有2,NXYXYXYU，可得到存在使，事实上只须令21TUIUH8即可。2UXYQR分解定理A可表示为AQR其中Q为正交阵而R为上三角阵。,IJNA证明把A写成列向量形式，不妨设（否则跳过这1,NA10A一步）根据的结果可知存在初等反射阵，使得11H1,E，1HA20A21NAR同理存在N1阶初等反射阵，使得2H，令，2230AHAA22101HA1230AA如此继续下去，存在一系列初等反射阵，使得11,NH9，令即得。121NHAR1NQHQR分解一般不唯一，至少主对角线上的元可。若A非奇异，且限制的对角元为正，则唯一。R证设，由于A非奇异，两边均为上三21AR112TR角正交阵，对角阵，的对角元为正1,NIDIAG12,注意A的QR分解中的不相似于122IIA，求A的特征值还须更复杂的方法。QR方法3设（分解好）令以代入得QRBRQTTAQBTBA对B仍可作QR分解，再算RQ基本QR算法1KKKAQR（的分解）K1,2易知定理11122,3QRTKKKKKKAQQRRA的分解定理2设，其特征值满足，A有标NX120N10准形，1AXD，有分解，1NDIAG1LU1XL则KNR本质上即0LIMKJIIJAIJ不一定存在注意Q的列向量不收敛于特征向量集合若A对称，满足定理条件，则收敛于对角阵，若不满足，可能不KAKA收敛于对角阵。A本身为正交阵,EG011Q1RI1KA一般情形的QR算法收敛性较为复杂，特殊的，若A的等模特征值只有重实特征值或多重共轭复特征值，则QR算法产生的本质上收敛于分块上K三角阵。1111MLB为A的实特征值，块的特征值为A的复共轭特征值，注意1M2IB的元素不一定收敛，但特征值收敛。IB一次迭代计算次数（即一次QR分解）计算量不可接受。3ON改进的方法正交相似变换成上H阵，再对上H阵用QR算法。HOUSEHOLDER方法定义方阵，如果当，则称为上IJNBB10IJIJB时，BHESSENBERG阵，即12121,0NNNBBB问题如何用正交相似变换化一般为上HESSENBERG阵NA现考虑用一系列初等反射阵，将化为上H阵如同大多数矩阵分解我们还是用减缩的方法12把矩阵写成列向量的形式找初等反射阵使1,NAA1H，,如前，很容易找到2112,NAHD0,TD使得取的形式（不唯一），设但现在A112HIU的第一列要取的形式。为使右乘后，的第一列不变，11A的第一列应为1H1101,0TH因此必须。1U下，由知D求与11AD1DA，2121,NIS111U，11213110,TNWADASA可能，为避免相近数相减，取。从而2S2SG121GNS令，2211AW1THIW,SGN,0,TDA13第步变换，仅是第一步的重复，只不过把变换应用与阶方阵上。I1NI若为对称，（上阵）显然为对称。为三对角矩阵。ATRBHB一次变换的计算量。354N但对上H阵作一次QR分解计算量仅为预处理的方法。2ON对上H阵作QR分解的GIVENS变换在中，2COSINPPX把向量逆时针方向旋转角度，P称为旋转矩阵。X推广到称为平面旋转矩阵。,NIJ1,1CSIPIJSCJIJ，（可以认为）21CSCOS,IN设2,TIJNXAA14，则1,TNPIJXB,IIJJIJKCASSACBAIJ如果取则22JIJIJS，（1）,0IIJBAB为正交阵，左乘只改变的第行和第行。右乘,PIJPAIJ只改变的第列和第列。改变的的第行、AIJ,TIJPAI第行，第列和第列其余元素不动。IJ这样的称为GIVENS矩阵或GIVENS旋转变换，它具有下,IJ列性质1为正交矩阵；P2与单位阵相比，只有在4个位置上的元素不同；,IJIJ3作用于向量，只改变的第两个元素X,IJ4的前I1行和前I1列与单位阵I相同。P通过（1）式，我们看到作旋转变换可有针对性地使某个元素变零，而用初等反射阵则一次使一串元素变为零。显然，用旋转变换也可实现矩阵的QR分解，特别是当A为上HESSENBERG阵时，每一列用一次，总共用N1次旋转变换即可实现QR分解，大大减少了计算量。算法对上HESSENBERG矩阵，用QR算法迭代一次可分两步A151用GIVENS变换作QR分解左乘将化0，左乘将化0，左乘12PA,1IP,IA将化0，得上三角阵R,N,N2右变换2A1231,TNR定理设为上HESSENBERG矩阵，那么由开始作QR算法所产生的矩阵11A序列的每个矩阵均为上HESSENBERG矩阵。KK证明只需要证明一步就可以了。设对上HESSENBERG矩阵用GIVENS旋K转变换作QR分解，即，或1,2,312NKPPR。现作反乘。1231,TKNKKAPRQKAQ1231,TNP分两步来证明仍然为上HESSENBERG矩阵。（1）容易证明是上HESSENBERG矩阵，这是因为12K12120KNRCSRPR。121200CRSC（2）任一上HESSENBERG矩阵与的乘积仍是上HESSENBERG矩阵。H1,IP作分块乘法16，其中1121,330SSSIIPIPXXXHXIHXPPP，2IIICS而,1,111,1,1,IIIIIIIIPIHCHSSHCCSHP显然，最后结果仍为上HESSENBERG矩阵。最后一个问题，在1,1,2,1,TTKKAPNAPN中，左乘和右乘是否能同时进行，以减少存储量，简化程序实际上关键的问题是要能找到正确的，注意是由,I,PM,KM的第M列确定改变的是上述矩阵的第M行和M1行，而对任意矩阵B，的第M列与B的第M列相同，因此对1,22,1TTBP的第M列作同样目2,1TTKAP标的GIVENS变换，也能得到正确的，所以左右变换可以按下列顺序同时进行2,312,31,3,4,21,4,2TTKKKTKPPAPPA带位移的QR算法数列构造算法KSK17（1）A（2）对分解KSIQRK1,2,（3）新矩阵1TKKKARSIA（4）TKQ（5）12KSISI有QR分解式KAR如果选，则可把分离，迭代进行到充分小，有形KNSAN,1|KNAKA式4为例440B对B（减一阶）续续用QR算法。收敛快。QR算法的证明、细节与改进定理21的证明18引理，当时若，则KKMQRKMIKQRI，证TTTK，第一行为KIJNRK1121,KNR2KKR0,2,IJJN同理逐行计算得11,KKKKRIIQMRI定理的证明11KKKKIJAXDLUXDLL元素01KIJKIJIJ由于IJ另一方面10MAXKKKKIJIJKJJDLIEEOIC可设1KKKXQRAIDUQIREDU19当K充分大时，非奇异11KKREIREKQII由引理KKKARDU的另一形式，QR分解112,NDIAGUU上式改写成1212KKKKAQDRDU正交阵对角元为正与上式同一QR分解。KKR211KKU代入定理1之（2）得1AQRD2121TKTKKKKKAQ为上所以有IR11KTKKBDR（对角线保持次序）1N2012121KTKKIJIIJJADB为对角阵，2I10KIJJ1IKIJIIABRDHOUSEHOLDER算法