计算方法--第3篇逐次逼近(基本迭代法的加速).pdfVIP

第3章 逐次逼近法 基本迭代法的加速 3.4 迭代法的加速 使用迭代法的困难所在是计算量难以估计。 有时迭代过程虽然收敛，但由于收敛速度缓慢，使 计算量变的很大而失去使用价值。 因此，迭代过程 的加速具有重要意义。 迭代法加速，就是要寻找 一种改进迭代法直接产生的序列的收敛速度的方法 ，使原来不收敛的序列变成收敛，使原来收敛较慢 的序列变得收敛快。 3.4.1 基本迭代法的加速 在3.1中介绍了线性方程组求解的Jacobi和Gauss-Seidel 基本迭代法，通过对基本迭代法加速可得其它迭代法。 一、超松弛法（SOR法） Gauss-Seidel法的迭代格式为： k +1 1 ⎛ i−1 k +1 n k ⎞ ( ) ( ) ( ) x ⎜b =−∑a x −∑a x ⎟ i i ij j ij j aii ⎝ j 1 j i+1 ⎠ （3-52 ） aii ≠0, i 1,2, L, n ( ) ( ) (k ) 如果将（3-52 ）的右端记为 x i k +1 ，并用x i k +1 和 x i 的 线性组合作迭代加速，得到 k k +1 ( ) ( ) k +1 1−ω x + ( ) ( ) i ωx i xi 1, 2n, , L i （3-53 ） 将（3-52 ）的右端代入（3-53 ），得 k +1 k ω ⎛ i−1 n ⎞ ( ) ( ) k +1 k x 1−ω x + b − a x( ) − i a x( )1,2n, , L 1,2k, , L i ( ) i ⎜ i ∑ ij j ∑ ij j ⎟ aii ⎝ j 1 j i+1 ⎠ 这就是逐次超松弛法，简称SOR法， ω称为松弛因子。SOR法的收敛速度与 ω 的取值有关，当 ω 1 时，它就是Gauss-Seidel法。 因此，可选取 ω 的值使 （3-55 ）的收敛速度较Gauss-Seidel法快，从而起到加速作用。 为了讨论 ω 的取值与收敛性的关系，特将（3-54 ）改写 成矩阵形式。 由（3-54 ）可得 ⎛ i−1 n ⎞ k +1