第五章迭代法51迭代过程的收敛性迭代加速

1、迭代法的思想迭代法的思想 压缩映像原理压缩映像原理 局部收敛性局部收敛性收敛性的阶收敛性的阶 求求 f (x) = 0 的根的根q 代数方程：代数方程： f (x) = a0 + a1x + . . . + anxn超越方程：超越方程： f (x) 含超越函数，如含超越函数，如 sin(x), ex, lnx 等等q 实根与复根实根与复根q 根的重数根的重数 f (x) = ( x x*)m g(x) 且且 g(x*) 0, 则则 x* 为为 f (x) 的的 m 重根重根q 有根区间：有根区间：a, b 上存在上存在 f (x) = 0 的一个实根的一个实根在在有根的前提下求出方程的的前提下

2、求出方程的近似根。研究研究 内容内容: (x) 的不动点的不动点x*f (x) = 0 x = (x) 称为迭代函数称为迭代函数等价变换等价变换p 基本思想基本思想从一个给定的初值从一个给定的初值 x0 出发，计算出发，计算 x1 = (x0), x2 = (x1), 若若 收敛，即存在收敛，即存在 x* 使得使得 ，则由，则由 的连续的连续性和性和 可得可得 x* = (x*)，即，即 x* 是是 的不的不动点，也就是动点，也就是 f (x) 的零点。的零点。 0kkx*limxxkk 1limlimkkkkxxp 具体做法：具体做法：不动点迭代f (x) 的零点的零点x*p 几何含义：几何

3、含义： 求曲线求曲线 y = (x) 与直线与直线 y = x 的交点的交点xk+1 = (xk)xyy = xxyy = xxyy = xxyy = xx*x*x*x*y= (x)y= (x)y= (x)y= (x)x0p0 x1p1x0p0 x1p1 x0p0 x1p1x0p0 x1p1x2 迭代公式迭代公式1：迭代公式迭代公式2：计算结果：计算结果：311kkxx131(1)kkxx2.3701.512512.341904kkx公式公式1：01.511.3572121.3308631.3258841.3249451.324761.324731.376724 2kkx公式公式2：怎么判断迭

4、代公式收敛或发散呢？怎么判断迭代公式收敛或发散呢？精确解精确解x* =1.3247179. 定理定理4.1设设 (x) Ca, b 且一阶导数连续，若且一阶导数连续，若(2) 0 L 1，使得，使得 | (x) | L 对对 x a, b 成立成立则函数则函数 f (x) = x - (x) 在在 a, b 中有中有唯一唯一的零点的零点 x*。(压缩映像原理，不动点原理压缩映像原理，不动点原理)x* 称为称为 (x) 的的不动 点 (x*) = x*(1) a (x) b 对一切对一切 x a, b 都成立都成立简证：简证：f(a) = a - (a) 0 , f(b) = b - (b) 0

5、f(x) 在在a, b 上有零点。上有零点。唯一性：反证法，假设存在唯一性：反证法，假设存在 x*, y* a, b 使得使得( *)( *)|( )|* xyxyxyL xyx* = (x*) y* = (y*)矛盾！矛盾！封闭性封闭性压缩性压缩性定理定理4.1设设 (x) Ca, b 且一阶导数连续，若且一阶导数连续，若(2) 0 L 1，使得，使得 | (x) | L 对对 x a, b 成立成立(1) a (x) b 对一切对一切 x a, b 都成立都成立则有则有(a) 对任意对任意 x0 a, b，由，由 xk+1 = (xk) 产生的迭代序列产生的迭代序列 均收敛到均收敛到 (x

6、) 在在 a, b 中的唯一不动点中的唯一不动点 x*。 0kkx(b) 有如下的误差估计有如下的误差估计11|*|1kkkxxxxL10|*|1kkLxxxxL可用可用| x k+1-xk | 来来控制收敛精控制收敛精 度度,L 越小收敛越快越小收敛越快. 后验估计后验估计:先验估计先验估计:证证: (a) 由压缩映像定理可知，不动点由压缩映像定理可知，不动点 x* 存在且唯一。存在且唯一。(b)1|*|*|kkxxL xx111|(*)(*)|*kkkkkkxxxxxxxxxx(1)*kL xx11*1kkkxxxxL1111|()()|( )| |kkkkkkkkxxxxxxL xx 又

7、又11101*111kkkkkkLLxxxxxxxxLLL111()( *)|( )| |*|*|*|kkkkxxxxxxxLx 2120|*|*|*|*|kkkkxxL xxLxxLxxlim|*|0kkxxlim*.kkxx即p 定理的条件保证了不动点迭代的定理的条件保证了不动点迭代的全局收敛性全局收敛性。即迭代的收敛性与初始点的选取无关。即迭代的收敛性与初始点的选取无关。p 这种在这种在 x* 的邻域内具有的收敛性称为的邻域内具有的收敛性称为局部收敛性局部收敛性。定理中的条件定理中的条件 | (x) | L 1 可以适当放宽可以适当放宽(2) (x) 在在 x* 的某个邻域内连续，且的某

