第三章線性方程組迭代解法

IterativetechniquesforsolvinglinearsystemNumericalAnalysis內容提要(content)

3.1概論(Introduction)

3.2(I)Jacobi

迭代法(Jacobiiterative)

3.2(II)Gauss-Seidel迭代法(Gauss-Seideliterative)

3.3迭代法的收斂性(Theconvergenceofiterativemethod)

3.4SOR法

(SORmethod))

本章學習要點概論引子迭代法的基本思想迭代法的主要步驟

直接法得到的解是理論上準確的，但是我們可以看得出，它們的計算量都是n3數量級，存儲量為n2量級，這在n比較小的時候還比較合適（n<400），但是對于現在的很多實際問題，往往要我們求解很大的n的矩陣，而且這些矩陣(系數矩陣)往往是含有大量的0元素。對于這類的矩陣，再用直接法時就會耗費大量的時間和存儲單元。另一方面,實際計算結果精度有時無法保證.

主要原因是在多次消去、回代過程中四則運算的誤差積累與傳播無法控制.因此我們有必要引入一類新的方法：迭代法。

引子(Introduction)返回節(jié)Directtechniquesareusedforsolvinglinearsystemsofsmalldimension.Forlargesystemswithhighpercentageof0entries,thedirectmethodsarenotefficientenoughintermOfcomputerstorageandcomputationamount.迭代法的基本思想

Theidealofiterativemethod

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

迭代法的基本思想是去構成一個向量序列{x(k)}，使其收斂至某個極限向量x*，并且x*就是要求解的方程組：Ax=b的準確解。返回節(jié)AniterativetechniquetosolvingAx=bstartswithaninitialApproximatex0andgeneratesasequenceof{x(k)}(k=1,2…..)thatconvergesTox.迭代法的主要步驟

Theprocessofiterativemethod解線性方程組迭代法的主要步驟是:1.把所給的線性方程組Ax=b化成如下形式的同解方程組

x=Bx+f

（3-1)

2.

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

x(k+1)=Bx(k)+f

(k=0,1,2,…)

（3-2)進行計算,其中k表迭代次數。ConvertingAx=bintoanequivalentformForgiveninitialvectorx0,thesequencesofapproximateSolutionsaregeneratedbycomputing

(3-2)

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

迭代公式的構造

迭代公式的收斂性Howtoconstructiterativescheme?2.Theconvergenceofiterativescheme.Problem:研究{x(k)}的收斂性引進誤差向量e(k+1)=x(k+1)-x*因此e(k+1)=Be(k)(k=1,2,…..)所以e(k+1)=Bk+1e(0)

x(k+1)=Bx(k)+f要考察{x(k)}

的收斂性,就要研究B在什么條件下有

e(k+1)0(k∞)亦即要研究B滿足什么條件時有

Bk+1

0Theconvergenceof{x(k)}

Bk+1

0Thecondition?基本迭代法

thebasediterativetechnique設有其中A為非奇異矩陣.

將A分裂為其中M為可選擇的非奇異矩陣，且使Mx=d容易求解，一般選擇為A的某種近似，稱M為分裂矩陣.SplittingAintotwoparts,nonsingularmatrixMandgeneralmatrix–N.ThatisA=M-N.于是，求解Ax=b轉化為求解Mx=Nx+b，即Ax=b

x=M-1Nx+M-1b

B=M-1N,f=M-1b注：選取M陣，就得到解Ax=b的各種迭代法.Remark:WecanobtainvariousiterativeschemesbychoosingdifferentM.

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

1）Jacobi迭代法,2）Gauss-Seidel

迭代法,3）超松弛迭代法（SOR法）及其收斂性。Thethreeiterativeschemesinthetextbook:1.Jacobiiteration2.Gauss-Seideliteration3.SORmethod§3.2(I)Jacobi迭代法

（Jacobiiterativemethod）數學問題的描述Jacobi迭代法的主要步驟Themathematicalform

TheprocessofJacobiiterativemethod數學問題的描述

設有線性方程組

Ax=b

即

（3-3）

其中A=(aij)nn

非奇異（A0），且aii≠0(i=1,2,…,n),由式（3-3）得

（3-4）

Jacobiiterativemethod若記

則有A=D-L-U成立，而式（3-4）的矩陣形式為

DX=（L+U）X+b

（3-5）

等式兩邊乘以D-1，得

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

（3-6）

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

