改進(jìn)的L-矩陣線性系統(tǒng)的預(yù)條件迭代法

程 軍，李正彪，朱 彪

(曲靖師范學(xué)院 a.學(xué)前與初等教育學(xué)院,b.數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,中國(guó) 曲靖 655011)

求解線性方程組

Ax=b，

(1)

其中A∈Rn×n是非奇矩陣，且b∈Rn×1,x∈Rn×1。若A=M-N，且M是非奇異矩陣。式(1)的基本迭代解法可以表示為

Mxk+1=Nxk+b,k=0,1,…。

當(dāng)aii≠0,i=1,2,…,n時(shí)，假設(shè)

A=I-L-U，

(2)

其中I是單位矩陣，U是嚴(yán)格上三角矩陣，L是嚴(yán)格下三角矩陣,通過對(duì)矩陣A進(jìn)行如上形式的分裂[1]，可得相應(yīng)的SOR迭代法：

x(i+1)=(I-ωL)-1[(1-ω)I+ωU]x(i)+(I-ωL)-1ωb，i=1,2,…。

其迭代矩陣為

Lω=(I-ωL)-1[(1-ω)I+ωU]，

(3)

其中參數(shù)ω(ω≠0)稱為松弛因子。顯然，當(dāng)ω=1時(shí)，SOR迭代法就轉(zhuǎn)化為Gauss-Seidel迭代法。當(dāng)?shù)仃囎V半徑小于1時(shí)，其迭代法是收斂的，且譜半徑越小，其收斂速度越快。為了加快其迭代法的收斂速度，通常用預(yù)條件迭代法來求解方程組(1)，即

PAx=Pb，

其中P為預(yù)條件子，且P為非奇異矩陣。類似地，如果假設(shè)

PA=D*-L*-U*，

就可以得到相應(yīng)的預(yù)條件SOR迭代法，其迭代矩陣為

擬消去A的次對(duì)角線上的元素，進(jìn)而提高了其相應(yīng)的迭代法的收斂速度，其中A為L(zhǎng)-矩陣且需滿足條件0

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

為方便起見，首先給出相關(guān)字義和引理。設(shè)C=(cij)∈Rn×n是n階實(shí)矩陣，diag(C)是對(duì)角矩陣，并且其對(duì)角矩陣的對(duì)角元素為cii，設(shè)A=(aij)和B=(bij)是n階實(shí)矩陣。如果aij≥bij(i,j=1,2,…,n)，記A≥B。如果A≥0(aij≥0)(i,j=1,2,…,n)稱矩陣A是非負(fù)矩陣，如果A≥B，則A-B≥0。ρ(·)表示矩陣的譜半徑。

定義1 矩陣A是一個(gè)L-矩陣，如果aii≥0i=1,2,…,n，并且aij≤0，對(duì)所有的i,j=1,2,…,n且i≠j。

引理1[9]若A≥0是不可約的n×n矩陣，則

(1)A有一個(gè)正的實(shí)特征值等于它的譜半徑;

(2)ρ(A)對(duì)應(yīng)的特征向量x>0;

(3)ρ(A)是A的單特征值。

引理2[10]若A是非負(fù)矩陣，則

(1)如果αx≤Ax對(duì)某一個(gè)非負(fù)向量x且x=0成立,那么α≤ρ(A);

(2)如果Ax≤βx對(duì)某一個(gè)正向量x成立，那么ρ(A)≤β，進(jìn)一步，如果A是不可約并且若有0≠αx≤Ax≤βx，αx≠Ax和Ax≠βx對(duì)某一非負(fù)向量x成立，那么α<ρ(A)<β且x是一正向量。

引理3[9]設(shè)A=M1-N1=M2-N2為A的兩個(gè)正則分裂且A-1≥0。如果N2≥N1≥0,那么

0≤ρ(M1-N1)≤ρ(M2-N2)<1。

進(jìn)一步,如果A-1>0且N2≥N1≥0,那么除等號(hào)外

