M-矩陣線性方程組的一類非定常迭代法*

關(guān)晉瑞，溫瑞萍

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

0 引 言

在科學(xué)計(jì)算和工程應(yīng)用中，許多問題最終都?xì)w結(jié)為線性方程組的求解，因此研究線性方程組解的理論以及求解方法具有重要的理論意義和應(yīng)用價(jià)值［1-4］.如何快速有效地求得線性方程組的解是計(jì)算數(shù)學(xué)的一個(gè)基本問題，也是目前仍在繼續(xù)研究的重要課題之一［5-16］.

本文考慮M-矩陣線性方程組的求解

式中A∈ Rn×n是非奇異的M-矩陣，b∈ Rn是給定的向量.這種類型的線性方程組在微分方程數(shù)值解、線性互補(bǔ)問題、Markov鏈以及物理學(xué)、生物學(xué)和經(jīng)濟(jì)學(xué)中都有著廣泛的應(yīng)用［2，4，17］.例如，對(duì)于 Poisson方程第一邊值問題，利用差分法離散化之后即得到一個(gè)系數(shù)矩陣為M-矩陣的線性方程組.在線性互補(bǔ)問題中，很多情況下的系數(shù)矩陣都是M-矩陣.在經(jīng)濟(jì)學(xué)中，投入產(chǎn)出分析對(duì)應(yīng)的矩陣也是M-矩陣［17］.

對(duì)于一般的線性方程組已有很多經(jīng)典的解法，如Gauss消去法、平方根法、Jacobi迭代法、Gauss-Seidel迭代法、SOR、共軛梯度法、Krylov子空間方法［1-4］和 HSS 迭代法［18］等.而對(duì)于一些具有特殊性質(zhì)和結(jié)構(gòu)的方程組，也有很多學(xué)者進(jìn)行了深入研究.本文利用M-矩陣的特點(diǎn)，針對(duì)M-矩陣線性方程組提出了一類迭代法.理論分析和數(shù)值實(shí)驗(yàn)表明，新方法是可行的，而且在一定情況下也是較為有效的.

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

首先簡(jiǎn)要介紹本文的符號(hào)記法及將要用到的一些預(yù)備知識(shí).

Rm×n表示實(shí)數(shù)域上全體m×n的矩陣，Rn表示實(shí)數(shù)域上全體n維列向量，ρ(A)表示矩陣A的譜半徑.n階單位矩陣記為In，在沒有混淆的情況下寫為I.用||·||來表示一個(gè)給定的矩陣范數(shù).

設(shè)A=(aij)∈ Rn×n，若A的每個(gè)元素都是非負(fù)的，則稱A為非負(fù)矩陣，記為A≥ 0.設(shè)A=(aij)∈ Rn×n，若對(duì)于任意的i≠j都有aij≤0成立，則稱A為Z-矩陣.一個(gè)Z-矩陣A若可以表示為A=sI-B，其中B為非負(fù)矩陣且s≥ρ(B)，則稱該Z-矩陣為M-矩陣.特別地，當(dāng)s＞ρ(B)時(shí)，稱A為非奇異的M-矩陣，當(dāng)s=ρ(B)時(shí)，稱A為奇異的M-矩陣.關(guān)于M-矩陣的詳細(xì)內(nèi)容可參考文獻(xiàn)［17］.

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

式中M是可逆的，代入式（1）得到原方程組的等價(jià)形式Mx=Nx+b，進(jìn)而可以得到迭代法

式中M-1N稱為分裂迭代法（2）的迭代矩陣.

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

引理1.1［19］分裂迭代法（2）收斂當(dāng)且僅當(dāng)?shù)仃嘙-1N的譜半徑ρ(M-1N)＜1.

引理 1.2［20］設(shè) ||·||是任意一個(gè)矩陣范數(shù)，則對(duì)任意的A∈Rn×n有

2 一類非定常迭代法

本節(jié)提出一類非定常迭代法，以求解M-矩陣線性方程組，并給出該方法的收斂性分析.

設(shè)A=(aij)∈ Rn×n為非奇異的 M-矩陣，則A存在自然的分裂

式中s＞0，而B≥0是非負(fù)矩陣.事實(shí)上，不難驗(yàn)證只要選取，令B=sI-A即可.于是基于上述分裂便可以得到如下的一類迭代法

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

由于A是非奇異的M-矩陣，可知s＞ρ(B).于是利用引理1.1，可得到如下的收斂性.

