外推Gauss－Seidel迭代法的收斂性及其與H－矩陣的關(guān)系

薛秋芳，高興寶，劉曉光

（1.陜西師范大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院，西安 710062；2.西安理工大學(xué)應(yīng)用數(shù)學(xué)系，西安 710054）

外推Gauss－Seidel迭代法的收斂性及其與H－矩陣的關(guān)系

薛秋芳1，2，高興寶1，劉曉光1

（1.陜西師范大學(xué)數(shù)學(xué)與信息科學(xué)學(xué)院，西安 710062；2.西安理工大學(xué)應(yīng)用數(shù)學(xué)系，西安 710054）

考慮外推Gauss－Seidel迭代法的收斂性及其與H－矩陣的關(guān)系，給出了外推Gauss－Seidel迭代法與Jacobi迭代法收斂性的關(guān)系及收斂的參數(shù)范圍.利用最優(yōu)尺度矩陣及M－1N的估計(jì)量給出了H－矩陣外推Gauss－Seidel法譜半徑的上界估計(jì)式，并基于外推Gauss－Seidel及Gauss－Seidel迭代法得到一般H－矩陣的等價(jià)條件.

H－矩陣；Gauss－Seidel迭代法；外推Gauss－Seidel迭代法；最優(yōu)尺度矩陣；譜半徑

0 引 言

對(duì)大型稀疏線性方程組

一般采用迭代法求解，這里：A＝（aij）為n×n階方陣；x和b均為n維向量.經(jīng)典的迭代法有Jacobi迭代法、Gauss－Seidel迭代法、SOR迭代法和AOR迭代法等.為改進(jìn)迭代收斂性，加快迭代收斂速度，對(duì)不同的迭代法人們又提出了相應(yīng)的外推迭代法，如外推Jacobi迭代法和外推Gauss－Seidel迭代法等.本文討論外推Gauss－Seidel迭代法.

設(shè)A＝D－L－U，其中：D，－L和－U分別是A的對(duì)角、嚴(yán)格下三角和嚴(yán)格上三角矩陣，則A的Gauss－Seidel迭代法（簡(jiǎn)稱GS迭代法）是基于分裂A＝（D－L）－U得到的，其迭代格式為

其中G＝（D－L）－1U為Gauss－Seidel迭代矩陣.相應(yīng)的外推Gauss－Seidel迭代法（簡(jiǎn)稱EGS方法）迭代格式為

其中：G h＝（1－h(huán)）I＋h G為外推Gauss－Seidel迭代矩陣；h為外推參數(shù).顯然，EGS迭代法是GS迭代法的推廣.當(dāng)h＝1時(shí)，其即為GS迭代法.目前，對(duì)外推迭代法收斂性的研究已有許多成果［1－11］.文獻(xiàn)［1］基于原迭代矩陣T的特征值給出了一般外推迭代法收斂的外推參數(shù)范圍.

定理1［1］外推迭代法收斂的充分必要條件是下列條件之一成立：

文獻(xiàn)［2］基于SSOR迭代法討論了H－矩陣的等價(jià)條件；文獻(xiàn)［3］討論了H－矩陣的塊AOR和塊SAOR迭代法的收斂性，基于塊Jacobi迭代法給出了當(dāng)參數(shù)在一定范圍時(shí)其譜半徑的上界估計(jì)式.Bru等［4］基于Jacobi迭代法給出了H－矩陣的如下等價(jià)條件：

定理2［4］設(shè)A＝（aij）∈Cn×n滿足a ii≠0（i＝1，2，…，n），則下列條件等價(jià)：

1）A為H－矩陣；

2）對(duì)任意的P∈Ω（A），ρ（J（P））＜1.

這里：ρ（J（P））為P的Jacobi迭代矩陣的譜半徑；Ω（A）為A的等模矩陣集合.

文獻(xiàn)［5］基于EGS迭代法給出了不可約H－矩陣的等價(jià)條件：