0<ρ(M1-1-N1)<ρ(M2-1N2)<1。

陣且存在一個(gè)非零集合α?N={1,2，…,n-1}使得

2 預(yù)條件SOR迭代法

考慮預(yù)條件線性方程組

(4)

對(duì)式(4)運(yùn)用SOR迭代法，得到其相應(yīng)的迭代矩陣為

(5)

為了得到證明一下主要結(jié)果，需要用到以下引理：

證：由于矩陣A是L-矩陣,可知L≥0，而且矩陣L是一個(gè)嚴(yán)格下三角矩陣。則(I-ωL)-1=I+ωL+ω2L2+…+ωn-1Ln-1≥0由式(3),可得

Lω=(I-ωL)-1[(1-ω)I+ωU]=[I+ωL+ω2L2+…+ωn-1Ln-1][(1-ω)I+ωU]=

(1-ω)I+ωU+ω(1-ω)L+ω2LU+(ω2L2+…+ωn-1Ln-1)[(1-ω)I+ωU]=

(1-ω)I+ωU+ω(1-ω)L+T，

其中

T=ω2LU+(ω2L2+…+ωn-1Ln-1)[(1-ω)I+ωU]≥0，

即得Lω是非負(fù)的，又由文獻(xiàn)[6]中的引理1，可知Lω是不可約的。由式(5)得

其中

定理1 設(shè)式(3)和(5)分別由SOR迭代法作用于式(1)和(4)得到的迭代矩陣。0<ω<1，如果A是一個(gè)L-矩陣且存在一個(gè)非零集合α?N={1,2,…,n-1}使得

則

Lωx=λx，

其中λ=ρ(Lω)，即得：

[(1-ω)I+ωU]x=λ(I-ωL)x。

對(duì)于x>0，則

設(shè)

其中μi=-(ω-1)ai,i+1ai+1,ixi-ai,i+1xi+1≥0，i=1,2,…,n-1。

注：顯然，如果α=N，預(yù)條件因子即轉(zhuǎn)化為[11]中的預(yù)條件因子。

易知，當(dāng)ω=1時(shí)，SOR迭代法就轉(zhuǎn)化為Gauss-Seidel迭代法。進(jìn)而，可得到如下推論：

那么

證：設(shè)

其中

注2通過上面的討論，易知，ω=1是SOR迭代法的最優(yōu)數(shù)值。即，在滿足0<ω≤1條件下，Gauss-Seidel迭代法的收斂速度比SOR迭代法的收斂速度快。

3 數(shù)值算例

這里給出相應(yīng)的數(shù)值算例，來說明前面迭代法的結(jié)果。

例：設(shè)式(1)的系數(shù)矩陣A為

類似地，PG-S表示用本文中提出的預(yù)條件Gauss-Seidel迭代法，PEG-S表示用預(yù)條件Gauss-Seidel迭代法。表1和表2給出了當(dāng)取不同參數(shù)ω和n的值時(shí)，迭代矩陣譜半徑的大小、迭代次數(shù)、CPU時(shí)間和誤差。表中的數(shù)值是通過Matlab 7.0計(jì)算獲得。

表1 定理1的數(shù)值實(shí)驗(yàn)Tab. 1 Numerical experiment of theorem 1

表2 推論1的數(shù)值實(shí)驗(yàn)Tab. 2 Numerical experiment of inference 1

4 結(jié)論

通過表1和表2中的數(shù)值實(shí)驗(yàn)表明，在滿足定理1以及推論1條件的情況下，其結(jié)論同樣是成立的。且我們提出的預(yù)條件子比很多文獻(xiàn)中提出的預(yù)條件子較優(yōu)。同時(shí)，該數(shù)值算例的結(jié)果也說明了在滿足0<ω≤1下，預(yù)條件Gauss-Seidel迭代法的收斂速度比預(yù)條件SOR迭代法的收斂速度快一些。