SOR的一种新的预处理方法

武瑞环

(太原师范学院 数学系,山西 晋中 030619)

0 引言

考虑下列线性系统:

Ax=b

其中,A∈Rn×n是非奇异矩阵,x,b∈Rn是n维向量.

基本迭代方法为:

Mxk+1=Nxk+b,k=0,1,…

这里,A=M-N，M是非奇异矩阵.则:

xk+1=Txk+c,k=0,1,…,

这里,T=M-1N且c=M-1b.不失一般性,设A=I-L-U，这里，I,-L,-U分别为矩阵A的对角部分,严格下三角部分和严格上三角部分.则古典SOR方法的迭代矩阵是:

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

这里，0<ω<2是松弛参数.显然地，当ω=1，得到古典Gauss-Seidel算法.

对线性系统进行预处理:

PAx=Pb

其中,P∈Rn×n是预处理子.

令PA=MP-NP,MP为非奇异矩阵,

则预处理后迭代方法为:

xk+1=Txk+c,k=0,1,…,

许多科学计算和工程领域，预处理是一个重要工具.因此，如何寻找合适的预处理子引起了许多专家和学者的关注，目前存在许多预处理子.比如,

Milaszewicz提出预处理子PC=I+C，这里,

设AC=PCA=(I+C)A=DC-LC-UC,DC=I+DPC,LC=L+LPC,UC=U+UPC，这里，DPC,-LPC,-UPC分别为矩阵C-CU的对角部分,严格下三角部分和严格上三角部分.则预处理SOR方法的迭代矩阵是:

TC=(DC-αLC)-1((1-α)DC+αUC)

这里，0<α<2是松弛参数.

Gunawardena等人考虑预处理子PS=I+S，这里,

类似地，设AS=PSA=(I+S)A=DS-LS-US,DS=I+DPS,LS=L+LPS,US=U+UPS，这里，DPS,-LPS,-UPS分别为矩阵S-SU-SL的对角部分,严格下三角部分和严格上三角部分.则预处理SOR方法的迭代矩阵是:

TS=(DS-βLS)-1((1-β)DS+βUS)

这里，0<β<2是松弛参数.

1 算法

本章主要考虑下列线性系统的预处理问题:

这里，0<τ<2是松弛参数.显然地，当τ=1，得到预处理的Gauss-Seidel 算法.

为了方便，我们给出一些定义.

定义1对于i,j=1,2,…,n且i≠j,满足aij<0，则矩阵A为Z矩阵.

定义2矩阵A为M矩阵.若A=sI-B,B≥0且s>ρ(B)，这里ρ(B) 是B的谱半径.

定义3矩阵A是不可约的,若A的有向图是强凸的.

2 数值结果

例2.1考虑 Weiner-Hopf 方程Anx=b，这里

表1 例2.1的不同方法的迭代矩阵的谱半径,迭代次数和迭代时间

3 总结

在本文中，提出线性系统SOR方法的一种新预处理子I+C+S，根据上述实验数据，可以看出该预处理子在迭代步数、迭代时间等方面都比古典SOR方法占优势，则具有更好地收敛效果.