特征值和特征向量的數(shù)值算法PPT課件

1、一對(duì)共軛復(fù)特征值。的是階對(duì)角塊的兩個(gè)特征值的實(shí)特征值，每一個(gè)二角塊即為一個(gè)一階對(duì)為一階或二階方陣，每其中的對(duì)角塊AAmiRii), 2 , 1(我們稱這種分塊上三交陣為矩陣A的Schur分塊上三角陣，上三角陣和對(duì)角陣是它的特殊情形。定理7.9并沒(méi)有解決如何計(jì)算全部特征的問(wèn)題。7.4.1 化矩陣為化矩陣為Hessenberg形形對(duì)于實(shí)對(duì)稱矩陣，可通過(guò)正交相似變換約化為對(duì)角矩陣。那么，對(duì)于一般的實(shí)矩陣，通過(guò)正交相似變換可約化到什么程度呢？線性代數(shù)中有如下結(jié)果。，使得存在正交矩陣對(duì)于任何矩陣QRAnn,mmmmTRRRRRRAQQ22211211定理定理7.9 （實(shí)實(shí)Schur分解定理分解定理）第1

2、頁(yè)/共24頁(yè)定義定義7.20ijnnijbRbB的次對(duì)角線以下的元素）（若矩陣(ij+1), 則稱B為上Hessenberg矩陣，簡(jiǎn)稱Hessenberg形，即B的形狀為B是可約的，則（有一個(gè)次對(duì)角元如若BnkbBkk),110, 1矩陣的特征值問(wèn)題。問(wèn)題約簡(jiǎn)為求解較小的形，可把求解特征值的約的否則是不可約。對(duì)于可Hessenberg可以用平面旋轉(zhuǎn)變換化矩陣為Hessenberg形,下面介紹另一種正交變換。為了節(jié)省運(yùn)算工作量，實(shí)用的方法是先將矩陣約化為與Schur分塊上三角陣很近似的Hessenberg形。第2頁(yè)/共24頁(yè)定義定義7.3則稱設(shè)向量, 1,2wRwnTwwIwH2)(（7.4.1

3、）為為（初等）鏡面反射矩陣（初等）鏡面反射矩陣，或，或Householder變換矩陣變換矩陣。Houholder矩陣H=H（w）有如下性質(zhì)： ，。事實(shí)上，顯然有是對(duì)稱正交陣，即HHHHHHTT1(1)得知又由12 wwwT。IwwwwwwIHHHTTTT)(442(2)22,xyHxyRxn有記對(duì)任何(3) 記S為與w垂直的平面,則幾何上x(chóng)與y=Hx關(guān)于平面S對(duì)稱。事實(shí)上,由得知xwwIHxyT)2( 。wxwyxT)(2上式表明向量x-y與w平行，注意到y(tǒng)與x的長(zhǎng)度相等，于是x經(jīng)變換后的象y=Hx是x關(guān)于s對(duì)稱的向量，如圖7-1所示。第3頁(yè)/共24頁(yè)xwyx-y圖圖7-1對(duì)應(yīng)于性質(zhì)（2），有

4、下面的定理。，使則有鏡面反射矩陣且設(shè)HyxyxRyxn,22定理定理7.10得Hx=y。則有令12,)(22wwwIHyxyxwT證證知由yyxxTT第4頁(yè)/共24頁(yè)。22)()(2)(2yxyxyxyyyxxxxyxTTTTT。yyxxyxxyxyxxxwwxHxTT)()(2222由此可得定理得證。，使得有鏡面反射矩陣是對(duì)該定理的一個(gè)重要應(yīng)用HxxxxTn0),(21。1eHx（7.4.2）的計(jì)算公式為。矩陣其中HexxsignT)0 , 0 , 1 (,)(121。，TuuIHxexu111)(,（7.4.3）第5頁(yè)/共24頁(yè)值計(jì)算的盡量大，從而有利于數(shù)使分母的的符號(hào)的選取，是為了關(guān)于穩(wěn)

5、定性。（7.4.2）的意義是對(duì)向量作消元運(yùn)算。與平面旋轉(zhuǎn)不同的是，鏡面反射變換可成批的消去向量的非零元。，使構(gòu)造鏡面反射對(duì)于向量HxT,) 1 , 1 , 5 , 3(。TxxsignHx)0 , 0 , 0 , 1 ()(21例例7.4 解解。Texuxxsignx) 1 , 1 , 5 , 9(, 6)(, 61212）得。按（3 . 4 . 754,1082u。53159153595529459945275411TuuIH第6頁(yè)/共24頁(yè)（7.4.4），使得存在正交陣對(duì)于任何矩陣，QRAnn,。AQQBT定理定理7.11為為Hessenberg形形。維向量。不含對(duì)角線）的第一列對(duì)角線以下

6、（為，設(shè)1111nAaAA證證111111,12 . 4 . 7eeaHHn其中，使得階對(duì)稱正交陣）可構(gòu)造根據(jù)（。用是對(duì)稱正交陣，顯然。記1111111), 1 ()0 , 0 , 1 (PPPHdiagPRnT作相似變換，易知對(duì)11AP。11112PAPA第7頁(yè)/共24頁(yè)造維向量，那么同理可構(gòu)角線）列對(duì)角線以下（不含對(duì)的第為記2222nAa22112222) , 0 , 0 , 1 (,2IReeaHHnnT。記其中，使得階對(duì)稱正交陣做相似對(duì)為對(duì)稱正交陣。用顯然階單位向量，為222222),(2APPHIdiagP 變換，有。212223PAPA如此類推，經(jīng)n-2步對(duì)稱正交相似變換，得到He

7、ssenberg形矩陣。2211222221nnnnnnPPAPPPPPAPA）。定理得證。，則有（若記4 . 4 . 7,2211nnPPPQAB第8頁(yè)/共24頁(yè)為，使得存在正交陣對(duì)于任何對(duì)稱矩陣AQQBQRATnn,推論7.1對(duì)稱三對(duì)角陣。這時(shí)，可以的維數(shù)大于的向量的矩陣，第一列被消元形。對(duì)于階數(shù)大于231a上述定理7.11的證明是構(gòu)造的，即可以用鏡面反射化矩陣Hessenberg形。此定理可用平面旋轉(zhuǎn)變換來(lái)證明，即也可用平面旋轉(zhuǎn)變換化矩陣為Hessenberg逐個(gè)化為零。個(gè)分量開(kāi)始的非零元素的從第，把連續(xù)使用平面旋轉(zhuǎn)變換21a如此類推，最后得到的正交矩陣Q，是平面旋轉(zhuǎn)矩陣的乘積。7.4.

8、2 QR算法及其收斂性算法及其收斂性 QR算法可以用來(lái)求任意的非奇異矩陣的全部特征值，是目前計(jì)算這類問(wèn)題最有效的方法之一。它基于對(duì)任何實(shí)的非奇異矩陣都可以分解為正交陣Q和上三角矩陣R的乘積。第9頁(yè)/共24頁(yè) 定理7.2 (QR分定理)正交陣與為非奇異矩陣，則存在設(shè)nnRA上三角陣R,使得A=QR,且當(dāng)R的對(duì)角元素均取正時(shí),分解是唯一的。證類似于定理7.11的證明，對(duì)矩陣A的左乘一系列正交變換矩陣，可以將A化為上三角形矩陣，因此，可得A的QR分解。下面證明分解的唯一性。設(shè)有兩種分解2211RQRQA此可得的對(duì)角元均為正數(shù)。由，而且21RR。11212RRQQT上式左邊為正交陣，即。）（）（111

9、2112RRRRT這個(gè)式子左邊是下三角陣，則右邊是上三角陣，所以只能是對(duì)角陣。設(shè)),(21112nddddiagRRD，進(jìn)而，從而故有且則有122, 2 , 1, 0,RRIDnidIDDDiT定理得證。，21QQ 第10頁(yè)/共24頁(yè)一般按平面旋轉(zhuǎn)變換或鏡面反射變換作出的分解A=QR，R的對(duì)角元不只要令一定是正的。設(shè)),(ijrR ),(22221111nnnnrrrrrrdiagD就是符合的上三角陣，這樣，為對(duì)角元是為正交陣，_1_RQArRDRQDQii定理7.12的唯一QR分解。BAQQBRQBQRAQRAT。這說(shuō)明，則有，那么令分解，即的設(shè)有，得陣。令分解，又可得一新的矩繼續(xù)作有相同的

10、特征值。對(duì)與AAQRBA1如下的算法：。, 2 , 1,1kQRARQAkkkkkk（7.4.5）的方法稱為）得到矩陣序列由（kA5 . 4 . 7或稱為基本QR算法。 QR算法，第11頁(yè)/共24頁(yè)證證 容易證容易證(1)從它遞推得從它遞推得,)()(11121121111kkTkkTkkkTkkQAQQQQAQQQQAQA1_1_1221_kkkkkkkRAQRRRQQQRQ。1_1_1_1_1_1kkkkTkkRQARQAQQ）。定理得證。，即證得（由此推及21111_1_AARQRQkA定理定理7.13QR算法產(chǎn)生的序列算法產(chǎn)生的序列 滿足滿足:;1kkTkkQAQA。，其中12_21_

11、,RRRRQQQQRQAkkkkkk（1）（2）kA一般情形下，QR算法的收斂性比較復(fù)雜。若矩陣序列 對(duì)角元均收斂，且嚴(yán)格下三角部分元素均收斂到零，則對(duì)求A的特征值而言已經(jīng)足夠了。此時(shí)，我們稱 基本收斂到上三角陣。下面對(duì)最簡(jiǎn)單的情性給出收斂性定理。kA第12頁(yè)/共24頁(yè)設(shè)矩陣 的特征值滿足kA定理7.14,nnRA, 021n121),(, 2 , 1,XxxxXnixnii的逆可分解為。若矩陣對(duì)應(yīng)特征向量=LU，其中L為單位下三角陣U為上三角陣，則QR算法產(chǎn)生的序列 基本收斂到上三角陣，其對(duì)角極限為。niaikiin, 2 , 1,lim)(kAkA更一般地，在一定條件下，由QR算法生成的序

12、列 收斂為Schur分塊上三角形，對(duì)角塊按特征值的模從大到小排列，上述定理是它的特殊情形。當(dāng)收斂結(jié)果為Schur分塊上三角形時(shí)，序列 的對(duì)角塊以上的元素以及2階塊的元素不一定收斂，但不影響求全部特征值。例7.5 用QR方法求下列矩陣的全部特征值。112112314)2( ,151311313153) 1 (第13頁(yè)/共24頁(yè)解先用鏡面反射變換化矩陣A為Hessenberg形矩陣 ，然后用平面旋轉(zhuǎn)變換作QR分解進(jìn)行迭代，生成序列 。（1）的計(jì)算結(jié)果為1AkA，2062. 14639. 05361. 59738.129284.137282. 23077. 40000. 31A，5229. 1465

13、6. 09381. 06362. 05511. 18265. 07711.171133.102A，9980. 10012. 06317. 10019. 30000. 02165. 99820.160001. 616A。9999. 10000. 06329. 100001. 30000. 02364. 99712.160000. 623A第14頁(yè)/共24頁(yè)該矩陣A非對(duì)稱，從計(jì)算結(jié)果看，收斂于上三角陣。（2）的計(jì)算結(jié)果為,0000. 10000. 10000. 10000. 18284. 24142. 18284. 20000. 41A,4000. 04899. 03266. 02667. 174

14、54. 01121. 59379. 13333. 22A,3333. 27456. 07263. 33336. 00002. 06516. 38171. 00003. 225A。9998. 02349. 22366. 29996. 20001. 02374. 29999. 20002. 226A第15頁(yè)/共24頁(yè) 從計(jì)算結(jié)果來(lái)看，迭代收斂于Schur分塊上三角形，對(duì)角塊分別是1階和2階子 ，迭代已接近收斂。階子矩陣的特征值都是的右下角的和矩陣。事實(shí)上，矩陣iAA0000.19999.022625 一般在實(shí)際使用QR方法之前，先用鏡面反射變換將A化為Hessenberg形矩陣H，然后對(duì)H作QR迭

15、代，這樣可以大大節(jié)省運(yùn)算工作量。因?yàn)樯?Hessenberg陣H的 次對(duì)角線以下元素均為零，所以用平面旋轉(zhuǎn)變換作QR分解較為方便。 對(duì)i = 1,2,.n - 1,依次用平面旋轉(zhuǎn)矩陣J（i , i+1）左乘H，使J（i , i+1）H的第i +1行第i列元素為零。左乘J(i,i+1)后，矩陣H的第i行與第i+1行零元素位置上仍為零，其他行不變。這樣，共n-1次左乘正交矩陣后得到上三角陣R。即 =R， =J（n-1,n）J(n-2,n-1)J(1,2)?？梢则?yàn)證 是一個(gè)下Hessenberg陣，即U是一個(gè)上Hessenberg陣。這樣，得到H的QR分解H=UR。在作QR迭代時(shí)，下一步計(jì)算RU，容

