計(jì)算方法-特征值2

1、一、基本一、基本QRQR方法方法 60年代出現(xiàn)的QR算法是目前計(jì)算中小型矩陣的全部特征值與特征向量的最有效方法。 實(shí)矩陣、非奇異。 理論依據(jù)：任一非奇異實(shí)矩陣都可分解成一個(gè)正交矩陣Q和一個(gè)上三角矩陣R的乘積，而且當(dāng)R的對角元符號取定時(shí)，分解是唯一的。()(1)(1)11111(2)1(2)111()(1) QRQR (1,2,). , (2,3,)kkkkkkkAQ RkAR QAAQ RQARAR QQAQAAAAkAA基本方法的基本思想是利用矩陣的分解 通過迭代格式 由 即 。于是 即與 相似。同理可得，。故它們有相同的特征值。 將化成相似A的上三角陣（或分塊上三角陣），從而求出矩陣 的全

2、部特征值與特征向量。 可證，在一定條件下，基本QR方法產(chǎn)生的矩陣序列A(k) “基本”收斂于一個(gè)Schur型陣。即主對角線及以下元素均收斂，主對角線以上元素可以不收斂。特別的，如果A是實(shí)對稱陣，則A(k) “基本”收斂于對角矩陣。 基本QR方法每次迭代都需作一次QR分解與矩陣乘法，計(jì)算量大，而且收斂速度慢。因此實(shí)際使用的QR方法是先用一系列矩陣相似變換將 A 約化成擬上三角矩陣(稱為上Hessenberg 矩陣)，然后對此矩陣用基本QR方法。因?yàn)閿M上三角矩陣具有較多零元素，故可減少運(yùn)算量?；疉為相似的擬上三角陣的方法有多種。1HouseholderAHouseholderA（ ）用變換將矩陣

3、化成上海森柏格矩陣H。(2) 用變換將對稱矩陣 化成對稱三對角矩陣。為了求矩陣特征值先進(jìn)行初等變換把矩陣變成較簡單形式( )22,nx yRxyHouseholderHHxy定理 : 設(shè)為中任意非零向量 且則存在矩陣使得。22222 2, (2)2( ).2 2( ) .TTTTxywHIwwxyxyxyHxIwwxxxxyxyxyxyxxyxyxyHxy證：令于是 由 范數(shù)的定義. 代入上式得二、豪斯豪爾德(Householder)方法221122112122122212 (,)1,12222122 22212TnnnTnnnnwwwwwwwwwwww www wHIwww ww wwHou

4、seholder設(shè)向量 滿足 則稱為 矩陣或反射矩陣。豪斯豪爾德(Householder)變換11;(2) det()1;THHHHH 可證其具有以下性質(zhì)：（ ）是實(shí)對稱的正交矩陣，即 111211121222123233311(2,3, ),nnnnnnnnniihhhhhhhhHhhhhhhin稱形如 的矩陣為擬上三角陣，也稱為上海森堡（Hessenberg)陣。如果此對角線元全不為零 則稱該矩陣為不可約的上Hessenberg矩陣。 Householder A討論用 變換將一般矩陣 相似變換 成 Hessenberg陣.11111111,1000 01HouseholderHHH AHH

5、HHHnHouseholder首先，選取 矩陣 使得經(jīng) 相似變換后的矩陣 的第一列中有盡可能多的零元素。為此，應(yīng)取 為如下形式其中為階 矩陣。11121112131111122122221213122211111(,) ,(,) ,.(1,0,0) ,2TTnnTnnnnTaaHH AHaaaaH aH AHaaaaaaAaaHH aH AHn 于 是 有 其 中由 上 節(jié) 定 理 ， 只 要 取使 得 就 會使 得 變 換 后 的 矩 陣 的 第 一 列 出 現(xiàn) 個(gè) 零 元 。111111211111122221122,() ()1000*0100*00* *00waae sign awHH

6、aae sign aHouseholderHH H AH HH為避免在計(jì)算 時(shí)會產(chǎn)生較大的誤差 取 。同理，可構(gòu)造如下列形式 矩陣 使得*12222112222, .nnnnnHouseholderH HHHH H AH HHHHHessenbergAH如此進(jìn)行 次，可以構(gòu)造 個(gè) 矩陣 使得其中 為上 矩陣。特別地，當(dāng) 為實(shí)對稱矩陣，則經(jīng)過上述正交變換后，變?yōu)槿龑顷嚒?5222321052 22 2 02100241HouseholderAA例 用 變 換 將 矩 陣 化 成 擬 上 三 角 陣 。1111122(1,0,0) ,(1,00) .21,02TTaH aHIHIHousehol

