矩阵特征值与特征向量的计算方法学习教案

1、会计学1矩阵矩阵(j zhn)特征值与特征向量的计算方特征值与特征向量的计算方法法第一页，共64页。2引言(ynyn)nnijaAR)(aaa 110)(naaaa 11na)(njnijea21)(), 2 , 1(nj第1页/共63页第二页，共64页。3Th1；，其中的特征值，且为设0 xxAxA(1)次多项式；为任一设mxrxrrxPmm10)(2)则：定义矩阵 mmArArIrAP10)(；的特征值，即为xPxAPAPP)()()()( 1)的特征向量。为且)()(APxP 2)Th2，则为相似矩阵，即与设APPBBA1有相同的特征值；与BA 1)(的特征向量。是的特征向量，则是若AP

2、yBy 2)(第2页/共63页第三页，共64页。4Th3(Gerschgorin圆盘(yun pn)定理)某个圆盘；下述的每一个特征值必属于则设AaAnnij,)(1), 2 , 1(|njaraijijiii 的一个特征值。中精确地包含则，即为孤立圆盘个圆盘是分离的且与其他是由一个圆盘组成的特征值。特别，当个内恰包含，则即不相交个圆盘是分离的且与余下的连通的圆盘组成并集的若ASnSAmSmnSmA)(1)()(2)第3页/共63页第四页，共64页。5411101014 A例：设1|4|1zD：2|2zD：2|4|3zD：孤立(gl)圆盘531), 1 , 1 (910diagDADDA11|

3、4|1 zD：9192|zD：8 . 1|4|3zD：三个孤立(gl)圆盘第4页/共63页第五页，共64页。6Th4(Schur定理(dngl)使，则存在酉阵设UAnnRRrrrrrrAUUnnnnH 22211211(上三角(snjio)阵)的特征值。为其中Aniriii), 2 , 1(第5页/共63页第六页，共64页。7Th5(实Schur分解(fnji)使，则存在正交矩阵设QAnnRnnnnTRRRRRRAQQ 22211211的一对共轭复特征值。块的两个特征值是对角的实特征值，每个二阶是且每个一阶为一阶或二阶方阵，其中对角块AARmiRiiii), 2 , 1(第6页/共63页第七页

4、，共64页。8Def，称为对称矩阵，设0 xAnnR),(),()(xxxAxxR商。的瑞利为对应向量)(Rayleighx第7页/共63页第八页，共64页。9Th6为为对称矩阵，其特征值设nnAR组成规范化正交组，则其对应的特征向量nnxxx,2121 )0,(),(),(1xxxxxAxnnR (1)(max01xRxxnR (2)(min0 xRxxnnR (3)第8页/共63页第九页，共64页。10幂法及反幂法幂法，nnijaAR)(有一组完全(wnqun)的特征向量组，), 2 , 1(nixAxiii 线性无关,21nxxx |21n主特征值第9页/共63页第十页，共64页。11幂

5、法的其本思想(sxing)nvR 0任取初始向量01Avv 0212vAAvv011vAAvvkkk的关系：与、现分析11kvx 第10页/共63页第十一页，共64页。12Th7；个线性无关的特征向量有设naAnnijR(1)(|21nA (2)的特征值满足设), 2 , 1()0(0110kAvvvkk (3)且幂法：则：；111limxvkkk (1)11)()(limikikkvv (2)第11页/共63页第十二页，共64页。13|121nrr若A的主特征值为实的重根，个线性无关的特征向量有设nxxxnA,21 ), 2 , 1(1rixAxii 且), 1(nrixAxiii 0v 任

6、取初始向量),(11不全为零且rniiix由幂法有0vAvkk)(1111nriikiiriiikxxkriiikkkxv11lim 第12页/共63页第十三页，共64页。14非零向量(xingling)的规范化v )max(vv u 绝对值最大的分量表示向量vv )max(迭代(di di)序列规范化序列(xli)000 vu01Auv )max(111vvu 1kkAuv)max(kkkvvu 第13页/共63页第十四页，共64页。15改进(gijn)的幂法)0(0100vu设1kkAuv)max(kkvkkkvu/迭代(di di)：规范化：, 2 , 1k第14页/共63页第十五页，共

7、64页。16迭代(di di)序列规范化序列(xli)01Auv )max(001AvAvu )max(0022AvvAv )max(02022vAvAu )max(010vAvAvkkk)max(00vAvAukkk（*）第15页/共63页第十六页，共64页。17niiixv10niikiikxvA10)(111kkx(*)(0)(21kxniikiik )max(00vAvAukkk)(max()(111111kkkkxx)max(1111kkxx)max(11xx第16页/共63页第十七页，共64页。18)max(010vAvAvkkk)(max()(11111111kkkkxx)max

8、(111111kkxx)max(kkv)max()max(111111kkxx)(1k 有下列(xili)结论：第17页/共63页第十八页，共64页。19Th8；个线性无关的特征向量有设naAnnijR(1)(|21nA (2)的特征值满足：设：由改进幂法得到，则有,kkvu(3)max(lim11xxukk (1)1)max(limlimkkkkv (2)(改进(gijn)幂法), 2 , 1(nixAxiii 且确定。且收敛速度由|12r第18页/共63页第十九页，共64页。20加速(ji s)方法原点平移(pn y)法pIAB 引进矩阵nA，：21pppBn，：21特征向量相同(xin

9、tn), 3 , 2(|1nippi (1)|max1212 (2)ppjnj|/|12r改进第19页/共63页第二十页，共64页。21，其特征值是实数，nnijaAR)(？如何选择 pn21设pppIABn或的主特征值为则111x、为计算|1pppn满足要求且min|,|max112ppppn即求极值(j zh)问题|,|maxmin112ppppnp22*np第20页/共63页第二十一页，共64页。22，其特征值是实数，nnijaAR)(nn121 若pppIABn或的主特征值为则1nnx、为计算|1pppn满足要求且min|,|max11ppppnnn211*np第21页/共63页第二十

10、二页，共64页。23Rayleigh商加速(ji s)为对称矩阵nnijaAR)(Th9足为对称矩阵，特征值满设nnAR(1)；|21n ；对应的特征向量满足ijjixx),(2)；应用改进的幂法计算1(3)近似较好的给出商的则规范化向量序列1)(kkuRuRayleigh)(),(),()(2112kkkkkkouuuAuuR第22页/共63页第二十三页，共64页。24反幂法(逆迭代(di di)为非奇异矩阵，且nnAR；|21n ，对应的特征向量，nxxx,21 的特征值为1A；|1|1|121n ，对应的特征向量，nxxx,21 求矩阵(j zhn)按模最小的特征值及对应的特征向量应用幂

11、法即可！对1A第23页/共63页第二十四页，共64页。25反幂法的迭代(di di)公式)0(000nvu设11kkuAv)max(kkvkkkvu/迭代(di di)：规范(gufn)：, 2 , 1k1kkuAv综合得到：第24页/共63页第二十五页，共64页。26Th8；个线性无关的特征向量有设naAnnijR(1)(0|11nnA (2)的特征值满足：设满足：量序列有上述反幂法得到的向,kkvu(3)max(limnnkkxxu (1)nkk1lim (2)(反幂法), 2 , 1(nixAxiii 且确定。且收敛速度由|1nnr第25页/共63页第二十六页，共64页。27反幂法的应用

12、(yngyng)求近似(jn s)特征值的特征向量应用幂法：对1)( pIA11)(kkupIAv)max(kkvkkkvu/第26页/共63页第二十七页，共64页。28Th10，个线性无关的特征向量有设naAnnijR(1)(且，设的一个近似取1)()(pIApjj (2)满足：序列则由反幂法得到的向量,kkvu)max(limjjkkxxu (1)pjkk1lim (2), 2 , 1(nixAxiii 即确定。且收敛速度由|min|pprijij)(|jippij jkp1第27页/共63页第二十八页，共64页。2911)(kkupIAv1)(kkuvpIA第28页/共63页第二十九页，

13、共64页。30计算对称矩阵(j zhn)特征值的Jacobi方法引言(ynyn)Th10，使得正交矩阵对称矩阵，则存在一个设PaAnnijR )(),(21nTAPPdiag的特征值；为且Anii), 2 , 1(1)的特征向量。对应为列向量jjnAvvvvP),(212)对称(duchn)矩阵第29页/共63页第三十页，共64页。31Jacobi方法的基本(jbn)思想,21PP变换选择一系列GivesAA 1TkkkkPAPA1, 2 , 1k收敛于对角阵kA),(21ndiag22211211aaaaA csscP sincossc 第30页/共63页第三十一页，共64页。3222211

14、211ccccPAPT 02112 cc2sin2122221111asacac 2sin2122221122acasac 2cos2sin)(211122212112aaacc 02112 cc 12221122cotaaa 第31页/共63页第三十二页，共64页。33古典(gdin)Jacobi方法11),( c s s c jiPij1cossinsincos1),( jiPsincoss c第32页/共63页第三十三页，共64页。34TPAPCAjjjiijiicccc cssc jjjiijiiaaaa cssc ),()()(jliljiC元素行列，第行列第csscaaccljli

15、ljli ),(),(), 2 , 1(jlilnl；jliljlilcccssccc ), 2 , 1(jlilnl；第33页/共63页第三十四页，共64页。35Th12为对称矩阵；设nnijaAR(1)(变换；则为平面旋转，其中设),(jiPPPAPCT(2)22|FFAC|(1)；即)1,1,22nslnsllslsca(22222222ijjjiiijjjiiaaaccc(2)第34页/共63页第三十五页，共64页。36Th13)(的元素计算公式TPAPC 为对称矩阵；设nnijaAR(1)(，则变换，为平面旋转，其中设)(),(ijTTaPAPCjiPPPAPC(2)2cos2sin

16、)(2sin2sin212222ijiijjjiijijjjiijjijjjiiiiaaaccacasacasacac (1)jliljljlililcasacsacacjiC，行元素行，第第(2), 2 , 1(jlilnl；第35页/共63页第三十六页，共64页。37ljlijlljlilicasacsacacjiC，列元素列，第第(3), 2 , 1(jlilnl；2cos2sin)(2121aaacciijjjiij0 0ijijjjiiaaaa，22cot第36页/共63页第三十七页，共64页。38Th14为对称矩阵；设nnijaAR(1)(；设)(0jiaij(2)；),(2222

17、jlilaaccjliljlil (2)0jiijcc；nslnsllslsca1,1,22(1)则；222222ijjjiijjiiaaacc(3)nlllijaADaADCD122)(2)，(4)sllsijaASaASCS22)(2)，(5)第37页/共63页第三十八页，共64页。39古典(gdin)Jacobi方法：为对称矩阵设)()1(1lsaAA, 0|max|11lssljiaa设)(),()2(111211111lsTaPAPAjiPP，, 0)2()2(1111ijjiaaAA 1TPAPA1112TkkkkTkkkkPPPAPPPPAPA)()(11111), 2 , 1(

18、kAk 第38页/共63页第三十九页，共64页。40Th15阶对称矩阵；为设naAAij)(1(1)，则方法产生古典Jacobi(2)kATkkkkPAPA1DAkklim(对角(du jio)矩阵)Jacobi方法(fngf)的特点Jacobi过关(gugun)方法第39页/共63页第四十页，共64页。41Def对A非对角元素(yun s)扫描一次为：for i=1,2,n-1 for j=i+1,n (3) goto | (1),|ijaif0,),(jiijTccPAPCjiPP (2)使，作选取j continue (3)i continue 。或关口为某一阀值其中)( 第40页/共6

19、3页第四十一页，共64页。42Jacobi过关(gugun)方法：阶对称矩阵为设naAij)(2121)()2(11120ASanlnlsls；设置阀值n/01 (1)()(1mlsmaAA)(|1)(slamls ；缩小阀值n/12 (2)(|2)(slarls t,21系列关口重复上述过程，经过一 (3)0)(nt第41页/共63页第四十二页，共64页。43)()(tlstaA )()(0slnt对所有 |)(tlsa2022222)() 1()()(ttsltlstnnnaAS2)()(ASASt第42页/共63页第四十三页，共64页。44Householder方法(fngf)Def,

20、0, 1,)(ijnnijbjibB如果设R(1)即矩阵为上则称,HessenbergBnnnnnnbbbbbbbbB 12222111211矩阵。可约上为不，则称如果Hessenberg (2)Bnibii) 1, 2 , 1(0, 1第43页/共63页第四十四页，共64页。45本节讨论(toln)下列两个问题：矩阵；矩阵为上约化一般用用正交相似变换HessenbergrHouseholde1)()(矩阵为三对角矩阵。约化对称用用正交相似变换)()(rHouseholde2第44页/共63页第四十五页，共64页。46AA 1kkkkUAUA1), 2 , 1(k 初等(chdng)反射矩阵第

21、45页/共63页第四十六页，共64页。47设(1)nnnnnnaaaaaaaaaA 212222111211(1)1(1)(1) 221211ACAA1A，11nCR01C不妨设TuuIR11111 选择初等反射阵1111eCR 使1 RU11第46页/共63页第四十七页，共64页。4812211112111112RARCRRAaUAUA(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，22nCR第47页/共63页第四十八页，共64页。49AA 11

22、112UAUA 111kkkkUAUA步：第k(2)(k)k(k)(k) 2212110ACAAAkkn-kn-kk矩阵，阶上为其中Hessenberg (k)kA11)()()(22knknkknkACRR，第48页/共63页第四十九页，共64页。500kC设,kR 选择初等反射阵1eCRkkk 使kkkRIU 令n-kkkkkkkkkkkkkkRARCRRAAUAUA)()()( 2212111)()()( 12211121110kkkkACAA矩阵阶上为其中Hessenberg )(1111kAk第49页/共63页第五十页，共64页。51221122nnUUAUUUU )1(12)2(2

23、22)1(11nnnn-n-aaa 1nA第50页/共63页第五十一页，共64页。52Th16)(阵约化阵为上HessenbergrHouseholde221,nnnUUUA，则存在初等反射阵设RHAUUUUAUUUUTnn00221122使需计算：kkkkkUAUAA1TkkkkuuIR1初等反射阵： (1)TkkkCR)0 , 0 ,( 使约化计算 (2)kkkRIU AUAUkkk第51页/共63页第五十二页，共64页。53Th17等反射阵为对称矩阵，则存在初设nnAR221122nnUUAUUUUTaaannnn-n- )1(112)2(2211)1(11 ，则正交矩阵令)(2210n

24、UUUU使221,nUUUTAUUT00(对称三对角(du jio)矩阵)第52页/共63页第五十三页，共64页。54QR 算法(sun f)引言(ynyn)QR算法(sun f)及收敛性nnijaAAR)(1设分解：进行对QRAA 1QRA正交矩阵上三角矩阵在一定条件下，kA本质上收敛于上三角阵！第53页/共63页第五十四页，共64页。55Th18 (基本(jbn)QR方法)，设nnijaAAR)(1), 2 , 1(1kQRARQAQRkkkkkk 算法：为上三角阵，且记为正交阵，其中kkRQ1221RRRRQQQQkkkk，则：；，即相似于kkTkkkkQAQAAA11)(1；kTkkT

25、kkQAQQQQAQQQA)()()(12112112kkkkRQAQRA)(分解式为：的3第54页/共63页第五十五页，共64页。56引理)()(kIRIQkIMRQRQMkkkkkkkk，则：元素的上三角阵，如果为具有正对角为正交阵，其中设 第55页/共63页第五十六页，共64页。57Th19 (QR方法(fngf)的收敛性)，设nnijaAAR)(1；的特征值满足0|)(21nA1，使奇异矩阵具有标准型，即存在非XA)(2),(211nDXDXAdiag，其中算法产生，则由有三角分解且记QRLUXX11阵，即本质上收敛于上三角矩kAnkRA 21)(本质上*)(k第56页/共63页第五十七页，共64页。58或ikiia)()(1)(k0)()(kijaji时，当2)(k)()()(kijkkijaAaji的极限不一定存在，时，当Th20 ),(19)(21nknnijDAQRThaAd