一類計算M-矩陣逆的二次收斂算法

關(guān)晉瑞，任孚鮫

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

1 引言

M-矩陣的概念是Ostrowski在1937年提出的.作為一類重要的特殊矩陣，M-矩陣的應(yīng)用十分廣泛，它在科學(xué)計算和工程應(yīng)用的許多領(lǐng)域，如矩陣理論、微分方程數(shù)值解、線性方程組迭代求解、線性互補問題、Markov鏈等問題中都有著重要的應(yīng)用[1-4].此外，M-矩陣在其他學(xué)科如物理學(xué)、生物學(xué)，以及經(jīng)濟學(xué)中也有著廣泛的應(yīng)用.

由于M-矩陣廣泛的應(yīng)用和優(yōu)美的性質(zhì)，國內(nèi)外很多人對其進行了深入的研究，得到了眾多的成果.自M-矩陣的概念提出之后，其眾多的性質(zhì)和等價條件不斷被發(fā)現(xiàn)，在專著[1]中總結(jié)的非奇異M-矩陣的等價條件已有50多個，之后還在繼續(xù)擴充[5-7].特別地，對于M-矩陣的判別也是人們一直探討的一個問題[8-9].

本文研究M-矩陣的逆矩陣的計算問題.一般求逆矩陣的算法是基于列主元高斯消去法得到的，但是用來計算M-矩陣的逆時，存在一定的缺陷：一方面，一般的算法未能充分利用M-矩陣豐富的性質(zhì)和結(jié)構(gòu)；另一方面，當(dāng)矩陣接近奇異時，所求出的逆矩陣可能誤差比較大.為了有效地計算M-矩陣的逆，本文提出了一類迭代法，該方法充分利用了M-矩陣的特點，在迭代中保持非負性，且具有二次收斂速度.

本文內(nèi)容安排如下：第2節(jié)給出本文所需的一些預(yù)備知識.第3節(jié)，提出一類計算M-矩陣逆的迭代算法，并分析其收斂性.第4節(jié)，給出幾個數(shù)值例子以驗證新方法的可行性和有效性.最后是簡要的總結(jié).

2 預(yù)備知識

本節(jié)介紹文中的符號記法、M-矩陣的定義和若干基本性質(zhì)，以及后面將要用到的一些預(yù)備知識.

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

設(shè)A=(aij)∈Rn×n，若對于任意的i≠j都有aij≤0成立，則稱A為Z-矩陣.對于Z-矩陣A，若存在非負矩陣B使得A=sI-B且s≥ρ(B)成立，則稱該Z-矩陣為M-矩陣，其中ρ(B)表示矩陣B的譜半徑.特別地，若s>ρ(B)，則稱A為非奇異的M-矩陣，若s=ρ(B)則稱A為奇異的M-矩陣.

引理2.1[1]設(shè)A∈Rn×n為Z-矩陣，則下面幾個結(jié)論是等價的：

1)A是非奇異的M-矩陣；

2)A-1≥0；

3)存在正向量v>0，使得Av>0；

4)A的全部特征值都具有正實部.

引理2.2[1]設(shè)A，B為非奇異的M-矩陣，且A≤B，則有A-1≥B-1.

3 一類二次收斂算法

本節(jié)中，利用M-矩陣的特點提出一類迭代法來計算它的逆，并給出新方法的收斂性分析.

設(shè)A∈Rn×n為非奇異的M-矩陣，則A可表示為A=sI-B，其中B為非負矩陣且s>ρ(B).矩陣A的逆A-1滿足下面的矩陣方程

AX=I.

將A=sI-B代入上式，整理可得如下不動點格式

從而可得迭代法

(3.1)

該迭代法在每步計算中，主要運算為一個矩陣乘積，運算量大約為2n3.

以下分析迭代法(3.1)的收斂性結(jié)果.

引理3.1 設(shè)A∈Rn×n為非奇異的M-矩陣，則對任意的k≥0，由迭代法(3.1)生成的序列{Xk}滿足下式

0≤Xk≤Xk+1≤A-1.

(3.2)

證明：利用數(shù)學(xué)歸納法來證明(3.2).

根據(jù)引理2.2可得X1≤A-1.于是當(dāng)k=0時結(jié)論(3.2)成立.

假設(shè)當(dāng)k=l時結(jié)論成立，則由

可知

因此結(jié)論對于k=l+1也成立.

根據(jù)數(shù)學(xué)歸納法，結(jié)論(3.2)對任意的k≥0都成立.證畢.

從引理3.1證明中可知

B1=s1I-s2I+B2，

從而ρ(B1)=s1-s2+ρ(B2).于是

為了提高迭代法(3.1)收斂率，利用矩陣技巧，我們將其迭代格式改寫為如下形式

(3.3)

定理3.3 設(shè)A∈Rn×n為非奇異的M-矩陣，則由迭代法(3.3)生成的序列{Xk}具有二次收斂率.

于是

4 數(shù)值算例

例4.1 考慮n階非奇異M-矩陣

對于階數(shù)的不同取值，實驗結(jié)果見表4.1.

表4.1 例4.1的實驗結(jié)果

例4.2 在Matlab中按照如下命令隨機生成n階的非奇異M-矩陣

a=rand(n，n)；A=diag(a*ones(n，1))-a+eye(n)；

對于階數(shù)n的不同取值，實驗結(jié)果見表4.2.

表4.2 例4.2的實驗結(jié)果

例4.3 考慮非奇異M-矩陣

其中ε>0.當(dāng)ε→0時，矩陣A接近奇異.對于參數(shù)ε的不同取值，實驗結(jié)果見表4.3.

表4.3 例4.3的實驗結(jié)果

由上述三個例子可見，算法(3.3)是可行的，而且也是較為有效的.

結(jié)論

本文研究了M-矩陣逆的迭代算法，并提出了一類二次收斂的算法以計算非奇異M-矩陣的逆矩陣，并證明了相應(yīng)的收斂性分析.數(shù)值例子表明，新方法是可行的，而且在一定情況下也是較為有效的.