李 斌

(湖南科技學(xué)院 理學(xué)院, 湖南 永州 425100)

關(guān)于H-矩陣的預(yù)條件AOR迭代法的收斂性探討

李 斌

(湖南科技學(xué)院 理學(xué)院, 湖南 永州 425100)

利用矩陣迭代理論與比較定理, 分析了線性方程組的系數(shù)矩陣為H-矩陣時(shí), 預(yù)條件后AOR迭代法的收斂性;并給出了當(dāng)加速因子γ不變時(shí), 松弛因子ω的大小與收斂速度的關(guān)系; 同時(shí)還給出了兩個(gè)數(shù)值實(shí)例驗(yàn)證了主要的結(jié)論.

預(yù)條件; AOR迭代法; Gauss-Seidel迭代法; M-矩陣

考慮線性方程組

這里A=(aij)∈?n×n是非奇異矩陣, b∈?n×1,x∈?n×1. 若A=M-N, 其中M, N∈?n×n, 并且M是非奇異的, 則分裂迭代法可以表示為

不失一般性, 假設(shè)A為對(duì)角元全為1的方陣, 且

其中I, -L, -U分別是A的對(duì)角, 嚴(yán)格下三角和嚴(yán)格上三角部分, 則線性方程組(1)的AOR迭代法的迭代矩陣為

其中0≤γ≤ω≤1,ω≠0.

為了更好地求解方程組(1), 我們引入各種各樣的非奇異預(yù)條件矩陣P來加快迭代矩陣的收斂速度.文[1]提出了一種更一般的預(yù)條件P=I+P1+P2, 它可以和A所有的元素有聯(lián)系.

其中I, P1, P2分別是預(yù)條件矩陣P的對(duì)角部分、嚴(yán)格下三角矩陣和嚴(yán)格上三角矩陣. 對(duì)線性方程組(1)實(shí)行預(yù)條件P=I+P1+P2后, 線性方程組(1)變?yōu)?/p>

1 相關(guān)引理和定義

定義1.1[1]設(shè)A=(aij)∈?n×n, 且aij≤0(i≠j, i, j=1,2,…,n), 則稱A為Z-矩陣. 如果A為非奇異的Z-矩陣, 且A-1≥0, 則稱A為M-矩陣.

定義1.2[2]設(shè)A=(aij)∈?n×n, 則稱A=M-N為矩陣A的一個(gè)分裂, 其中M為非奇異矩陣. 分別稱A=M-N為矩陣A的

(1) 收斂分裂, 如果ρ(M-1N )＜1;

(2) 正則分裂, 如果M-1≥0, 且N≥0;

(3) 弱正則分裂, 如果M-1N≥0;

(4) M-分裂, 如果M為非奇異M-矩陣, 且N≥0.

引理1.1[1]設(shè)A=(aij)∈?n×n為非奇異的M-矩陣, 如果P=(pij)≥0是一個(gè)非奇異的矩陣, 且滿足pii=1,i=1,2,…,n,≤0,1≤i≠j≤n, 則PA也是一個(gè)非奇異的M-矩陣.

引理1.2[1]設(shè)A=(aij)∈?n×n為非奇異的H-矩陣. 如果P=(pij)≥0是一個(gè)非奇異的矩陣, 且滿足pii=1,i=1,2,…,n ,≤0,1≤i≠j≤n, 則PA也是一個(gè)非奇異的H-矩陣.

引理1.3[3]設(shè)A是一個(gè)Z-矩陣, 則下列說法是等價(jià)的:

(a) A是一個(gè)非奇異的M-矩陣;

(b) 存在一個(gè)矢量x＞0, 使得Ax＞0;

(c) 任何弱正則分裂是收斂的.

引理1.4[3]若A是非負(fù)矩陣, 則

(a) 如果αx≤Ax , 對(duì)某一個(gè)非負(fù)的向量x且x≠0成立, 則α≤ρ(A);

(b) 如果Ax≤βx對(duì)某一個(gè)正向量x成立, 則ρ(A)≤β. 進(jìn)一步, 如果A是不可約的, 且若有0≠αx≤Ax≤βx , αx≠Ax 和Ax≠βx對(duì)某一個(gè)非負(fù)的向量x成立, 則α＜ρ(A)＜β, 且x是一個(gè)正向量.

引理1.5[4]若A≥0是矩陣, 則

(a) A有一個(gè)非負(fù)的實(shí)特征值等于它的譜半徑;

(b)ρ(A)對(duì)應(yīng)的特征向量x≥0, 且x≠0;

(c) 當(dāng)A的任何元素增大, ρ(A)不減.

定理1.1[1], 設(shè)A=(aij)∈?n×n是一個(gè)非奇異的Z-矩陣, 若對(duì)?0≤γ≤ω≤1,ω≠0, P=(pij)≥0是一個(gè)的非奇異的矩陣, 且pii=1,i=1,2,…,n ,1≤i≠j≤n, 則

(a) 如果ρ(Tγ,ω)＜1, 則

(b) 如果ρ(Tγ,ω)＞1, 且P滿足1≤i≤n , 則

2 預(yù)條件后的AOR迭代方法

