新的L-矩陣線性方程組的預(yù)條件AOR迭代法

李 園，韓海山

(內(nèi)蒙古民族大學(xué) 數(shù)學(xué)學(xué)院，內(nèi)蒙古 通遼 028043)

本文考慮如下線性方程組：

Ax=b，

(1)

其中:A∈Rn×n為非奇異矩陣，b∈Rn為已知向量，x∈Rn為未知量.預(yù)條件方法通常是找到合適的預(yù)條件算子P，將Ax=b等價地轉(zhuǎn)化為如下預(yù)條件線性方程組:PAx=Pb，其中P∈Rn為非奇異預(yù)條件矩陣.

文獻(xiàn)[1]中給出了預(yù)條件矩陣為Pα=I+Sα的預(yù)條件AOR迭代法，其中:

α是參數(shù).

文獻(xiàn)[2]中改進(jìn)了上述迭代法，給出了預(yù)條件矩陣為Pαβ=I+Sαβ的預(yù)條件AOR迭代法，該預(yù)條件也是文獻(xiàn)[3]中預(yù)條件的推廣，其中:

(2)

α，β是參數(shù)，當(dāng)β=0時，Sαβ=Sα.

本文建立了新的預(yù)條件AOR迭代法與文獻(xiàn)[1]和文獻(xiàn)[2]以及經(jīng)典的AOR迭代法的比較定理.通過比較定理，得出本文提出的預(yù)條件方法比文獻(xiàn)[1]和文獻(xiàn)[2]以及經(jīng)典的AOR迭代法更有效.

為方便起見，令A(yù)=I-L-U，其中I是單位矩陣，-L和-U分別是矩陣A的嚴(yán)格下三角和嚴(yán)格上三角矩陣，則線性方程組(1)相應(yīng)的預(yù)條件AOR方法的迭代矩陣為：

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

(3)

其中：ω和γ是參數(shù)，ω≠0.

記本文討論的預(yù)條件線性系統(tǒng)為:

(4)

若記SαβU=DS+ES,RL=DR+FR，其中DS和ES分別為SαβU的對角和嚴(yán)格下三角矩陣，DR和FR分別為RL的對角和嚴(yán)格下三角矩陣，則有:

I-L+Sαβ-(U-R+RU)-DS-ES-DR-FR=

(I-DS-DR)-(L+ES+FR-Sαβ)-(U-R+RU)=

1 預(yù)備知識

為方便起見，本文給出如下記號.設(shè)A=(aij)∈Rn×n為n×n實矩陣.diag(A)為矩陣A的對角元素aii(i=1,2,…,n)構(gòu)成的n×n對角矩陣.對于任意矩陣A=(aij)，B=(bij)∈Rn×n，稱A≥B，如果對所有i,j=1,2,…,n，成立aij≥bij.若矩陣A的每一個元素aij≥0，i,j=1,2,…,n，則稱矩陣矩陣A是非負(fù)矩陣，記作A≥0.稱A-B≥0當(dāng)且僅當(dāng)A≥B.對于n維向量也有類似的定義，ρ(·)表示矩陣的譜半徑.

定義1[3]矩陣A=(aij)∈Rn×n，

1)若aij≤0，i≠j，i,j=1,2,…,n，則稱矩陣A為Z-矩陣；

2)若A∈Z且aii≥0，i=1,2,…,n，則稱A為L-矩陣；

3)若A∈Z非奇異且A-1≥0，則稱A為M-矩陣.

定義2[4]設(shè)矩陣M∈Rn×n非奇異，矩陣分裂A=M-N稱為：

1)收斂的，如果ρ(M-1N)<1；

2)正則分裂，如果M-1≥0且N≥0；

3)弱正則分裂，如果M-1≥0且M-1N≥0；

4)M-分裂，如果M是M-矩陣且N≥0.

定義3[5]矩陣A=(aij)∈Rn×n稱為可約的，如果存在n×n階置換矩陣P，使得:

其中:A11是r×r階矩陣，A22是(n-r)×(n-r)階矩陣，1rn.如果矩陣A不是可約的，則稱A不可約.

引理1[5](Perron-Frobenius) 若矩陣A=(aij)∈Rn×n為非負(fù)不可約矩陣，則:

1)ρ(A)為矩陣A的一個正特征值；

2)對于ρ(A)，相應(yīng)地存在一個正的特征向量x>0；

3)ρ(A)是矩陣A的一個單特征值；

4)ρ(A)隨矩陣A的任一元素增加而增加.

引理2[6]如果矩陣A是一個L-矩陣，則A是M-矩陣當(dāng)且僅當(dāng)存在一個正的向量x>0，使得Ax>0.

