基于矩陣分裂的預條件SOR迭代法收斂性

雷剛

(寶雞文理學院 數學系，陜西 寶雞 721013)

基于矩陣分裂的預條件SOR迭代法收斂性

雷剛

(寶雞文理學院 數學系，陜西 寶雞 721013)

對預條件方法解線性方程組，利用黃廷祝等在[“modified SOR-type iterative method for z-matrices”]中提到的預條件能加速SOR迭代法的收斂性，結合矩陣分裂理論及比較定理，給出一種基于矩陣分裂的含參數預條件SOR迭代方法，說明這種方法不僅能加速SOR迭代法的收斂性，而且優于一般的預條件方法，找出參數的最優選取方法，最后通過數值例子加以說明.

預條件；收斂性；SOR迭代法； 譜半徑；矩陣分裂

隨著計算機的廣泛應用，對大型線性方程組的求解大都采用迭代法，但是迭代法的收斂性以及迭代法的收斂速度通常難于把握，近年來都是對線性方程組進行預處理，加速迭代法的收斂性，如何使用預處理以及如何加速收斂速度成為人們關注[1-3]的問題.

1 預備知識

運用迭代法求解大型線性方程組

Ax=b，

(1)

其中A=(aij)n×n∈Rn×n，x，b∈Rn常常都是通過預條件的方法[1-3]加速迭代法的收斂性，也就是給方程組的兩邊同時左乘一個非奇異矩陣P∈Rn×n，使原方程變為

PAx=Pb.

(2)

為討論方便，一般假設A=I-L-U為非奇異矩陣(當A為奇異矩陣時，可通過矩陣變換為低階的非奇異矩陣)，其中I為單位矩陣，-L為嚴格下三角矩陣，-U為嚴格上三角矩陣.)

那么，解方程組(1)的SOR(超松馳)迭代法的迭代矩陣為

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

(3)

若令M=(I-ωL)，N=[(1-ω)I+ωU]，則SOR迭代矩陣T=M-1N.

常見的預條件因子如文獻[1]中提到的P=(I+C)，其中，I為單位矩陣，C為如下形式的方陣

(4)

其中a21，a31，…，an1分別是系數矩陣A=(aij)n×n對應位置上的元素.那么，在預處理因子P=(I+C)作用后，方程組PAx=Pb的系數矩陣記為AC，則

(5)

其中，CL=0，CU=D1+L1+U1；(I-D1)，-(L-C+L1)和-(U+U1)分別是矩陣AC的對角線部分、嚴格下三角部分和嚴格上三角部分.從而一般的預處理后的SOR迭代法的迭代矩陣為

TC=[(I-D1)-ω(L-C+L1)]-1[(1-ω)(I-D1)+ω(U+U1)].

(6)

記為TC=MC-1NC.引入參數α，利用矩陣分裂理論，將矩陣AC分裂為

(7)

則改進的SOR迭代法的迭代矩陣為

Tcα=[αI-ω(L-C+L1)]-1[(α-ω)I+ωD1+ω(U+U1)]，

(8)

記為TCα=MCα-1NCα.

2 結論

定義1[4]記所有n×n實矩陣A=(aij)所組成的集合為Rn,n，Rn,n的子集為

Zn,n={A=(aij)|A∈Rn×n,aij≤0，(?i,j,i≠j)}，

當A∈Zn,n，aiigt;0(?i)成立時，稱矩陣A為L-矩陣.

定義2[5]如果矩陣A能表示為A=sI-B，I為n階的單位矩陣，B≥0,當s≥ρ(B)時，稱A為M-矩陣，特別當sgt;ρ(B)時，稱A為非奇異的M-矩陣；當s=ρ(B)時，稱A為奇異M-矩陣.其中ρ(B)為B的譜半徑.

定義3[6]設方陣A=(aij)的階n≥2，如果對集合W={1,2,…,n}的任意2個非空不相交的子集S和T，S+T=W，都有i和j滿足i∈S,j∈T，使aij≠0，則稱A是不可約的，否則稱為可約的.

引理1[4](Perron-Frobenius定理)如果A為n階非負方陣，那么就有

1)A有非負特征值等于其譜半徑ρ(A)；

2)A有與ρ(A)相對應的非負特征向量；

3)A的任一元素增加時，ρ(A)不減.

引理2[6]設A為非負矩陣，則

1)若ax≤Ax對某一個非負向量x且x≠0成立，那么就有α≤ρ(A)；

2)若Ax≤βx對某一個正向量x成立，那么就有ρ(A)≤β，進一步，如果A不可約且有0≠ax≤Ax≤βx,ax≠Ax，Ax≠βx對某一個非負向量x成立，則αlt;ρ(A)lt;β.

引理3[3]設A為L-矩陣，滿足0lt;ai,i+1ai+1,i,i=1,2,…,n-1，且0lt;ai1a1ilt;1,i=2,3,…,n，那么當0lt;ωlt;1時，由式(3)給出的SOR迭代矩陣T是非負不可約的.