定理2.1設(shè)線性方程組（1）的系數(shù)矩陣是非奇異的M-矩陣，則對(duì)于任意給定的初始向量，迭代法（4）都是收斂的.

在迭代法（4）中存在一個(gè)參數(shù)s.下面討論參數(shù)s對(duì)迭代的影響，并給出最優(yōu)參數(shù)的值.

定理2.2迭代法（4）中的最優(yōu)參數(shù)為

證明設(shè)A=s1I-B1=s2I-B2為矩陣A的2個(gè)分裂，其中s1，都是正數(shù)，且s1＞s2，而B1，B2是非負(fù)矩陣.相應(yīng)的迭代矩陣譜半徑分別為

由B1=(s1-s2)I+B2，且ρ(B1)=s1-s2+ρ(B2)，可得

因此，參數(shù)s越小，收斂越快.從而當(dāng)時(shí)，迭代法（4）收斂最快.證畢.

定理2.3設(shè)線性方程組（1）的系數(shù)矩陣為非奇異的M-矩陣，則迭代法（5）是收斂的，且具有二次收斂率.

證明由迭代法（4）可得方程組的精確解為

式中0為（4）的初始向量.直接驗(yàn)證可知非定常迭代法（5）得到的序列{xk} 滿足

兩邊取范數(shù)，并利用引理1.2，可得

因此，序列{xk}是收斂的且具有二次收斂率.證畢.

盡管非定常迭代（5）相對(duì)于（4）運(yùn)算量較大，但是上面的定理表明迭代收斂很快.因此是可行的.

3 數(shù)值實(shí)驗(yàn)

例 3.1［19］考慮M-矩陣線性方程組（1），其中

而n=m2，b=(1，1，…，1)T∈ Rn.當(dāng)m取不同值，2個(gè)迭代法得出的結(jié)果如表1所示.與迭代法（4）相比，迭代法（5）不僅迭代次數(shù)和運(yùn)行時(shí)間都明顯要少，而且求得解的精度也高.特別地，當(dāng)系數(shù)矩陣的階數(shù)增加時(shí)，迭代法（4）的迭代次數(shù)急劇增加，但迭代法（5）的迭代次數(shù)增加不明顯.

表1 m取不同值時(shí)不同迭代公式對(duì)應(yīng)的結(jié)果

例3.2考慮M-矩陣線性方程組（1），其中A由下列命令生成

a=rand（n，n）；A=diag（a*ones（n，1））-a+eye（n）；而b=(1，1，…，1)T∈ Rn.對(duì)于階數(shù)n的不同取值，表2中給出了實(shí)驗(yàn)結(jié)果.從表2中可見，隨著系數(shù)矩陣階數(shù)的增加，迭代法（4）的迭代次數(shù)與運(yùn)行時(shí)間都急劇增加，但迭代法（5）的迭代次數(shù)和運(yùn)行時(shí)間并沒有明顯的增加.

表2 n取不同值時(shí)不同迭代公式對(duì)應(yīng)的結(jié)果

例3.3考慮M-矩陣線性方程組（1），其中

ε＞0是正數(shù).當(dāng)ε→ 0時(shí)，矩陣A接近奇異.對(duì)于參數(shù)ε的不同取值，實(shí)驗(yàn)結(jié)果見表3.當(dāng)參數(shù)越來越小時(shí)，迭代法（4）的迭代次數(shù)急劇增加，但迭代法（5）的迭代次數(shù)并沒有明顯的增加.

表3 參數(shù)取不同值時(shí)不同迭代公式對(duì)應(yīng)的結(jié)果

由以上3個(gè)數(shù)值例子可見，迭代法（4）收斂較慢，特別當(dāng)系數(shù)矩陣接近奇異時(shí)，收斂非常緩慢，而迭代法（5）始終收斂很快，且求得解的精度也比較高，因此迭代法（5）是較為有效的.

4 結(jié)束語(yǔ)

本文提出了一類非定常迭代法以求解M-矩陣線性方程組.理論分析表明該方法具有二次收斂率.數(shù)值實(shí)驗(yàn)表明，該方法是可行的，而且在一定情況下也是較為有效的.但是該方法在每步迭代中運(yùn)算量較大，如何減少運(yùn)算量并保持較快的收斂速度，還有待進(jìn)一步的研究.另外，由于H-矩陣和M-矩陣具有很多相近的性質(zhì)，本文的方法還可以推廣到H-矩陣線性方程組.