不动点迭代法及其加速技术

1、迭代法的加速二、二、Aitken加速法加速法一、待定参数法一、待定参数法 /* accelerating convergence */若若 | g(x) | 1，则将则将 x = g(x) 等价地改造为等价地改造为)()()1()(xxKgxKxKgKxxx 1|)(1|)(| xgKKx 求求K，使得，使得一、待定参数法一、待定参数法例：例：求求 在在 (1, 2) 的实根。的实根。013)(3 xxxf如果用如果用 进行迭代，则在进行迭代，则在(1, 2)中有中有)()1(313xgxx 1| )(|2 xxg现令现令)1(3)1()()1()(3 xKxKxKgxKx 希望希望1|1|

2、)(|2 KxKx 0122 Kx，即，即在在 (1, 2) 上可取任意上可取任意 ，例如，例如K = 0.5，则对应则对应 即产生收敛序即产生收敛序列。列。032 K)1(61233 xxx设设 xk 是根是根 x* * 的某个预测值，用迭代公的某个预测值，用迭代公式校正一次得：式校正一次得：)(1kkxgx 假设假设 在所考虑范围内改变不大，在所考虑范围内改变不大，其估计值为其估计值为L L，则有，则有)(xg 二、二、Aitken加速法加速法)()(1 xgxgxxkk)()(1 xgxgxxkk)(12 kkxgx)(1 xxLk)( xxLk xxk 2相相除除将将 再校正一次，再校

3、正一次，1 kx xxxxxxxxkkkk121所以所以kkkkkkkkkkkkxxxxxxxxxxxxx 1221122212)(2)( Aitken 加速：加速：xyy = xy = g(x)x*x0P(x0, x1)x1x2x P(x1, x2)21020102)(xxxxxxx 一般地，有：一般地，有：21212)( KKKKKKKxxxxxxx.),(,),(,),(),(,34123012010 xgxxxgxxxgxxgxx 比比 收敛收敛得略快。得略快。 Kx KxNewton 迭代法迭代法将将f(x)f(x)在点在点xn作作TaylorTaylor展开展开: : )( )(

4、)()()(! 2)()( )( )()(2nnnnnnnnxxxfxfxfxxxfxxxfxfxf TaylorTaylor展开线性化展开线性化f(x)=0 近似于近似于 f(xn)+ f(xn)(x-xn)=0 (1)从从(1)解出解出x, 记为记为xn+1 , ,则则1() (n0,1,.) (2)()nnnnf xxxfx它对应的迭代方程为 显然是f(x)=0的同解方程，故其迭代函数为 在 f(x)=0的根 x* 的某个邻域 内, 在 x* 的邻域R 内，对任意初值 ，应用应用公式（2）来解方程的方法就称为来解方程的方法就称为牛顿迭代法牛顿迭代法。它。它是解代数方程和超越方程的有效方法

5、之一是解代数方程和超越方程的有效方法之一.)(xR0)(xf0 x)()()(xfxfxx1)()()()(2 Lxfxfxfx)()(xfxfxx)0)( xf )()( )(nnnxxxfxfy 与与x轴轴(y=0)的交点的交点x,x,作为下一个迭代点作为下一个迭代点xn+1 , ,即即 )( )(1nnnnxfxfxx 用用f(x)f(x)在在 xn 处处的切线的切线Newton迭代法又称切线法迭代法又称切线法.用用NewtonNewton迭代法求下面方程的一个正根迭代法求下面方程的一个正根, ,计计算结果精确到算结果精确到7 7位小数位小数. .02010223 xxx322 ( )2

6、1020,(0)200,(2)160.0,2 , ( ) 34x 100, ( )6404.2. f xxxxfffxxfxx 设在上满足定理的条件由由NewtonNewton迭代法迭代法)()(1kkkkxfxfxx322210203410kkkkkkxxxxxx 由由NewtonNewton迭代法迭代法 得得取取初初值值,x2020 x1 1 = 1.4666667 ,x4 4 = 1.3688081x5 5 = 1.3688081迭代迭代5 5次次精度达精度达10-7x* * 1.3688081kx*x)( xfy kx（1）Newton迭代公式在单根情况下至少迭代公式在单根情况下至少2

7、阶收敛阶收敛; （2） 设设 f(x*)=0, ,且在且在 x* 的邻域的邻域 上上 存在存在, 连续连续, 则可得则可得( *)0fxf*1* 2*()()()2()limnnnxxfxcxxfx将将f(x)在在 xn 处作处作2阶阶Taylor展开展开,并将解并将解x*代入代入212222* 20 )x*x()x( f)(fx)x*x()x( f)(f)x( f)x(fxx)x*x(!)(f)x*x)(x( f)x(f*)x(fnnnnnnnnnnnnnnn 注意到注意到 n n 在在xn 及及x*之间之间,及及 , 故故*xxnnlim 所以，所以，Newton法至少二阶收敛法至少二阶收

8、敛. )x( f)x(f)x( f)(fxxxx*nn*n*n2221*0()()00()()0fxfx二阶收敛 若大于二阶收敛 若21222* )x*x()x( f)(fx)x*x()x( f)(f)x( f)x(fxxnnnnnnnnnn 注意到注意到 n n 在在xn 及及x*之间之间,及及 ,故故*xxnnlim 1|*|lim (0)*|npnnxxccxx*1* 2*()()lim()2()kxkxxfxxxfx例3.证明迭代法重根的是方程设,)2(0)(*mxfx)()(1kkkkxfxfxx为线性收敛证明:故重根的是方程因为,0)(*mxfx)(*)()(xgxxxfm2,0*

9、)(mxg且所以)(xf )(*)()(*)(1xgxxxgxxmmm)(*)()(*)()(*)(1kmkkmkkmkkxgxxxgxxmxgxxx)()(1kkkkxfxfxx)(*)()()(*)(kkkkkkxgxxxmgxgxxx*1xxk)(*)()()(1*)(kkkkkxgxxxmgxgxx*lim1xxxxkkk)(*)()()(1(limkkkkkxgxxxmgxgm11011 ,2mm时重根是线性收敛的该迭代法对)2(m例4.证明迭代法且设,0)(,0)(afaf)()(1kkkkxfxfxx至少是平方收敛的由定义1注意例4与例3的迭代法是相同的,两例有何区别?证明:令)

10、()()(xfxfxx)(x则22)()()()(1xfxfxfxf 2)()()(xfxfxf 0)( a所以由定理2该迭代法至少是平方收敛的 Newton迭代公式是一种特殊的不动点迭代迭代公式是一种特殊的不动点迭代,其其迭代矩阵为迭代矩阵为: Newton迭代是局部线性化方法迭代是局部线性化方法,它在单根附近它在单根附近具有较高的收敛速度具有较高的收敛速度. 方法有效前提方法有效前提: ( )( )( )f xxxfx()0kfx开方公式开方公式 对于给定正数 应用牛顿迭代法解二次方程可导出求开方值 的计算公式 设 是 的某个近似值，则 自然也是一个近似值，上式表明，它们两者的算术平均值将

11、是更好的近似值。 定理定理 开方公式对于任意给定的初值开方公式对于任意给定的初值 均为均为平方收敛。平方收敛。 ckxc20 xc112kkkcxxxc/kc x00 x 牛顿迭代法的优缺点牛顿迭代法的优缺点 优点：优点： 在单根附近在单根附近, 牛顿迭代法具有平方收敛的速牛顿迭代法具有平方收敛的速 度，所以在迭代过程中只要迭代几次就会得到很精度，所以在迭代过程中只要迭代几次就会得到很精 确解确解。 缺点缺点:1. 重根情形下为局部线性收敛重根情形下为局部线性收敛; 2. 牛顿迭代法计算量比较大牛顿迭代法计算量比较大:因每次迭代除因每次迭代除 计算函数值外还要计算微商值计算函数值外还要计算微商

12、值; 3. 选定的初值要接近方程的解，否则有可能得选定的初值要接近方程的解，否则有可能得 不到收敛的结果不到收敛的结果;牛顿迭代法的改进牛顿迭代法的改进缺点克服缺点克服: 1. 局部线性收敛局部线性收敛-改进公式或加速改进公式或加速 2.每步都要每步都要计算微商值计算微商值-简化简化Newton迭代法迭代法 或弦截法或弦截法 3. 初值近似问题初值近似问题-二分法求初值或二分法求初值或”下山算法下山算法”方法一方法一. 若已知重数m(m1),则利用m构造新的迭代公式: 此时, , 至少2阶收敛. 不实用: m往往不确定.方法二方法二. 取 ,再对函数F(x)用Newton迭代:此时,X*为F(

13、x)的单根,所以是2阶收敛. 但要用到二阶导数.1()()kkkkf xxxmfx( )*( )( ),()0f xfxxxmx( )( )( )f xF xfx12()()()()()()()kkkkkkkkkkF xf xfxxxxF xfxf xfx)()(1kkkkxfxfxxNewtonNewton迭代法迭代法需要求每个迭代点处的导数需要求每个迭代点处的导数 f (xk)复杂！复杂！得中的近似替代用,)(0kkxxfx)()(01xfxfxxkkk这种格式称为这种格式称为简化简化NewtonNewton迭代法迭代法精度稍低精度稍低则则NewtonNewton迭代法变为迭代法变为)()

14、()()(111kkkkkkkxxxfxfxfxx这种格式称为这种格式称为弦截法弦截法收敛阶约为收敛阶约为1.6181.618)(kxf 如果用数值导数代替11)()()(kkkkkxxxfxfxf用简化用简化Newton法和弦截法解下面方程的根，并和法和弦截法解下面方程的根，并和Newton 迭代法比较迭代法比较0133xx13)(3xxxf设33)(2xxf由简化由简化Newton法法)()(01xfxfxxkkk3313203xxxxkkk由弦截法由弦截法)()()()(111kkkkkkkxxxfxfxfxx由由Newton迭代法迭代法)()(1kkkkxfxfxx331323kkkk

15、xxxxx0= 0.5x1= 0.3333333333x2 = 0.3497942387x3 = 0.3468683325x4 = 0.3473702799x5 = 0.3472836048x6 = 0.3472985550 x7 = 0.3472959759x8 = 0.3472964208x9 = 0.3472963440 x10 = 0.3472963572x11 = 0.3472963553x0=0.5;x1=0.4;x2 = 0.3430962343x3 = 0.3473897274x4 = 0.3472965093x5 = 0.3472963553x6 = 0.3472963553

16、简化简化Newton法法由弦截法由弦截法要达到精度要达到精度10-8 简化简化Newton法迭代法迭代11次次弦截法迭代弦截法迭代5次次Newton迭代法迭代迭代法迭代4次次x0 =0.5;x1 =0.3333333333x2 =0.3472222222x3 =0.3472963532x4 =0.3472963553由由Newton迭代法迭代法无论哪种迭代法：无论哪种迭代法：NewtonNewton迭代法迭代法简化简化NewtonNewton法法弦截法弦截法00 *x,)xarctan()x(f精精确确解解用用NewtonNewton迭代法求解迭代法求解: :)1(arctan21kkkkxx

17、xxx0 = 2x1 = -3.54x2 = 13.95x3 = -279.34x4 = 122017是否收敛均与初值的位置有关是否收敛均与初值的位置有关. .20 x若若取取初初值值x0 =1x1 = -0.5708x2 = 0.1169x3 = -0.0011x4 = 7.963110-10 x5 = 0收敛收敛发散发散10 x若若取取初初值值牛顿下山法牛顿下山法 一般地说，牛顿法的收敛性依赖于初值 的选取，如果 偏离 较远，则牛顿法可能发散。 为了防止发散，通常对迭代过程再附加一项要求，即保证函数值单调下降： 满足这项要求的算法称为下山法下山法。 牛顿下山法牛顿下山法采用以下迭代公式：其

18、中 称为下山因子。 1kkf xf x011kkkkfxxxfx0 x0 x*x牛顿下山法只有线性收敛牛顿下山法只有线性收敛.的选取方式的顺序，按322121211成立为止直到|)(|)(|1kkxfxf例7.30( )0,0.993xf xxx 求解方程取初值5110|nnxx解:1.先用Newton迭代法1)(2xxf)()(1kkkkxfxfxx)1(3323kkkkxxxx)1(332003001xxxxx50598.32)1(332113112xxxxx69118.2115689.15x4 = 9.70724 x5 = 6.54091 x6 = 4.46497 x7 = 3.13384 x8 = 2.32607 x9 = 1.90230 x10= 1.75248x11= 1.73240 x12= 1.73205x13= 1.73205)1(332223223xxxxx迭代13次才达到精度要求2.用Newton下山法,结果如下k=0 x0 =-0.99