数值分析：3-4超松弛迭代法

1、第三章第三章 线性方程组迭代解法线性方程组迭代解法 3.4 超松弛迭代法(SOR)超松弛超松弛迭代法迭代法(l一、一、SOR法迭代公式法迭代公式l例例 用用SOR法求解线性方程组法求解线性方程组l二、二、SOR法的收敛性法的收敛性lSOR法收敛与收敛速度有关定理法收敛与收敛速度有关定理lSOR法分类与现状法分类与现状 SOR（Successive Over-Relaxation）法，即超松弛迭代法超松弛迭代法，是目前解大型线性方程组的一种常用的方法常用的方法，是Gauss-Seidel迭代迭代法法的一种加速方法加速方法。 设线性方程组设线性方程组 AX=b其中其中 A非奇异，且非奇异，且aii

2、 0（i=1,2,n ） 。 如果已经得到第如果已经得到第k次迭代量次迭代量x (k) 及第及第k+1次迭代量次迭代量x (k+1) 的前的前i-1个个 分量分量 （x1 (k+1),x2 (k+1) ,xi-1 (k+1) )，在计算在计算xi (k+1) 时，先用时，先用Gauss-Seidel迭代法迭代法得到得到 iikjnijijkjijijikiaxaxabx/ )()1(11)1(1) 选择参数选择参数，取，取 )1()()1()1 (kikikixxx(2)返回引用返回引用把把 式（式（1 1）代入式（）代入式（2）即得）即得SOR法法i 1n(k 1)(k)(k 1)(k)ii

3、iijjijjj 1j i 1ii(0)(0)(0)(0) T12nx(1)xba xa x (i1,2,n)aX(x ,x ,x )(k 1,2,) 其中，其中， 参数参数叫做松弛因子；叫做松弛因子； 若若 =1，它就是，它就是Gauss-Seidel迭代法。迭代法。 返回引用返回引用 243024410143034321xxx解解 方程组的精确解为方程组的精确解为 x=(3,4,-5) T，为了进行比较为了进行比较，利用同利用同一初值一初值 x(0)(0)=(1,1,1)T，分别取分别取=1 (即即Gauss-Seidel迭代法迭代法)和和 =1.25两组算式同时求解方程组。两组算式同时求

4、解方程组。 取=1 ，即Gauss-Seidel迭代： 625. 05 . 725. 075. 0675. 0)1(2)1(3)(3)1(1)1(2)(2)1(1kkkkkkkxxxxxxx 取=1.25 ，即SOR迭代法： 5 . 725. 03125. 075. 93125. 025. 09375. 05 . 79375. 025. 0)(3)1(2)1(3)(3)(2)1(1)1(2)(2)(1)1(1kkkkkkkkkkxxxxxxxxxx返回引用 迭代结果见表3.3。 表3.3 Gauss-Seidel迭代法与SOR迭代法比较 Gauss-Seidel迭代法SOR迭代法(=1.25)

5、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.13330274.0402646-5.096686343.05493163.9542236-5.01144102.95705124.0074838-4.973489753.0

6、3433233.9713898-5.00715263.00372114.0029250-5.005713563.02145773.9821186-5.00447032.99632764.0009262-4.998282273.01341103.9888241-5.00279403.00004984.0002586-5.0003486 迭代法若要精确到七位小数，迭代法若要精确到七位小数，u Gauss-Seidel迭代法需要迭代法需要34次迭代；次迭代；u 而用而用SOR迭代法迭代法(=1.25)，只需要，只需要14次迭代。次迭代。 可见，若选好参数可见，若选好参数，SOR迭代法收敛速度会很迭代

7、法收敛速度会很快。快。返回节返回节 为了利用第为了利用第3节的收敛定理，要先给出节的收敛定理，要先给出SOR法的矩阵表达法的矩阵表达式。由式。由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、由定理由定理3.1 及定理及定理3.2直接得知：直接得知： (1)SOR法收敛的充要条件是法收敛的充要条件是(B)1。(2) SOR法收敛的充分条件是法收敛的充分条件是 | B|1。 前面我们看到，前面我们看到，SOR法收敛与否或收敛速度都法收敛与否或收敛速度都与松弛因子与松弛因子有关，关于有关，关于的范围，有如下定理。的范围，有如下定理。 SOR法收敛与收敛速度有关定理定理定理3.5 设设ARn n，满足，满足a ii0 (i=1,2,n),则有则有(B) |1-| 。 推论推论 解线性方程组，解线性方程组，SOR法收敛的必要条件是法收敛的必要条件是 |1-| 1 ，即，即 0 2。 定理定

9、理3.6 设设ARn n对称正定，且对称正定，且 02，则，则SOR法对任意法对任意 的初始向量的初始向量都收敛。都收敛。 nTnRxxxx ),()0()0(2)0(1)0( 由于定理由于定理3.4只是定理只是定理3.6的特殊情况，故定理的特殊情况，故定理3.4可以可以看作定理看作定理3.6的推论。的推论。 定理定理3.7 设设A是对称正定的三对角矩阵，则是对称正定的三对角矩阵，则(BG) =(BJ) 2 1 时，称为时，称为超松弛算法超松弛算法；(2)(2)当当1 时，称为时，称为亚松弛算法亚松弛算法。 目前还没有自动选择因子的一般方法，实目前还没有自动选择因子的一般方法，实际计算中，通常

10、取（际计算中，通常取（0, ,2）区间内几个不同的）区间内几个不同的值进行试算，通过比较后，确定比较理想的松弛值进行试算，通过比较后，确定比较理想的松弛因子因子。 243024410143034321xxx解 系数矩阵 025. 0025. 0075. 0075. 00410143034JBA625. 0)(JB由式（3-24）得 24. 1625. 0112)(1122JoptB根据定理3. 7，有(BG) =(BJ) 2 =0.625， (Bopt)= opt 1 = 0.24 , 可见采用SOR 方法比Jacobi迭代法和Gauss-Seidel迭代法快得多。 返回章返回章返回节返回节1

11、 Jacobi迭代法、迭代法、Gauss-Seidel迭代法和迭代法和SOR法法（1 1）迭代公式的分量形式、矩阵形式以及它们）迭代公式的分量形式、矩阵形式以及它们的迭代矩阵；的迭代矩阵； (2) (2) 线性方程组的系数矩阵为某些特殊情形下，线性方程组的系数矩阵为某些特殊情形下，Jacobi迭代法、迭代法、Gauss-Seidel迭代法的收敛性的重迭代法的收敛性的重要结论。要结论。 本章学习要点本章学习要点返回章返回章2 迭代法收敛性的判定定理和收敛速度迭代法收敛性的判定定理和收敛速度 (1) (1) 迭代法收敛的充要条件；迭代法收敛的充要条件； (2) (2) 从迭代矩阵的范数判别迭代法的收敛性；从迭