定理4.2 加权－超松弛迭代算法,满足迭代关系式(4),其迭代矩阵
B??BSOR??1???BSSOR.
其中,
BSOR??D??L????1???D??U??
?1BSSOR??D??U?D?D??L????1???D??L??D???1???D??U??
?1?1?1且(11)对任意的初始向量都收敛的充要条件为??B??1.
证明:由4.2.1中的分析知该定理结论显然成立. ■
5.算法的不足与改进方法
上述两种算法本质上都是添加了一个加权因子,不同之处在于一个是对分裂
后的矩阵添加的,而另一个是对迭代矩阵添加的.增加了加权因子之后,如何对其取值才最合理就变成了一个亟需解决的问题.像SOR算法中很难确定?的值一样,我们很难找到一种通用的方法来确定所增加的加权因子的值.在下面的数值实例中,为了验证算法的优越性,我们可以让加权因子?遍取[0,1]中的某些值,通过MATLAB编程搜索出迭代次数最少时?的取值.但是在解决实际问题时如果仍这样做,不但不能减少迭代的总次数,反而是增加了计算机的工作量和解决问题所需要的时间.
下面提供一种解决实际问题时加权因子?值的确定方法:(1)给定某个迭代次数n,搜索出迭代n次后解的精度最小的那个?的值；（2）用（1）中?的值作为加权因子的值求解线性方程组的指定精度的解.
6.数值实例
6.1渐进收敛速度
为方便比较和表述用不同的迭代方法解线性方程组时的收敛速度,我们引入下述定义.
定义6.1[5]称
Rk?B???lnB为迭代法X(k)?BX(k?1)?f的平均收敛率.
1kk
此处定义的是平均压缩率的对数值(再取负号),它依赖于所选择的范数和迭代次数,使用起来非常不便.由于
limBk??1kk???B?
则再给出下面的定义:
定义6.2[5]称
R?B???ln??B?
为迭代法的渐进收敛速度,简称迭代法的收敛速度.
9
6.2几种迭代方法的比较
下面我们用不同的迭代方法求解n元线性方程组Ax?b,其中
?4?1??3??????14?1???2??,b????. A??????????14?1???2???3??14?????方程的精确解为x*??1,1,?,1?.取n?10,初始向量x(0)为零向量.下表给出了几种迭代方法达到不同精度时所需的迭代次数.(程序见附录)
表1 不同的迭代算法达到某一精度时所需迭代次数的比较 T算法 参数值 迭代次数 精度 21 Jacobi迭代法 \\ 13 Gauss-Seidel迭代法 \\ ??1.2 15 SOR算法 1?10?6 ??1.2 8 SSOR算法 ??0.89 13 4.1中的算法 ??1.2,r?0.02 7 4.2中的算法 27 Jacobi迭代法 \\ 17 Gauss-Seidel迭代法 \\ ??1.2 17 SOR算法 1?10?8 ??1.2 10 SSOR算法 ??0.96 16 4.1中的算法 ??1.2,r?0.13 8 4.2中的算法 由上表可以看到,若合理的选取参数值,解系数矩阵为三对角矩阵的线性方程组时,4.2中提供的方法收敛速度最快.根据6.2的定义,我们算出精度为1?10?8时各种迭代算法的渐进收敛速度,见表2. (程序见附录)
表2 精度为1?10时各种迭代算法的渐进收敛速度
?8算法 Jacobi迭代法 Gauss-Seidel迭代法 SOR算法 SSOR算法 4.1中的算法 4.2中的算法 渐进收敛速度 0.7345 1.4690 1.6094 1.9171 1.3595 2.0020 结合表1与表2,我们可以看到:当迭代结果的精度达到1?10?8时,表1显示的Jacobi迭代法、Gauss-Seidel迭代法、SOR算法、SSOR算法和对称－超松弛迭代算法所需的迭代次数逐渐减少,4.2中给出的方法是收敛最快的,这与表2中
10
给出的其渐进收敛速度逐渐变大的结果一致.我们还可以看到,用4.1中的算法进行计算所需的迭代次数较SSOR方法的迭代次数多,但由定义6.2计算出的其渐进收敛速度却较小,这说明用该定义意义下的范数去度量4.1中的算法的收敛速度,并不是一个好的度量方式.
考虑方程组
?101??x1??5???????-110x??7???2??? ?12?3??x???17????3???其精确解为?2,?5,3?.求出各种迭代方法的迭代矩阵B对应的谱半径??B?,可以看到只有Jacobi迭代法和4.1中的算法是收敛的,其他方法均发散.下面我们比
较Jacobi迭代法和4.1中的算法在达到指定精度时的收敛次数,见表3.(程序见附录)
表3 两种迭代法达到指定精度所需迭代次数的比较
T参数 迭代次数/次 Jacobi迭代法 4.1中的算法 Jacobi迭代法 4.1中的算法 0.86 212 15 10-5 \\ 0.84 253 19 10-6 \\ 0.85 293 21 10-7 \\ 0.86 333 22 10-8 \\ 0.87 374 24 10-9 \\ 我们可以看到4.1中给出的方法解该方程组的收敛速度远远大于Jacobi迭代法. 精度 参考文献
[1] 张韵华,奚梅成,陈效群,数值计算方法与算法[M].北京:科学出版社,2009: 130-140.
[2] 邵新慧,大型线性方程组的迭代解法[J].东北大学博士学论文,2009. [3] 李大明,数值线性代数[M].北京:清华大学出版社,2010:177-192.
[4] 余德浩,汤华中.微分方程数值解法[M].北京:科学出版社,2004:320-328. [5] 薛毅,数值分析与实验[M].北京:北京工业大学出版社,2005:88-93. [6] 马云,数值分析中的迭代法解线性方程组[J].考试周刊,2010:71-72.
[7] 段班祥,吴教育,朱小平,非线性互补问题的改进超松弛迭代算法[J].江西师范大学学报.2009,33(5):617-621.
[8] 蒋家羚,王勇,最优超松弛因子的一种确定方法及其在裂纹计算中的应用[J].机械强度,2002,24(1):133-135.
[9] 郑亚敏,迭代法解线性方程组的收敛性比较[J].江西科学.2009.10: 659-661.
[10] 谢刚,不定线性方程组的一种迭代算法[J].科学技术与工程.2007.第7卷,第14期.
[11] 张步林,线性代数方程组迭代解法的MATLAB实现[J].成都纺织高等专科
11
学校学报,2008.10:45-47.
[12] 李春光,徐成贤,确定SOR最佳松弛因子的一个实用算法[J].计算力学学报.2002.8:299-302.
[13] 曾闽丽,加权-对称超松弛算法[J].莆田学院院报,2008.4,第15卷,第2期. [14] 周荣富,蔡治亚,关于超松弛迭代法收敛的一个判别准则[J].1991.6.第6卷.第2期.
[15] 唐永建,向隆万,最佳双松弛因子迭代法的存在条件[J].上海电力学院学报,第17卷,第1期.
[16] 高虹霓,曹泽阳,一种新的非线性方程求根迭代法[J].空军工程大学学报,2002.4.第3卷,第2期.
12
