L-矩陣多參數(shù)預(yù)條件AOR迭代法收斂性分析

羅 芳，康淑瑰，王振芳

（山西大同大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，山西大同，037009）

L-矩陣多參數(shù)預(yù)條件AOR迭代法收斂性分析

羅 芳，康淑瑰，王振芳

（山西大同大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，山西大同，037009）

文章主要研究了L-矩陣多參數(shù)預(yù)條件AOR迭代方法中參數(shù)的選取對(duì)收斂速度的影響，并給出了相應(yīng)的比較定理,最后通過數(shù)值例子來進(jìn)行說明。

預(yù)條件;AOR迭代法;L-矩陣;M-矩陣;收斂

考慮線性方程組

不失一般性，設(shè)A=I-L-U是一個(gè)n×n的非奇異矩陣,D是A的對(duì)角矩陣,-L和-U分別為A的嚴(yán)格下三角和上三角部分，x和b是n維列向量,迭代求解方程組(1)的AOR[1]方法定義為:

它的迭代矩陣表示為：

其中r和w≠0均為實(shí)參數(shù)，分別稱為加速因子與超松弛因子。當(dāng)r=0,w=1時(shí)，AOR方法為Jacobi方法；當(dāng)r=1,w=1時(shí)，AOR方法為Gauss-Seidel方法；當(dāng)w=r時(shí)，AOR方法即為SOR方法。

當(dāng)r≠0時(shí)，AOR方法可以看作是SOR方法的外推，記作ESOR方法。此時(shí)，若記，則有：

1 解線性方程組的AOR方法

因此，若記μ為SOR方法的迭代矩陣Lw,w的特征值，λ為相應(yīng)的Lr,w的特征值，則成立下面關(guān)系式：

定理1[1]若A為L-矩陣，且滿足 0≤r≤w≤1(w≠0)，則解方程組（1）的AOR方法收斂的充分必要條件是解方程組（1）的Jacobi方法收斂。

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

為方便起見，我們首先給出一些將在后面用到的定義、引理和定理。

定義1[2]設(shè)A=[aij]∈Rm×n,如果aij≥0,對(duì)一切i,j成立,則稱A是非負(fù)的,記為A≥0;如果aij＞0對(duì)一切i,j成立,則稱A是正的,記為A＞0。如果A,B∈Rm×n滿足A-B≥0,則記為A≥B；類似地，可以定義A＞B。通過n×1矩陣，也可以定義一個(gè)n維列向量x≥0,x＞0。

此外，我們用ρ(A)表示A的譜半徑。

定義2[2]設(shè)A=[aij]∈Rn×n,若aij≤0,i≠j。則稱A是Z-矩陣；稱矩陣A=(aij)∈Rn×n為L-矩陣，若aii＞0,i=1,2,…,n,且aij≤0，i≠j。對(duì)于任一個(gè)Z-矩陣A,都可表示成A=sI-B,其中s是一個(gè)正數(shù),B≥0。如果一個(gè)Z-矩陣A滿足s≥ρ(B),則稱A是M-矩陣。當(dāng)s＞ρ(B)時(shí),稱之為非奇異的M-矩陣，其中ρ(A)表示A的譜半徑。

引理1[3](Frobenius-Perron定理)若矩陣A≥0為不可約矩陣，則

(1)A存在一個(gè)正的實(shí)的特征值等于它的譜半徑ρ(A)；

(2)相應(yīng)于ρ(A)，存在一個(gè)正的特征向量x＞0，稱為A的Perron向量；

(3)ρ(A)是矩陣A的一個(gè)單特征值;

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

引 理 2[2]若A=[aij]∈Rn×n,A≥0,x=(ξj)∈Rn,x＞0。若α,β≥0使得αx≤Ax≤βx，則α≤ρ(A)≤β;若αx＜Ax,則ρ(A)＞α;若Ax＜βx，則ρ(A)＜β。特別地,若Ax=λx,則λ=ρ(A)。

引理3[2]A=[aij]∈Rn×n是一個(gè)Z-矩陣,則下列命題等價(jià):

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

(2)A非奇異且A-1≥0;

(3)存在x∈Rn滿足x＞0使得Ax＞0。

定義3[3]矩陣A稱為單調(diào)的,如果Ax≥0，則必有x≥0。

定義4[4]如果M是非奇異的,則稱A=M-N為矩陣A的分裂;如果ρ(M-1N)＜1,則稱分裂收斂;如果M是非奇異的M-矩陣且N≥0則稱為M-分裂;如果M-1≥0且N≥0,則稱為正則分裂;如果M-1≥0且M-1N≥0,則稱為弱正則分裂。

引理4[4]設(shè)A=M-N是一個(gè)M-分裂,則ρ(M-1N)＜1，當(dāng)且僅當(dāng)A是非奇異的M-矩陣。

引理5[5]若A,B都是非奇異的M-矩陣,如果A≤B,則A-1≥B-1。

引理6[6]關(guān)于A的一個(gè)正則分裂A=M-N,ρ(M-1N)＜1，當(dāng)且僅當(dāng)A是一個(gè)單調(diào)矩陣。

引理7[7]設(shè)A1=M1-N1,A2=M2-N2分別是單調(diào)矩陣A1,A2的弱正則分裂,使得如果存在一個(gè)正向量x使得0≤A1x≤A2x,且，則關(guān)于x的單調(diào)范數(shù)有

