数以算 第六章逐次逼近法 §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)
Dx(+1)=Lx(k+1)+Ux()+b x(k+1)=D-1Lx(+1)+D1Ux()+D1b X (k) x()+D 1 Lx(k+1)+DUx +d b r=x X 第k+1次迭代时x的改变量 =-x()+D-1Lx(+1)+D1Ux()+D1b (5) (k+1 x+or 在r()前加上因子o (1-0o)x6)+o(D (k+1) td Ux (k) +D
( k ) ( k 1) ( k ) r = x - x + ( k 1) ( k ) ( k ) x = x +wr + Dx Lx Ux b k k k = + + ( +1) ( +1) ( ) x D Lx D Ux D b ( k +1) -1 ( k +1) -1 ( k ) -1 = + + x x D Lx D Ux D b ( k ) ( k ) -1 ( k +1) -1 ( k ) -1 = - + + + x D Lx D Ux D b ( k ) -1 ( k +1) -1 ( k ) -1 = - + + + (1 ) ( ) ( ) 1 ( 1) 1 ( ) 1 x D Lx D Ux D b k - k + - k - = -w +w + + ------(5) 第k + 1次迭代时 x的改变量 在 前加上因子 w ( k ) r
Dx+1)=(1-0)Dx(6)+0(Lx(k+ +C(k) tb (D-oL)x+)=(1-0)D+0U)x6)+0b x(+1)=(D-OL)(1-0)D+0U)x)+0(D-OL)1b--( B=(D-oL)(1-0)D+U/) f=0(D-0L)b B (k) x+ 上式为逐次超松弛法(SOR迭代法)的矩阵形式 Bn为SOR法的迭代矩阵
(1 ) ( ) ( 1) ( ) ( 1) ( ) Dx Dx Lx Ux b k k k k = - + + + + + w w D L x D U x b k k -w = -w +w +w ( +1) ( ) ( ) ((1 ) ) x D L D U x D L b ( k 1) 1 ( k ) 1 ( ) ((1 ) ) ( ) + - - = -w -w +w +w -w ----(6) 上式为逐次超松弛法(SOR迭代法)的矩阵形式 ( ) ((1 ) ) 1 Bw = D -wL -w D +wU - f D L b 1 ( ) - w = w -w 令 w w x B x f k k = + ( +1) ( ) ----(7) Bw为SOR法的迭代矩阵
当O=1时,SOR法化为 x(+)=(D-)Ux()+(D-1)2bGS迭代法 G-S法为SOR法的特例,SOR法为G-S法的加速 例1.用G-S法和SOR法求下列方程组的解,取ω=1.45 4 2-1 24 认\分 0 1-23 x 要求精度1e6
当w = 1时, SOR法化为 x D L Ux D L b ( k 1) 1 ( k ) 1 ( ) ( ) + - - = - + - G-S迭代法 G-S法为SOR法的特例, SOR法为G-S法的加速 例1. 用G-S法和SOR法求下列方程组的解, 取w = 1.45 ÷ ÷ ÷ ø ö ç ç ç è æ - - - - - - 1 2 3 2 4 2 4 2 1 ÷ ÷ ÷ ø ö ç ç ç è æ 3 2 1 x x x ÷ ÷ ÷ ø ö ç ç ç è æ = - 3 2 0 要求精度1e-6
解:(1)GS迭代法 40 BG =(d-LU 24 003 02 120 00.50.25 00.250.625 01/30.5 400 0 f=(d-l)b 240 2 0.5 1-23(3 2/3
解: (1)G-S迭代法 BG D L U 1 ( ) - = - 1 1 2 3 2 4 0 4 0 0 - ÷ ÷ ÷ ø ö ç ç ç è æ - - = - ÷ ÷ ÷ ø ö ç ç ç è æ 0 0 0 0 0 2 0 2 1 ÷ ÷ ÷ ø ö ç ç ç è æ = 0 1/3 0.5 0 0.25 0.625 0 0.5 0.25 f D L b 1 ( ) - = - 1 1 2 3 2 4 0 4 0 0 - ÷ ÷ ÷ ø ö ç ç ç è æ - - = - ÷ ÷ ÷ ø ö ç ç ç è æ - 3 2 0 ÷ ÷ ÷ ø ö ç ç ç è æ = - 2 /3 0.5 0
取初值xO=(0.0,0) gauss seidel.m Ix, k=gauss seidel(a, b,L1, 1,Ile-6) 满足精度的解 0.75000000.37500001.5000000 0.56250000.53125001.5416667 0.999995 0.65104170.59635421.6145833 0.999994 0.70182290.65820311.6727431 1.999995 0.99999330999992319999926 0.999309395999迭选达代次数为71次 0.99999520.999994419999946
(0,0, )' 取初值x (0) = ０ gauss_seidel.m [x,k]=gauss_seidel(a,b,[1,1,1]',1e-6) 1 1 1 0.7500000 0.3750000 1.5000000 0.5625000 0.5312500 1.5416667 0.6510417 0.5963542 1.6145833 0.7018229 0.6582031 1.6727431 ……………………………………… . 0.9999933 0.9999923 1.9999926 0.9999943 0.9999935 1.9999937 0.9999952 0.9999944 1.9999946 k = 71 x= 0.999995 0.999994 1.999995 满足精度的解 迭代次数为71次