王慧勤

(寶雞文理學(xué)院 數(shù)學(xué)系, 陜西 寶雞 721013)

0 引言

對線性方程組Ax=b的求解，主要有直接法求解和迭代法求解.直接法很難克服存儲問題.而在求解線性方程組的許多實(shí)際問題中，尤其在偏微分方程的差分方法與有限元方法求解問題之中，方程具有重要的特征，一是多為大型稀疏矩陣；二是滿足一些條件如對稱正定、對角占優(yōu)等，這使迭代法得到廣泛的應(yīng)用.另外，與直接法相比，迭代法還具有一些明顯的優(yōu)點(diǎn)，比如占用計(jì)算機(jī)的內(nèi)存單元少、計(jì)算程序比較簡單、收斂速度比較快等.近年來都是對線性方程組進(jìn)行預(yù)處理，以加速迭代法的收斂性，那么如何使用預(yù)處理以及如何加速收斂速度成為人們關(guān)注[1-3]的問題.

1 預(yù)備知識

在用預(yù)條件迭代法求解大型線性方程組Ax=b時(shí)，對線性方程組兩邊分別乘非奇異矩陣P，轉(zhuǎn)化為

PAx=Pb

(1)

其中A=(aij)n×n∈Rn×n，x,b∈Rn.本文運(yùn)用預(yù)處理因子P=(I+S)以及矩陣分析和矩陣?yán)碚?，給出預(yù)處理后含參數(shù)的分裂形式，使得預(yù)處理后的系數(shù)矩陣分裂更加一般化，討論得到能加速超松弛迭代法(SOR迭代法)的收斂性，而且優(yōu)于一般的預(yù)處理方法.其中，I為單位矩陣，S為如下形式的方陣

(2)

an1是系數(shù)矩陣A=(aij)n×n對應(yīng)位置上的元素.通常設(shè)矩陣A=I-L-U,I為單位矩陣，L為和U分別是嚴(yán)格下三角矩陣和嚴(yán)格上三角矩陣.那么求解方程組Ax=b的SOR迭代法的迭代矩陣為

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

(3)

在預(yù)處理因子P=(I+S)作用后，方程組PAx=Pb的系數(shù)矩陣記為AS，則

AS=PA=(I+S)(I-L-U)

=(I-D1)-(L-S+L1)-U

其中，SL=0,SU=D1+L1;(I-D1),-(L-S+L1)和-U分別是矩陣AS的對角線部分、嚴(yán)格下三角部分和嚴(yán)格上三角部分.則預(yù)處理后的SOR迭代法的迭代矩陣為

TS=[(I-D1)-γ(L-S+L1)]-1

[(1-γ)(I-D1)+γU]

(4)

記為TS=M-1N.為加快迭代法的收斂性，引入?yún)?shù)β，將預(yù)處理后的矩陣AS分解為

(5)

則改進(jìn)的SOR迭代法的迭代矩陣為

[(β-γ)(I-D1)+γU]

(6)

2 定義和引理

定義1[4]：如果矩陣A能表示為A=sI-B，I為n階的單位矩陣，B≥0,當(dāng)s≥ρ(B)時(shí)，稱A為M-矩陣，特別當(dāng)s>ρ(B)時(shí)，稱A為非奇異的M-矩陣；當(dāng)s=ρ(B)時(shí)，稱A為奇異M-矩陣.其中ρ(B)為B的譜半徑.

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

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

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

(2)A有與ρ(A)相對應(yīng)的非負(fù)特征向量；

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

引理2[6]：設(shè)A為非負(fù)矩陣，則

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

(2)若Ax≤βx對某一個(gè)正向量x成立，那么就有ρ(A)≤β，進(jìn)一步，如果A不可約且有0≠αx≤Ax≤βx,αx≠Ax,Ax≠βx對某一個(gè)非負(fù)向量x成立，則α<ρ(A)<β.

引理3[7]：設(shè)A為L-矩陣，滿足0

3 結(jié)果與證明

證明：由引理3知，T是一個(gè)不可約的非負(fù)矩陣，再由引理1知，存在一個(gè)正向量x=(x1,x2,…,xn)T，滿足Tx=λx，其中λ=ρ(T).即有[(1-γ)I+γU]x=(I-γL)λx另外利用SL=0，可得γSUx=[(λ-1)SI+γSI]λx.

-λ[β(I-D1)-γ(L-S+L1)]

=(λ-1)[(1-β)(I-D1)+D1+γL1]x

那么

=[β(I-D1)-γ(L-S+L1)]-1

(λ-1)[(1-β)(I-D1)+D1+γL1]x

證明： 由式(7)知

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

AS=(I-D1)-(L-S+L1)-U

證明： 由于β1<β2，則非負(fù)矩陣

[β1(I-D1)-γ(L-S+L1)]

≤[β2(I-D1)-γ(L-S+L1)],

從而相應(yīng)的逆矩陣就有

[β1(I-D1)-γ(L-S+L1)]-1

≥[β2(I-D1)-γ(L-S+L1)]-1,

4 數(shù)值例子

例：如果矩陣A的表達(dá)式如下所示：

則計(jì)算可知，以A為線性方程組的系數(shù)矩陣，對不同的當(dāng)γ,β時(shí)，譜半徑的比較如下表1：

從表1可以看出，對給定的γ，文中給出的新迭代法隨著β的減小其譜半徑也在減小，并且當(dāng)γ=β時(shí)譜半徑達(dá)到最??；對不同的γ，γ越大，SOR迭代法的譜半徑就越小，但是不論γ,β如何變化，都可以得到當(dāng)γ=β時(shí)這種新的迭代法的譜半徑達(dá)到最小.

表1 不同參數(shù)的迭代法譜半徑

5 結(jié)束語

理論分析和數(shù)值例子顯示在引入?yún)?shù)以后，系數(shù)矩陣的分裂更加一般化，迭代法的收斂速度進(jìn)一步加快，迭代法的譜半徑隨著參數(shù)β的變化可以減小，當(dāng)γ=β時(shí)，該方法的譜半徑達(dá)到最小，加速收斂的效果優(yōu)于一般的預(yù)條件方法，為大型線性方程組的迭代求解提供新的理論依據(jù).

[1] Ting-Zhu Huang, Guang-Hui Cheng, Xiao-Yu Cheng. Modified SOR-type iterative method for Z-matrices[J]. Applied Mathematics and Computation,2006，175(2):258-268.

[2] Hiroshi Niki, Kyouji Harada, Munenori Morimoto.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(3): 587-600.

[3] Jae Heon Yun. A note on the modified SOR method for z-matrices[J]. Applied Mathematics and Computation,2007，194(3):572-576.

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

[5] Richard S. Varga. Matrix iterative analysis[M]. Spring-Verlag Heidelberg, 2000.

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

[7] 雷 剛.預(yù)條件(I+S)后改進(jìn)矩陣分裂的SOR迭代法收斂性分析[J].寶雞文理學(xué)院學(xué)報(bào),2010,31(3):13-17.