應(yīng)用數(shù)值分析chapt6線性方程組迭代法-6.4超松弛

第六章線性方程組迭代解法NumericalValueAnalysis§6.4超松弛迭代法(SOR)§6.4超松弛迭代法(SOR)一、SOR法迭代公式例3.6用SOR法求解線性方程組二、SOR法的收斂性SOR法收斂與收斂速度有關(guān)定理SOR法分類與現(xiàn)狀

SOR（SuccessiveOver-Relaxation）法，即超松弛迭代法，是目前解大型線性方程組的一種最常用的方法，是Gauss-Seidel迭代法的一種加速方法。

一、SOR法迭代公式

設(shè)線性方程組AX=b其中A非奇異，且aii

0（i=1,2,,n）。

如果已經(jīng)得到第k次迭代量x(k)

及第k+1次迭代量x(k+1)

的前i-1個(gè)分量（x1(k+1),x2(k+1),,xi-1(k+1))，在計(jì)算xi(k+1)

時(shí)，先用Gauss-Seidel迭代法得到(1)

返回引用選擇參數(shù)ω，取

(2)返回引用把式（1）代入式（2）可以綜合寫成：即得超松弛法或逐次超松弛迭代法（SuccessiveOver-RelaxationMethod），簡稱SOR法。或可表示成增量的形式：其中，參數(shù)ω叫做松弛因子；若

ω=1，它就是Gauss-Seidel迭代法。

返回引用令A(yù)=D-L-U,SOR法(2)式可寫成：

再整理成：于是可導(dǎo)出SOR法的矩陣形式：其中，迭代矩陣和f為:例6.6用SOR法求解線性方程組

解

方程組的精確解為

x=(3,4,-5)

T，為了進(jìn)行比較，利用同一初值

x(0)=(1,1,1)T，分別取ω=1(即Gauss-Seidel迭代法)和

ω=1.25兩組算式同時(shí)求解方程組。

返回引用

①取ω=1，即Gauss-Seidel迭代：

②取ω=1.25，即SOR迭代法：

返回引用

迭代結(jié)果見表3.3。

表6.3Gauss-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.13330274.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.0003486

迭代法若要精確到七位小數(shù)，

Gauss-Seidel迭代法需要34次迭代；而用SOR迭代法(ω=1.25)，只需要14次迭代。可見，若選好參數(shù)ω，SOR迭代法收斂速度會(huì)很快。返回節(jié)二、SOR法的收斂性

為了利用第3節(jié)的收斂定理，要先給出SOR法的矩陣表達(dá)式。令A(yù)=D-L-U,SOR法(2)式可寫成：

再整理成：于是可導(dǎo)出SOR法的矩陣形式：其中，迭代矩陣和f為:

由定理6.1及定理6.2直接得知：

SOR法收斂的充要條件是ρ(Bω)<1。

SOR法收斂的充分條件是

||Bω||<1。

前面我們看到，SOR法收斂與否或收斂速度都與松弛因子ω有關(guān)，關(guān)于ω的范圍，有如下定理。

SOR法收斂與收斂速度有關(guān)定理定理6.5

設(shè)A∈Rnn，滿足aii≠0(i=1,2,,n),則有ρ(Bω)≥|1-ω|。推論

解線性方程組，SOR法收斂的必要條件是

|1-ω|<1，即0<ω<2。定理6.6

設(shè)A∈Rnn對(duì)稱正定，且

0<ω<2，則SOR法對(duì)任意的初始向量都收斂。

由于定理6.4只是定理6.6的特殊情況，故定理6.4可以看作定理6.6的推論。

定理6.7

設(shè)A是對(duì)稱正定的三對(duì)角矩陣，則ρ(BG)=[ρ(BJ)]2<1，且SOR法松弛因子ω的最優(yōu)選擇為

（4）

這時(shí)，有SOR迭代法矩陣譜半徑ρ(Bopt)=ωopt-1。

通常，當(dāng)ω>1

時(shí)，稱為超松弛算法，當(dāng)ω<1

時(shí)，稱為亞松弛算法。目前，還沒有自動(dòng)選擇因子的一般方法，實(shí)際計(jì)算中，通常?。?，2）區(qū)間內(nèi)幾個(gè)不同的ω值進(jìn)行試算，通過比較后，確定比較理想的松弛因子ω。

返回引用SOR法分類與現(xiàn)狀

通常，當(dāng)ω>1

時(shí)，稱為超松弛算法；當(dāng)ω<1

時(shí)，稱為亞松弛算法。目前還沒有自動(dòng)選擇因子的一般方法，實(shí)際計(jì)算中，通常?。?,2）區(qū)間內(nèi)幾個(gè)不同的ω值進(jìn)行試算，通過比較后，確定比較理想的松弛因子ω。

例3.7

討論例3.6用SOR法的ω取值。

解

系數(shù)矩陣

由式（3-24）得

根據(jù)定理6.7，有ρ(BG)=[ρ(BJ)]2=0.625，

ρ(Bopt)=ωopt

–1=0.24,

可見采用SOR

方法比Jacobi迭代法和Gauss-Seidel迭代法快得多。返回章返回節(jié)1．

Jacobi迭代法、Gauss-Seidel迭代法和SOR法

（1）計(jì)算分量形式、矩陣形式以及它們的迭代矩陣表示；

(2)線性方程組的系數(shù)矩陣為某些特殊情形下，Jacobi迭代法、Gauss-Seidel迭