數(shù)值分析方程組迭代法

數(shù)值分析課件方程組迭代法1第一頁，共五十四頁，2022年，8月28日

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

實(shí)際問題中，往往方程組的階數(shù)很高，而且這些矩陣(系數(shù)矩陣)往往是含有大量的0元素（稀疏矩陣方程組）。直接法運(yùn)算量將會很大并且大量占用計算機(jī)資源。

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

引言2第二頁，共五十四頁，2022年，8月28日

迭代法的基本思想

迭代法是解線性方程組的一種重要的實(shí)用方法，特別適用于求解在實(shí)際中大量出現(xiàn)的，系數(shù)矩陣為稀疏陣的大型線性方程組。

迭代法的基本思想是去構(gòu)成一個向量序列{x(k)}，使其收斂至某個極限向量x*，并且x*就是要求解的方程組：Ax=b的準(zhǔn)確解。3第三頁，共五十四頁，2022年，8月28日迭代法的主要步驟

Theprocessofiterativemethod

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

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

x=Bx+f

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

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

進(jìn)行計算,其中k表迭代次數(shù)。4第四頁，共五十四頁，2022年，8月28日

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

問題

迭代公式的建立迭代公式的收斂性收斂速度誤差估計5第五頁，共五十四頁，2022年，8月28日基本迭代公式把矩陣A分裂為則記

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

則注：選取M陣，就得到解Ax=b的各種迭代法.6第六頁，共五十四頁，2022年，8月28日

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

Jacobi迭代法

Gauss-Seidel迭代法

超松弛迭代法（SOR法）7第七頁，共五十四頁，2022年，8月28日J(rèn)acobi迭代法由方程組AX=b的第i個方程解出得到一個同解方程組

8第八頁，共五十四頁，2022年，8月28日獲得相應(yīng)的迭代公式Jacobi迭代法取初始向量稱上式為雅可比迭Jacobi迭代公式。9第九頁，共五十四頁，2022年，8月28日J(rèn)acobi迭代法的矩陣形式若記

則有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

10第十頁，共五十四頁，2022年，8月28日

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

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

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

計算過程中,初始數(shù)據(jù)A始終不變;11第十一頁，共五十四頁，2022年，8月28日問題：如何判斷迭代終止？

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

此定理給出了一個停止迭代的判別準(zhǔn)則。12第十二頁，共五十四頁，2022年，8月28日

輸入最大迭代次數(shù)N，控制誤差ε以及迭代初值

x=（x1，x2…，xn）輸出近似值y=（y1，y2，…，yn）Jacobi迭代法的計算步驟

k=1；

如果||y-x||<ε，則輸出y=（y1，y2，…，yn）。

否則k=k+1，如果k>N，算法失敗。如果k<=N,

置x=y，即xi=yi

(i=1,2,…,n)，goto②

；

13第十三頁，共五十四頁，2022年，8月28日例子解：相應(yīng)的雅可比迭代公式為14第十四頁，共五十四頁，2022年，8月28日例子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)確解為取初值得計算結(jié)果，按迭代公式進(jìn)行迭代，15第十五頁，共五十四頁，2022年，8月28日MatlabforJacobiMethodfunction

y=jacobi(a,b,x0)D=diag(diag(a));U=-triu(a,1);L=-tril(a,-1);B=D\(L+U);f=D\b;y=B*x0+f;n=1;whilenorm(y–x0)>=1.0e–6x0=y;y=B*x0+f;n=n+1;end16第十六頁，共五十四頁，2022年，8月28日高斯—塞德爾(Gauss-Seidel)迭代法

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

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

的分量時，當(dāng)計算到的分量時，當(dāng)計算到都已經(jīng)求得.設(shè)想一旦新分量代替舊分量，可能會加速收斂。

例如

17第十七頁，共五十四頁，2022年，8月28日…

…

…

…Gauss-Seidel迭代法分量形式18第十八頁，共五十四頁，2022年，8月28日Gauss-Seidel迭代的矩陣形式作

A的另一個分裂：

迭代矩陣19第十九頁，共五十四頁，2022年，8月28日例子解：相應(yīng)的高斯-賽德爾迭代公式為20第二十頁，共五十四頁，2022年，8月28日取迭代初值按此迭代公式進(jìn)行迭代，計算結(jié)果為01234500.30.88040.98430.99780.999701.561.94451.99231.99891.999902.6842.95392.99382.99912.999921第二十一頁，共五十四頁，2022年，8月28日迭代法的收斂性

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

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