16、易驗(yàn)證RU是一個(gè)上Hessenberg陣。以上說(shuō)明了QR算法保持了H的上Hessenberg結(jié)構(gòu)形式。 HUTUTUT例 7.6求Hessenberg形矩陣 2100322023011525H的特征值。 第16頁(yè)/共24頁(yè)解解），使得，（），（），（有平面旋轉(zhuǎn)矩陣的次對(duì)角線非零元素，根據(jù)令43322111JJJHHH 7822. 00002736. 35242. 2005288. 25852. 10381. 203922. 04912. 59612. 10992. 58989. 03962. 0000740. 01761. 09813. 004192. 08804. 01887. 01961.

17、 01038. 01923. 00377. 09806. 0111RUH，逆序相乘，求出和）。然后將求得的，（），（），（其中2111213243HRUJJJUT7031. 03099. 0001294. 38525. 04770. 205361. 15171. 29401. 13997. 02390. 05922. 19508. 56157. 4112URH重復(fù)上面的過(guò)程，計(jì)算11次得0000. 1*1211. 03290. 1*5910. 38789. 1*0000. 412H至此，不難看出，一個(gè)特征值是4，另一個(gè)特征值是-1，其他兩個(gè)特征值是方程第17頁(yè)/共24頁(yè), 020775234上

