Jacobi迭代法與Gauss-Seidel迭代法

郝艷花

（山西大同大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院,山西大同037009）

Jacobi迭代法與Gauss-Seidel迭代法

郝艷花

（山西大同大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院,山西大同037009）

迭代法是解線性方程組的一個(gè)很重要的方法，特別是在系數(shù)矩陣為稀疏矩陣的大型線性方程組中尤為重要。主要討論解線性方程組的雅可比迭代法與高斯-塞德爾迭代法這兩種方法,針對(duì)這兩種迭代法的定義，收斂性，以及收斂速度展開討論。

線性方程組；雅可比迭代法；高斯-塞德爾迭代法；收斂性

目前在工程技術(shù)、物理學(xué)、生物學(xué)以及自然科學(xué)中很多問題的解決經(jīng)常歸結(jié)為解線性代數(shù)方程組，例如用有限元或者差分法解常微分方程，偏微分方程邊值問題，用最小二乘法求實(shí)驗(yàn)數(shù)據(jù)的曲線擬合，經(jīng)濟(jì)學(xué)中的投入-產(chǎn)出分析以及增長模型等問題都導(dǎo)致求解線性代數(shù)方程組，而這些方程組中的未知量往往多達(dá)幾百個(gè)，用傳統(tǒng)方法求解顯然很復(fù)雜，只能借助計(jì)算機(jī)。

目前關(guān)于線性方程組的數(shù)值解法一般有兩類：迭代法和直接法。直接法是經(jīng)過有限布算術(shù)運(yùn)算，可求得線性方程組精確解的方法，但是在實(shí)際問題中存在舍入誤差以及它的影響，這種方法只能求得線性方程組的近似解。而相對(duì)于直接法，迭代法是用某種極限過程逐步逼近線性方程組精確解的方法，它具有需要程序設(shè)計(jì)簡單，計(jì)算機(jī)的存儲(chǔ)單元較少，原始系數(shù)矩陣在計(jì)算過程中一直不變等優(yōu)點(diǎn)，但存在收斂性和收斂速度等問題。[1-2]本文主要討論解線性方程組的雅可比迭代法與高斯-塞德爾迭代法的收斂性。[3-4]

1 迭代法的基本概念

1.1 迭代法的定義

定義1對(duì)于給定的線性方程組x=Ax+f,設(shè)有唯一解x*，則x*=Ax+f，又設(shè)x(0)為認(rèn)取的初始向量，按以下公式構(gòu)造向量序列x(k+1)=Ax(k)+f,k=0,1,2,…,其中k表示迭代次數(shù)。

定義2對(duì)于給定的線性方程組x=Ax+f，用逐步代入求近似解的方法稱為迭代法。

2 迭代法的收斂性

設(shè)有線性方程組,Ax=b，其中A=aij∈Rn×n為非奇異矩陣，下面研究建立解Ax=b的迭代法。

將A分裂為A=E-F，其中E為可選擇的非奇異矩陣，且Ex=b容易求解，稱E為分裂矩陣。于是，求解Ax=b轉(zhuǎn)化為求解Ex=Fx+b，即求解

即解線性方程組

從而可構(gòu)造一階定常迭代法：

其中B=E-1F=E-1(E-A)=I-E-1A,f=E-1b,稱B為迭代法的迭代矩陣，選取E矩陣，就得到解Ax=b的各種迭代法。

定理1（迭代法收斂的充分條件）設(shè)有線性方程組x=Bx+f及一階定常x(k+1)=Bx(k)+f,如果有B的某種算子范數(shù)‖B‖=q＜1，則

（1）迭代法收斂，即對(duì)任意的x(0)有且x*=Bx(k)+f；

定理2（迭代法收斂的充要條件）給定線性方程組（1）以及一階定常迭代法，對(duì)任意選取的初始向量x(0)，迭代法（2）式收斂的充要條件是矩陣B的譜半徑ρ(B)＜1。

證明必要性:設(shè)對(duì)任意選取的x(0)，有其中x(k+1)=Bx(k)+f。

顯然，極限x*是線性方程組（1）的解，且誤差向量ε(k)=x(k)-x*=Bε(k-1)=…=Bkε(0)→0(k→∞)，

