秦 算法1.2求解线性方程组的G-S迭代方法 1:Choose an initial guess (0) 2:while not converge do 3: for i=1 to n do 4: x+= 1 agt-,a j=+1 5: end for 6:end while G-S算法的主要优点是充分利用了已经获得的最新数据 但G-S算法中未知量的更新是按自然顺序进行的，不适合并行计算 http://math.ecnu.edu.cn/~jypan 16/86
算法 1.2 求解线性方程组的 GS 迭代方法 1: Choose an initial guess x (0) 2: while not converge do 3: for i = 1 to n do 4: x (k+1) i = 1 aii bi − i P−1 j=1 aijx (k+1) j − Pn j=i+1 aijx (k) j ! 5: end for 6: end while ✍ GS 算法的主要优点是充分利用了已经获得的最新数据 ✍ 但 GS 算法中未知量的更新是按自然顺序进行的, 不适合并行计算 http://math.ecnu.edu.cn/~jypan 16/86
秦 1.4sOR迭代 在G-S算法的基础上，我们可以通过引入一个松弛参数w来加快收敛速度.这 就是SOR(Successive Overrelaxation)算法： z(k+i)=(1-w)z()+w(D-I(Lz(k+1)+Ux()+D-1b). 整理后即为 x(k+1)=(D-wL)-1((1-w)D+wU)z()+w(D-wL)-1b, 其中w称为松弛参数 白注意，这里是对向量进行整体松弛，而不是对分量进行松弛 http://math.ecnu.edu.cn/-jypan 17/86
1.4 SOR 迭代 在 GS 算法的基础上, 我们可以通过引入一个松弛参数 ω 来加快收敛速度. 这 就是 SOR (Successive Overrelaxation) 算法: x (k+1) = (1 − ω)x (k) + ω D−1 (Lx(k+1) + Ux(k) ) + D−1 b . 整理后即为 x (k+1) = (D − ωL) −1 (1 − ω)D + ωU x (k) + ω(D − ωL) −1 b, 其中 ω 称为松弛参数. ✍ 注意, 这里是对向量进行整体松弛, 而不是对分量进行松弛. http://math.ecnu.edu.cn/~jypan 17/86
秦 (1)当w=1时，SOR即为G-S算法 (2)当w<1时，称为低松弛(under relaxation)算法， (3)当w>1时，称为超松池(over relaxation)算法. SO算法曾经在很长一段时间内是科学计算中求解大规模线性方程组 的首选方法 在大多数情况下，当ω>1时会取得比较好的收敛效果 http://math.ecnu.edu.cn/~jypan 18/86
(1) 当 ω = 1 时, SOR 即为 GS 算法, (2) 当 ω < 1 时, 称为低松弛 (under relaxation) 算法, (3) 当 ω > 1 时, 称为超松弛 (over relaxation) 算法. ✍ SOR 算法曾经在很长一段时间内是科学计算中求解大规模线性方程组 的首选方法. ✍ 在大多数情况下, 当 ω > 1 时会取得比较好的收敛效果. http://math.ecnu.edu.cn/~jypan 18/86
SOR的迭代矩阵为 秦 GSOR=(D-wL)-1((1-w)D+wU); 对应的矩阵分裂为 M=D-L,N=1-“D+U SOR迭代的分量形式为 -1 http://math.ecnu.edu.cn/~jypan 19/86
SOR 的迭代矩阵为 GSOR = (D − ωL) −1 ((1 − ω)D + ωU), 对应的矩阵分裂为 M = 1 ω D − L, N = 1 − ω ω D + U. SOR 迭代的分量形式为 x (k+1) i = (1 − ω)x (k) i + ω aii bi − X i−1 j=1 aijx (k+1) j − Xn j=i+1 aijx (k) j = x (k) i + ω aii bi − X i−1 j=1 aijx (k+1) j − Xn j=i aijx (k) j http://math.ecnu.edu.cn/~jypan 19/86
秦 算法1.3求解线性方程组的SOR迭代方法 1:Choose an initial guess (0)and parameterw 2:while not converge do 3: for i=1 to n do 4: w=0-2+品 -宫-盒） 5: end for 6:end while SOR算法最大的优点是引入了松弛参数w,通过选取适当的w可以大大 提高算法的收敛速度。 白 但是SOR算法最大的难点就是如何选取最优的参数. http://math.ecnu.edu.cn/~jypan 20/86
算法 1.3 求解线性方程组的 SOR 迭代方法 1: Choose an initial guess x (0) and parameter ω 2: while not converge do 3: for i = 1 to n do 4: x (k+1) i = (1 − ω)x (k) i + ω aii bi − i P−1 j=1 aijx (k+1) j − Pn j=i+1 aijx (k) j ! 5: end for 6: end while ✍ SOR 算法最大的优点是引入了松弛参数 ω, 通过选取适当的 ω 可以大大 提高算法的收敛速度. ✍ 但是 SOR 算法最大的难点就是如何选取最优的参数. http://math.ecnu.edu.cn/~jypan 20/86