數(shù)值分析：3-4超松弛迭代法

1、第三章第三章 線性方程組迭代解法線性方程組迭代解法 3.4 超松弛迭代法(SOR)超松弛超松弛迭代法迭代法(l一、一、SOR法迭代公式法迭代公式l例例 用用SOR法求解線性方程組法求解線性方程組l二、二、SOR法的收斂性法的收斂性lSOR法收斂與收斂速度有關(guān)定理法收斂與收斂速度有關(guān)定理lSOR法分類與現(xiàn)狀法分類與現(xiàn)狀 SOR（Successive Over-Relaxation）法，即超松弛迭代法超松弛迭代法，是目前解大型線性方程組的一種常用的方法常用的方法，是Gauss-Seidel迭代迭代法法的一種加速方法加速方法。 設線性方程組設線性方程組 AX=b其中其中 A非奇異，且非奇異，且aii

2、 0（i=1,2,n ） 。 如果已經(jīng)得到第如果已經(jīng)得到第k次迭代量次迭代量x (k) 及第及第k+1次迭代量次迭代量x (k+1) 的前的前i-1個個 分量分量 （x1 (k+1),x2 (k+1) ,xi-1 (k+1) )，在計算在計算xi (k+1) 時，先用時，先用Gauss-Seidel迭代法迭代法得到得到 iikjnijijkjijijikiaxaxabx/ )()1(11)1(1) 選擇參數(shù)選擇參數(shù)，取，取 )1()()1()1 (kikikixxx(2)返回引用返回引用把把 式（式（1 1）代入式（）代入式（2）即得）即得SOR法法i 1n(k 1)(k)(k 1)(k)ii

3、iijjijjj 1j i 1ii(0)(0)(0)(0) T12nx(1)xba xa x (i1,2,n)aX(x ,x ,x )(k 1,2,) 其中，其中， 參數(shù)參數(shù)叫做松弛因子；叫做松弛因子； 若若 =1，它就是，它就是Gauss-Seidel迭代法。迭代法。 返回引用返回引用 243024410143034321xxx解解 方程組的精確解為方程組的精確解為 x=(3,4,-5) T，為了進行比較為了進行比較，利用同利用同一初值一初值 x(0)(0)=(1,1,1)T，分別取分別取=1 (即即Gauss-Seidel迭代法迭代法)和和 =1.25兩組算式同時求解方程組。兩組算式同時求

4、解方程組。 取=1 ，即Gauss-Seidel迭代： 625. 05 . 725. 075. 0675. 0)1(2)1(3)(3)1(1)1(2)(2)1(1kkkkkkkxxxxxxx 取=1.25 ，即SOR迭代法： 5 . 725. 03125. 075. 93125. 025. 09375. 05 . 79375. 025. 0)(3)1(2)1(3)(3)(2)1(1)1(2)(2)(1)1(1kkkkkkkkkkxxxxxxxxxx返回引用 迭代結(jié)果見表3.3。 表3.3 Gauss-Seidel迭代法與SOR迭代法比較 Gauss-Seidel迭代法SOR迭代法(=1.25)

5、kx1x2x3x1x2x301.00000001.00000001.00000001.00000001.00000001.000000015.25000003.1825000-5.04687506.31250003.9195313-6.650146523.14062503.8828125-5.02929692.62231453.9585266-4.600423833.08789063.9267587-5.01831053.13330274.0402646-5.096686343.05493163.9542236-5.01144102.95705124.0074838-4.973489753.0

6、3433233.9713898-5.00715263.00372114.0029250-5.005713563.02145773.9821186-5.00447032.99632764.0009262-4.998282273.01341103.9888241-5.00279403.00004984.0002586-5.0003486 迭代法若要精確到七位小數(shù)，迭代法若要精確到七位小數(shù)，u Gauss-Seidel迭代法需要迭代法需要34次迭代；次迭代；u 而用而用SOR迭代法迭代法(=1.25)，只需要，只需要14次迭代。次迭代。 可見，若選好參數(shù)可見，若選好參數(shù)，SOR迭代法收斂速度會很迭代

7、法收斂速度會很快?？臁７祷毓?jié)返回節(jié) 為了利用第為了利用第3節(jié)的收斂定理，要先給出節(jié)的收斂定理，要先給出SOR法的矩陣表達法的矩陣表達式。由式。由Gauss-Seidel迭代法的矩陣表達形式，可以看出迭代法的矩陣表達形式，可以看出 X(k+1) =(1-)X(k)+D-1(b+LX(k+1)+UX(k)DX(k+1) =(1-)DX(k)+(b+LX(k+1)+UX(k)）(D-L)X（k+1） =(1-)D+U X(k)+b解得 X(k+1) =(D-L)-1 (1-)D+U X(k)+(D-L)-1b (3) 記記 B=(D-L)-1 (1-)D+U 稱為稱為SOR法迭代矩陣。法迭代矩陣。

8、由定理由定理3.1 及定理及定理3.2直接得知：直接得知： (1)SOR法收斂的充要條件是法收斂的充要條件是(B)1。(2) SOR法收斂的充分條件是法收斂的充分條件是 | B|1。 前面我們看到，前面我們看到，SOR法收斂與否或收斂速度都法收斂與否或收斂速度都與松弛因子與松弛因子有關(guān)，關(guān)于有關(guān)，關(guān)于的范圍，有如下定理。的范圍，有如下定理。 SOR法收斂與收斂速度有關(guān)定理定理定理3.5 設設ARn n，滿足，滿足a ii0 (i=1,2,n),則有則有(B) |1-| 。 推論推論 解線性方程組，解線性方程組，SOR法收斂的必要條件是法收斂的必要條件是 |1-| 1 ，即，即 0 2。 定理定

9、理3.6 設設ARn n對稱正定，且對稱正定，且 02，則，則SOR法對任意法對任意 的初始向量的初始向量都收斂。都收斂。 nTnRxxxx ),()0()0(2)0(1)0( 由于定理由于定理3.4只是定理只是定理3.6的特殊情況，故定理的特殊情況，故定理3.4可以可以看作定理看作定理3.6的推論。的推論。 定理定理3.7 設設A是對稱正定的三對角矩陣，則是對稱正定的三對角矩陣，則(BG) =(BJ) 2 1 時，稱為時，稱為超松弛算法超松弛算法；(2)(2)當當1 時，稱為時，稱為亞松弛算法亞松弛算法。 目前還沒有自動選擇因子的一般方法，實目前還沒有自動選擇因子的一般方法，實際計算中，通常

10、?。H計算中，通常?。?, ,2）區(qū)間內(nèi)幾個不同的）區(qū)間內(nèi)幾個不同的值進行試算，通過比較后，確定比較理想的松弛值進行試算，通過比較后，確定比較理想的松弛因子因子。 243024410143034321xxx解 系數(shù)矩陣 025. 0025. 0075. 0075. 00410143034JBA625. 0)(JB由式（3-24）得 24. 1625. 0112)(1122JoptB根據(jù)定理3. 7，有(BG) =(BJ) 2 =0.625， (Bopt)= opt 1 = 0.24 , 可見采用SOR 方法比Jacobi迭代法和Gauss-Seidel迭代法快得多。 返回章返回章返回節(jié)返回節(jié)1

11、 Jacobi迭代法、迭代法、Gauss-Seidel迭代法和迭代法和SOR法法（1 1）迭代公式的分量形式、矩陣形式以及它們）迭代公式的分量形式、矩陣形式以及它們的迭代矩陣；的迭代矩陣； (2) (2) 線性方程組的系數(shù)矩陣為某些特殊情形下，線性方程組的系數(shù)矩陣為某些特殊情形下，Jacobi迭代法、迭代法、Gauss-Seidel迭代法的收斂性的重迭代法的收斂性的重要結(jié)論。要結(jié)論。 本章學習要點本章學習要點返回章返回章2 迭代法收斂性的判定定理和收斂速度迭代法收斂性的判定定理和收斂速度 (1) (1) 迭代法收斂的充要條件；迭代法收斂的充要條件； (2) (2) 從迭代矩陣的范數(shù)判別迭代法的收斂性；從迭