定理3［5］設(shè)A＝（aij）∈Cn×n為不可約方陣，且aii≠0，則下列條件等價(jià)：

1）A為H－矩陣；

這里：ρ（｜J｜）為A的Jacobi迭代陣絕對(duì)值的譜半徑；Ω（A）為A的等模矩陣集合.

本文進(jìn)一步研究EGS迭代法的收斂性，討論EGS迭代法收斂性與H－矩陣的關(guān)系，從而將文獻(xiàn)［4］中基于Jacobi迭代法的H－矩陣等價(jià)條件推廣為基于EGS迭代法的等價(jià)條件，并將文獻(xiàn)［5］中關(guān)于不可約H－矩陣的等價(jià)條件推廣到一般的H－矩陣.

1 EGS迭代法的收斂性

引理1［13］設(shè)方陣E≥0，F(xiàn)≥0，B＝E＋F，若ρ（E）≤1，則下列結(jié)論成立：

1）當(dāng)ρ（B）＜1時(shí)，0≤ρ（（I－E）－1F）≤ρ（B）＜1；

2）當(dāng)ρ（B）＝1時(shí)，ρ（（I－E）－1F）＝ρ（B）＝1；

3）當(dāng)ρ（B）＞1時(shí)，ρ（（I－E）－1F）≥ρ（B）＞1.

由引理1，對(duì)L－矩陣，可建立如下EGS迭代矩陣的譜半徑與Jacobi迭代矩陣譜半徑的關(guān)系.

定理4設(shè)A是L－矩陣，則下列結(jié)論成立：

1）當(dāng)ρ（J）＜1時(shí)，1－h(huán)≤ρ（G h）≤（1－h(huán)）＋hρ（J）＜1；

2）當(dāng)ρ（J）＝1時(shí)，ρ（G h）＝ρ（J）＝1；

3）當(dāng)ρ（J）＞1時(shí)，ρ（G h）≥（1－h(huán)）＋hρ（J）＞1.

這里0＜h≤1.

證明：顯然G＝（D－L）－1U＝（I－D－1L）－1D－1U，J＝D－1（L＋U）＝D－1L＋D－1U.令E＝D－1L，F(xiàn)＝D－1U，則G＝（I－E）－1F，J＝E＋F并且ρ（E）＝0.由A為L－矩陣可知E≥0，F(xiàn)≥0，從而由引理1可知：當(dāng)ρ（J）＜1時(shí)，0≤ρ（G）≤ρ（J）＜1；當(dāng)ρ（J）＝1時(shí)，ρ（G）＝ρ（J）＝1；當(dāng)ρ（J）＞1時(shí)，ρ（G）≥ρ（J）＞1.因?yàn)镚 h＝（1－h(huán)）I＋h G，0＜h≤1，所以ρ（G h）＝（1－h(huán)）＋hρ（G），進(jìn)而由ρ（G）和ρ（J）的關(guān)系可得：當(dāng)ρ（J）＜1時(shí)，1－h(huán)≤ρ（G h）≤（1－h(huán)）＋hρ（J）＜1；當(dāng)ρ（J）＝1時(shí)，ρ（G h）＝ρ（J）＝1；當(dāng)ρ（J）＞1時(shí)，ρ（G h）≥（1－h(huán)）＋hρ（J）＞1.證畢.

由定理4知，當(dāng)0＜h≤1時(shí)，L－矩陣的EGS迭代法是否收斂依賴于Jacobi迭代法是否收斂.

下面討論復(fù)矩陣EGS迭代法的收斂性.

證畢.

定理6表明對(duì)一類特殊的復(fù)矩陣，當(dāng)外推參數(shù)在一定范圍時(shí)，不僅可以確定其EGS迭代法收斂，而且可以明確給出其迭代矩陣的譜半徑.下面討論H－矩陣EGS迭代法的收斂性.

2 H－矩陣與EGS迭代法收斂性的關(guān)系