“誰在外面？”病房里的人聽見門口的動(dòng)靜出聲詢問。雷染君回過神，抹干眼淚站起來，看見姜祈緩緩下了床，艱難地挪動(dòng)到門邊。雷染君推開門，目光第一時(shí)間落在他病服袖口之外的纏著紗布的雙腕上。她緊緊抿住嘴唇，雙手局促不安地握在一起。頭發(fā)束成的馬尾也像失去了往常的活力，毫無生氣地耷拉著。

特別是如果當(dāng)M-11N1存在一個(gè)正的Perron向量，則有

進(jìn)一步，若x是的正的Perron向量，且（4）不等式嚴(yán)格成立，則（5）不等式也嚴(yán)格成立。

3 主要結(jié)論

為改善求解線性方程組(1)的迭代法的收斂速度或者使原來不收斂的迭代法變得收斂，往往對(duì)線性方程組進(jìn)行預(yù)條件處理。其基本思想是在方程組的兩端同時(shí)左乘一個(gè)特殊的可逆矩陣P∈Rn×n(P稱為預(yù)條件因子)，左乘方程組(1)后，使原方程組變?yōu)?/p>

關(guān)于AOR方法的預(yù)處理是在2001年由D J Evans等人提出的，取預(yù)條件因子P=I+S，到目前為止，已經(jīng)有許多種取S的方法,證明在多參數(shù)預(yù)條件因子Pα=I+Sα下AOR方法的收斂性。

其中：

0≤αij≤1(1≤i≠j≤n)是參數(shù),其相應(yīng)的預(yù)條件系統(tǒng)的AOR方法的迭代矩陣記為：

0≤βij≤1(1≤i≠j≤n)，其相應(yīng)的預(yù)條件系統(tǒng)的AOR迭代矩陣為：

為了討論的方便，我們先取

其中，

則，

而

因此，若A是一個(gè)L-矩陣，則有故有，又均為M-矩陣，故由引理5，必有。又由文獻(xiàn)[4]的定理2知，均為非負(fù)不可約矩陣，故由引理1，Lˉαr,w有正的Perron向量，再結(jié)合引理7，有

進(jìn)一步，我們?nèi)ε的上三角部分均為參數(shù)形式，即

可以得到，（8）式仍然成立。

對(duì)于Sε若為下三角的情形，我們同樣先來考慮其簡單形式，即取

則此時(shí)

同理，當(dāng)Sε的下三角部分均為參數(shù)形式時(shí)（9）亦成立。

綜上討論，我們可以得到：

定理2設(shè)A是一個(gè)L-矩陣,,其中:，滿足：,則若ρ(Lr,w)＜1，0≤r≤w≤1,w≠0,就有＜1，且隨著αij的增大，譜半徑變小，進(jìn)而，當(dāng)αij均取為1時(shí)，譜半徑最小。即當(dāng)

對(duì)應(yīng)的預(yù)條件AOR方法收斂最快。

4 數(shù)值例子

為了說明含參預(yù)條件因子中參數(shù)對(duì)AOR方法收斂性的影響，我們考慮以下算例，見表1。設(shè)A為(其中由αij(i＞j)全部取為0.2,αij(i＜j)全部取為0.3所得；由αij(i＞j)全部取為0.4,αij(i＜j)全部取為0.5所得；由αij(i＞j)全部取為0.6,αij(i＜j)全部取為0.5所得；由αij(i≠j)全部取為1所得。

表1 選取不同的預(yù)條件因子下AOR迭代法的譜半徑比較

[1]HADJIMOS A.Accelerated overrelaxation method[J].Math Comp,1978（32）:149-157.

[2]徐樹方.控制論中的矩陣計(jì)算[M].北京:高等教育出版社，2011:37-44.

[3]YOUNG D M.Iterative Solution of Large Linear Systems[M].New York：Academic Press,1971.

[4]LI Wang.Comparison Results for AOR Iterative Method with a New Preconditioner[J].Internatonal Journal or Nonlinear Science,2006,2(1):16-28.

[5]CAO Z H.On the convergence of nested stationary iterative methods[J].Linear Algebra and its Applications,1995(221):159-170.

[6]VARGA R S.Matrix Iterative Analysis[M].New Jersey:Prentice-Hall,1981.

[7]NEUMANN M,PLEMMONS R J.Convergence of parallel multi-splitting iter-ative methods for M-matrices[J].Linear Algebra Appl,1987(88∕89):559-573.

〔責(zé)任編輯 高?！?/p>

The Convergence Analysis of Multi-parameters Preconditioned AOR Iterative Method for L-matrices

LUO Fang,KANG Shu-gui,WANG Zhen-fang
(School of Mathematics and Computer Science,Shanxi Datong University,Datong Shanxi,037009)

The paper mainly studied the parameter’s influence on the rate of convergence for L-matrix multi-parameter preconditioned AOR iterative method A At the same time the corresponding comparison theorem is given.Lastly,we provide numerical experiments to illustrate the theoretical results.

preconditioner;AOR iterative method;L-matrix;M-matrix;convergence

O241.6

A

1674-0874(2015)06-0003-04

2015-09-15

山西大同大學(xué)校級(jí)科研資助項(xiàng)目[2012K7]

羅芳(1970-),女,山西右玉人,碩士，副教授,研究方向：計(jì)算數(shù)學(xué)。