矩阵特征值与特征向量的计算方法

1、1第六章第六章 矩阵特征值与矩阵特征值与特征向量的计算方法特征向量的计算方法 2引言nnijaAR)(aaa 110)(naaaa 11na)(njnijea21)(), 2 , 1(nj3Th1；，其中的特征值，且为设0 xxAxA(1)次多项式；为任一设mxrxrrxPmm10)(2)则：定义矩阵 mmArArIrAP10)(；的特征值，即为xPxAPAPP)()()()( 1)的特征向量。为且)()(APxP 2)Th2，则为相似矩阵，即与设APPBBA1有相同的特征值；与BA 1)(的特征向量。是的特征向量，则是若APyBy 2)(4Th3(Gerschgorin圆盘定理)某个圆盘；下

2、述的每一个特征值必属于则设AaAnnij,)(1), 2 , 1(|njaraijijiii 的一个特征值。中精确地包含则，即为孤立圆盘个圆盘是分离的且与其他是由一个圆盘组成的特征值。特别，当个内恰包含，则即不相交个圆盘是分离的且与余下的连通的圆盘组成并集的若ASnSAmSmnSmA)(1)()(2)5411101014 A例：设1|4|1zD：2|2zD：2|4|3zD：孤立圆盘531), 1 , 1 (910diagDADDA11|4|1 zD：9192|zD：8 . 1|4|3zD：三个孤立圆盘6Th4(Schur定理)使，则存在酉阵设UAnnRRrrrrrrAUUnnnnH 22211

3、211(上三角阵)的特征值。为其中Aniriii), 2 , 1(7Th5 (实Schur分解)使，则存在正交矩阵设QAnnRnnnnTRRRRRRAQQ 22211211的一对共轭复特征值。块的两个特征值是对角的实特征值，每个二阶是且每个一阶为一阶或二阶方阵，其中对角块AARmiRiiii), 2 , 1(8Def，称为对称矩阵，设0 xAnnR),(),()(xxxAxxR商。的瑞利为对应向量)(Rayleighx9Th6为为对称矩阵，其特征值设nnAR组成规范化正交组，则其对应的特征向量nnxxx,2121 )0,(),(),(1xxxxxAxnnR (1)(max01xRxxnR (2

4、)(min0 xRxxnnR (3)10幂法及反幂法幂法，nnijaAR)(有一组完全的特征向量组，), 2 , 1(nixAxiii 线性无关,21nxxx |21n主特征值11幂法的其本思想nvR 0任取初始向量01Avv 0212vAAvv011vAAvvkkk的关系：与、现分析11kvx 12Th7；个线性无关的特征向量有设naAnnijR(1)(|21nA (2)的特征值满足设), 2 , 1()0(0110kAvvvkk (3)且幂法：则：；111limxvkkk (1)11)()(limikikkvv (2)13|121nrr若A的主特征值为实的重根，个线性无关的特征向量有设nx

5、xxnA,21 ), 2 , 1(1rixAxii 且), 1(nrixAxiii 0v 任取初始向量),(11不全为零且rniiix由幂法有0vAvkk)(1111nriikiiriiikxxkriiikkkxv11lim 14非零向量的规范化v )max(vv u 绝对值最大的分量表示向量vv )max(迭代序列规范化序列000 vu01Auv )max(111vvu 1kkAuv)max(kkkvvu 15改进的幂法)0(0100vu设1kkAuv)max(kkvkkkvu/迭代：规范化：, 2 , 1k16迭代序列规范化序列01Auv )max(001AvAvu )max(0022Av

6、vAv )max(02022vAvAu )max(010vAvAvkkk)max(00vAvAukkk（*）17niiixv10niikiikxvA10)(111kkx(*)(0)(21kxniikiik )max(00vAvAukkk)(max()(111111kkkkxx)max(1111kkxx)max(11xx18)max(010vAvAvkkk)(max()(11111111kkkkxx)max(111111kkxx)max(kkv)max()max(111111kkxx)(1k 有下列结论：19Th8；个线性无关的特征向量有设naAnnijR(1)(|21nA (2)的特征值满足：

7、设：由改进幂法得到，则有,kkvu(3)max(lim11xxukk (1)1)max(limlimkkkkv (2)(改进幂法), 2 , 1(nixAxiii 且确定。且收敛速度由|12r20加速方法原点平移法pIAB 引进矩阵nA，：21pppBn，：21特征向量相同), 3 , 2(|1nippi (1)|max1212 (2)ppjnj|/|12r改进21，其特征值是实数，nnijaAR)(？如何选择 pn21设pppIABn或的主特征值为则111x、为计算|1pppn满足要求且min|,|max112ppppn即求极值问题|,|maxmin112ppppnp22*np22，其特征值

8、是实数，nnijaAR)(nn121 若pppIABn或的主特征值为则1nnx、为计算|1pppn满足要求且min|,|max11ppppnnn211*np23Rayleigh商加速为对称矩阵nnijaAR)(Th9足为对称矩阵，特征值满设nnAR(1)；|21n ；对应的特征向量满足ijjixx),(2)；应用改进的幂法计算1(3)近似较好的给出商的则规范化向量序列1)(kkuRuRayleigh)(),(),()(2112kkkkkkouuuAuuR24反幂法(逆迭代)为非奇异矩阵，且nnAR；|21n ，对应的特征向量，nxxx,21 的特征值为1A；|1|1|121n ，对应的特征向量

9、，nxxx,21 求矩阵按模最小的特征值及对应的特征向量应用幂法即可！对1A25反幂法的迭代公式)0(000nvu设11kkuAv)max(kkvkkkvu/迭代：规范：, 2 , 1k1kkuAv综合得到：26Th8；个线性无关的特征向量有设naAnnijR(1)(0|11nnA (2)的特征值满足：设满足：量序列有上述反幂法得到的向,kkvu(3)max(limnnkkxxu (1)nkk1lim (2)(反幂法), 2 , 1(nixAxiii 且确定。且收敛速度由|1nnr27反幂法的应用 求近似特征值的特征向量应用幂法：对1)( pIA11)(kkupIAv)max(kkvkkkvu

10、/28Th10，个线性无关的特征向量有设naAnnijR(1)(且，设的一个近似取1)()(pIApjj (2)满足：序列则由反幂法得到的向量,kkvu)max(limjjkkxxu (1)pjkk1lim (2), 2 , 1(nixAxiii 即确定。且收敛速度由|min|pprijij)(|jippij jkp12911)(kkupIAv1)(kkuvpIA30计算对称矩阵特征值的Jacobi方法引言Th10，使得正交矩阵对称矩阵，则存在一个设PaAnnijR )(),(21nTAPPdiag的特征值；为且Anii), 2 , 1(1)的特征向量。对应为列向量jjnAvvvvP),(21

11、2)对称矩阵31Jacobi方法的基本思想,21PP变换选择一系列GivesAA 1TkkkkPAPA1, 2 , 1k收敛于对角阵kA),(21ndiag22211211aaaaA csscP sincossc 3222211211ccccPAPT 02112 cc2sin2122221111asacac 2sin2122221122acasac 2cos2sin)(211122212112aaacc 02112 cc 12221122cotaaa 33古典Jacobi方法11),( c s s c jiPij1cossinsincos1),( jiPsincoss c34TPAPCAjjj

12、iijiicccc cssc jjjiijiiaaaa cssc ),()()(jliljiC元素行列，第行列第csscaaccljliljli ),(),(), 2 , 1(jlilnl；jliljlilcccssccc ), 2 , 1(jlilnl；35Th12为对称矩阵；设nnijaAR(1)(变换；则为平面旋转，其中设),(jiPPPAPCT(2)22|FFAC|(1)；即)1,1,22nslnsllslsca(22222222ijjjiiijjjiiaaaccc(2)36Th13)(的元素计算公式TPAPC 为对称矩阵；设nnijaAR(1)(，则变换，为平面旋转，其中设)(),(

13、ijTTaPAPCjiPPPAPC(2)2cos2sin)(2sin2sin212222ijiijjjiijijjjiijjijjjiiiiaaaccacasacasacac (1)jliljljlililcasacsacacjiC，行元素行，第第(2), 2 , 1(jlilnl；37ljlijlljlilicasacsacacjiC，列元素列，第第(3), 2 , 1(jlilnl；2cos2sin)(2121aaacciijjjiij0 0ijijjjiiaaaa，22cot38Th14为对称矩阵；设nnijaAR(1)(；设)(0jiaij(2)；),(2222jlilaaccjlil

14、jlil (2)0jiijcc；nslnsllslsca1,1,22(1)则；222222ijjjiijjiiaaacc(3)nlllijaADaADCD122)(2)，(4)sllsijaASaASCS22)(2)，(5)39古典Jacobi方法：为对称矩阵设)()1(1lsaAA, 0|max|11lssljiaa设)(),()2(111211111lsTaPAPAjiPP，, 0)2()2(1111ijjiaaAA 1TPAPA1112TkkkkTkkkkPPPAPPPPAPA)()(11111), 2 , 1(kAk 40Th15阶对称矩阵；为设naAAij)(1(1)，则方法产生古典

15、Jacobi(2)kATkkkkPAPA1DAkklim(对角矩阵)Jacobi方法的特点Jacobi过关方法41Def对A非对角元素扫描一次为：for i=1,2,n-1 for j=i+1,n (3) goto | (1),|ijaif0,),(jiijTccPAPCjiPP (2)使，作选取j continue (3)i continue 。或关口为某一阀值其中)( 42Jacobi过关方法：阶对称矩阵为设naAij)(2121)()2(11120ASanlnlsls；设置阀值n/01 (1)()(1mlsmaAA)(|1)(slamls ；缩小阀值n/12 (2)(|2)(slarls

16、 t,21系列关口重复上述过程，经过一 (3)0)(nt43)()(tlstaA )()(0slnt对所有 |)(tlsa2022222)() 1()()(ttsltlstnnnaAS2)()(ASASt44Householder方法Def, 0, 1,)(ijnnijbjibB如果设R(1)即矩阵为上则称,HessenbergBnnnnnnbbbbbbbbB 12222111211矩阵。可约上为不，则称如果Hessenberg (2)Bnibii) 1, 2 , 1(0, 145本节讨论下列两个问题：矩阵；矩阵为上约化一般用用正交相似变换HessenbergrHouseholde1)()(矩

17、阵为三对角矩阵。约化对称用用正交相似变换)()(rHouseholde246AA 1kkkkUAUA1), 2 , 1(k 初等反射矩阵47设(1)nnnnnnaaaaaaaaaA 212222111211(1)1(1)(1) 221211ACAA1A，11nCR01C不妨设TuuIR11111 选择初等反射阵1111eCR 使1 RU114812211112111112RARCRRAaUAUA(1)1(1) )2()2(3)2(2)2(3)2(33)2(32)2(2)2(221)2(1)2(121100nnnnnnnaaaaaaaaaaa (2)2(2)(2) 2212110ACAA，22n

18、CR49AA 11112UAUA 111kkkkUAUA步：第k(2)(k)k(k)(k) 2212110ACAAAkkn-kn-kk矩阵，阶上为其中Hessenberg (k)kA11)()()(22knknkknkACRR，500kC设,kR 选择初等反射阵1eCRkkk 使kkkRIU 令n-kkkkkkkkkkkkkkRARCRRAAUAUA)()()( 2212111)()()( 12211121110kkkkACAA矩阵阶上为其中Hessenberg )(1111kAk51221122nnUUAUUUU )1(12)2(222)1(11nnnn-n-aaa 1nA52Th16)(阵

19、约化阵为上HessenbergrHouseholde221,nnnUUUA，则存在初等反射阵设RHAUUUUAUUUUTnn00221122使需计算：kkkkkUAUAA1TkkkkuuIR1初等反射阵： (1)TkkkCR)0 , 0 ,( 使约化计算 (2)kkkRIU AUAUkkk53Th17等反射阵为对称矩阵，则存在初设nnAR221122nnUUAUUUUTaaannnn-n- )1(112)2(2211)1(11 ，则正交矩阵令)(2210nUUUU使221,nUUUTAUUT00(对称三对角矩阵)54QR 算法引言QR算法及收敛性nnijaAAR)(1设分解：进行对QRAA 1

20、QRA 正交矩阵上三角矩阵在一定条件下，kA本质上收敛于上三角阵！55Th18 (基本QR方法)，设nnijaAAR)(1), 2 , 1(1kQRARQAQRkkkkkk 算法：为上三角阵，且记为正交阵，其中kkRQ1221RRRRQQQQkkkk，则：；，即相似于kkTkkkkQAQAAA11)(1；kTkkTkkQAQQQQAQQQA)()()(12112112kkkkRQAQRA)(分解式为：的356引理)()(kIRIQkIMRQRQMkkkkkkkk，则：元素的上三角阵，如果为具有正对角为正交阵，其中设 57Th19 (QR方法的收敛性)，设nnijaAAR)(1；的特征值满足0|)(21nA1，使奇异矩阵具有标准型，即存在非XA)(2),(211nDXDXAdiag，其中算法产生，则由有三角分解且记QRLU