數(shù)值分析第三章：方程組迭代法

1第三章線性方程組的數(shù)值解法-------迭代法Iterativetechniquesforlinearequations2

直接法得到的解是理論上準(zhǔn)確的，但是計(jì)算量都是n3數(shù)量級(jí)，存儲(chǔ)量為n2量級(jí)，這在n比較小的時(shí)候還比較合適（n<400）

實(shí)際問題中，往往方程組的階數(shù)很高，而且這些

矩陣(系數(shù)矩陣)往往是含有大量的0元素（稀疏矩

陣方程組）。因此有必要引入一類新的方法：迭代法。

引言3

迭代法的基本思想

迭代法是解線性方程組的一種重要的實(shí)用方法，特

別適用于求解在實(shí)際中大量出現(xiàn)的，系數(shù)矩陣為稀

疏陣的大型線性方程組。

迭代法的基本思想是給定一個(gè)預(yù)測(cè)近似值，用某一

個(gè)固定公式去反復(fù)校正，使之逐步精確化，最后滿

足需要精度即可。4迭代法的主要步驟

Theprocessofiterativemethod

解線性方程組迭代法的主要步驟是:

把線性方程組Ax=b化成如下形式的同解方程組

x=Bx+f

給出初始向量,按迭代公式

x(k+1)=Bx(k)+f(k=0,1,2,…)

進(jìn)行計(jì)算,其中k表迭代次數(shù)。5

如果按上述迭代公式所得到的向量序列{x(k)}收斂于某個(gè)向量x*,則x*就是方程組Ax=b的解，并稱此迭代法收斂。否則，就叫不收斂或發(fā)散。迭代公式中的矩陣B，稱為迭代矩陣。

問題

迭代公式的建立迭代公式的收斂性收斂速度誤差估計(jì)6基本迭代公式把矩陣A分裂為則記

B=M-1N，f=M-1b，

則注：選取M陣，就得到解Ax=b的各種迭代法.7

本章重點(diǎn)介紹三個(gè)迭代法，即：

Jacobi迭代法

Gauss-Seidel迭代法

超松弛迭代法（SOR法）8Jacobi迭代法由方程組AX=b的第i個(gè)方程解出得到一個(gè)同解方程組

9獲得相應(yīng)的迭代公式Jacobi迭代法取初始向量稱上式為雅可比迭Jacobi迭代公式。10Jacobi迭代法的矩陣形式若記

則有A=D-L-U成立，矩陣形式為

Dx=（L+U)x+b

等式兩邊乘以D-1，得

x=D-1（L+U）x+D-1b

由此得到迭代公式(Theiterativeschemeis:)

x（k+1）=D-1（L+U）x（k）+D-1b

11

迭代矩陣Jacobi迭代法的特點(diǎn)

每迭代一次主要是計(jì)算一次矩陣乘向量所以計(jì)算量為n平方數(shù)量級(jí)。

計(jì)算過程中涉及到的中間變量及,需要兩組工作單元x(n),y(n)來(lái)存儲(chǔ).

計(jì)算過程中,初始數(shù)據(jù)A始終不變;12問題：如何判斷迭代終止？

定理若迭代矩陣B滿足||B||〈1則

此定理給出了一個(gè)停止迭代的判別準(zhǔn)則。13例子解：相應(yīng)的雅可比迭代公式為14例子0123400.30000.80000.91800.971601.50001.76001.92601.970002.00002.66002.86402.9540567890.98940.99630.99860.99950.99981.98971.99611.99861.99951.99982.98232.99382.99772.99922.9998原方程組的準(zhǔn)確解為取初值得計(jì)算結(jié)果，按迭代公式進(jìn)行迭代，15Jacobi迭代法的計(jì)算流程圖16MatlabforJacobiMethodfunction

y=jacobi(A,b,x，M)D=diag(diag(A));U=-triu(A,1);L=-tril(A,-1);B=D\(L+U);f=D\b;y=B*x+f;n=1;whilenorm(y–x)>=1.0e–6&n<Mx=y;y=B*x+f;n=n+1;end17高斯—塞德爾(Gauss-Seidel)迭代法

Jacobi迭代法的優(yōu)點(diǎn)是公式簡(jiǎn)單，迭代矩陣容易得到，稱為同時(shí)替換法：在每一步迭代計(jì)算過程中，計(jì)算x(k+1)時(shí)是用x(k)的全部分量代入求x(k+1)的全部分量。

研究雅可比迭代法，我們發(fā)現(xiàn)在逐個(gè)求

的分量時(shí)，當(dāng)計(jì)算到的分量時(shí)，當(dāng)計(jì)算到都

已經(jīng)求得.設(shè)想一旦新分量代替舊分量，可能會(huì)加速收斂。

例如

18…

…

…

…Gauss-Seidel迭代法分量形式19Gauss-Seidel迭代的矩陣形式作

A的另一個(gè)分裂：

迭代矩陣20例子解：相應(yīng)的高斯-賽德爾迭代公式為21取迭代初值按此迭代公式進(jìn)行迭代，計(jì)算結(jié)果為01234500.30.88040.98430.99780.999701.561.94451.99231.99891.999902.6842.95392.99382.99912.999922迭代法的收斂性

迭代法的收斂性，是指方程組

從任意初始向量X(0)出發(fā)，由迭代算法算出向量序列隨著k的增加而趨向于解向量X*。

記各次誤差向量23迭代法的收斂性

迭代法的收斂性等價(jià)于誤差向量序列隨著k的增加而趨向于零。

由

x(k+1)=Bx(k)+f及x*=Bx*+fεk+1=X(k+1)-X*=B（X(k)-X*）=·

·

·

·

·

