王慧勤

(宝鸡文理学院 数学系, 陕西 宝鸡 721013)

0 引言

对线性方程组Ax=b的求解，主要有直接法求解和迭代法求解.直接法很难克服存储问题.而在求解线性方程组的许多实际问题中，尤其在偏微分方程的差分方法与有限元方法求解问题之中，方程具有重要的特征，一是多为大型稀疏矩阵；二是满足一些条件如对称正定、对角占优等，这使迭代法得到广泛的应用.另外，与直接法相比，迭代法还具有一些明显的优点，比如占用计算机的内存单元少、计算程序比较简单、收敛速度比较快等.近年来都是对线性方程组进行预处理，以加速迭代法的收敛性，那么如何使用预处理以及如何加速收敛速度成为人们关注[1-3]的问题.

1 预备知识

在用预条件迭代法求解大型线性方程组Ax=b时，对线性方程组两边分别乘非奇异矩阵P，转化为

PAx=Pb

(1)

其中A=(aij)n×n∈Rn×n，x,b∈Rn.本文运用预处理因子P=(I+S)以及矩阵分析和矩阵理论，给出预处理后含参数的分裂形式，使得预处理后的系数矩阵分裂更加一般化，讨论得到能加速超松弛迭代法(SOR迭代法)的收敛性，而且优于一般的预处理方法.其中，I为单位矩阵，S为如下形式的方阵

(2)

an1是系数矩阵A=(aij)n×n对应位置上的元素.通常设矩阵A=I-L-U,I为单位矩阵，L为和U分别是严格下三角矩阵和严格上三角矩阵.那么求解方程组Ax=b的SOR迭代法的迭代矩阵为

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

(3)

在预处理因子P=(I+S)作用后，方程组PAx=Pb的系数矩阵记为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的对角线部分、严格下三角部分和严格上三角部分.则预处理后的SOR迭代法的迭代矩阵为

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

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

(4)

记为TS=M-1N.为加快迭代法的收敛性，引入参数β，将预处理后的矩阵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]：设方阵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)相对应的非负特征向量；

(3)A的任一元素增加时，ρ(A)不减.

引理2[6]：设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]：设A为L-矩阵，满足0

3 结果与证明

证明：由引理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)],

从而相应的逆矩阵就有

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

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

4 数值例子

例：如果矩阵A的表达式如下所示：

则计算可知，以A为线性方程组的系数矩阵，对不同的当γ,β时，谱半径的比较如下表1：

从表1可以看出，对给定的γ，文中给出的新迭代法随着β的减小其谱半径也在减小，并且当γ=β时谱半径达到最小；对不同的γ，γ越大，SOR迭代法的谱半径就越小，但是不论γ,β如何变化，都可以得到当γ=β时这种新的迭代法的谱半径达到最小.

表1 不同参数的迭代法谱半径

5 结束语

理论分析和数值例子显示在引入参数以后，系数矩阵的分裂更加一般化，迭代法的收敛速度进一步加快，迭代法的谱半径随着参数β的变化可以减小，当γ=β时，该方法的谱半径达到最小，加速收敛的效果优于一般的预条件方法，为大型线性方程组的迭代求解提供新的理论依据.

[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] 张谋成,黎 稳.非负矩阵论[M]. 广州:广东高等教育出版社,1995.

[7] 雷 刚.预条件(I+S)后改进矩阵分裂的SOR迭代法收敛性分析[J].宝鸡文理学院学报,2010,31(3):13-17.