羅 芳，康淑瑰，王振芳

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

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

羅 芳，康淑瑰，王振芳

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

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

預條件;AOR迭代法;L-矩陣;M-矩陣;收斂

考慮線性方程組

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

它的迭代矩陣表示為：

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

當r≠0時，AOR方法可以看作是SOR方法的外推，記作ESOR方法。此時，若記，則有：

1 解線性方程組的AOR方法

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

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

2 預備知識

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

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

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

定義2[2]設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。對于任一個Z-矩陣A,都可表示成A=sI-B,其中s是一個正數(shù),B≥0。如果一個Z-矩陣A滿足s≥ρ(B),則稱A是M-矩陣。當s＞ρ(B)時,稱之為非奇異的M-矩陣，其中ρ(A)表示A的譜半徑。

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

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

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

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

(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是一個Z-矩陣,則下列命題等價:

(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]設A=M-N是一個M-分裂,則ρ(M-1N)＜1，當且僅當A是非奇異的M-矩陣。

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

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

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

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

特別是如果當M-11N1存在一個正的Perron向量，則有

進一步，若x是的正的Perron向量，且（4）不等式嚴格成立，則（5）不等式也嚴格成立。

3 主要結論

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

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

其中：

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

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

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

其中，

則，

而

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

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

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

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

則此時

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

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

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

對應的預條件AOR方法收斂最快。

4 數(shù)值例子

為了說明含參預條件因子中參數(shù)對AOR方法收斂性的影響，我們考慮以下算例，見表1。設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 選取不同的預條件因子下AOR迭代法的譜半徑比較

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

[2]徐樹方.控制論中的矩陣計算[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.

〔責任編輯 高海〕

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

山西大同大學校級科研資助項目[2012K7]

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