定理1 設T和TCα分別由式(3)和(8)給出的SOR迭代法的迭代矩陣，當線性方程組的系數矩陣A是對角元素為1的L-矩陣，滿足0lt;ai,i+1ai+1,i，i=1,2,…,n-1，0lt;ai1a1ilt;1，i=2,3,…,n,且0lt;ω≤α≤1時，就有

1)當ρ(T)gt;1時，ρ(TCα)≥ρ(T)；

2)當ρ(T)=1時，ρ(TCα)=ρ(T)；

3)當ρ(T)lt;1時，ρ(TCα)≤ρ(T).

證明由引理3知，T是一個不可約的非負矩陣，再由引理1知，存在一個正向量x={x1,x2,…,xn}T，滿足Tx=λx，其中λ=ρ(T)，即有

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

另外利用CL=0，可得ωCUx=[(λ-1)CI+ωCI]λx.

由A是對角元素為1的L-矩陣，0lt;ω≤α≤1且0lt;αi1a1ilt;1，i=2,3,…,n，結合矩陣L-C+L1是非負的下三角矩陣可知

NCα=[(α-ω)I+ωD1+ω(U+U1)]≥0.

考慮

TCαx-λx=MCα-1NCαx-λx=MCα-1(NCα-λMCα)x=

[αI-ω(L-C+L1)]-1{αI-ωI+ωD1+ωU+ωU1-λ[αI-ω(L-C+L1)]}x=

[αI-ω(L-C+L1)]-1{(1-λ)αI+(λ-1)I+(λ-1)C+ωC-λωC+(λ-1)ωL1}x=

[αI-ω(L-C+L1)]-1{(1-λ)αI+(λ-1)I+(λ-1)(1-ω)C+(λ-1)ωL1}x=

[αI-ω(L-C+L1)]-1(λ-1){(1-α)I+(1-ω)C+ωL1}x.

可知TCαx-λx=[αI-ω(L-C+L1)]-1(λ-1){(1-α)I+(1-ω)C+ωL1}x.

令y=[αI-ω(L-C+L1)]-1{(1-α)I+(1-ω)C+ωL1}x，易知ygt;0，結合文獻[8]，有

1)如果λgt;1，則TCαx-λx≥0，但TCαx-λx≠0，因此TCαx≥λx，由引理2可得ρ(TCa)≥λ=ρ(T)；

2)如果λ=1，則TCαx-λx=0，因此TCαx=λx，由引理2可得ρ(TCα)=λ=ρ(T)；

3)如果λlt;1，則TCαx-λx≤0，但TCαx-λx≠0，因此TCαx≤λx，由引理2可得ρ(TCα)≤λ=ρ(T).

定理2 設TC和TCα分別由式(6)和(8)給出的SOR迭代法的迭代矩陣，當A為非奇異不可約M-矩陣，滿足0lt;αi,i+1αi+1,i,i=1,2,…,n-1，0lt;αi1α1ilt;1，i=2,3,…，n,且0lt;ω≤α≤min{1-αi1α1i}時，就有ρ(TCα)≤ρ(TC)lt;1.

證明由式(7)知

又由于0lt;ω≤α≤min{1-ai1a1i}，L-C+L1是非負的下三角矩陣，結合定理1的證明有

另一方面，由式(5)對AC做如下分裂：

AC=(I-D1)-(L-C+L1)-(U+U1)=

結合條件0lt;ai1a1ilt;1，有I-D1=1-ai1a1igt;0，i=2,3,…,n，0lt;ω≤α≤min{1-ai1a1i}且L-C+L1是非負的下三角矩陣，U+U1是非負的上三角矩陣，從而

另外，有MCα≠MC，事實上，若MCα=MC，

[αI-ω(L-C+L1)]=[(I-D1)-ω(L-C+L1)]，

即

(1-α)I=D1.

由于0lt;α≤min{1-ai1a1i}，且D1為CU的對角元素組成的方陣，其第1個元素為零，所以這是不可能的，結合條件0lt;α≤min{1-ai1a1i}知，MCα≤MC，從而有MCα-1≥MC-1.

綜上，由引理4結合文獻[8]可知ρ(TCα)≤ρ(TC)lt;1.

定理3 設T和TCα分別由式(3)和(8)給出的SOR迭代法的迭代矩陣，當A為非奇異不可約M-矩陣，滿足0lt;ai,i+1ai+1,i，i=1,2,…,n-1，0lt;ai1a1ilt;1，i=2,3,…,n,且0lt;ω≤αi≤min{1-ai1a1i}時，那么對α1lt;α2，就有

1)當ρ(T)lt;1時，ρ(TCα1)≤ρ(TCα2)；

2)當ρ(T)≥1時，ρ(TCα1)≥ρ(TCα2).

證明由于α1lt;α2，則非負矩陣α1I-(L-C+L1)≤α2I-(L-C+L1)，從而相應的逆矩陣就有[α1I-(L-C+L1)]-1≥[α2I-(L-C+L1)]-1，即MCα1-1≥MCα2-1.

又由定理2知，TCα1是非負矩陣，結合引理1可知其譜半徑是它的一個特征值，且有與之相對應的非負特征向量x=(x1,x2,…,xn)T，使得TCα1x=ρ(TCα1)x.所以

