關晉瑞，宋儒瑛

(太原師范學院 數(shù)學系，山西 晉中 030619)

0 引言

在科學計算和工程應用的許多領域，例如大地測量、結構分析、網(wǎng)絡分析、數(shù)據(jù)分析、最優(yōu)化、非線性方程組以及微分方程數(shù)值解等，許多問題的求解最終都歸結為線性方程組，因此研究線性方程組的求解具有重要的理論意義和應用價值[1-3].

本文我們考慮M-矩陣線性方程組

Ax=b，

(1)

其中A∈Rn×n是非奇異的M-矩陣，b∈Rn是給定的向量.這種類型的線性方程組在微分方程數(shù)值解、線性互補問題、Markov鏈以及物理學，生物學和經(jīng)濟學中都有著廣泛的應用[4-6].

對于一般線性方程組的求解，已有很多經(jīng)典的方法，如Gauss消去法、平方根法、Jacobi迭代法、Gauss-Seidel迭代法、SOR、共軛梯度法和Krylov子空間方法等等[3,5].而對于一些特殊類型的線性方程組，國內(nèi)外許多學者也進行了深入的研究，并發(fā)展出了眾多有效的算法[7-15].本文我們利用M-矩陣的特點，針對M-矩陣線性方程組提出了一類迭代法.理論分析和數(shù)值實驗表明，新方法是可行的，而且在一定情況下也是較為有效的.

1 預備知識

我們用Rm×n表示實數(shù)域上全體m×n的矩陣，用Rn表示實數(shù)域上全體n維列向量，用ρ(A)表示矩陣A的譜半徑.n階單位矩陣記為I.

設A=(aij)∈Rn×n，若A的每個元素都是非負的，則稱A為非負矩陣，記為A≥0.若對于任意的i≠j都有aij≤0成立，則稱A為Z-矩陣.對于Z-矩陣A，若存在非負矩陣B使得A=sI-B且s≥ρ(B)成立，則稱該Z-矩陣為M-矩陣.特別地，若s>ρ(B)則稱A為非奇異的M-矩陣，若s=ρ(B)則稱A為奇異的M-矩陣.

引理1[16]設A∈Rn×n為Z-矩陣，則A是非奇異的M-矩陣當且僅當存在正向量v>0使得Αv>0.

分裂迭代法是求解線性方程組(1)的最簡單的一類迭代法.它的基本思路是，給定系數(shù)矩陣A的一個分裂

Α=Μ-Ν，

其中M是可逆的，代入方程組(1)得到迭代法

xk+1=M-1Nxk+M-1b，k=0,1,2,…

(2)

其中M-1N稱為分裂迭代法(2)的迭代矩陣.

如果對于任意給定的初始向量x0∈Rn，若由(2)生成的序列{xk}都收斂于方程組(1)的解x*，則稱迭代法(2)是收斂的.

引理2[5]分裂迭代法(2)收斂當且僅當?shù)仃嘙-1N的譜半徑ρ(M-1N)<1.

2 一類Jacobi-like迭代法

本節(jié)，我們對M-矩陣線性方程組提出一類迭代法，并給出該方法的收斂性分析.

設A=(aij)∈Rn×n為非奇異的M-矩陣，且不妨設A的對角元素都為1，否則在方程組兩端左乘D-1即可，其中D為A的對角元組成的對角矩陣.基于分裂

A=I-L-U,

其中

可以得到計算方程組(1)的Jacobi迭代法

xk+1=(L+U)xk+b，k=0,1,2,…

其中x0∈Rn是任意給定的初始向量.

若記B=L+U，則有A=I-B，B≥0，于是可將Jacobi迭代法改寫為

xk+1=Bxk+b，k=0,1,2,…

(3)

由于A是非奇異的M-矩陣，可知ρ(B)<1.從而根據(jù)引理2，Jacobi迭代法對于方程組(1)是收斂的.

下面我們考慮對Jacobi迭代法進行加速.利用預處理的技巧，選取預處理子

則方程組(1)等價于方程組

PAx=Pb.

(4)

若記P=I+S，其中

(5)

則我們可以得到(4)系數(shù)矩陣如下的分裂

于是代入方程組(4)可得如下的迭代法

xk+1=(B-SA)xk+Pb，k=0,1,2,…

(6)

其中x0∈Rn是任意給定的初始向量.

容易發(fā)現(xiàn)，由于S的特殊結構，(6)的迭代矩陣B-SA與Jacobi迭代法(3)的迭代矩陣B僅在第一行元素不同.容易驗證，由矩陣B構造矩陣B-SA的運算量大約為2n2，因此迭代矩陣B-SA是容易構造的.我們稱迭代法(6)為Jacobi-like迭代法.

下面討論迭代法(6)的收斂性.

引理3設A=(aij)∈Rn×n為對角元素都為1的非奇異M-矩陣，矩陣B和S定義如上，則B-SA是非負矩陣.

β11=a12a21+a13a31+…+a1nan1≥0，

而對于k=2,…,n有

引理4設A=(aij)∈Rn×n為對角元素都為1的非奇異M-矩陣，矩陣P定義如上，則PA也是非奇異的M-矩陣.

證明 由于PA=I-(B-SA)，而B-SA是非負矩陣，于是PA為Z-矩陣.

由于A=(aij)∈Rn×n為非奇異的M-矩陣，根據(jù)引理1，存在正向量v>0使得Av>0.又P=I+S，S是非負矩陣.從而

PAv=(I+S)Av=Av+SAv>0.

利用引理1，可知PA為非奇異的M-矩陣.證畢.

定理1對于M-矩陣線性方程組(1)，迭代法(6)對任意給定的初始向量x0∈Rn都是收斂的.

證明 1)若方程組(1)系數(shù)矩陣A的對角元素都是1，則根據(jù)引理3和4可知

PA=I-(B-SA)，B-SA≥0，

且PA為非奇異的M-矩陣.從而由M-矩陣的定義得ρ(B-SA)<1.再利用引理2可知迭代法(6)是收斂的.

2)否則，考慮方程組(1)的等價形式D-1Ax=D-1b，顯然該方程組的對角元素都是1.于是根據(jù)上述分析，迭代法(6)收斂.證畢.

3 數(shù)值例子

給出兩個數(shù)值例子來檢驗迭代法(6)的數(shù)值效果，并與Jacobi迭代法(3)進行比較.實驗中，所有的程序都用Matlab (R2012a)編寫，并在個人筆記本電腦(2G CPU和8G內(nèi)存)上運行.

例1考慮M-矩陣線性方程組(1)，其中

直接計算可知

其中矩陣B為Jacobi迭代法(3)的迭代矩陣，B-SA為迭代法(6) 的迭代矩陣.由于

ρ(B-SA)=0.822 1<ρ(B)=0.879 2，

迭代法(6)比Jacobi迭代法(3)收斂要快.

例2考慮M-矩陣線性方程組(1)，其中

表1 例2的實驗結果

從表1可見，對于參數(shù)ε的不同值，(6)所需的迭代次數(shù)都比較少.

由以上兩個例子可見，本文所提的方法(6)是可行的，而且與Jacobi迭代法相比，新方法的迭代次數(shù)較少，因此加速效果是較為明顯的.

4 結論

本文中我們提出了一類Jacobi-like迭代法以計算M-矩陣線性方程組的解，并給出了相應的收斂性分析.數(shù)值實驗表明，該方法是可行的，而且在一定情況下比Jacobi迭代法所需的迭代次數(shù)要少.