计算的分量.也就是把xi即:
(k?1)取为Gauss-Seidel迭代法中xi(k)与xi(k?1)的某个平均值,
(k?1)xi??1???xi(k)??xi(k?1)?x(k)i???x(k?1)i?x(k)i?
当??1时,它就是Gauss-Seidel迭代法.因此希望选取合适的?使得它比Gauss-Seidel迭代法具有更快的收敛速度. 3.4 SSOR算法
SOR迭代格式还可以写为
(k)?D??L?X(k?1)????1???D??U??X??b,k?0,1,?
将上式L和U的位置互换就得到一个新的迭代格式,具体表示为:
1(k?)?(k)2??1??D??UX??b?????D??L?X?? ?1??D??L?X(k?1)???1???D??U?X(k?2)??b,k?0,1,????若消去X1(k?)2,就得到迭代格式(4),其中
?1?1?1B??D??U?D?D??L??1??D??LD????????1???D??U??,f???2????D??U?D?D??L??1?1
称为对称逐次超松弛迭代法(Symmetric Successive Over Relaxation,简称SSOR). 对一类椭圆微分方程离散后得到的线性方程组,Young[3]给出了最佳松弛因子,即为
??21?1??2?B?
其中B是Jacobi迭代法中的迭代矩阵.在实际问题中最佳松弛因子是很难计算的,但一般都在(0,2)之间. 3.5收敛性分析
定义3.1[3] 若实矩阵A??aij?nn,满足
j?1,j?i?nnaij?aii,?i?1,2,?n?
或
i?1,i?j?aij?ajj,?j?1,2,?n?
则称A为严格对角占优矩阵；若满足
4
j?1,j?i?nnaij?aii,?i?1,2,?n?
或
i?1,i?j?aij?ajj,(j?1,2,?n)
且上述不等式至少有一个严格成立,则称A为弱严格对角占优矩阵.
定义3.2[3] 设A为n阶矩阵,n?2.若存在n阶排列矩阵P,使得
?APTAP??11?0A12?? A22?其中A11为r阶矩阵,1?r?n,则称A是可约的,否则称A不可约.
定理3.1[3] 若A为n阶严格对角占优矩阵或不可约的弱严格对角占优矩阵,则对任意的初始值x(0),(1)式中的Jacobi迭代法、Gauss-Seidel迭代法和关于
0???1的SOR迭代法均收敛.
定理3.2 [4] 对所有?均成立不等式
??BSOR????1
当?是实数时,SOR方法收敛的一个必要条件是0???2.
定理3.3[4] 如果系数矩阵A是Hermite矩阵,则SOR方法收敛的充要条件是:A正定和0???2.
4.几种新的迭代算法
4.1 基于矩阵分裂形式的新迭代算法
上述几种基本迭代方法都是通过对线性方程组(1)的系数矩阵A进行分裂得到的,不同之处在于A分裂成A?M?N的形式时,M和N的取值不同.由(3),(4)可知此种格式下的迭代矩阵B?M?1N?E?M?1A,所以当M是A一个很好的近似时,Bp就会很小.再由定理2.1和定理2.2可知此时得到的迭代法收敛速度也更快.另一方面,我们构造的迭代格式为Mx(k?1)?Nx(k)?b,k?0,1?,由于每一次迭代都要解一个方程组,所以我们也要求非退化的矩阵M的形式比较简单,如对角矩阵、下三角矩阵等.
比较Jacobi迭代、Gauss-Seidel迭代及SOR算法中M的取值,我们可以看到M的形式都为对角矩阵或下三角矩阵,并且随着M越近似等于A,所得到的迭代方法的收敛速度也越快.满足上述两个条件,对M取不同于这三种算法中M取值的形式,我们可以得到下述新的算法.
4.1.1 算法的建立 取
5
M?D??L,N??1???L?U.0???1, (9)
作为A?M?N的一个新分裂,在此分裂的基础上可得到一个新的迭代公式
x(k?1)?B?x(k)?f?,k?0,1,? (10)
其中,B???D??L??1??1???L?U?,f???D??L??1b,0???1.显然,当??0时
就是Jacobi迭代法；当??1时就是Gauss-Seidel迭代法.
4.1.2 收敛性分析
引理1[3] A可约的充要条件为存在非空子集J??1,2,?n?,使得
aij?0,i?J,j?J.
引理2[3] 若A为n阶严格对角占优矩阵或不可约的弱严格对角占优矩阵,则A是非退化的.
定理4.1 若A为n阶严格对角占优矩阵或不可约的弱严格对角占优矩阵,则对任意的初始值x(0),当0???1时,(10)式表示的迭代格式收敛.
证明:(10)式的迭代矩阵为
B???D??L??1??1???L?U?
?1我们有
det??E?B???det?E??D??L??1??1???L?U???
?det??D??L???det???D??L????1???L?U??其中?为B?的特征值.若A?D?L?U为严格对角占优矩阵,则D??L也为严格对角占优矩阵；若A?D?L?U为不可约的弱对角占优矩阵,则D??L也为不可
约的弱对角占优矩阵.由引理2,我们有
det?D??L?所以
??1??0
?det??E?B???0?det??D??L????1???L?U??0
?令
H???D??L????1???L?U???D???????1?L?U
a12a13a23???????1?an3?a11????????1?a21????????????1?an1?
?a22???????1?an2a1n???a2n???????ann???6
下面证明??1,用反证法.
假设??1,由0???1可知A和H的对应元素一定同时为0或非0.由引理1知,A不可约推出H也不可约.
下面比较?和?????1的大小. ①当??1时,
???????1???????1??1???????1??1????1??1????0
②当???1时,?1???1?0,
???????1????????1??????????1????1?????1????1??1???1??1?0由①、②知:当??1,0???1时,???????1.所以有:A为弱对角占优矩阵时,H也是弱对角占优矩阵；A为严格对角占优矩阵时,H也是严格对角占优矩阵.再由引理2,可以得到H为非退化的矩阵.从而,det?H??0.进而,det??E?B???0.这与?是B?的特征值矛盾,所以??1.进一步可得到
????B???1,我们就证明了(10)式表示的迭代格式收敛.
4.2 加权－对称超松弛迭代法
■
4.2.1 算法的建立
考虑SOR算法和4.1给出的新迭代算法,其实质都是给矩阵A分裂以后的因子一个权重后得到的,目的是使得迭代格式(4)的收敛速度尽可能快.按照这种思想,如果在SOR和SSOR迭代中引入一个参数?,就可以得到迭代格式
X(k?1)???BSORX(k)?fSOR???1????BSSORX(k)?fSSOR?,??[0,1] (11)
其中,BSOR,BSSOR分别为SOR迭代和SSOR迭代算法的迭代矩阵.此时的迭代矩阵B??BSOR??1???BSSOR.显然,当??0时,该算法即为SSOR迭代；当??1时,即为SOR迭代.
7
若迭代格式(11)收敛到某个向量X*,则有
X*???BSORX*?fSOR???1????BSSORX*?fSSOR?,??[0,1]
所以不管?在[0,1]内如何取值,当迭代格式(11)收敛时,它必定是原来方程
X?BX?f的解.选取适当的B,根据(4)式的定义,这样的解也是方程(1)的解.显
然我们可以选择一个较好的?,使得迭代格式(11)收敛的尽可能快.
已知SOR迭代的核心部分为:
fori?1:1:nx(k?1)i??1???x(k)i??bi??aijxaii?j?1??i?1(k?1)j?(k)? ax?ijj?j?i?1?nendSSOR迭代的核心部分为:
fori?1:1:nxendfori?n:?1:1xend将SOR迭代和SSOR迭代生成的向量进行加权平均,可得到改进的SSOR迭代算法,其核心部分为:
(k?1)i(k?1)i??1???x(k)i??bi??aijxaii?j?1??i?1(k?1)j?(k)?ax?ijj?j?i?1?n
(k)i??1???x??bi??aijxaii?j?1??i?1(k?1)j?(k)?ax?ijj?j?i?1?nfori?1:1:nx(k?1)i??1???x(k)i??bi??aijxaii?j?1??i?1(k?1)j?(k)?ax?ijj?j?i?1?nendfori?n:?1:1i?1n?(k?1)??(k)(k?1)?xi??1???xi??bi??aijxj??aijx(jk)?
aii?j?1j?i?1?endfori?1:1:nxiend其中,?为权重,可以取[0,1]之间的任意实数,在此称之为加权－超松弛迭代法.
4.2.2 收敛性分析
8
(k?1)?i(k?1)??xi(k?1)??1???x
