M-矩陣線性方程組的一類Jacobi-Like迭代法

關(guān)晉瑞，宋儒瑛

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

0 引言

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

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

Ax=b，

(1)

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

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

1 預(yù)備知識(shí)

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

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

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

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

Α=Μ-Ν，

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

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

(2)

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

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

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

2 一類Jacobi-like迭代法

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

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

A=I-L-U,

其中

可以得到計(jì)算方程組(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迭代法對(duì)于方程組(1)是收斂的.

下面我們考慮對(duì)Jacobi迭代法進(jìn)行加速.利用預(yù)處理的技巧，選取預(yù)處理子

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

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的特殊結(jié)構(gòu)，(6)的迭代矩陣B-SA與Jacobi迭代法(3)的迭代矩陣B僅在第一行元素不同.容易驗(yàn)證，由矩陣B構(gòu)造矩陣B-SA的運(yùn)算量大約為2n2，因此迭代矩陣B-SA是容易構(gòu)造的.我們稱迭代法(6)為Jacobi-like迭代法.

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

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

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

而對(duì)于k=2,…,n有

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

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

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

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

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

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

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

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

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

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

3 數(shù)值例子

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

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

直接計(jì)算可知

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

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

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

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

表1 例2的實(shí)驗(yàn)結(jié)果

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

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

4 結(jié)論

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