8、个邻域内连续，且 | (x*) | 1由由 (x) 的连续性及的连续性及 | (x*) | 1 即可推出：即可推出：若若 (x)的一阶导数连续的一阶导数连续, 且满足条件且满足条件(2), 则一定存在则一定存在 x* 的的某个某个 邻域邻域 N(x*) =x*- , x* + , 使得对使得对 x N(x*)都有都有| (x) | L 1, 则由则由 x0 N(x*) 开始开始的迭代都收敛。的迭代都收敛。 具有局部收敛性的迭代计算上不一定收敛，它是否收敛还具有局部收敛性的迭代计算上不一定收敛，它是否收敛还要看初值是否取的恰当；要看初值是否取的恰当； 而不具有局部收敛性的迭代对任何初值都不可能收

9、敛。而不具有局部收敛性的迭代对任何初值都不可能收敛。定理定理4.2迭代公式迭代公式1：迭代公式迭代公式2：迭代公式迭代公式3：迭代公式迭代公式4：计算结果：计算结果：213kkkxxx 13/kkxx 怎么判断收敛的迭代公式的速度快慢呢？怎么判断收敛的迭代公式的速度快慢呢？321(3)/ 4kkkxxx 13)/ 2(/kkkxxx 0123123402222131.51.751.752921.7343751.7321433871.51.7323611.732051kkxxxxx方方法法方方法法方方法法方方法法31.7320508.精确值：设迭代设迭代 xk+1 = (xk) 收敛到收敛到 (

10、x) 的不动点的不动点 x*。记记 绝对误差绝对误差ek = xk x*，若若1lim0krkkeCe定义定义则称该迭代为则称该迭代为 r 阶收敛。(1) 当当 r =1 时称为时称为线性收敛，此时，此时 |C| 1 时称为时称为超线性收敛。p 不动点迭代中，若不动点迭代中，若 (x*) 0，且迭代收敛，则且迭代收敛，则11*()( *)( )kkkkexxxxe取极限得取极限得1lim( *)0kkkexe(C为常数为常数)线性收敛线性收敛.设迭代设迭代 xk+1 = (xk) ，若，若 (p)(x) 在在 x* 的某邻域内连续，的某邻域内连续，则该迭代法具有则该迭代法具有 p 阶收敛的充要

11、条件是阶收敛的充要条件是定理定理4.3(1)()( *)*,( *)( *)( *)0,( *)0ppxxxxxx()11lim( *)!pkpkkexep并且有并且有( )1()()( *)( *)(*).(*)!ppkkkkkxxxxxxxxp证明：充分性充分性. 根据泰勒展开有根据泰勒展开有( )1()*(*)!ppkkkxxxxp()11lim( *)!pkpkkexep必要性必要性(不证不证). 设迭代设迭代 xk+1 = (xk) 是是 p 阶收敛。阶收敛。迭代两边取极限迭代两边取极限 ，由，由 (x) 的连续性可知的连续性可知 x* = (x*) 。设设 p0 是满足是满足00(

12、1)()( *)( *)( *)0,( *)0 ppxxxx的最小正整数。的最小正整数。由充分性的证明过程可知迭代由充分性的证明过程可知迭代 p0 阶收敛。阶收敛。00111kkppppkkkeeeee又又若若 p0 p， 与迭代与迭代 p0 阶收敛矛盾阶收敛矛盾.p0 = p第二节第二节 迭代加速迭代加速p 设有不动点迭代：设有不动点迭代：1()kkxx 1*( )(*)()( *)kkkxxxxxx 11( )*( )kkxxx （ 在在 xk 和和 x* 之间）之间）设：设：( )()kx 11()*()kkkkxxxxx 11()()()kkkkkxxxxx 缺点缺点：每次迭代需计算每

13、次迭代需计算()kx 如何避免计算导数？如何避免计算导数？简化：简化：11()kkkxDxxD 设：设：*( )()( )xD 111()*kkkkxDxxDxxDD “迭代迭代-加速加速”格式格式迭代函数由迭代函数由 变为变为( )x 1( )( )xDxxD ( ) ( ), xxxx 等等价价于于 所以此格式定义合理。所以此格式定义合理。01( )( ),xDxD 故选择适当的故选择适当的D, 可能使可能使|( )| |( )|,xx 从而此迭代格式应该比原迭代格式的收敛速度从而此迭代格式应该比原迭代格式的收敛速度更快更快！ 1*()(*)kkkxxxx 设：设：1()()kk 121*kkkkxxxxxxxx Aitken 加速加速211*()(*)kkkxxxx 21212*kkkkkkxxxxxxx 21 2(),()kkkkkkkkkkkyxzyyxxxzyx 为了避免计算导数为了