線性方程組的4種迭代方法

雍龍泉

(陜西理工大學 數(shù)學與計算機科學學院， 陜西 漢中 723000)

?

線性方程組的4種迭代方法

雍龍泉

(陜西理工大學 數(shù)學與計算機科學學院， 陜西 漢中 723000)

研究了線性方程組的4種迭代方法——Jacobi迭代、Gauss-Seidel迭代、HSS迭代、Richardson迭代，給出了4種迭代方法收斂的充分條件。數(shù)值實驗進一步表明，在大規(guī)模線性方程求解時，迭代矩陣譜半徑的大小決定算法的收斂速度；在譜半徑小于1的前提下，譜半徑越小，則收斂速度越快。

線性方程組；Jacobi迭代；Gauss-Seidel迭代；HSS迭代；Richardson迭代；譜半徑

考慮如下線性方程組

記

當矩陣A∈Rn×n非奇異時，方程組Ax=b具有唯一解。

消去法是求解線性方程組的一類有效方法，但是針對大規(guī)模線性方程組，消去法計算效率較低，而迭代法能夠快速地收斂到線性方程組的解[1]。迭代法的基本思想就是構(gòu)造方程組Ax=b的等價方程組x=Bx+f，從而建立迭代公式

當?shù)仃嘊的譜半徑ρ(B)<1時，則對任意的初始向量x0∈Rn，迭代法都收斂[2-4]。

在構(gòu)造線性方程組的迭代時需要注意兩個原則：

①迭代矩陣譜半徑要小于1，即首先要保證收斂；

②迭代矩陣譜半徑遠小于1，則迭代收斂越快。

下面給出4種常見的迭代方法。

1　迭代方法及收斂性

1.1Jacobi迭代

考慮線性方程組Ax=b，這里A∈Rn×n，記

假設aii≠0，i=1,2,…,n。則Jacobi迭代為

(1)

其中BJ=-D-1(L+U)， fJ=D-1b。

1.2Gauss-Seidel迭代

利用Jacobi迭代，可得Gauss-Seidel迭代為

(2)

其中BS=-(L+D)-1U， fS=(L+D)-1b。det(L+D)=a11a22…ann≠0，故(L+D)-1存在。

下面給出Jacobi迭代與Gauss-Seidel迭代收斂的充分條件。

定理1(1)若矩陣A∈Rn×n是嚴格對角占優(yōu)，則Jacobi迭代與Gauss-Seidel迭代均收斂；(2)若矩陣A∈Rn×n是對稱正定矩陣，則Gauss-Seidel迭代收斂，Jacobi迭代不一定收斂。

定理1的證明見文獻[1,5]。

1.3HSS迭代

考慮線性方程組Ax=b，這里A∈Rn×n，且A為廣義正定矩陣。對矩陣A做分解A=H+S，其中H=(A+AT)/2，S=(A-AT)/2，H稱為A的對稱分量，S稱為A的反對稱分量；顯然，n階實方陣A的對稱分量H和反對稱分量S是唯一的。A是廣義正定矩陣的充分必要條件是A的對稱分量H是對稱正定矩陣[6-7]。

A是廣義正定矩陣，則A的對稱分量H是對稱正定矩陣。記矩陣H的特征值為0<λmin=λ1≤λ2≤λ3≤…≤λn-1≤λn=λmax，對任意的α>0，構(gòu)造方程組Ax=b的迭代格式為

(3)

這里B(α)=(αI+S)-1(αI-H)(αI+H)-1(αI-S)，G(α)=2α(αI+S)-1(αI+H)-1，稱迭代(3)為線性方程組Ax=b的HSS迭代[8]。下面給出HSS迭代法的收斂性。

定理2的證明見文獻[8-9]。

當A是對稱正定矩陣時，H=A，S=O，此時

1.4Richardson迭代

考慮線性方程組Ax=b，這里A∈Rn×n，且A為對稱正定矩陣，設矩陣A的特征值為0<λmin=λ1≤λ2≤λ3≤…≤λn-1≤λn=λmax，對任意的τ>0，方程組Ax=b等價于x=(I-τA)x+τb，構(gòu)造迭代

(4)

這里B(τ)=(I-τA)，稱迭代(4)為線性方程組Ax=b的Richardson迭代[10]。下面給出Richardson迭代法的收斂性。

定理3的證明見文獻[11]。

定理1、定理2、定理3分別給出了Jacobi迭代、Gauss-Seidel迭代、HSS迭代、Richardson迭代收斂的充分條件，這4種迭代都有嚴格的適用范圍；對一般矩陣，若不滿足上述條件，則只能用迭代矩陣的譜半徑來判別收斂性；理論上，在譜半徑小于1的前提下，譜半徑越小，則收斂速度越快。下面通過算例來說明上述4種迭代法的收斂性。

2　數(shù)值實驗

算例考慮線性方程組Ax=b，其中

方程組的精確解為x=(1,1,…,1)T∈Rn。這里矩陣A嚴格對角占優(yōu)，且為廣義正定矩陣(由于其對稱分量H是對稱正定矩陣，故A是廣義正定矩陣)，因此，該線性方程組可以用Jacobi迭代、Gauss-Seidel迭代、HSS迭代進行求解；由于矩陣A不是對稱正定，因此不能直接用定理3來判別Richardson迭代的收斂性，只能用譜半徑來判別迭代是否收斂。

表1　4種迭代法的計算結(jié)果

注：ρ表示迭代矩陣譜半徑，k表示迭代次數(shù)，t表示運行時間(單位：s)。

