计算方法--第3章逐次逼近(基本迭代法的加速).pdf
文本预览下载声明
第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
显示全部