數值分析課件方程組迭代法1第1頁，課件共54頁，創作于2023年2月

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

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

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

引言2第2頁，課件共54頁，創作于2023年2月

迭代法的基本思想

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

迭代法的基本思想是去構成一個向量序列{x(k)}，使其收斂至某個極限向量x*，并且x*就是要求解的方程組：Ax=b的準確解。3第3頁，課件共54頁，創作于2023年2月迭代法的主要步驟

Theprocessofiterativemethod

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

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

x=Bx+f

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

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

進行計算,其中k表迭代次數。4第4頁，課件共54頁，創作于2023年2月

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

問題

迭代公式的建立迭代公式的收斂性收斂速度誤差估計5第5頁，課件共54頁，創作于2023年2月基本迭代公式把矩陣A分裂為則記

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

則注：選取M陣，就得到解Ax=b的各種迭代法.6第6頁，課件共54頁，創作于2023年2月

本章重點介紹三個迭代法，即：

Jacobi迭代法

Gauss-Seidel迭代法

超松弛迭代法（SOR法）7第7頁，課件共54頁，創作于2023年2月Jacobi迭代法由方程組AX=b的第i個方程解出得到一個同解方程組

8第8頁，課件共54頁，創作于2023年2月獲得相應的迭代公式Jacobi迭代法取初始向量稱上式為雅可比迭Jacobi迭代公式。9第9頁，課件共54頁，創作于2023年2月Jacobi迭代法的矩陣形式若記

則有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第10頁，課件共54頁，創作于2023年2月

迭代矩陣Jacobi迭代法的特點

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

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

計算過程中,初始數據A始終不變;11第11頁，課件共54頁，創作于2023年2月問題：如何判斷迭代終止？

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

此定理給出了一個停止迭代的判別準則。12第12頁，課件共54頁，創作于2023年2月

輸入最大迭代次數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第13頁，課件共54頁，創作于2023年2月例子解：相應的雅可比迭代公式為14第14頁，課件共54頁，創作于2023年2月例子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原方程組的準確解為取初值得計算結果，按迭代公式進行迭代，15第15頁，課件共54頁，創作于2023年2月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第16頁，課件共54頁，創作于2023年2月高斯—塞德爾(Gauss-Seidel)迭代法

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

研究雅可比迭代法，我們發現在逐個求

的分量時，當計算到的分量時，當計算到都已經求得.設想一旦新分量代替舊分量，可能會加速收斂。

例如

17第17頁，課件共54頁，創作于2023年2月…

…

…

…Gauss-Seidel迭代法分量形式18第18頁，課件共54頁，創作于2023年2月Gauss-Seidel迭代的矩陣形式作

A的另一個分裂：

迭代矩陣19第19頁，課件共54頁，創作于2023年2月例子解：相應的高斯-賽德爾迭代公式為20第20頁，課件共54頁，創作于2023年2月取迭代初值按此迭代公式進行迭代，計算結果為01234500.30.88040.98430.99780.999701.561.94451.99231.99891.999902.6842.95392.99382.99912.999921第21頁，課件共54頁，創作于2023年2月迭代法的收斂性

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

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

記各次誤差向量22第22頁，課件共54頁，創作于2023年2月迭代法的收斂性

迭代法的收斂性等價于誤差向量序列隨著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第23頁，課件共54頁，創作于2023年2月迭代法的收斂性定理

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

24第24頁，課件共54頁，創作于2023年2月

迭代法的收斂性定理

定理

(充分條件判別法)給定方程組X=BX+f如果，則迭代公式1.對任意初始向量收斂。2.有如下估計25第25頁，課件共54頁，創作于2023年2月證明

26第26頁，課件共54頁，創作于2023年2月注

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

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

進一步可以推知：由于ρ(B)≤‖B‖<1，‖B‖越小，說明ρ(B)越小，序列{X(k)}收斂越快。27第27頁，課件共54頁，創作于2023年2月收斂速度下面我們給出收斂速度的概念：定義

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

