薛秋芳，高興寶，劉曉光

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

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

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

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

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

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

0 引 言

對大型稀疏線性方程組

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

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

其中G＝（D－L）－1U為Gauss－Seidel迭代矩陣.相應的外推Gauss－Seidel迭代法（簡稱EGS方法）迭代格式為

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

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

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

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

1）A為H－矩陣；

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

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

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

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

1）A為H－矩陣；

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

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

1 EGS迭代法的收斂性

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

1）當ρ（B）＜1時，0≤ρ（（I－E）－1F）≤ρ（B）＜1；

2）當ρ（B）＝1時，ρ（（I－E）－1F）＝ρ（B）＝1；

3）當ρ（B）＞1時，ρ（（I－E）－1F）≥ρ（B）＞1.

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

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

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

2）當ρ（J）＝1時，ρ（G h）＝ρ（J）＝1；

3）當ρ（J）＞1時，ρ（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可知：當ρ（J）＜1時，0≤ρ（G）≤ρ（J）＜1；當ρ（J）＝1時，ρ（G）＝ρ（J）＝1；當ρ（J）＞1時，ρ（G）≥ρ（J）＞1.因為G h＝（1－h(huán)）I＋h G，0＜h≤1，所以ρ（G h）＝（1－h(huán)）＋hρ（G），進而由ρ（G）和ρ（J）的關(guān)系可得：當ρ（J）＜1時，1－h(huán)≤ρ（G h）≤（1－h(huán)）＋hρ（J）＜1；當ρ（J）＝1時，ρ（G h）＝ρ（J）＝1；當ρ（J）＞1時，ρ（G h）≥（1－h(huán)）＋hρ（J）＞1.證畢.

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

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

證畢.

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

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

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

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

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

定理9設A為n階復方陣，且對任意的i，aii≠0，則下列條件等價：

1）A為H－矩陣；

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

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

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

1）A為H－矩陣；

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

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

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

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

類似文獻［5］的討論，對矩陣A定義集合：

3 數(shù)值實例

綜上，本文研究了外推Gauss－Seidel迭代法的收斂性，討論了H－矩陣與其EGS迭代法收斂性的關(guān)系，得到了EGS迭代法的收斂性結(jié)論，并給出了H－矩陣EGS迭代法的收斂范圍及其譜半徑上界的估計式，從而將文獻［5］中的不可約H－矩陣的等價條件推廣到一般的H－矩陣，還給出了一般H－矩陣的幾個等價條件，進一步發(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迭代法的幾個等價條件［J］.山東大學學報：理學版，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－矩陣的實用充分條件［J］.計算數(shù)學，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］.吉林大學學報：理學版，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］.計算數(shù)學，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ù)值計算的研究，E－mail：qiufangxue＠163.com.通信作者：高興寶（1966—），男，漢族，博士，教授，博士生導師，從事智能計算的研究，E－mail：xinbaog＠snnu.edu.cn.

國家自然科學基金（批準號：61273311；10902062）.

趙立芹）