文獻[12-13]表明，針對大規(guī)模線性方程組，HSS迭代法適用范圍廣，且計算效率高。但是對該問題而言：(ⅰ)隨著維數(shù)的增加，4種迭代矩陣譜半徑都小于1，因此上述4種迭代都收斂；(ⅱ)隨著維數(shù)的增加，Jacobi和Gauss-Seidel迭代的譜半徑卻在減小(圖1)，因此迭代次數(shù)和運行時間較少；而HSS和Richardson迭代的譜半徑在增大(圖2)，因此迭代次數(shù)和運行時間變大；(ⅲ)隨著維數(shù)的增加，Jacobi和Gauss-Seidel迭代譜半徑都遠遠小于1，且Gauss-Seidel的譜半徑更小，因此Gauss-Seidel收斂速度更快，精度更高。圖1、圖2分別給出了在不同維數(shù)下迭代矩陣的譜半徑。

圖1　Jacobi與Gauss-Seidel迭代譜半徑　　　　　圖2　HSS與Richardson迭代譜半徑

該例子進一步表明，在大規(guī)模線性方程求解時，若選用迭代算法，一定要重點考察迭代矩陣的譜半徑，在譜半徑小于1的前提下，譜半徑越小，則收斂速度越快。

圖3—圖6分別給出了n=50時Jacobi迭代、Gauss-Seidel迭代、HSS迭代、Richardson迭代的收斂過程(橫軸表示迭代次數(shù)，縱軸表示迭代過程中向量x分量的取值)。

圖3　Jacobi迭代的收斂過程　　　　　　　　　圖4　Gauss-Seidel迭代的收斂過程

圖5　HSS迭代的收斂過程　　　　　　　　　圖6　Richardson迭代的收斂過程

限于篇幅，其余維數(shù)的收斂過程圖不一一列出；針對該問題而言，隨著維數(shù)的增加，HSS迭代和Richardson迭代的譜半徑接近1，收斂呈現(xiàn)振蕩性，因此收斂較慢；而Jacobi迭代和Gauss-Seidel迭代的譜半徑遠遠小于1，因此收斂速度較快。

3　結(jié)　語

本文研究了線性方程組常見的4種迭代方法，給出了4種迭代方法收斂的充分條件。對一般矩陣，若不滿足這些充分條件，則只能用迭代矩陣的譜半徑來判別收斂性；因此，在實際問題求解時，如果能夠找到多種收斂的迭代方法，則需要重點比較迭代矩陣的譜半徑，在譜半徑小于1的前提下，譜半徑越小，則收斂速度越快。

[1]谷同祥,安恒斌,劉興平,等.迭代方法和預處理技術(shù):上冊[M].北京:科學出版社,2015:21-186.

[2]徐樹方,高立,張平文.數(shù)值線性代數(shù)[M].2版.北京:北京大學出版社,2013:15-197.

[3]王轉(zhuǎn)德.迭代矩陣的譜分析[D].成都:電子科技大學,2009.

[4]李愛芹.線性方程組的迭代解法[J].科學技術(shù)與工程,2007,7(14):3357-3364.

[5]楊大地,王開榮.數(shù)值分析[M].北京:科學出版社,2006:47-59.

[6]李炯生.實方陣的正定性[J].數(shù)學的實踐與認識,1985,15(3):67-73.

[7]雍龍泉,劉三陽,史加榮,等.幾類特殊矩陣及性質(zhì)[J].蘭州大學學報:自然科學版,2016,52(3):385-389.

[8]BAI Zhong-zhi,GOLUB G H,NG M K.Hermitian and skew-Hermitian splitting methods for non-Hermitian positive definite linear systems[J].SIAM Journal on Matrix Analysis and Applications,2003,24(3):603-626.

[9]BAI Zhong-zhi,YANG Xi.On HSS-based iteration methods for weakly nonlinear systems[J].Applied Numerical Mathematics,2009,59(12):2923-2936.

[10]施妙根,顧麗珍.科學和工程計算基礎[M].北京:清華大學出版社,1999:108-109.

[11]RYABENKII V S,TSYNKOV S V.A theoretical introduction to numerical analysis[M].Florida:CRC Press,2006:173-194.

[12]陳芳,左軍.鞍點問題的HSS-GS迭代法與收斂理論[J].北京信息科技大學學報:自然科學版,2014,29(4):25-29.

[13]吳世良,李翠霞.求解一類復對稱線性系統(tǒng)的改進的SNS和SSS迭代法[J].中國科學:數(shù)學,2014,44(9):1007-1020.

[責任編輯：魏 強]

Four iterative methods to linear systems

YONG Long-quan

(School of Mathematics and Computer Science, Shaanxi Sci-Tech University,Hanzhong 723000, China)

Four iterative methods to linear systems, such as Jacobi, Gauss-Seidel, HSS, and Richardson iterative, are studied, and sufficient conditions for the convergence of these iterative methods are given. Numerical experiments further show that the size of spectral radius of iterative matrix determines convergence rate in solving large-scale linear systems. Under the premise of spectral radius of iterative matrix less than 1, the smaller the spectral radius, the faster convergence speed.

linear systems;Jacobi iterative;Gauss-Seidel iterative;HSS iteration;Richardson iterative;spectral radius

1673-2944(2016)05-0080-05

2016-06-02

2016-08-08

陜西省教育廳科研基金資助項目(16JK1150)；陜西理工學院科研計劃項目(SLGKYQD2-14)

雍龍泉(1980—)，男，陜西省洋縣人，陜西理工大學副教授，博士，主要研究方向為優(yōu)化理論與算法。

O151.2

A