6.4超松弛迭代法

1、第六章 線性方程組迭代解法Numerical Analysis 6.4 超松弛迭代法(SOR)1 6.4超松弛迭代法(SOR)一、SOR法迭代公式例6.6 用SOR法求解線性方程組二、SOR法的收斂性SOR法收斂與收斂速度有關(guān)定理SOR法分類與現(xiàn)狀 SOR（Successive Over-Relaxation）法，即超松弛迭代法，是目前解大型線性方程組的一種最常用的方法，是Gauss-Seidel迭代法的一種加速方法。 2一、SOR法迭代公式 設(shè)線性方程組 AX=b其中 A非奇異，且aii 0（i=1,2,n ） 。 如果已經(jīng)得到第k次迭代量x (k) 及第k+1次迭代量x (k+1) 的前i

2、-1個 分量 （x1 (k+1),x2 (k+1) ,xi-1 (k+1) )，在計算xi (k+1) 時，先用Gauss-Seidel迭代法得到 (1) 選擇參數(shù)，取 (2)返回引用3把 式（1）代入式（2）即得SOR法其中， 參數(shù)叫做松弛因子； 若 =1，它就是Gauss-Seidel迭代法。 返回引用4例6.6 用SOR法求解線性方程組 解 方程組的精確解為 x=(3,4,-5) T，為了進(jìn)行比較，利用同一初值 x(0)=(1,1,1)T，分別取=1 (即Gauss-Seidel迭代法)和 =1.25兩組算式同時求解方程組。 取=1 ，即Gauss-Seidel迭代： 取=1.25 ，即

3、SOR迭代法： 返回引用5 迭代結(jié)果見表6.3。 表6.3 Gauss-Seidel迭代法與SOR迭代法比較 Gauss-Seidel迭代法SOR迭代法(=1.25)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.1333

4、0274.0402646-5.096686343.05493163.9542236-5.01144102.95705124.0074838-4.973489753.03433233.9713898-5.00715263.00372114.0029250-5.005713563.02145773.9821186-5.00447032.99632764.0009262-4.998282273.01341103.9888241-5.00279403.00004984.0002586-5.00034866 迭代法若要精確到七位小數(shù)， Gauss-Seidel迭代法需要34次迭代； 而用SOR迭代法(=

5、1.25)，只需要14次迭代。 可見，若選好參數(shù)，SOR迭代法收斂速度會很快。返回節(jié)7二、SOR法的收斂性 為了利用第3節(jié)的收斂定理，要先給出SOR法的矩陣表達(dá)式。由式（2） 以及Gauss-Seidel迭代法的矩陣表達(dá)形式，可以看出 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 由定理6

6、.1 及定理6.2直接得知： SOR法收斂的充要條件是(B)1。 SOR法收斂的充分條件是 | B|1。 前面我們看到，SOR法收斂與否或收斂速度都與松弛因子有關(guān)，關(guān)于的范圍，有如下定理。 9SOR法收斂與收斂速度有關(guān)定理定理6.5 設(shè)ARnn，滿足a ii0 (i=1,2,n),則有(B) |1-| 。 推論 解線性方程組，SOR法收斂的必要條件是 |1-| 1 ，即 0 2。 定理6.6 設(shè)ARnn對稱正定，且 02，則SOR法對任意 的初始向量都收斂。 由于定理6.4只是定理6.6的特殊情況，故定理6.4可以看作定理6.6的推論。 10定理6.7 設(shè)A是對稱正定的三對角矩陣，則(BG)

7、=(BJ) 2 1 時，稱為超松弛算法；當(dāng)1 時，稱為亞松弛算法。 目前還沒有自動選擇因子的一般方法，實際計算中，通常?。?,2）區(qū)間內(nèi)幾個不同的值進(jìn)行試算，通過比較后，確定比較理想的松弛因子。 12例6.7 討論例6.6用SOR法的取值。 解 系數(shù)矩陣 由式（4）得 根據(jù)定理6. 7，有(BG) =(BJ) 2 =0.625， (Bopt)= opt 1 = 0.24 , 可見采用SOR 方法比Jacobi迭代法和Gauss-Seidel迭代法快得多。 返回章返回節(jié)131 Jacobi迭代法、Gauss-Seidel迭代法（和SOR法 簡介）（1）計算公式分量形式、矩陣形式以及它們的迭 代矩陣表示； (2)線性方程組的系數(shù)矩陣為某些特殊情形下， Jacobi迭代法、Gauss-Seidel迭代法的收斂性 的重要結(jié)論。 本章學(xué)習(xí)要點返回章142 迭代法收斂性的判定定理和收斂速度 (1)迭代法收斂的充要條件； (2)從迭代矩陣的范數(shù)判別迭代法的收斂性及其證明； (3)線性方程組的系數(shù)