【文章內(nèi)容簡介】 算；不足之處是需要存 放 和 的兩個存儲空間。 表示得到： 即： 寫成分量形式得到： ( 1 ) ( )( ) ,kkD L x U x b?? ? ?( 1 ) ( 1 ) ( ) ,k k kD x L x U x b??? ? ?( 0 ) ( 0 ) ( 0 ) ( 0 )121( 1 ) ( 1 ) ( )11( , , , ),( 1 , 2 , , ) ( 0 , 1 ,Tnink k ki i ij j ij j iij j ix x x xx b a x a x ai n k???? ? ?? ?????? ? ?? ?????? ?????表 示 迭 代 次 數(shù) ）()kx ( 1)kx ? 基本迭代法 ? Jacobi迭代法和 GaussSeidel迭代法的異同： Jacobi迭代法公式簡單，每次只需做矩陣和向量的 一次乘法，特別適合于并行計算；不足之處是需要存 放 和 的兩個存儲空間。 GaussSeidel方法只需要一個向量存儲空間，一旦 計算出 立即存入 的位置，可節(jié)約一套存儲單元 這是對 Jacobi方法的改進，在某些情況下，它能起到 加速收斂的作用。但它是一種典型的串行算法，每一 步迭代中，必須依次計算解的各個分量。 ()kx ( 1)kx ?( 1)kjx ? ()kjx 基本迭代法 ? 解大型稀疏線性方程組的逐次超松弛法 選取分裂矩陣 為帶參數(shù)的下三角矩陣 其中 為可選擇的松弛因子，于是構(gòu)造迭代法如 下： 其中： 這就是解 的 逐次超松弛迭代法 (SOR方法 )。其 分量形式為： M 1 ()M D L????0??11( ) ( ) ( ( 1 ) )L I D L A D L D U? ? ? ? ? ???? ? ? ? ? ? ?( 0 )( 1 ) ( ) ( 0 , 1 , )kkxx L x f k???? ? ? ?? 取 為 初 始 向 量Ax b? ( 0 ) ( 0 ) ( 0 ) ( 0 )121( 1 ) ( ) ( 1 ) ( )11( , , , ),( 1 , 2 , , ) ( 0 , 1 ,Tnink k k ki i i ij j ij j iij j ix x x xx x b a x a x ai n k ?????? ? ?? ?????? ? ? ?? ?????? ?????表 示 迭 代 次 數(shù) ） , 為 松 弛 因 子 基本迭代法 ? 關(guān)于 SOR方法的幾點注釋： (1) 顯然，當(dāng) 時， SOR方法就是 GaussSeidel方法。 (2) SOR方法每一次迭代的主要運算量是計算一次矩陣 與向量的乘法。 (3) 時稱為超松弛方法， 時稱為低松弛方法。 (4) 計算機實現(xiàn)時可用 控制 迭代終止，或用 控制終止。 (5) SOR方法可以看成是 GaussSeidel方法的一種修正。 1??1?? 1??( 1 ) ( )11m a x m a xkki i ii n i nx x x ??? ? ? ?? ? ? ?( ) ( )kkr b A x ?? ? ? ? 迭代法的收斂性 例：分別用 Jacobi迭代法和 GaussSeidel迭代法計 算下列方程組，均取同樣的初值 ，觀察其計 算結(jié)果。 解：對方程組 1，其精確解 Jacobi迭代得： GaussSeidel迭代得： 對方程組 2，其精確解 Jacobi迭代得： 125次迭代可得精度為 ； GaussSeidel迭代得： 9次迭代可得精度為 ； 對方程組 3，其精確解 Jacobi迭代得： GaussSeidel迭代得： ( 0 ) (1,1,1) Tx ?1 2 31 2 31 2 39 1 0 1( 1 ) 9 5 08 7 4x x xx x xx x x? ? ? ??? ? ? ? ??? ? ? ??1 2 31 2 31 2 35 3 1( 2 ) 2 4 03 4 1 5 4x x xx x xx x x? ? ? ??? ? ? ? ??? ? ? ? ??1 2 31 2 31 2 31 0 4 5 1( 3 ) 1 0 7 05 7 1 0 4x x xx xx x x? ? ? ??? ? ? ??? ? ? ??* ( 0 . 4 5 1 1 , 1 . 2 3 8 3 , 1 . 0 5 9 6 ) Tx ? ? ?( 4 ) ( 7 6 6 6 , 7 0 2 3 , 3 3 2 7 ) Tx ? ? ?( 3 ) ( 1 0 9 7 8 , 9 2 6 8 7 , 7 3 6 0 7 7 ) Tx ? ? ?* ( 0 . 0 9 8 4 , 1 . 1 6 3 9 , 0 . 5 5 4 7 ) Tx ? ? ?* ( 0 . 3 6 5 8 , 0 . 5 1 3 2 , 0 . 9 4 2 1 ) Tx ? ? ?( 2 9 9 ) 1 0 1 0 1 0( 0 . 3 5 1 0 , 0 . 4 1 1 0 , 0 . 4 3 1 0 ) Tx ? ? ? ? ? ? ?( 3 0 0 ) 1 0 1 0 1 0(0 . 3 8 1 0 , 0 . 4 5 1 0 , 0 . 4 7 1 0 ) Tx ? ? ? ?( 6 ) ( 0 . 3 6 6 , 0 . 5 1 4 , 0 . 9 4 3 ) Tx ? ? ?( 7 ) ( 0 . 3 6 6 , 0 . 5 1 4 , 0 . 9 4 2 ) Tx ? ? ? 迭代法的收斂性 設(shè) ，其中 為非奇異矩陣，記 為方程 的精確解， 的等價方程組為： ，于是： 設(shè)有解方程組 的一階定常迭代法： 我們希望研究的問題是：迭代矩陣滿足什么條件時， 迭代法產(chǎn)生的迭代序列 收斂到 。 引進誤差向量 其遞推公式為： 由本章引言可知：我們要研究的問題就是 滿足什么 條件時，有 Ax b? nnAR??Ax b? x B x f??**x B x f??Ax b?( 1 ) ( )kkx B x f? ??(){}kx*x*x( ) ( ) * ( 0 , 1 , 2 , )kk x x k? ? ? ?( 1 ) ( ) ( ) ( 0 ), ( 0 , 1 , 2 , )k k k kB B k? ? ? ?? ? ? ?()kBk? ? ?0B 迭代法的收斂性 定義 2：設(shè)有矩陣序列 及 ， 如果 個數(shù)列極限存在且有 則稱 收斂于 ，記為 。 例：設(shè)有矩陣序列 且設(shè) ，考查其極限。 解：顯然，當(dāng) 時，有 矩陣序列極限概念可以用矩陣算子范數(shù)來描述。 定理 1： ，其中 為矩陣的 任意一種算子范數(shù)。 ()()k n nk i jA a R ??? () nnijA a R ???2n()l i m ( , 1 , 2 , , )ki j i jk a a i j n?? ??{}kA A lim kk AA?? ?1212, , , ,00 0kkkkkA A A? ? ? ???? ????? ? ? ?? ? ? ??? ? ? ?? ? ? ? ??1??1?? 00l im l im 00kkkkAA? ? ? ? ???? ????l i m l i m 0kkkkA A A A? ? ? ?? ? ? ? 迭代法的收斂性 證明：顯然有 再利用矩陣范數(shù)的等價性，可證定理對其他算子范數(shù) 亦對。 定理 2： 對任何向量 都有 定理 3：設(shè) ，則 的充分必要條件 是矩陣 的譜半徑 。 證明：由矩陣 的若當(dāng)標(biāo)準(zhǔn)型，存在非奇異矩陣 使 其中若當(dāng)塊 l i m l i m 0kkkkA A A A ?? ? ? ?? ? ? ?l im kk AA?? ?? nxR? lim kk A x A x?? ?() nnijB b R ??? lim 0kk B?? ?B ( ) 1B? ?B P121,rJJP B P JJ???????????11iiiiiinnJ??????????????? 迭代法的收斂性 且 ，顯然有： ，其中： 于是 下面考查 的情況，引進記號： 顯然有： ，由于 因此： 1riinn??? 11, kkB P J P B P J P????12kkkkrJJJJ???????????l i m 0 l i m 0 l i m 0 ( 1 , 2 , , )kkk ik k kB J J i r? ? ? ? ? ?? ? ? ? ? ?kiJ?,0 ()00ttt k iI tkE R t n????? ? ?????, 0 , , 1 , 0 ( ) , ( ) kt t k t t kE I E k t E E? ? ? ?,1i i tJ I E???1, 1 , 1 ,00( ) ( )ktk k j k j j j k ji i t k i t k i t jjjJ I E C E C E? ? ??????? ? ? ??? 迭代法的收斂性 利用極限 得到 所以 的充要條件是