X（k+1）=D-1（L+U）X（k）+D-1b（3-7）即 （3-8）這種迭代法，稱為Jacobi迭代法。

返回節(jié)D-1bD-1（L+U）x（k）Jacobi迭代的分量形式3.2雅可比(Jacobi)迭代法迭代矩陣(Iterativematrix);每迭代一次主要是計算一次矩陣乘向量；Thecalculationamountliesinineverystep.計算過程中,初始數據A始終不變;ThematrixAisalwaysunchangedintheiterativeprocess

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

y(n)來存儲.

Twocomputerstoragesx(n),y(n)arerequired.

問題：如何判斷可以終止迭代？若迭代矩陣B滿足||B||〈1則給出了一個停止迭代的判別準則。Problem:stoppingcriteria?Theorem:IfthenormofBissmallerthan1,thenSopossiblestoppingcriteriaistoiterateuntil|x(k+1)-x(k)|issmallerthangiventolerance.

Jacobi

迭代法的計算步驟(5步)為：

①k=1；②

；

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

k=k+1，如果k>N，算法失敗。

⑤

置x=y，即xi=yi(i=1,2,…,n)，goto②；

Jacobi迭代法的主要步驟else輸入最大迭代次數N，控制誤差ε以及迭代初值x=（x1，x2，…，xn）輸出近似值y=（y1，y2，…，yn）else3.1求解Jacobi迭代公式為：解:選取X（0）=(0,0,0,0)T,迭代10次，結果見表3-1

返回引用Examplekx1（k）

x2（k）

x3（k）

x4（k）

00.00000.00000.00000.0000

10.60002.2727-1.10001.8750

21.04731.7157-0.80520.8852

30.93262.0533-1.04931.1309

41.01521.9537-0.96810.9739

50.98902.0114-1.01031.0214

61.00321.9922-0.99450.9944

70.99812.0023-1.00201.0036

81.00061.9987-0.99900.9989

90.99972.0004-1.00041.0006

101.00011.9998-1.99980.9998例3.1迭代結果表3-1返回引用對于Jacobi迭代法,它的每一步設定計算順序為在計算迭代值時,

利用它前面已計算的值而此時也已計算,但是Jacobi迭代法并沒有充分及時地利用這些信息,為此我們得到改進的格式,稱為高斯—塞德爾(Gauss–Seidel)迭代公式。

Jacobi迭代法的改進返回章AnpossibleimprovementinJacobiiterativemethodistousetheComponentsoftocompute.ItresultsinGuass-SeidelScheme.§3.2(II)Gauss-Seidel迭代法算法分析與描述實例求解算法分析與描述(3-8)可寫成形如

原Jacobi迭代公式(3-8)

在Jacobi

迭代中，是用x(k)的全部分量來計算x(k+1)的全部分量的。

我們應該注意到，在計算新分量xi(k+1)時，分量x1(k+1),x2(k+1),…,xi-1(k+1)都已經算出。返回引用

如果

Jacobi

法收斂，則可期望x(k+1)比X(k)更好，在式(3-8)中右邊第1個求和號中，用x(k+1)的分量代替x(k)的分量，似乎更合理些。這對許多問題來說，不僅會加快收斂速度，更重要的是，在排程序時，不必另設一套單元來記存上一次的近似解。這就是逐個代換算法，又稱Gauss-Seidel迭代法。因此，我們就得到新的迭代公式：（3-9)

這就是Gauss-Seidel迭代公式．Gauss-Seidel迭代的分量形式ThecomponentofGuass-seideliterativemethod推導Gauss-Seidel迭代法的矩陣形式ThematrixformofGuass-Seideliterativemethod3-dimensioncase

Thegeneralcase:

X(k+1)=BG

X(k)+fG

（3-10）

其中

BG=(D-L)-1U，fG=(D-L)-1b，稱BG為G-S迭代矩陣。

由于Gauss-Seidel迭代法逐次用計算出來的新值代替舊值，所以在收斂的條件下，它要比Jacobi迭代法收斂速度快。但是對于某些線性方程，Jacobi迭代法收斂，而Gauss-Seidel迭代法不收斂。返回節(jié)Gauss-Seidel迭代公式的其矩陣形式為：Ingeneralspeaking,Gauss-SeidelmethodissuperiortotheJacobimethod,especialconvergentspeed.However,Forsomelinearsystem,theJacobimethodconvergesandGauss-Seide