由于Gauss-Seidel迭代法逐次用計算出來的新值代替舊值，所以在收斂的條件下，它要比Jacobi迭代法收斂速度快。。28第28頁，課件共54頁，創作于2023年2月Jacobi和Gauss-Seidel的收斂性29第29頁，課件共54頁，創作于2023年2月注30第30頁，課件共54頁，創作于2023年2月對于前面的例子由迭代矩陣的特征方程因而雅可比迭代公式是收斂的。31第31頁，課件共54頁，創作于2023年2月注32第32頁，課件共54頁，創作于2023年2月直接用矩陣A判定斂散性

收斂性定理雖然給出了判別迭代法收斂的充要條件，但實際使用時很不方便，因為求逆矩陣和特征值的難度并不亞于用直接法求解線性方程組。下面對一些特殊的方程組，從方程組本身出發給出幾個常用的判別條件，而不必求迭代陣的特征值或范數。

定義如果矩陣A滿足條件則稱A是嚴格對角占優陣(strictlydiagonallydominantmatrix)；33第33頁，課件共54頁，創作于2023年2月A為按行按列嚴格對角占優陣；B為按行對角占優陣。實例(Example)34第34頁，課件共54頁，創作于2023年2月定理1若A為嚴格對角占優陣，則Jacobi迭代法和

G-S迭代法收斂。

定理2

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

相關定理

可以總結，討論迭代法的收斂性，應首先從A出發討論其是否具有主對角占優或對稱正定性；其次對迭代法的迭代陣討論其是否有范數小于1；最后利用迭代陣的譜半徑討論（這是充分必要條件）。35第35頁，課件共54頁，創作于2023年2月定理1的證明證

首先證明Jacobi

迭代的收斂性。由易求

由嚴格對角占優定義，得BJ∞<1,所以,Jacobi

迭代法收斂。36第36頁，課件共54頁，創作于2023年2月

下面證明G-S迭代法的收斂性。對于嚴格對角占優陣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第37頁，課件共54頁，創作于2023年2月

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

38第38頁，課件共54頁，創作于2023年2月是嚴格對角占優陣，所以它是非奇異的，即det((D-L)-U)0與特征值滿足det((D-L)-U)=0

矛盾。故

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

39第39頁，課件共54頁，創作于2023年2月注值得注意的是，改變方程組中方程的次序，即將系數矩陣進行行交換，會改變迭代法的收斂性。

無法直接判斷Jacobi

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

40第40頁，課件共54頁，創作于2023年2月注

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

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

41第41頁，課件共54頁，創作于2023年2月

超松弛迭代法(SOR)

通過引入參數，在Gauss-Seidel法的基礎上作適當修改，在不增加過多的計算量的條件下，可得到一種新的，收斂更快的迭代法。

：

首先用G-S法定義輔助量：選擇參數ω，取42第42頁，課件共54頁，創作于2023年2月

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

43第43頁，課件共54頁，創作于2023年2月

超松弛迭代法(SOR)另一種理解將Gauss-Seidel迭代格式改寫為被稱為增量形式。可以將看做加一個修正量得到的。44第44頁，課件共54頁，創作于2023年2月

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

時，稱為超松弛算法，當ω<1

時，稱為亞松弛算法。目前，還沒有自動選擇因子的一般方法，實際計算中，通常取（0，2）區間內幾個不同的ω值進行試算，通過比較后，確定比較理想的松弛因子ω。

45第45頁，課件共54頁，創作于2023年2月例用SOR法求解線性方程組①取ω=1，即Gauss-Seidel迭代：

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

46第46頁，課件共54頁，創作于2023年2月例

迭代結果見表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第47頁，課件共54頁，創作于2023年2月

迭代法若要精確到七位小數，

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

48第48頁，課件共54頁，創作于2023年2月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+