引理3[7]設(shè)A=(aij)∈Rn×n為非負(fù)矩陣，則：

1)若存在x≥0，x≠0滿足Ax≥αx，則ρ(A)≥α，進(jìn)一步地，若Ax>αx，則ρ(A)>α；

2)若存在x≥0，x≠0滿足Axβx，則ρ(A)≤β，進(jìn)一步地，若Ax<βx，則ρ(A)<β；

3)若A不可約并且有0≠αx≤Ax≤βx，αx≠Ax和Ax≠βx對某一非負(fù)向量x成立，則α<ρ(A)<β且x是一個正向量.

引理4[8]設(shè)A=M-N是M-分裂，則ρ(M-1N)<1當(dāng)且僅當(dāng)A是非奇異M-矩陣.

2 主要結(jié)論

本文的證明需要用到下面的定理：

因為A是M-矩陣，aij≤0，i≠j，且aii=1，所以當(dāng)i=1,2,…,n-1；j=1,2,…,n時，aij-σiai,i+1ai+1,j≤0.

；j=2,…,n-1，

根據(jù)定理1，可以建立下面的比較定理：

矩陣A的元素滿足00(i=1,2,…,n-1)，則有：

(ii)設(shè)A=I-L-U是不可約矩陣，因為：

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

其中：T=(I-γL)-1γL[ω(1-γ)L+ωU]≥0，可知Lγω是不可約矩陣，由引理1，存在一個向量x>0，使得Lγωx=λx，其中λ=ρ(Lγω)，則有：[(1-ω)I+(ω-γ)L+ωU]x=λ(I-γL)x，

上式等價于： [(1-ω-λ)I+(ω-γ-λγ)L+ωU]x=0

和： (λ-1)(I-γL)x=ω(L+U-I)x，

于是：

(ω-γ+λγ)(L+ES+FR-Sαβ)+ω(U-R+RU)]x=

ωU-(1-ω-λ)(DS+DR)+(ω-γ+λγ)(ES+FR-Sαβ)+ω(RU-R)]x=

ω(DS+DR+ES+FR-Sαβ+RU-R)]x=

ω(R+Sαβ)(L+U-I)]x=

(λ-1)(R+Sαβ)(I-γL)]x=

FR-Sαβ-RL)+(λ-1)(R+Sαβ)]x=

DR-Sαβ)+(λ-1)(R+Sαβ)]x=

(λ-1)(R+Sαβ)]x=

γ(λ-1)(ES-Sαβ)+(λ-1)(R+Sαβ)]x=

由上述定理可得如下推論：

當(dāng)ω=γ時，AOR迭代法即為超松弛(SOR)迭代法，相應(yīng)地有如下結(jié)論：

當(dāng)ω=1，γ=0時，AOR迭代法即為雅可比(Jacobi)迭代法，相應(yīng)地有如下結(jié)論：

3 數(shù)值舉例

運(yùn)用文獻(xiàn)[2]中的例子，將本文的新算法與已知算法進(jìn)行比較，來說明新算法更為有效.文獻(xiàn)[2]中線性方程組(1)的系數(shù)矩陣為：

表1 幾種預(yù)條件AOR迭代法迭代矩陣譜半徑的比較

表2 幾種預(yù)條件SOR迭代法迭代矩陣譜半徑的比較

表3 幾種預(yù)條件Jacobi迭代法迭代矩陣譜半徑的比較

由表1～3，當(dāng)ω和γ取不同值時，可以看出本文所提出的預(yù)條件AOR迭代法、預(yù)條件SOR迭代法和Jacobi迭代法的收斂速度更快，這也正好驗證了本文的結(jié)論.

[1] Li Y T，Li C X，Wu S L.Improvements of preconditioned AOR iterative methods forL-matrices[J].J Comput Appl Math，2007，206：656-665.

[2] Wang H J，Li Y T.A New preconditioned AOR iterative methods forL-matrices[J]. J Comput Appl Math，2009，229：47-53.

[3] Li Y T，Wang H J，Zhang C Y. New preconditioned AOR iterative methods for Linear System[J]. SEAMS Bull Math，2007，31：295-306.

[4] Young D M. Iterative Solution of Large Linear Systems[M].London：Academic Press，NY，1971.

[5] Varga R S. Matrix Iterative Analysis[M].NY：Prentice-Hall，Englewood Cliffs，1962.

[6] 陳景良，陳向暉.特殊矩陣[M].北京：清華大學(xué)出版社，2001.

[7] Gunawardena A D，Jain S K，Snyder L.Modified Iterative Method for Consintent Linear System[J].Linear Algebra Appl，1991，154/156：123-143.

[8] Andreas F，Daniel B S.H-splitting and two-stage iterative methods[J].Numer Math，1992，63：345-356.