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

程 軍，李正彪，朱 彪

(曲靖師范學(xué)院 a.學(xué)前與初等教育學(xué)院,b.數(shù)學(xué)與統(tǒng)計學(xué)院,中國 曲靖 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,…。

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

A=I-L-U，

(2)

其中I是單位矩陣，U是嚴格上三角矩陣，L是嚴格下三角矩陣,通過對矩陣A進行如上形式的分裂[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)稱為松弛因子。顯然，當ω=1時，SOR迭代法就轉(zhuǎn)化為Gauss-Seidel迭代法。當?shù)仃囎V半徑小于1時，其迭代法是收斂的，且譜半徑越小，其收斂速度越快。為了加快其迭代法的收斂速度，通常用預(yù)條件迭代法來求解方程組(1)，即

PAx=Pb，

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

PA=D*-L*-U*，

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

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

1 預(yù)備知識

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

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

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

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

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

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

引理2[10]若A是非負矩陣，則

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

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

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

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

進一步,如果A-1>0且N2≥N1≥0,那么除等號外

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

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

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

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

(4)

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

(5)

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

證：由于矩陣A是L-矩陣,可知L≥0，而且矩陣L是一個嚴格下三角矩陣。則(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ω是非負的，又由文獻[6]中的引理1，可知Lω是不可約的。由式(5)得

其中

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

則

Lωx=λx，

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

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

對于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ù)條件因子。

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

那么

證：設(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給出了當取不同參數(shù)ω和n的值時，迭代矩陣譜半徑的大小、迭代次數(shù)、CPU時間和誤差。表中的數(shù)值是通過Matlab 7.0計算獲得。

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

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

4 結(jié)論

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