充分性：設(shè)ρ(B)＜1,易知Ax=f(A=I-B)唯一解，記為x*，則x*=Bx*+f，誤差向量ε(k)=x(k)-x*=Bkε(0),ε(0)=x(0)-x*。設(shè)ρ(B)＜1 ，所以有0，于是對(duì)任意x(0)，有即

3 迭代法的收斂速度

定義4一階定常迭代法

解:先求迭代矩陣B0的特征值，由特征方程

解得λ1,λ2,λ3，所以ρ(B0)＜1,所以用該迭代法解此線性方程組是收斂的。

例2考察用迭代法解線性方程組x(k+1)=Bx(k)+f的收斂性，其中

解：特征方程為 det(λI-B)=λ2-5λ+4=0，所以λ1=1,λ2=4，即ρ(B)≥ 1,所以由迭代法收斂的充要條件，得用此迭代法解該線性方程組不收斂。

4 雅可比迭代法與高斯-塞德爾迭代法及其收斂性

4.1 高斯-塞德爾迭代法

將線性方程組Ax=b中的系數(shù)矩陣A=aij∈Rn×n分成三部分,

選取分裂矩陣E=D-L（下三角矩陣），A=E-F，于是由一階定常迭代法可以得到解Ax=b的高斯-塞德爾迭代法，

其中，稱G為Ax=b的高斯-塞德爾迭代法的迭代矩陣。

下面給出高斯-塞德爾迭代法的分量計(jì)算公式。

于是解Ax=b的高斯-塞德爾迭代法的計(jì)算公式為

4.2 雅可比迭代法

選取分裂矩陣E=D（對(duì)角矩陣）A=D-F,同樣由一階定常迭代法得到解Ax=b的雅可比迭代法

其中B=1-D-1A=D-1(L+U)=J,f=D-1b稱J為解Ax=b的雅可比迭代法的迭代矩陣。

由雅可比迭代公式有

于是得到解Ax=b的雅可比迭代法的計(jì)算公式為

例3設(shè)線性方程組

分別寫出雅可比迭代法與高斯-塞德爾迭代法。

解：雅可比迭代為

高斯-塞德爾迭代法

4.3 雅可比迭代法與高斯-塞德爾迭代法收斂性

由定理1得，高斯-塞德爾迭代法與雅可比迭代法收斂的充要條件分別是ρ(BG)＜1，其中G=(D-L)-1U，和ρ(BJ)＜1，其中J=D-1(L+U)。

由定理2得，高斯-塞德爾迭代法與雅可比迭代法收斂的充分條件是‖G‖＜1，其中G=(DL)-1U，和‖J‖＜1，其中J=D-1(L+U)。

另外，在實(shí)際問題的求解過程中，線性方程組Ax=b，其矩陣A經(jīng)常具有某些特征。例如A為對(duì)稱正定矩陣，或?yàn)椴豢杉s矩陣，或者A具有對(duì)角占優(yōu)性質(zhì)等。下面討論當(dāng)A具有這些性質(zhì)時(shí)解線性方程組Ax=b的收斂性。

[1]李慶揚(yáng)，王能超，易大義.數(shù)值分析[M].5版.北京：清華大學(xué)出版社.

[2]張傳林.數(shù)值方法[M].北京：中國科學(xué)文化出版社，2001：80-150.

[3]馬云.數(shù)值分析中的迭代法解線性方程組[J].考試周刊，2010（50）：71-72.

[4]趙丹.雅可比迭代法與高斯-塞德爾迭代法研究[J].興義民族師范學(xué)院學(xué)報(bào),2012（2）：108-112.

〔責(zé)任編輯 高海〕

Jacobi Iteration Method and Gauss-Seidel Iteration Method

HAO Yan-Hua
(School of Mathematics and Computer Science,Shanxi Datong University,Datong Shanxi,037009)

Iteration method is a very important method for solving linear equations,especially in large linear equations with coeffi?cient matrices as sparse matrices.In this paper,we mainly discuss on the Jacobi iteration method and the Gauss-Seidel iteration meth?od for solving the linear equations.We mainly study the definition,convergence and convergence speed of these two iteration methods.

linear equations;Jacobi iteration;Gauss-Seidel iteration;astringency

TP273

A

1674-0874(2017)05-0003-03

2017-06-26

郝艷花（1974-），女，山西廣靈人，碩士，副教授，研究方向：計(jì)算數(shù)學(xué)。