系數(shù)矩陣含參數(shù)分裂形式的SOR迭代法收斂性分析

王慧勤

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

0 引言

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

1 預(yù)備知識

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

PAx=Pb

(1)

其中A=(aij)n×n∈Rn×n，x,b∈Rn.本文運用預(yù)處理因子P=(I+S)以及矩陣分析和矩陣理論，給出預(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分別是嚴格下三角矩陣和嚴格上三角矩陣.那么求解方程組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ù)處理后的SOR迭代法的迭代矩陣為

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

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

(4)

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

(5)

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

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

(6)

2 定義和引理

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

定義2[5]：設(shè)方陣A=(aij) 的階n≥2，如果對集合W={1,2,…,n}的任意兩個非空不相交的子集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)相對應(yīng)的非負特征向量；

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

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

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

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

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

3 結(jié)果與證明

證明：由引理3知，T是一個不可約的非負矩陣，再由引理1知，存在一個正向量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，則非負矩陣

[β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的表達式如下所示：

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

從表1可以看出，對給定的γ，文中給出的新迭代法隨著β的減小其譜半徑也在減小，并且當γ=β時譜半徑達到最?。粚Σ煌摩?，γ越大，SOR迭代法的譜半徑就越小，但是不論γ,β如何變化，都可以得到當γ=β時這種新的迭代法的譜半徑達到最小.

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

5 結(jié)束語

理論分析和數(shù)值例子顯示在引入?yún)?shù)以后，系數(shù)矩陣的分裂更加一般化，迭代法的收斂速度進一步加快，迭代法的譜半徑隨著參數(shù)β的變化可以減小，當γ=β時，該方法的譜半徑達到最小，加速收斂的效果優(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).非負矩陣論[M]. 廣州:廣東高等教育出版社,1995.

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