定理2.1設(shè)A=(aij)∈?n×n是一個(gè)非奇異的M-矩陣. 假設(shè) 0≤γ≤ω≤1,ω≠0,P=(pij)≥0是一個(gè)非奇異的矩陣, pii=1,i=1,2,…,n , pij滿足下面的條件之一:

證明1) 當(dāng)pij滿足條件i)時(shí), 由文獻(xiàn)[1]的定理2.7可知, 結(jié)論成立.

2) 當(dāng)pij滿足條件ii)時(shí), 因A是一個(gè)非奇異的M-矩陣, 由引理1.3知ρ(Tγ,ω)＜1.

注:定理2.1在保持結(jié)論不變的情況下對(duì)文[1]的定理2.7的預(yù)條件矩陣P的取值范圍進(jìn)行了推廣.

定理2.2設(shè)A=(aij)∈?n×n是一個(gè)H-矩陣. 假設(shè)0≤γ≤ω≤1,ω≠0,P=(pij)≥0是一個(gè)非奇異的預(yù)條件矩陣, 且pii=1,i=1,2,…,n ,

則PA也是一個(gè)H-矩陣.

證明注意到

由引理1.2知, PA也是一個(gè)H-矩陣.

定理2.3設(shè)A=(aij)∈?n×n是一個(gè)H-矩陣. 假設(shè)0≤γ≤ω≤1,ω≠0,P=(pij)≥0是一個(gè)非奇異的預(yù)條件矩陣, 且

則有

這里Tγ,ω(B)代表矩陣B所對(duì)應(yīng)的AOR迭代矩陣.

證明A是一個(gè)H-矩陣, 則〈A〉是一個(gè)非奇異的M-矩陣, 故由引理1.3有ρ(Tγ,ω〈(A〉 ))＜1.

由引理1.1知P〈 A〉也是一個(gè)非奇異的M-矩陣, 因此, 由文[1]定理2.1, 有

定理2.4設(shè)A=(aij)∈?n×n是一個(gè)H-矩陣. 假設(shè)0≤γ≤ω2≤ω1≤1,ωi≠0,i=1,2, P=(pij)≥0是一個(gè)非奇異的預(yù)條件矩陣, 且滿足定理2.3的條件, 則有

證明根據(jù)已知條件, 由定理2.3有

下面證明, ρ(Tγ,ω1P〈 A〉)＜ρ(Tγ,ω2P〈 A〉 ).

事實(shí)上, 由于P〈 A〉是非奇異的M-矩陣, 易得Tγ,ω2(P〈 A〉 )≥0. 結(jié)合引理1.5知, 存在向量x≥0, 且x≠0,Tγ,ω2P〈 A〉 x=ρ(Tγ,ω2P〈 A〉)x . 不妨設(shè)ρ(Tγ,ω2P〈 A〉 )=λ, 有ρ(Tγ,ω2P〈 A〉) x=λx , 即

3 數(shù)值試驗(yàn)

例 設(shè)

由于A的比較矩陣〈A〉是一個(gè)M-矩陣, 故A為H-矩陣. 表1反映的是定理2.3中, 當(dāng)αij=0時(shí), 譜半徑的大小情況; 表2反映的是定理2.4中, 當(dāng)γ不變, ω增大時(shí), 譜半徑的大小情況, 從而驗(yàn)證了結(jié)論的正確性.

表1 不同條件下AOR迭代法的譜半徑

表2 在γ不變, ω增大的條件下AOR迭代法的譜半徑

[1] L.Wang, Y.Song. Preconditioned AOR iterative methods for M-matrices[J]. J.Comput.Appl. Math. 2009, 226: 114～124

[2] RICHARD S VARGA. Matrix iterative analysis[M]. Heidelberg. Spring-Verlag, 2000: 89～121

[3] A.Berman, R.J. Plemmons. Nonnegative Matrices in the Mathematical Sciences[M]. Academic Press, New York, 1979, SIAM, Philadelphia, PA, 1994

[4] R.S.Varga. Matrix Iterative Analysis[M]. Prentice-Hall, Englewood Cliffs, NJ, 1962; Springer Series in Computational Mathematics, vol. 27, Springer-Verlag, Berlin, 2000

[5] A. Frommer. D.B.Szyld, H-splitting and two-stage iterative methods[J]. Numer. Math. 1992, 63: 345～356

[6] 程云鵬. 矩陣論[M]. 西安: 西北工業(yè)大學(xué)出版社, 2004

The Convergence Discussion of the AOR Precondition Iterative Methods for H-matrices

LI Bin
(College of Science, Hunan University of Science and Engineering, Yongzhou 425100, China)

This paper firstly presents the convergence analysis of AOR-type iterative method for solving linear systems with H-matrices by using matrix iterative analysis and comparison theorems; then gets the relations between the size of relaxation factorωand the rate of convergence when the acceleration factor γis constant. Finally, the author verifies his conclusions through two numerical examples.

precondition; AOR-type iterative method; Gauss-Seidel iterative method; M-matrix

O151.21

: A

1672-5298(2015)03-0012-05

2015-07-01

湖南科技學(xué)院教學(xué)改革研究項(xiàng)目(湘科院教字[2014]14號(hào))

李 斌(1973- ), 男, 湖南雙峰人, 碩士, 湖南科技學(xué)院理學(xué)院講師. 主要研究方向: 計(jì)算數(shù)學(xué)