7、derHH 解：因 由 為使 矩陣 滿足 222(), () (2,2)2(1,0)(22,2) 222 ,22 22iiiiTTTTxxe sign xwxxe sign xwwww 由 公式 ，。22 222222104422 2012222244221000010022 0022220022THIwwH2112 100052223 201001052 22 222 000210222202410022100052510100103222 000223220012220022HH H AH H 于是有四、擬上三角矩陣的QR分解2121(2)(2)(2)11112131(2)(2)(1122

8、23221 1 0(cossin00sincos000011nnHnGivensHQRhVrhhhhhhV H因?yàn)閿M上三角陣 的特殊形狀，通常用個(gè)旋轉(zhuǎn)變換（又稱變換）可將它化成上三角矩陣，從而得到 的分解式。具體步驟為：設(shè)否則進(jìn)行下一步），取旋轉(zhuǎn)矩陣 則2)(2)(2)(2)32333(2)(2)1(2)221121111112111 cos, sin, .nnnnnhhhhhhhHrhhrr其中232222232(3 )(3 )(3 )(3 )11213111(3 )(3 )(3 )223212(3 )(3 )(3 )23331332(3 )(3 )(43414 0(10cossinsinc

9、os 11 nnnnnnnnhVrhhhhrhhhhhhVHhhh（）（）設(shè)否 則 進(jìn) 行 下 一 步 ） ， 再 取 旋 轉(zhuǎn) 矩 陣 則(3 )3 )(3 )(3 )1( 2 )( 2 )( 2 )2( 2 )23222222223222 cos, sin, ()() .nnnnHhhhhrhhrr其 中( )(1)1( )( )( )( )1111111( )( )( )11111( )( )( )1( )( )( )1111( )( )1 1 kkkkkkkkkknnkkkkkkknknkkkkkknknkkkkkknknkknnnnkHVHrhhhhrhhhhhhhhhhh假設(shè)上述過程

10、已進(jìn)行了步，有()11()()1()2()21 0,11 cossinsincos1 cos, sin, ()() . kkkkkkkkkkkkkkkkkkkkkkkkkkhVhhrrrhh設(shè)取其中(1)(1)(1)11111(1)(1)1( )(1)(1)(1)(1)111111(1)(1)(1)21212(1)(1)1 1kkkkknkkkkkknkkkkkkkkkknknkkkkkknknkknnnnrhhhrhhVHHhhhhhhhhn于是因此，最多做次旋轉(zhuǎn)變( )( )( )112131( )( )2232( )( )1122133 nnnnnnnnnnnnnnnrhhhrhhHVV

11、V HRrhr換，即得121 32121 32123 (2,3, ) 4 ,( ) iiTTTnnTTTnnVinHV VVRQRQ V VVnQRO nHRQQRQR因?yàn)榫鶠檎痪仃?，故其中仍為正交矩陣?？伤愠鐾瓿蛇@一過程的運(yùn)算量約為比一般矩陣的分解的運(yùn)算量少一個(gè)數(shù)量級。可證明仍是擬上三角陣，于是可按上述步驟一直迭代下去，這樣得到的方法的運(yùn)算量比基本方法大為減少。需要說明QR的是，通常用方法計(jì)算特征值，然后用反冪法求其相應(yīng)的特征向量。222532644445 (6,4)64 (1,0)(652,4) (0.957092,0.289784) 2100.9160250.27 73500.8320

12、500.55 2010.2773500.0839747TTTTTQRAAwwwwIww用方法求矩陣的全部特征值。首先將 化成擬上三角陣解：，取例：147000.5547000.83205010000.8320500.55470000.5547000.832050H于是 11(1)2211112151.3867503.328200 7.2111021.2307688.15384000.1538462.230767, 5( 7.21102)8.774964 cos50.56980. sin0.821781 HH AHHAHQRHHrrV 即為與 相似的擬上三角矩陣。將 進(jìn)行分解，記取0.56980

13、30.821781 00.8217810.5698030001(1)2122222228.7749641.8015968.597089 00.4383101.91103000.1538462.230767 (0.438310)( 0.153846)0.464526, cos0.4383100.943564, sin0.1538460.331189 V Hrrr 于是再取32(1)32211100 00.9435640.33118900.3311890.9435648.7749641.8015968.597089 00.4645262.541982001.471953VV V HR于是12132

14、(2)110.5698030.7754030.272165 0.8217810.5376430.18871200.3311890.9435643.5194824.92549110.8401170.3817391.0916272.31065300.4874951.38888,11 3TTQV VHRQ 第一次迭代得重復(fù)上述過程迭代 次(12)1232.9920321.0003853 12.013392 0.0074962.0046951.94197100.0003250.9998952.992032,2.004695,0.999895 3,2,1.0.007496HQR 得精確值下三角非對角元的最大模為。方法“基本”收斂較慢。五、帶原點(diǎn)移位的QR方法( )( )121( )( )1121 QR,(), , kknnnnkknnnnnnnHhAAHhkuuuuu 理論分析和實(shí)際計(jì)算均表明，方法產(chǎn)生的矩陣序列的右下角對角元素最先與 的特征值接近。可以證明，若矩陣 的特征值滿足則的右下角對角元且收斂速度是線性的，速率為。于是考慮原點(diǎn)移位的技巧來加快收斂速度