推論3若A為M－矩陣，則ρ（G（A））≤ρ（J）＜1，其中J為A的Jacobi迭代陣.

由推論3，當(dāng)A為M－矩陣時(shí)，無論其是否不可約，它的GS迭代法和Jacobi迭代法均收斂，且其GS迭代法收斂速度不慢于Jacobi迭代法收斂速度.

由定理8可將文獻(xiàn)［5］中定理1推廣到可約H－矩陣的情形.

定理9設(shè)A為n階復(fù)方陣，且對(duì)任意的i，aii≠0，則下列條件等價(jià)：

1）A為H－矩陣；

2）定理9將文獻(xiàn)［5］中不可約H－矩陣的等價(jià)條件推廣到一般的H－矩陣，包括可約H－矩陣和不可約H－矩陣.

3）文獻(xiàn)［4］給出了H－矩陣基于Jacobi迭代法收斂性的等價(jià)條件（定理2），而本文的定理9則給出了H－矩陣基于EGS迭代法收斂性的等價(jià)條件.

定理10設(shè)A＝（aij）∈Cn×n，且aii≠0，則下列條件等價(jià)：

1）A為H－矩陣；

2）對(duì)任意的P∈Ω（A），ρ（G（P））＜1；

3）〈A〉的GS迭代法收斂，即ρ（G（〈A〉））＜1.

這里G（〈A〉）和G（P）分別為〈A〉和P的Gauss－Seidel迭代陣.

證明：顯然1）可以推出2）和3）.反之，如果3）成立，由文獻(xiàn)［5］中推論1的證明可知，A是H－矩陣，即1）成立，從而2）成立.所以，當(dāng)A為H－矩陣時(shí)，1）～3）等價(jià).證畢.

類似文獻(xiàn)［5］的討論，對(duì)矩陣A定義集合：

3 數(shù)值實(shí)例

綜上，本文研究了外推Gauss－Seidel迭代法的收斂性，討論了H－矩陣與其EGS迭代法收斂性的關(guān)系，得到了EGS迭代法的收斂性結(jié)論，并給出了H－矩陣EGS迭代法的收斂范圍及其譜半徑上界的估計(jì)式，從而將文獻(xiàn)［5］中的不可約H－矩陣的等價(jià)條件推廣到一般的H－矩陣，還給出了一般H－矩陣的幾個(gè)等價(jià)條件，進(jìn)一步發(fā)展和完善了H－矩陣的相關(guān)理論.

［1］ CAO Zhihao.A Convergence Theorem on an Extrapolated Iterative Method and Its Applications［J］.Applied Numerical Mathematics，1998，27（3）：203－209.

［2］ Alefeld G，Varga R S.Zur Konvergenz des Symmetrischen Relaxationsverfahren［J］.Numerische Mathematik，1976，25（3）：291－295.

［3］ XIANG Shuhuang，ZHANG Shenglei.A Convergence Analysis of Block Accelerated Over－Relaxation Iterative Methods for Weak Block H－Matrices to Partitionπ［J］.Linear Algebra and Its Applications，2006，418（1）：20－32.

［4］ Bru R，Corral C，Gimenez I，et al.Classes of General H－Matrices［J］.Linear Algebra and Its Applications，2008，429（10）：2358－2366.

［5］ 薛秋芳，高興寶，劉曉光.H－矩陣基于外推Gauss－Seidel迭代法的幾個(gè)等價(jià)條件［J］.山東大學(xué)學(xué)報(bào)：理學(xué)版，2013，48（4）：65－71.（XUE Qiufang，GAO Xingbao，LIU Xiaoguang.Several Equivalent Conditions for H－Matrix Based on the Extrapolated Gauss－Seidel Iterative Method［J］.Journal of Shandong University：Natural Science，2013，48（4）：65－71.）

［6］ Evans D J，Martins M M.On the Convergence of the Extrapolated AOR Method［J］.International Journal of Computer Mathematics，1992，43（3／4）：161－171.