·

·

·

·

·

·

·

·=B

k+1（X(0)-X)=B

k+1

ε0

可推知

{x(k)}的收斂性

Bk

0

(k

∞)

24迭代法的收斂性定理

定理(充要條件判別法)給定方程組X=BX+f則迭代公式對(duì)任意初始向量，都收斂的充要條件為

25

迭代法的收斂性定理

定理

(充分條件判別法)給定方程組X=BX+f如果，則迭代公式1.對(duì)任意初始向量收斂。2.有如下估計(jì)26證明

27注

由于此估計(jì)式，在實(shí)際計(jì)算中，用||X(k+1)-X(k)||≤ε

作為迭代終止條件是合理的。

進(jìn)一步可以推知：由于ρ(B)≤‖B‖<1，‖B‖越小，說明ρ(B)越小，序列{X(k)}收斂越快。28收斂速度下面我們給出收斂速度的概念：定義

R(B)=-lnρ(B)，稱為迭代法的漸進(jìn)收斂速度。

由于Gauss-Seidel迭代法逐次用計(jì)算出來(lái)的新值代替舊值，所以在收斂的條件下，它要比Jacobi迭代法收斂速度快。。29Jacobi和Gauss-Seidel的收斂性30注31對(duì)于前面的例子由迭代矩陣的特征方程因而雅可比迭代公式是收斂的。32注33直接用矩陣A判定斂散性

收斂性定理雖然給出了判別迭代法收斂的充要條件，但實(shí)際使用時(shí)很不方便，因?yàn)榍竽婢仃嚭吞卣髦档碾y度并不亞于用直接法求解線性方程組。下面對(duì)一些特殊的方程組，從方程組本身出發(fā)給出幾個(gè)常用的判別條件，而不必求迭代陣的特征值或范數(shù)。

定義如果矩陣A滿足條件則稱A是嚴(yán)格對(duì)角占優(yōu)陣(strictlydiagonallydominantmatrix)；34A為按行按列嚴(yán)格對(duì)角占優(yōu)陣；B為按行對(duì)角占優(yōu)陣。實(shí)例(Example)35定理1若A為嚴(yán)格對(duì)角占優(yōu)陣，則Jacobi迭代法和

G-S迭代法收斂。

定理2

若A為對(duì)稱正定陣，則G-S迭代法收斂。

相關(guān)定理

可以總結(jié)，討論迭代法的收斂性，應(yīng)首先從A出發(fā)討論其是否具有主對(duì)角占優(yōu)或?qū)ΨQ正定性；其次對(duì)迭代法的迭代陣討論其是否有范數(shù)小于1；最后利用迭代陣的譜半徑討論（這是充分必要條件）。36定理1的證明證

首先證明Jacobi

迭代的收斂性。由易求

由嚴(yán)格對(duì)角占優(yōu)定義，得

BJ

∞<1,所以,Jacobi

迭代法收斂。37

下面證明G-S迭代法的收斂性。對(duì)于嚴(yán)格對(duì)角占優(yōu)陣A，其對(duì)角元素aii≠0

，

i=1,2,,n，故

考慮BG的特征值λ，其特征方程為

det(

I-BG)=det(

I-(D-L)-1U)=det(D-L)-1det(

(D-L)-U)=０

=>det(

(D-L)-U)=038

我們通過A的嚴(yán)格對(duì)角占優(yōu)性質(zhì)去證明det(

(D-L)-U)=0的根

有性質(zhì)|

|<1。用反證法：假設(shè)|

|≥1，且由于A的嚴(yán)格對(duì)角占優(yōu)性質(zhì)，有

39是嚴(yán)格對(duì)角占優(yōu)陣，所以它是非奇異的，即det(

(D-L)-U)0與特征值

滿足det(

(D-L)-U)=0

矛盾。故

|

|<1即ρ(BG)<1，G-S迭代法收斂。定理得證。

40注值得注意的是，改變方程組中方程的次序，即將系數(shù)矩陣進(jìn)行行交換，會(huì)改變迭代法的收斂性。

無(wú)法直接判斷Jacobi

迭代法和G-S迭代法的收斂性，但如果將方程組的次序修改為

41注

對(duì)于對(duì)稱正定矩陣A，Jacobi迭代法不一定收斂。

迭代法程序簡(jiǎn)單，對(duì)于許多問題，收斂較快。因而，有時(shí)能夠解決一些高階問題。但應(yīng)注意，對(duì)于某些問題，迭代法可能發(fā)散或收斂很慢，以致失去使用價(jià)值。這種情況下，仍以采用直接法為宜。

42

超松弛迭代法(SOR)

通過引入?yún)?shù)，在Gauss-Seidel法的基礎(chǔ)上作適當(dāng)修改，在不增加過多的計(jì)算量的條件下，可得到一種新的，收斂更快的迭代法。

：

首先用G-S法定義輔助量：選擇參數(shù)ω，取43

超松弛迭代法(SOR)即得SOR法其中，

參數(shù)ω叫做松弛因子；

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

44

超松弛迭代法(SOR)另一種理解將Gauss-Seidel迭代格式改寫為被稱為增量形式。可以將看做加一個(gè)修正量得到的。45

超松弛迭代法(SOR)如果將修正量改為即為SOR.通常，當(dāng)ω>1

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

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

46例用SOR法求解線性方程組①取ω=1，即Gauss-Seidel迭代：

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

47例

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

表3.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.000348648

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

Gauss-Seidel迭代法需要34次迭代；而用SOR迭代法(ω=1.25)，只需要14次迭代?？梢?，若選好參數(shù)ω，SOR迭代法收斂速度會(huì)很快。

49SOR迭代的矩陣形式：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