6.4超松弛迭代法

1、第六章 线性方程组迭代解法Numerical Analysis 6.4 超松弛迭代法(SOR)1 6.4超松弛迭代法(SOR)一、SOR法迭代公式例6.6 用SOR法求解线性方程组二、SOR法的收敛性SOR法收敛与收敛速度有关定理SOR法分类与现状 SOR（Successive Over-Relaxation）法，即超松弛迭代法，是目前解大型线性方程组的一种最常用的方法，是Gauss-Seidel迭代法的一种加速方法。 2一、SOR法迭代公式 设线性方程组 AX=b其中 A非奇异，且aii 0（i=1,2,n ） 。 如果已经得到第k次迭代量x (k) 及第k+1次迭代量x (k+1) 的前i

2、-1个 分量 （x1 (k+1),x2 (k+1) ,xi-1 (k+1) )，在计算xi (k+1) 时，先用Gauss-Seidel迭代法得到 (1) 选择参数，取 (2)返回引用3把 式（1）代入式（2）即得SOR法其中， 参数叫做松弛因子； 若 =1，它就是Gauss-Seidel迭代法。 返回引用4例6.6 用SOR法求解线性方程组 解 方程组的精确解为 x=(3,4,-5) T，为了进行比较，利用同一初值 x(0)=(1,1,1)T，分别取=1 (即Gauss-Seidel迭代法)和 =1.25两组算式同时求解方程组。 取=1 ，即Gauss-Seidel迭代： 取=1.25 ，即

3、SOR迭代法： 返回引用5 迭代结果见表6.3。 表6.3 Gauss-Seidel迭代法与SOR迭代法比较 Gauss-Seidel迭代法SOR迭代法(=1.25)kx1x2x3x1x2x301.00000001.00000001.00000001.00000001.00000001.000000015.25000003.1825000-5.04687506.31250003.9195313-6.650146523.14062503.8828125-5.02929692.62231453.9585266-4.600423833.08789063.9267587-5.01831053.1333

4、0274.0402646-5.096686343.05493163.9542236-5.01144102.95705124.0074838-4.973489753.03433233.9713898-5.00715263.00372114.0029250-5.005713563.02145773.9821186-5.00447032.99632764.0009262-4.998282273.01341103.9888241-5.00279403.00004984.0002586-5.00034866 迭代法若要精确到七位小数， Gauss-Seidel迭代法需要34次迭代； 而用SOR迭代法(=

5、1.25)，只需要14次迭代。 可见，若选好参数，SOR迭代法收敛速度会很快。返回节7二、SOR法的收敛性 为了利用第3节的收敛定理，要先给出SOR法的矩阵表达式。由式（2） 以及Gauss-Seidel迭代法的矩阵表达形式，可以看出 X(k+1) =(1-)X(k)+D-1(b+LX(k+1)+UX(k)DX(k+1) =(1-)DX(k)+(b+LX(k+1)+UX(k)）(D-L)X（k+1） =(1-)D+U X(k)+b解得 X(k+1) =(D-L)-1 (1-)D+U X(k)+(D-L)-1b (3) 记 B=(D-L)-1 (1-)D+U 称为SOR法迭代矩阵。 8 由定理6

6、.1 及定理6.2直接得知： SOR法收敛的充要条件是(B)1。 SOR法收敛的充分条件是 | B|1。 前面我们看到，SOR法收敛与否或收敛速度都与松弛因子有关，关于的范围，有如下定理。 9SOR法收敛与收敛速度有关定理定理6.5 设ARnn，满足a ii0 (i=1,2,n),则有(B) |1-| 。 推论 解线性方程组，SOR法收敛的必要条件是 |1-| 1 ，即 0 2。 定理6.6 设ARnn对称正定，且 02，则SOR法对任意 的初始向量都收敛。 由于定理6.4只是定理6.6的特殊情况，故定理6.4可以看作定理6.6的推论。 10定理6.7 设A是对称正定的三对角矩阵，则(BG)

7、=(BJ) 2 1 时，称为超松弛算法；当1 时，称为亚松弛算法。 目前还没有自动选择因子的一般方法，实际计算中，通常取（0,2）区间内几个不同的值进行试算，通过比较后，确定比较理想的松弛因子。 12例6.7 讨论例6.6用SOR法的取值。 解 系数矩阵 由式（4）得 根据定理6. 7，有(BG) =(BJ) 2 =0.625， (Bopt)= opt 1 = 0.24 , 可见采用SOR 方法比Jacobi迭代法和Gauss-Seidel迭代法快得多。 返回章返回节131 Jacobi迭代法、Gauss-Seidel迭代法（和SOR法 简介）（1）计算公式分量形式、矩阵形式以及它们的迭 代矩阵表示； (2)线性方程组的系数矩阵为某些特殊情形下， Jacobi迭代法、Gauss-Seidel迭代法的收敛性 的重要结论。 本章学习要点返回章142 迭代法收敛性的判定定理和收敛速度 (1)迭代法收敛的充要条件； (2)从迭代矩阵的范数判别迭代法的收敛性及其证明； (3)线性方程组的系数