［7］ WANG Xinmin，Evans D J.Convergence of the Extrapolated AOR and SOR Iterative Methods［J］.International Journal of Computer Mathematics，1994，52（1／2）：65－74.

［8］ Kohno T，Niki H，Sawami H，et al.An Iterative Test for H－Matrix［J］.Journal of Computational and Applied Mathematics，2000，115（1／2）：349－355.

［9］ 干泰彬，黃廷祝.非奇異H－矩陣的實(shí)用充分條件［J］.計(jì)算數(shù)學(xué)，2004，26（1）：109－116.（GAN Taibin，HUANG Tingzhu.Practical Suffcient Conditions for Nonsingular H－Matrices［J］.Mathematica Numerica Sinica，2004，26（1）：109－116.）

［10］ GUO Zhijun，YANG Jianguang.A New Criteria for a Matrix Is Not Generalized Strictly Diagonally Dominant Matrix［J］.Applied Mathematical Sciences，2011，5（6）：273－278.

［11］ 郭麗.非奇異H－矩陣的判定［J］.吉林大學(xué)學(xué)報(bào)：理學(xué)版，2010，48（2）：226－228.（GUO Li.Criteria for Nonsingular H－Matrices［J］.Journal of Jilin University：Science Edition，2010，48（2）：226－228.）

［12］ Berman A，Plemmons R J.Nonnegative Matrices in the Mathematica Sciences［M］.New York：Academic Press，1979.

［13］ WANG Xinmin.Generalized Stein－Rosenberg Theorems for the Regular Splittings and Convergence of Some Generalized Iterative Methods［J］.Linear Algebra and Its Applications，1993，184：207－234.

［14］ Young D M.Iterative Solution of Large Linear Systems［M］.New York：Academic Press，1971.

［15］ 胡家贛.尺度變換和矩陣分解的收斂性［J］.計(jì)算數(shù)學(xué)，1983（1）：72－78.（HU Jiagan.Scaling Transformation and Convergence of Splittings of Matrix［J］.Mathematica Numerica Sinica，1983（1）：72－78.）

［16］ HU Jiagan.Upper Bounds of the Spectral Radii of Some Iterative Matrices［J］.Journal of Computational Mathematics，1990，8（2）：118－127.

Convergence of Extrapolated Gauss－Seidel Iterative Method and Its Relationship with H－Matrix

XUE Qiufang1，2，GAO Xingbao1，LIU Xiaoguang1
（1.CollegeofMathematicsandInformationScience，ShaanxiNormalUniversity，Xi’an710062，China；2.DepartmentofAppliedMathematics，Xi’anUniversityofTechnology，Xi’an710054，China）

The convergence performance of the extrapolated Gauss－Seidel iterative method and its relationship with H－matrix were discussed.The convergence relationship between the extrapolated Gauss－Seidel and the Jacobi iterative methods and also the range of the extrapolated parameter when the method converges were given.The upper bound estimates for the spectral radius of the extrapolated Gauss－Seidel iterative method were obtained by using the optimally scaled matrix and the estimator ofM－1N.Meanwhile，equivalent conditions for general H－matrices based on the extrapolated Gauss－Seidel and the Gauss－Seidel iterative methods were provided.

H－matrix；Gauss－Seidel iterative method；extrapolated Gauss－Seidel iterative method；optimally scaled matrix；spectral radius

O241.6

A

1671－5489（2014）03－0413－08

10.13413／j.cnki.jdxblxb.2014.03.03

2013－09－09.

薛秋芳（1978—），女，漢族，博士研究生，講師，從事數(shù)值計(jì)算的研究，E－mail：qiufangxue＠163.com.通信作者：高興寶（1966—），男，漢族，博士，教授，博士生導(dǎo)師，從事智能計(jì)算的研究，E－mail：xinbaog＠snnu.edu.cn.

國家自然科學(xué)基金（批準(zhǔn)號(hào)：61273311；10902062）.

趙立芹）