1、會(huì)計(jì)學(xué)1矩陣特征值與特征向量的計(jì)算方法矩陣特征值與特征向量的計(jì)算方法2引言nnijaAR)(aaa 110)(naaaa 11na)(njnijea21)(), 2 , 1(nj第1頁(yè)/共63頁(yè)3Th1；，其中的特征值，且為設(shè)0 xxAxA(1)次多項(xiàng)式；為任一設(shè)mxrxrrxPmm10)(2)則：定義矩陣 mmArArIrAP10)(；的特征值，即為xPxAPAPP)()()()( 1)的特征向量。為且)()(APxP 2)Th2，則為相似矩陣，即與設(shè)APPBBA1有相同的特征值；與BA 1)(的特征向量。是的特征向量，則是若APyBy 2)(第2頁(yè)/共63頁(yè)4Th3(Gerschgorin

2、圓盤定理)某個(gè)圓盤；下述的每一個(gè)特征值必屬于則設(shè)AaAnnij,)(1), 2 , 1(|njaraijijiii 的一個(gè)特征值。中精確地包含則，即為孤立圓盤個(gè)圓盤是分離的且與其他是由一個(gè)圓盤組成的特征值。特別，當(dāng)個(gè)內(nèi)恰包含，則即不相交個(gè)圓盤是分離的且與余下的連通的圓盤組成并集的若ASnSAmSmnSmA)(1)()(2)第3頁(yè)/共63頁(yè)5411101014 A例：設(shè)1|4|1zD：2|2zD：2|4|3zD：孤立圓盤531), 1 , 1 (910diagDADDA11|4|1 zD：9192|zD：8 . 1|4|3zD：三個(gè)孤立圓盤第4頁(yè)/共63頁(yè)6Th4(Schur定理)使，則存在酉陣

3、設(shè)UAnnRRrrrrrrAUUnnnnH 22211211(上三角陣)的特征值。為其中Aniriii), 2 , 1(第5頁(yè)/共63頁(yè)7Th5(實(shí)Schur分解)使，則存在正交矩陣設(shè)QAnnRnnnnTRRRRRRAQQ 22211211的一對(duì)共軛復(fù)特征值。塊的兩個(gè)特征值是對(duì)角的實(shí)特征值，每個(gè)二階是且每個(gè)一階為一階或二階方陣，其中對(duì)角塊AARmiRiiii), 2 , 1(第6頁(yè)/共63頁(yè)8Def，稱為對(duì)稱矩陣，設(shè)0 xAnnR),(),()(xxxAxxR商。的瑞利為對(duì)應(yīng)向量)(Rayleighx第7頁(yè)/共63頁(yè)9Th6為為對(duì)稱矩陣，其特征值設(shè)nnAR組成規(guī)范化正交組，則其對(duì)應(yīng)的特征向量n

4、nxxx,2121 )0,(),(),(1xxxxxAxnnR (1)(max01xRxxnR (2)(min0 xRxxnnR (3)第8頁(yè)/共63頁(yè)10冪法及反冪法冪法，nnijaAR)(有一組完全的特征向量組，), 2 , 1(nixAxiii 線性無(wú)關(guān),21nxxx |21n主特征值第9頁(yè)/共63頁(yè)11冪法的其本思想nvR 0任取初始向量01Avv 0212vAAvv011vAAvvkkk的關(guān)系：與、現(xiàn)分析11kvx 第10頁(yè)/共63頁(yè)12Th7；個(gè)線性無(wú)關(guān)的特征向量有設(shè)naAnnijR(1)(|21nA (2)的特征值滿足設(shè)), 2 , 1()0(0110kAvvvkk (3)且冪法

5、：則：；111limxvkkk (1)11)()(limikikkvv (2)第11頁(yè)/共63頁(yè)13|121nrr若A的主特征值為實(shí)的重根，個(gè)線性無(wú)關(guān)的特征向量有設(shè)nxxxnA,21 ), 2 , 1(1rixAxii 且), 1(nrixAxiii 0v 任取初始向量),(11不全為零且rniiix由冪法有0vAvkk)(1111nriikiiriiikxxkriiikkkxv11lim 第12頁(yè)/共63頁(yè)14非零向量的規(guī)范化v )max(vv u 絕對(duì)值最大的分量表示向量vv )max(迭代序列規(guī)范化序列000 vu01Auv )max(111vvu 1kkAuv)max(kkkvvu 第

6、13頁(yè)/共63頁(yè)15改進(jìn)的冪法)0(0100vu設(shè)1kkAuv)max(kkvkkkvu/迭代：規(guī)范化：, 2 , 1k第14頁(yè)/共63頁(yè)16迭代序列規(guī)范化序列01Auv )max(001AvAvu )max(0022AvvAv )max(02022vAvAu )max(010vAvAvkkk)max(00vAvAukkk（*）第15頁(yè)/共63頁(yè)17niiixv10niikiikxvA10)(111kkx(*)(0)(21kxniikiik )max(00vAvAukkk)(max()(111111kkkkxx)max(1111kkxx)max(11xx第16頁(yè)/共63頁(yè)18)max(010v

7、AvAvkkk)(max()(11111111kkkkxx)max(111111kkxx)max(kkv)max()max(111111kkxx)(1k 有下列結(jié)論：第17頁(yè)/共63頁(yè)19Th8；個(gè)線性無(wú)關(guān)的特征向量有設(shè)naAnnijR(1)(|21nA (2)的特征值滿足：設(shè)：由改進(jìn)冪法得到，則有,kkvu(3)max(lim11xxukk (1)1)max(limlimkkkkv (2)(改進(jìn)冪法), 2 , 1(nixAxiii 且確定。且收斂速度由|12r第18頁(yè)/共63頁(yè)20加速方法原點(diǎn)平移法pIAB 引進(jìn)矩陣nA，：21pppBn，：21特征向量相同), 3 , 2(|1nippi

8、 (1)|max1212 (2)ppjnj|/|12r改進(jìn)第19頁(yè)/共63頁(yè)21，其特征值是實(shí)數(shù)，nnijaAR)(？如何選擇 pn21設(shè)pppIABn或的主特征值為則111x、為計(jì)算|1pppn滿足要求且min|,|max112ppppn即求極值問(wèn)題|,|maxmin112ppppnp22*np第20頁(yè)/共63頁(yè)22，其特征值是實(shí)數(shù)，nnijaAR)(nn121 若pppIABn或的主特征值為則1nnx、為計(jì)算|1pppn滿足要求且min|,|max11ppppnnn211*np第21頁(yè)/共63頁(yè)23Rayleigh商加速為對(duì)稱矩陣nnijaAR)(Th9足為對(duì)稱矩陣，特征值滿設(shè)nnAR(1

9、)；|21n ；對(duì)應(yīng)的特征向量滿足ijjixx),(2)；應(yīng)用改進(jìn)的冪法計(jì)算1(3)近似較好的給出商的則規(guī)范化向量序列1)(kkuRuRayleigh)(),(),()(2112kkkkkkouuuAuuR第22頁(yè)/共63頁(yè)24反冪法(逆迭代)為非奇異矩陣，且nnAR；|21n ，對(duì)應(yīng)的特征向量，nxxx,21 的特征值為1A；|1|1|121n ，對(duì)應(yīng)的特征向量，nxxx,21 求矩陣按模最小的特征值及對(duì)應(yīng)的特征向量應(yīng)用冪法即可！對(duì)1A第23頁(yè)/共63頁(yè)25反冪法的迭代公式)0(000nvu設(shè)11kkuAv)max(kkvkkkvu/迭代：規(guī)范：, 2 , 1k1kkuAv綜合得到：第24頁(yè)

10、/共63頁(yè)26Th8；個(gè)線性無(wú)關(guān)的特征向量有設(shè)naAnnijR(1)(0|11nnA (2)的特征值滿足：設(shè)滿足：量序列有上述反冪法得到的向,kkvu(3)max(limnnkkxxu (1)nkk1lim (2)(反冪法), 2 , 1(nixAxiii 且確定。且收斂速度由|1nnr第25頁(yè)/共63頁(yè)27反冪法的應(yīng)用 求近似特征值的特征向量應(yīng)用冪法：對(duì)1)( pIA11)(kkupIAv)max(kkvkkkvu/第26頁(yè)/共63頁(yè)28Th10，個(gè)線性無(wú)關(guān)的特征向量有設(shè)naAnnijR(1)(且，設(shè)的一個(gè)近似取1)()(pIApjj (2)滿足：序列則由反冪法得到的向量,kkvu)max(

11、limjjkkxxu (1)pjkk1lim (2), 2 , 1(nixAxiii 即確定。且收斂速度由|min|pprijij)(|jippij jkp1第27頁(yè)/共63頁(yè)2911)(kkupIAv1)(kkuvpIA第28頁(yè)/共63頁(yè)30計(jì)算對(duì)稱矩陣特征值的Jacobi方法引言Th10，使得正交矩陣對(duì)稱矩陣，則存在一個(gè)設(shè)PaAnnijR )(),(21nTAPPdiag的特征值；為且Anii), 2 , 1(1)的特征向量。對(duì)應(yīng)為列向量jjnAvvvvP),(212)對(duì)稱矩陣第29頁(yè)/共63頁(yè)31Jacobi方法的基本思想,21PP變換選擇一系列GivesAA 1TkkkkPAPA1,

12、2 , 1k收斂于對(duì)角陣kA),(21ndiag22211211aaaaA csscP sincossc 第30頁(yè)/共63頁(yè)3222211211ccccPAPT 02112 cc2sin2122221111asacac 2sin2122221122acasac 2cos2sin)(211122212112aaacc 02112 cc 12221122cotaaa 第31頁(yè)/共63頁(yè)33古典Jacobi方法11),( c s s c jiPij1cossinsincos1),( jiPsincoss c第32頁(yè)/共63頁(yè)34TPAPCAjjjiijiicccc cssc jjjiijiiaaaa

13、 cssc ),()()(jliljiC元素行列，第行列第csscaaccljliljli ),(),(), 2 , 1(jlilnl；jliljlilcccssccc ), 2 , 1(jlilnl；第33頁(yè)/共63頁(yè)35Th12為對(duì)稱矩陣；設(shè)nnijaAR(1)(變換；則為平面旋轉(zhuǎn)，其中設(shè)),(jiPPPAPCT(2)22|FFAC|(1)；即)1,1,22nslnsllslsca(22222222ijjjiiijjjiiaaaccc(2)第34頁(yè)/共63頁(yè)36Th13)(的元素計(jì)算公式TPAPC 為對(duì)稱矩陣；設(shè)nnijaAR(1)(，則變換，為平面旋轉(zhuǎn)，其中設(shè))(),(ijTTaPAPC

14、jiPPPAPC(2)2cos2sin)(2sin2sin212222ijiijjjiijijjjiijjijjjiiiiaaaccacasacasacac (1)jliljljlililcasacsacacjiC，行元素行，第第(2), 2 , 1(jlilnl；第35頁(yè)/共63頁(yè)37ljlijlljlilicasacsacacjiC，列元素列，第第(3), 2 , 1(jlilnl；2cos2sin)(2121aaacciijjjiij0 0ijijjjiiaaaa，22cot第36頁(yè)/共63頁(yè)38Th14為對(duì)稱矩陣；設(shè)nnijaAR(1)(；設(shè))(0jiaij(2)；),(2222jli

15、laaccjliljlil (2)0jiijcc；nslnsllslsca1,1,22(1)則；222222ijjjiijjiiaaacc(3)nlllijaADaADCD122)(2)，(4)sllsijaASaASCS22)(2)，(5)第37頁(yè)/共63頁(yè)39古典Jacobi方法：為對(duì)稱矩陣設(shè))()1 (1lsaAA, 0|max|11lssljiaa設(shè))(),()2(111211111lsTaPAPAjiPP，, 0)2()2(1111ijjiaaAA 1TPAPA1112TkkkkTkkkkPPPAPPPPAPA)()(11111), 2 , 1(kAk 第38頁(yè)/共63頁(yè)40Th15

16、階對(duì)稱矩陣；為設(shè)naAAij)(1(1)，則方法產(chǎn)生古典Jacobi(2)kATkkkkPAPA1DAkklim(對(duì)角矩陣)Jacobi方法的特點(diǎn)Jacobi過(guò)關(guān)方法第39頁(yè)/共63頁(yè)41Def對(duì)A非對(duì)角元素掃描一次為：for i=1,2,n-1 for j=i+1,n (3) goto | (1),|ijaif0,),(jiijTccPAPCjiPP (2)使，作選取j continue (3)i continue ?；蜿P(guān)口為某一閥值其中)( 第40頁(yè)/共63頁(yè)42Jacobi過(guò)關(guān)方法：階對(duì)稱矩陣為設(shè)naAij)(2121)()2(11120ASanlnlsls ；設(shè)置閥值n/01 (1)(

17、)(1mlsmaAA)(|1)(slamls ；縮小閥值n/12 (2)(|2)(slarls t,21系列關(guān)口重復(fù)上述過(guò)程，經(jīng)過(guò)一 (3)0)(nt第41頁(yè)/共63頁(yè)43)()(tlstaA )()(0slnt對(duì)所有 |)(tlsa2022222)() 1()()(ttsltlstnnnaAS2)()(ASASt第42頁(yè)/共63頁(yè)44Householder方法Def, 0, 1,)(ijnnijbjibB如果設(shè)R(1)即矩陣為上則稱,HessenbergBnnnnnnbbbbbbbbB 12222111211矩陣?？杉s上為不，則稱如果Hessenberg (2)Bnibii) 1, 2 ,

18、1(0, 1第43頁(yè)/共63頁(yè)45本節(jié)討論下列兩個(gè)問(wèn)題：矩陣；矩陣為上約化一般用用正交相似變換HessenbergrHouseholde1)()(矩陣為三對(duì)角矩陣。約化對(duì)稱用用正交相似變換)()(rHouseholde2第44頁(yè)/共63頁(yè)46AA 1kkkkUAUA1), 2 , 1(k 初等反射矩陣第45頁(yè)/共63頁(yè)47設(shè)(1)nnnnnnaaaaaaaaaA 212222111211(1)1(1)(1) 221211ACAA1A，11nCR01C不妨設(shè)TuuIR11111 選擇初等反射陣1111eCR 使1 RU11第46頁(yè)/共63頁(yè)4812211112111112RARCRRAaUAUA

19、(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頁(yè)/共63頁(yè)49AA 11112UAUA 111kkkkUAUA步：第k(2)(k)k(k)(k) 2212110ACAAAkkn-kn-kk矩陣，階上為其中Hessenberg (k)kA11)()()(22knknkknkACRR，第48頁(yè)/共63頁(yè)500kC設(shè),kR 選擇初等反射陣1eCRkkk 使kkkRIU 令n-kkkkkkkkkkkkkkRARCRRAAUAUA)()()

20、( 2212111)()()( 12211121110kkkkACAA矩陣階上為其中Hessenberg )(1111kAk第49頁(yè)/共63頁(yè)51221122nnUUAUUUU )1(12)2(222)1(11nnnn-n-aaa 1nA第50頁(yè)/共63頁(yè)52Th16)(陣約化陣為上HessenbergrHouseholde221,nnnUUUA，則存在初等反射陣設(shè)RHAUUUUAUUUUTnn00221122使需計(jì)算：kkkkkUAUAA1TkkkkuuIR1初等反射陣： (1)TkkkCR)0 , 0 ,( 使約化計(jì)算 (2)kkkRIU AUAUkkk第51頁(yè)/共63頁(yè)53Th17等反射

21、陣為對(duì)稱矩陣，則存在初設(shè)nnAR221122nnUUAUUUUTaaannnn-n- )1(112)2(2211)1(11 ，則正交矩陣令)(2210nUUUU使221,nUUUTAUUT00(對(duì)稱三對(duì)角矩陣)第52頁(yè)/共63頁(yè)54QR 算法引言QR算法及收斂性nnijaAAR)(1設(shè)分解：進(jìn)行對(duì)QRAA 1QRA正交矩陣上三角矩陣在一定條件下，kA本質(zhì)上收斂于上三角陣！第53頁(yè)/共63頁(yè)55Th18 (基本QR方法)，設(shè)nnijaAAR)(1), 2 , 1(1kQRARQAQRkkkkkk 算法：為上三角陣，且記為正交陣，其中kkRQ1221RRRRQQQQkkkk，則：；，即相似于kkTkkkkQAQAAA11)(1；kTkkTkkQAQQQQAQQQA)()()(12112112kkkkRQAQRA)(分解式為：的3第54頁(yè)/共63頁(yè)56引理)()(kIRIQkIMRQRQMkkkkkkkk，則：元素的上三角陣，如果為具有正對(duì)角為正交陣，其中設(shè) 第55頁(yè)/共63頁(yè)57Th19 (QR方法的收斂性)，設(shè)nnijaAAR)(1；的特征值滿足0|)(21nA1，使奇異矩陣具有標(biāo)準(zhǔn)型，即存在非XA)(2),(211nDXDXAdiag，其中算法產(chǎn)生，則由有三角分解且記QRLUXX11陣，即本