記各次誤差向量22第二十二頁，共五十四頁，2022年，8月28日迭代法的收斂性

迭代法的收斂性等價于誤差向量序列隨著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∞)

23第二十三頁，共五十四頁，2022年，8月28日迭代法的收斂性定理

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

24第二十四頁，共五十四頁，2022年，8月28日

迭代法的收斂性定理

定理

(充分條件判別法)給定方程組X=BX+f如果，則迭代公式1.對任意初始向量收斂。2.有如下估計25第二十五頁，共五十四頁，2022年，8月28日證明

26第二十六頁，共五十四頁，2022年，8月28日注

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

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

進(jìn)一步可以推知：由于ρ(B)≤‖B‖<1，‖B‖越小，說明ρ(B)越小，序列{X(k)}收斂越快。27第二十七頁，共五十四頁，2022年，8月28日收斂速度下面我們給出收斂速度的概念：定義

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

由于Gauss-Seidel迭代法逐次用計算出來的新值代替舊值，所以在收斂的條件下，它要比Jacobi迭代法收斂速度快。。28第二十八頁，共五十四頁，2022年，8月28日J(rèn)acobi和Gauss-Seidel的收斂性29第二十九頁，共五十四頁，2022年，8月28日注30第三十頁，共五十四頁，2022年，8月28日對于前面的例子由迭代矩陣的特征方程因而雅可比迭代公式是收斂的。31第三十一頁，共五十四頁，2022年，8月28日注32第三十二頁，共五十四頁，2022年，8月28日直接用矩陣A判定斂散性

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

定義如果矩陣A滿足條件則稱A是嚴(yán)格對角占優(yōu)陣(strictlydiagonallydominantmatrix)；33第三十三頁，共五十四頁，2022年，8月28日A為按行按列嚴(yán)格對角占優(yōu)陣；B為按行對角占優(yōu)陣。實(shí)例(Example)34第三十四頁，共五十四頁，2022年，8月28日定理1若A為嚴(yán)格對角占優(yōu)陣，則Jacobi迭代法和

G-S迭代法收斂。

定理2

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

相關(guān)定理

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

首先證明Jacobi

迭代的收斂性。由易求

由嚴(yán)格對角占優(yōu)定義，得BJ∞<1,所以,Jacobi

迭代法收斂。36第三十六頁，共五十四頁，2022年，8月28日

下面證明G-S迭代法的收斂性。對于嚴(yán)格對角占優(yōu)陣A，其對角元素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)=037第三十七頁，共五十四頁，2022年，8月28日

我們通過A的嚴(yán)格對角占優(yōu)性質(zhì)去證明det((D-L)-U)=0的根有性質(zhì)||<1。用反證法：假設(shè)||≥1，且由于A的嚴(yán)格對角占優(yōu)性質(zhì)，有

38第三十八頁，共五十四頁，2022年，8月28日是嚴(yán)格對角占優(yōu)陣，所以它是非奇異的，即det((D-L)-U)0與特征值滿足det((D-L)-U)=0

矛盾。故

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

39第三十九頁，共五十四頁，2022年，8月28日注值得注意的是，改變方程組中方程的次序，即將系數(shù)矩陣進(jìn)行行交換，會改變迭代法的收斂性。

無法直接判斷Jacobi

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

40第四十頁，共五十四頁，2022年，8月28日注

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

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

41第四十一頁，共五十四頁，2022年，8月28日

超松弛迭代法(SOR)

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

：

首先用G-S法定義輔助量：選擇參數(shù)ω，取42第四十二頁，共五十四頁，2022年，8月28日

超松弛迭代法(SOR)即得SOR法其中，參數(shù)ω叫做松弛因子；若ω=1，它就是Gauss-Seidel迭代法。

43第四十三頁，共五十四頁，2022年，8月28日

超松弛迭代法(SOR)另一種理解將Gauss-Seidel迭代格式改寫為被稱為增量形式?？梢詫⒖醋黾右粋€修正量得到的。44第四十四頁，共五十四頁，2022年，8月28日

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

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

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

45第四十五頁，共五十四頁，2022年，8月28日例用SOR法求解線性方程組①取ω=1，即Gauss-Seidel迭代：

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

46第四十六頁，共五十四頁，2022年，8月28日例

迭代結(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.000348647第四十七頁，共五十四頁，2022年，8月28日

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

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

48第四十八頁，共五十四頁，2022年，8月28日SOR迭代的矩陣形式：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