18、述用QR方法求得的特征值是該特征方程的準(zhǔn)確解。7.4.3 帶原點(diǎn)位移的帶原點(diǎn)位移的QR算法算法 前面我們介紹了在反冪法中應(yīng)用原點(diǎn)位移的策略，這種思想方法也可用于QR算法。一般我們針對(duì)上Hessenberg矩陣討論QR算法，并且假設(shè)每次QR迭代中產(chǎn)生的 都是不可約的，否則，可以將問(wèn)題分解為較小型的問(wèn)題。這樣，帶原點(diǎn)位移的QR算法可以描述為：。（正交相似變換），分解），（形（初始化），的為取,2, 111kIsQRAQRRQIsAHessenbergAAkkkkkkkk變換的變換稱為原點(diǎn)位移的到這里QRAAkk1,01211. 03290. 15910. 38789. 1的特征方程為陣。事實(shí)上，可

19、以求得矩的根，求得為Hi 21第18頁(yè)/共24頁(yè)即每個(gè)所以，由于kkTkkkkkkTkkTkkkkkTkkkkQAQAQIsRQQQQsQRQQIsQR1,)( 的其余近似特征值?？芍鸩角蟪鏊惴?，就應(yīng)用縮方法，即對(duì)的近似特征值。采用收作為且基本收斂于三角陣，并則在一定的條件下，取階順序主子矩陣，若選的是。設(shè)的序列陣生一正交相似于反復(fù)應(yīng)用上述變換就產(chǎn)不同的位移相似。實(shí)際計(jì)算時(shí)，用相似，從而與原矩陣都與AQRRBAaAasnABaAAHessenbergsssAAAnnkknnkknnkkknnkijkkkk11211,1, ,1,11,1,11,1,knnknnknnknnknnknnaaaaA

20、aa則與相鄰元素進(jìn)行，取準(zhǔn)或者將充分小的準(zhǔn)則可以是判別 的一個(gè)近似特征值。就作為足上述準(zhǔn)則時(shí)，可認(rèn)為為給定的精度要求。滿其中Aaaknnknn, 01,第19頁(yè)/共24頁(yè)根據(jù)QR算法的收斂性質(zhì)，位移量有下列兩種取法： 最接近的一個(gè)。的特征值中與取為矩陣。knnknnknnknnknnkknnkaaaaasas1, 11, 121變換可表達(dá)為進(jìn)行原點(diǎn)位移的矩陣轉(zhuǎn)變換對(duì)具體計(jì)算時(shí)，用平面旋QRAHessenberg1。IsPPPRARIsAPPPTnnTTnn1, 12312121111223, 1,)(矩陣。仍為上容易驗(yàn)證，HessenbergA2例7.7 用帶原點(diǎn)位移的QR算法求下列矩陣的特征

21、值：611142121A第20頁(yè)/共24頁(yè)解 先用鏡面反射變換把A化為上Hessenberg矩陣。按（7.4.3）式有4 .62 .002 .06 .35051,525/105/15/2000121AHHAwwIHTT,114997409. 0,392590761. 0, 5 . 6211s角元素，則有量，即取位移量為右下若按第一種方法取位移,cossin0sincos0001,1000cossin0sincos2222211111PP同理可得421062856. 6002432908. 00002432908. 0779171336. 4666846149. 00666846149. 020

22、0234192. 04 . 6,021202899. 0183563711. 0743000879. 1076516671. 0137183510. 3844655679. 5)4 . 6(21121121IPPRAIAPPRTT第21頁(yè)/共24頁(yè)421066615.6000866668465.4036401350.00036401350.0287735078.0,421066615.6000000006.00000000006.0862139274.4157002612.00157002612.0283205888.043AA。，矩陣的特征值，得。求左上角故有特征值866925525. 4287992138. 022421066615. 6213類似于上面的計(jì)算可得，矩陣的特征值，則有量，即取