ρ(TCα1)x-TCα2x=TCα1x-TCα2x=

MCα1-1(NCα1-λMCα1)x-MCα2-1(NCα2-λMCα2)x≤

MCα1-1[(NCα1-λMCα1)]-(NCα2-λMCα2)x=

MCα1-1(1-λ)(α1-α2)Ix，

即

ρ(TCα1x)-TCα2x≤MCα1-1(1-λ)(α1-α2)Ix.

所以，當ρ(T)=λlt;1，α1lt;α2時，上述不等式右端小于0，從而ρ(TCα1)≤ρ(TCα2)；另一方面，當ρ(T)=λ≥1，α1lt;α2時，同上可知

ρ(TCα1x)-TCα2x=TCα1x-TCα2x=

MCα2-1(λMCα2-NCα2)x-MCα1-1(λMCα1-NCα1)x≥

MCα2-1[(λMCα2-NCα2)-(λMCα1-NCα1)]x=

MCα2-1(λ-1)(α2-α1)Ix.

所以，當ρ(T)=λ≥1時，上述不等式右端大于或等于0，所以ρ(TCα1)≥ρ(TCα2).

推論設TCα是由式(8)給出的SOR迭代法的迭代矩陣，A為非奇異不可約M-矩陣，滿足0lt;ai,i+1ai+1,i，i=1,2,…,n-1，0lt;ai1a1ilt;1，i=2,3,…，n，0lt;ω≤α≤min{1-ai1a1i}，那么當ω=α時，由式(8)給出的SOR迭代法的譜半徑達到最小.

舉例如果矩陣的表達式如下:

則計算可知，以A為線性方程組的系數矩陣，對不同的ω和α時，譜半徑的比較如下表1.

表1 不同參數的迭代法譜半徑

從表1可以看出，對給定的ω，文中給出的新迭代法隨著α的減小其譜半徑也在減小，并且當ω=α時譜半徑達到最小；對不同的ω，ω越大，SOR迭代法的譜半徑就越小，但是不論ω，α如何變化，都可以得到當ω=α時新的迭代法的譜半徑達到最小.

3 結論

理論分析和數值例子顯示在新的分裂形式下，譜半徑隨著參數α的變化可以減小，當ω=α時，該方法的譜半徑達到最小，加速收斂的效果優于一般的預條件方法，為大型線性方程組的迭代求解提供新的理論依據.今后可以考慮在加速收斂性的同時適當降低對系數矩陣的要求.

[1] HUANG Tingzhu, CHENG Guanghui, CHENG XiaoYu.Modified SOR-type iterative method for Z-matrices[J].Applied Mathematics and Computation， 2006，175:258-268.

[2] HIROSHi NIKI, KYOUJI HARADA, MUNENORI MORIMOTO，et al.The survey of preconditioners used for accelerating the rate of convergence in the Gauss-Seidel method [J].Journal of Computational and Applied Mathematics， 2004,165: 587-600.

[3] JAE H Y.A note on the modified SOR method for Z-matrices[J].Applied Mathematics and Computation, 2007，194:572-576.

[4] DAVID M Y.Iterative solution of large linear systems[M].New York :Academic Press, 1971.

[5] RICHARD S V.Matrix iterative analysis[M].Spring-Verlag: Heidelberg, 2000.

[6] 張謀成,黎穩.非負矩陣論[M].廣州:廣東高等教育出版社,1995.

ZHANG Moucheng,LI Wen.Non-negative matrix theory[M].Guangzhou:Guangdong Higher Education Press,1955.

[7] WANG Zhuande, HUANG Tingzhu.Comparison result between Jacobi and other iterative methods[J].Journal of Computational and Applied Mathematics, 2004，169:45-51.

[8] WANG Xuezhong, HUANG Tingzhu，FU Yingding.Comparison results on preconditioned SOR-type iterative method for Z-matrices linear systems[J].Journal of Computational and Applied Mathematics, 2007，206:726-732.

(責任編輯：王蘭英)

ConvergencediscussionofSORiterativemethodinpreconditionbasedonmatrixsplitting

LEIGang

( Department of Mathematics, Baoji University of Arts and Sciences, Baoji Shaanxi, 721013,China)

It studies the preconditioned iterative method for the solving the linear system.Ting-Zhu Huang gives the preconditioned to accelerate convergence of SOR iterative method atquot;modified SOR-type iterative method for z-matricesquot;.by using matrix iterative analysis and comparison theorems to make an improved SOR iterative method to solve the large linear system in preconditioned based on matrix splitting, then prove the improved method not only to accelerate the SOR iterative method, but also to excel the general preconditioned SOR method.Last the numerical example is given.

precondition; convergence; SOR iteration method; spectral radius; matrix splitting

O241.6

A

1000-1565(2012)01-0012-05

2011-04-27

國家自然科學基金資助項目(10071048);寶雞文理學院重點基金資助項目(ZK1031)

雷剛(1977-),男，陜西合陽人，寶雞文理學院講師，主要從事數值計算方向研究.

E-mail: lg3048@163.com

MSC2010: 65F10