34超松弛迭代法.pptVIP

第三章 线性方程组迭代解法 § 3.4超松弛迭代法(SOR) 一、SOR法迭代公式 例 用SOR法求解线性方程组 二、SOR法的收敛性 SOR法收敛与收敛速度有关定理 SOR法分类与现状 一、SOR法迭代公式 例3.3 用SOR法求解线性方程组 二、SOR法的收敛性 SOR法收敛与收敛速度有关定理 SOR法分类与现状 例3.7 讨论例3.3用SOR法的ω取值。 本章学习要点 本章学习要点 * * § 3.4 超松弛迭代法(SOR) SOR（Successive Over-Relaxation）法，即超松弛迭代法，是目前解大型线性方程组的一种常用的方法，是Gauss-Seidel迭代法的一种加速方法。 设线性方程组 AX=b 其中 A非奇异，且aii ? 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迭代法得到 (1) 选择参数ω，取 (2) 返回引用 把 式（1）代入式（2）即得SOR法 其中， ? 参数ω叫做松弛因子； ? 若 ω=1，它就是Gauss-Seidel迭代法。 返回引用 解 方程组的精确解为 x=(3,4,-5) T，为了进行比较，利用同一初值 x(0)=(1,1,1)T，分别取ω=1 (即Gauss-Seidel迭代法)和 ω=1.25两组算式同时求解方程组。 ①取ω=1 ，即Gauss-Seidel迭代： ②取ω=1.25 ，即SOR迭代法： 返回引用 迭代结果见表3.3。 表3.3 Gauss-Seidel迭代法与SOR迭代法比较 ? Gauss-Seidel迭代法 SOR迭代法(ω=1.25) k x1 x2 x3 x1 x2 x3 0 1.0000000 1.0000000 1.0000000 1.0000000 1.0000000 1.0000000 1 5.2500000 3.1825000 -5.0468750 6.3125000 3.9195313 -6.6501465 2 3.1406250 3.8828125 -5.0292969 2.6223145 3.9585266 -4.6004238 3 3.0878906 3.9267587 -5.0183105 3.1333027 4.0402646 -5.0966863 4 3.0549316 3.9542236 -5.0114410 2.9570512 4.0074838 -4.9734897 5 3.0343323 3.9713898 -5.0071526 3.0037211 4.0029250 -5.0057135 6 3.0214577 3.9821186 -5.0044703 2.9963276 4.0009262 -4.9982822 7 3.0134110 3.9888241 -5.0027940 3.0000498 4.0002586 -5.0003486 迭代法若要精确到七位小数， Gauss-Seidel迭代法需要34次迭代； 而用SOR迭代法(ω=1.25)，只需要14次迭代。 可见，若选好参数ω，SOR迭代法收敛速度会很快。 返回节 为了利用第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法迭代矩阵。 由定理3.1 及定理3.2直接得知： SOR法收敛的充要条件是ρ(Bω)1。 SOR法收敛的充分条件是 || Bω||1。 前面我们看到，SOR法收敛与否或收敛速度都与松弛因子ω有关，关于ω的范围，有如下定理。 定理3.5 设A∈Rn?n，满足a ii≠0 (i=1,2,??????,n),则有 ρ(Bω)≥ |1-ω| 。 推论 解线性方程组，SOR法收敛的必要条件是 |