【正文】 方程組的 RK 算法公式。 方程組求解 Newton 法與最速下降法基本理論。 向量范數(shù)與矩陣范數(shù)。 DFT與 FFT的構成，公式與算法。還有一些其它求特征值的算法，如適用于并行計算的同倫算法等，同樣也不詳述了。于是考慮原點移位的技巧來加快收斂速度，即取位移使其滿足且11 ( )nnuH uI Q RuQR???? ? ??－。將 進行 分解，記取0 .5 6 9 8 0 3 0 .8 2 1 7 8 1 00 .8 2 1 7 8 1 0 .5 6 9 8 0 3 00 0 1???????????( 1 )212222222 0 831 0 103 00 384 6 076 7 ( 831 0) ( 384 6) 452 6 , c os 0 4 , si n 6 9 VHrrr???????????? ???? ? ? ???? ? ? ?于是再取32( 1 )32 21 11 0 0 0 4 90 118 9 356 4 0 452 6 198 20 0 195 3VV V H R????????????????? ? ???????于是1 2 1 3 2( 2 )11 0. 82 17 81 0. 53 76 43 0. 18 87 120 0. 33 11 89 0. 94 35 64 0 0. 48 74 95 1. 38 88 83, 11TTQ V VH R Q????? ? ????? ???????? ? ? ????? ???第一次迭代得重復上述過程 迭代 次( 1 2 )1 2 3 0. 00 74 96 2. 00 46 95 1. 94 19 710 0. 00 03 25 0. 99 98 95 , , 3,2,1.HQR? ? ???????????? ???? ? ?得精確值下三角非對角元的最大模為 。 2 239?？伤愠鐾瓿蛇@一過程的運算量約為 比一般矩陣的 分解的運算量 少一個數(shù)量級。239。同理，可構造如下列形式 矩陣使得如此進行122 2 2 1 1 2 22 , , , .n n nn H ou se ho lde r H HH H H H A H H H HH H e sse nb e rg AH? ? ???次，可以構造 個 矩陣使得其中 為 矩陣。討論用 變換將一般矩陣 相似變換成Hessenberg 陣11111111111 21 1 1 21 31 111 1 22 12 12 13 1 ,1 0 00 01( , , , ) ,( , , ,TTnH ouse hol de r H HH AHHHHH n H ouse hol de ra a HH AH a a a aH a H A Ha a a a???????????????????????????首先，選取 矩陣 使得經(jīng) 相似變換后的矩陣 的第一列中有盡可能多的零元素。特別地取 則 經(jīng)過 變換后可變成只有一個分量不為零。( 3 )TnnnT nn n nTw w w w w ww w w w ww w w w wH I w ww w w w wH ous e hol de rH H H HHH?? ? ? ? ???? ? ???? ? ???? ? ?????? ? ?????????設向量 滿足 則稱為 矩陣或反射矩陣。3 3 3 1 1 3 2 239。 1 2 3111239。 基本 QR方法每次迭代都需作一次 QR分解與矩陣乘法，計算量大，而且收斂速度慢。1 1 1 11 2 1 21 2 1 139。 39。2 1 1 21 1 1 1 1 139。 基本的 QR方法的主要運算是對矩陣 QR分解，分解的方法有多種。 可證，在一定條件下，基本 QR方法產(chǎn)生的矩陣序列｛ A(k)｝ “基本”收斂于一個上三角陣（或分塊上三角陣）。由 即 。 一、基本 QR方法 60年代出現(xiàn)的 QR算法是目前計算中小型矩陣的全部特征值與特征向量的最有效方法。( 0 )122 1 0 1 2 10 1 2 1 , 2 , 2 0 , ,41c os si n ,21102211 ( ) 0220 0 1AAi j c tgVV???????????? ? ????? ???? ? ? ???????????? ? ???????????例： 用Jacobi方 法求 的特征值。? ?( ) ( 0 ) ( )( ) ( )( ) 2 ( )( 1 )( 1 ) 2 ( 1 ) , , l im ( ) 0 , m a x1 ( ) ( )( 1 ) ( ) ( ) kkkkkij lmlmkkijkkkii jjA n A J ac ob iA A A E A J ac ob iJ ac ob i a aa E AnnAaa???????????＋定理：設 為 階實對稱陣，對 用古典 法得到序列其中 則 即古典 法收斂。二、 Jacobi方法 ( 1 )()()( ) ( )1 , ,( ,0,2. , , m a x3. 2kkijkkkij lml m n l miiA A AJ ac obi AaJ ac obik A Ai j a aaa c tg ??? ? ??????通過一系列旋轉(zhuǎn)相似變換將 變成 求得 的全部特征值與特征向量的方法稱為 方法。一、矩陣的旋轉(zhuǎn)變換 11c os si n1()1si n c os11ijAnV???????????????????????????設 為 階實對稱矩陣，考慮矩陣( 1 ) ( 1 )( 1 ) 2 2( 1 ) 2 2( 1 ) ( 1 )(1 ( ) ( )c os si n si n 2 si n c os si n 2 c os si n ( , ) Tij ij ij ijii ii jj ijjj ii jj ijik k i ik jkjkV A V AV aa a a aa a a aa a a a k i ja?? ? ?? ? ?????? ? ?? ? ?? ? ? ?是正交矩陣，若記則有) ( 1 )( 1 ) ( 1 )( 1 ) ( 1 )si n c os ( , , )1( ) si n 2 c os 2 20, 2 2 / ( ) k j ik jkk l lk k lij ji jj ii ijij ij jj iia a aa a a k l i ja a a a aa t g a a a???????????? ? ? ? ??? ? ???? ? ? ???? ? ?如果 取 使得( 1 ) ( 1 )( / 4)0,.ij ji ij jia a A a a?? ?? ? ?則有得到一個使 中非零的非對角元素 變成零的正交相似變換? ?( 1 ) ( 2 ) ( )( 1 ) 2 ( 1 ) ( 1 ) 2( 1 ) ( 1 ) ( 1 )( 1 ) , ( ) , ( ) ( ) ( , , ) c os si nkk l k lk l k lk l k l ik k i ik jkjk kA A AA A E A a E A aa a k l i j a a a aaa????????? ? ? ? ????對 重復上述過程 得到一個矩陣序列 。 12 Ja c ob i,:( 1) , ( , , , ) ( 1 , 2 , ) ,2 ( ) ,Tniij n nTAQ Q A Q diag in A QAaQ B Q A Q? ? ? ???????方法是求實對稱矩陣的全部特征值及相應特征向量的一種方法 它基于以下兩個結論任意實對稱矩陣 可通過正交相似變換化成對角陣 即存在正交矩陣 使得 其中是 的特征值 中各列即為相應的特征向量。因此，對 用反冪法求 一般收斂很快，通常 只要經(jīng)過二、三次迭代就能達到較高的精度。1( 1 ) ( )( 1 ) 1 ( )( 1 ) kkkkkAAA x xx A xxA??????＋因為 的計算比較麻煩，而且往往不能保持矩陣 的一些好性質(zhì)（如稀疏性），因此，反冪法在實際運算時以求解方程組 代替冪法迭代求得 ，每迭代一次要解一個線性方程組。( 也可采用冪法迭代兩步或三步，加速一次的方法）三、反冪法 反冪法是計算矩陣按模最小的特征值及特征向量的方法，也是修正特征值、求相應特征向量的最有效的方法。? ?? ? ? ?1211222 1 12 1 2 1 l im 0 ()22kkkkkkkkk k k k kkkk k k k k kkkaaaacaaa a a aka a a aa a a a aa a aa a a a a aa a a A it k??????? ? ?? ? ? ????????????? ? ? ? ?? ? ? ?（二）、冪法的埃特肯(A it ke n) 加速如果序列 線性收斂到 ，即則當 充分大時，有序列 比 更快地收斂到 ，這就是? ?kena加速法。在一些簡單情形， 可估。 12??／000( 1 ) ( )0( 1 ) ( )0( 1 ) 1 12 0 01 0 1 1 2 21 0 1 00 ( )( ) [ ( ) ( ) ]iikkkkk k knnnA A I AAIA I x Axx A I xu u u??? ? ???? ? ? ?? ? ? ? ?? ? ? ????? ? ??????????? ? ? ? ???（一）原點移位法矩陣 與 的特征值有以下關系