数以算 第六章逐次逼近法 §65迭代法的加速
第六章 逐次逼近法 §6.5 迭代法的加速
§65迭代法的加速 无论是解线性方程组的 Jacobi迭代法和GS迭代法 还是解非线性方程 Newton系列迭代法 都涉及到收敛速度问题 也涉及到初值的选取问题 如何加快迭代法的速度呢? 如何改善迭代法的适用范围呢?
§6.5 迭代法的加速 无论是解线性方程组的Jacobi迭代法和G— S迭代法 还是解非线性方程Newton系列迭代法 都涉及到收敛速度问题 如何加快迭代法的速度呢？ 也涉及到初值的选取问题 如何改善迭代法的适用范围呢？
线性方程组迭代法的加速 考虑解线性方程组的 Gauss-Seideli迭代法 (k+1) ∑anx+1--∑ (k x:+ ii=i+1 (k+1) 1 b-∑ k (k+1) 1 ∑ ax:+x (k) 1 x/)+-(b (k+1) (k) a::X a::X j=1
i ii n j i k ij j ii i j k ij j ii k i b a a x a a x a x 1 1 1 1 ( ) 1 1 ( 1 ) ( 1 ) = - å - å + = + - = + + 一、线性方程组迭代法的加速 考虑解线性方程组的Gauss-Seidel迭代法 å å= + - = + = - - n j i k ij j ii i j k ij j ii i ii a x a a x a b a 1 ( ) 1 1 1 1 ( 1 ) 1 ( ) ( ) 1 1 1 1 ( 1 ) 1 k i n j i k ij j ii i j k ij j ii i ii a x x a a x a b a = - å - å + = - = + ( ) 1 ( ) 1 1 ( ) ( 1 ) å å= - = + = + - - n j i k ij j i j k i ij j ii k i b a x a x a x ------(1)
令 (k) (k+1) (k) (b (k+1) -(2 r()为第k+1次迭代时x的改变量 因此 (k+1 =x(k)+k) 在改变量r)前加一个因子o,(0<0<2)得 (k+1) (k)+07 ck) x:+ /=1(k+1) ∑a1x()
令 ( ) ( 1 ) ( k ) i k i k i r = x - x + ( ) 1 ( ) 1 1 ( 1 ) å å= - = + = - - n j i k ij j i j k i ij j ii b a x a x a ri ( k )为第 k + 1次迭代时 x的改变量 ( 1 ) ( ) ( k ) i k i k i x = x + r 因此 + 在改变量 ri ( k )前加一个因子 w ,(0 < w < 2 ),得 ( 1 ) ( ) ( k ) i k i k i x = x + wr + ( ) ( ) 1 1 ( ) ( 1 ) å å= - = + = + - - n j i k ij j i j k i ij j ii k i b a x a x a x w ------(2)
在上式中合并x(),得 (k+1) (k) 1-)x()+ (b (k+1) ∑anx() +1 i=1,2…n,k=0,1,2, (3) 上式称为逐次超松弛法(OR迭代法O称为松弛因子 由G-S迭代法的矩阵形式 (k+1) BGx)+fG -(4 =(D-)x6)+(D-L)b (D-L)(+D)=Ux )+b
在上式中合并 xi ( k ) ,得 (1 ) ( ) 1 ( ) 1 1 ( 1 ) ( ) ( 1 ) å å= + - = + + = - + - - n j i k ij j i j k i ij j ii k i k i b a x a x a x x w w i = 1,2 ,L n , k = 0,1,2 ,L ------(3) 上式称为逐次超松弛法(SOR迭代法), w称为松弛因子 G k G k x = B x + f ( +1) ( ) D L Ux D L b 1 ( k ) 1 ( ) ( ) - - = - + - D L x Ux b k k - = + ( +1) ( ) ( ) 由G-S迭代法的矩阵形式 ------(4)