不動(dòng)點(diǎn)迭代法及其加速技術(shù)

1、迭代法的加速二、二、Aitken加速法加速法一、待定參數(shù)法一、待定參數(shù)法 /* accelerating convergence */若若 | g(x) | 1，則將則將 x = g(x) 等價(jià)地改造為等價(jià)地改造為)()()1()(xxKgxKxKgKxxx 1|)(1|)(| xgKKx 求求K，使得，使得一、待定參數(shù)法一、待定參數(shù)法例：例：求求 在在 (1, 2) 的實(shí)根。的實(shí)根。013)(3 xxxf如果用如果用 進(jìn)行迭代，則在進(jìn)行迭代，則在(1, 2)中有中有)()1(313xgxx 1| )(|2 xxg現(xiàn)令現(xiàn)令)1(3)1()()1()(3 xKxKxKgxKx 希望希望1|1|

2、)(|2 KxKx 0122 Kx，即，即在在 (1, 2) 上可取任意上可取任意 ，例如，例如K = 0.5，則對(duì)應(yīng)則對(duì)應(yīng) 即產(chǎn)生收斂序即產(chǎn)生收斂序列。列。032 K)1(61233 xxx設(shè)設(shè) xk 是根是根 x* * 的某個(gè)預(yù)測值，用迭代公的某個(gè)預(yù)測值，用迭代公式校正一次得：式校正一次得：)(1kkxgx 假設(shè)假設(shè) 在所考慮范圍內(nèi)改變不大，在所考慮范圍內(nèi)改變不大，其估計(jì)值為其估計(jì)值為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)在點(diǎn)在點(diǎn)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它對(duì)應(yīng)的迭代方程為 顯然是f(x)=0的同解方程，故其迭代函數(shù)為 在 f(x)=0的根 x* 的某個(gè)鄰域 內(nèi), 在 x* 的鄰域R 內(nèi)，對(duì)任意初值 ，應(yīng)用應(yīng)用公式（2）來解方程的方法就稱為來解方程的方法就稱為牛頓迭代法牛頓迭代法。它。它是解代數(shù)方程和超越方程的有效方法

5、之一是解代數(shù)方程和超越方程的有效方法之一.)(xR0)(xf0 x)()()(xfxfxx1)()()()(2 Lxfxfxfx)()(xfxfxx)0)( xf )()( )(nnnxxxfxfy 與與x軸軸(y=0)的交點(diǎn)的交點(diǎn)x,x,作為下一個(gè)迭代點(diǎn)作為下一個(gè)迭代點(diǎn)xn+1 , ,即即 )( )(1nnnnxfxfxx 用用f(x)f(x)在在 xn 處處的切線的切線Newton迭代法又稱切線法迭代法又稱切線法.用用NewtonNewton迭代法求下面方程的一個(gè)正根迭代法求下面方程的一個(gè)正根, ,計(jì)計(jì)算結(jié)果精確到算結(jié)果精確到7 7位小數(shù)位小數(shù). .02010223 xxx322 ( )2

6、1020,(0)200,(2)160.0,2 , ( ) 34x 100, ( )6404.2. f xxxxfffxxfxx 設(shè)在上滿足定理的條件由由NewtonNewton迭代法迭代法)()(1kkkkxfxfxx322210203410kkkkkkxxxxxx 由由NewtonNewton迭代法迭代法 得得取取初初值值,x2020 x1 1 = 1.4666667 ,x4 4 = 1.3688081x5 5 = 1.3688081迭代迭代5 5次次精度達(dá)精度達(dá)10-7x* * 1.3688081kx*x)( xfy kx（1）Newton迭代公式在單根情況下至少迭代公式在單根情況下至少2

7、階收斂階收斂; （2） 設(shè)設(shè) f(x*)=0, ,且在且在 x* 的鄰域的鄰域 上上 存在存在, 連續(xù)連續(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.證明迭代法重根的是方程設(shè),)2(0)(*mxfx)()(1kkkkxfxfxx為線性收斂證明:故重根的是方程因?yàn)?0)(*mxfx)(*)()(xgxxxfm2,0*

9、)(mxg且所以)(xf )(*)()(*)(1xgxxxgxxmmm)(*)()(*)()(*)(1kmkkmkkmkkxgxxxgxxmxgxxx)()(1kkkkxfxfxx)(*)()()(*)(kkkkkkxgxxxmgxgxxx*1xxk)(*)()()(1*)(kkkkkxgxxxmgxgxx*lim1xxxxkkk)(*)()()(1(limkkkkkxgxxxmgxgm11011 ,2mm時(shí)重根是線性收斂的該迭代法對(duì))2(m例4.證明迭代法且設(shè),0)(,0)(afaf)()(1kkkkxfxfxx至少是平方收斂的由定義1注意例4與例3的迭代法是相同的,兩例有何區(qū)別?證明:令)

10、()()(xfxfxx)(x則22)()()()(1xfxfxfxf 2)()()(xfxfxf 0)( a所以由定理2該迭代法至少是平方收斂的 Newton迭代公式是一種特殊的不動(dòng)點(diǎn)迭代迭代公式是一種特殊的不動(dòng)點(diǎn)迭代,其其迭代矩陣為迭代矩陣為: Newton迭代是局部線性化方法迭代是局部線性化方法,它在單根附近它在單根附近具有較高的收斂速度具有較高的收斂速度. 方法有效前提方法有效前提: ( )( )( )f xxxfx()0kfx開方公式開方公式 對(duì)于給定正數(shù) 應(yīng)用牛頓迭代法解二次方程可導(dǎo)出求開方值 的計(jì)算公式 設(shè) 是 的某個(gè)近似值，則 自然也是一個(gè)近似值，上式表明，它們兩者的算術(shù)平均值將

11、是更好的近似值。 定理定理 開方公式對(duì)于任意給定的初值開方公式對(duì)于任意給定的初值 均為均為平方收斂。平方收斂。 ckxc20 xc112kkkcxxxc/kc x00 x 牛頓迭代法的優(yōu)缺點(diǎn)牛頓迭代法的優(yōu)缺點(diǎn) 優(yōu)點(diǎn)：優(yōu)點(diǎn)： 在單根附近在單根附近, 牛頓迭代法具有平方收斂的速牛頓迭代法具有平方收斂的速 度，所以在迭代過程中只要迭代幾次就會(huì)得到很精度，所以在迭代過程中只要迭代幾次就會(huì)得到很精 確解確解。 缺點(diǎn)缺點(diǎn):1. 重根情形下為局部線性收斂重根情形下為局部線性收斂; 2. 牛頓迭代法計(jì)算量比較大牛頓迭代法計(jì)算量比較大:因每次迭代除因每次迭代除 計(jì)算函數(shù)值外還要計(jì)算微商值計(jì)算函數(shù)值外還要計(jì)算微商

12、值; 3. 選定的初值要接近方程的解，否則有可能得選定的初值要接近方程的解，否則有可能得 不到收斂的結(jié)果不到收斂的結(jié)果;牛頓迭代法的改進(jìn)牛頓迭代法的改進(jìn)缺點(diǎn)克服缺點(diǎn)克服: 1. 局部線性收斂局部線性收斂-改進(jìn)公式或加速改進(jìn)公式或加速 2.每步都要每步都要計(jì)算微商值計(jì)算微商值-簡化簡化Newton迭代法迭代法 或弦截法或弦截法 3. 初值近似問題初值近似問題-二分法求初值或二分法求初值或”下山算法下山算法”方法一方法一. 若已知重?cái)?shù)m(m1),則利用m構(gòu)造新的迭代公式: 此時(shí), , 至少2階收斂. 不實(shí)用: m往往不確定.方法二方法二. 取 ,再對(duì)函數(shù)F(x)用Newton迭代:此時(shí),X*為F(

13、x)的單根,所以是2階收斂. 但要用到二階導(dǎo)數(shù).1()()kkkkf xxxmfx( )*( )( ),()0f xfxxxmx( )( )( )f xF xfx12()()()()()()()kkkkkkkkkkF xf xfxxxxF xfxf xfx)()(1kkkkxfxfxxNewtonNewton迭代法迭代法需要求每個(gè)迭代點(diǎn)處的導(dǎo)數(shù)需要求每個(gè)迭代點(diǎn)處的導(dǎo)數(shù) f (xk)復(fù)雜！復(fù)雜！得中的近似替代用,)(0kkxxfx)()(01xfxfxxkkk這種格式稱為這種格式稱為簡化簡化NewtonNewton迭代法迭代法精度稍低精度稍低則則NewtonNewton迭代法變?yōu)榈ㄗ優(yōu)?()

14、()()(111kkkkkkkxxxfxfxfxx這種格式稱為這種格式稱為弦截法弦截法收斂階約為收斂階約為1.6181.618)(kxf 如果用數(shù)值導(dǎo)數(shù)代替11)()()(kkkkkxxxfxfxf用簡化用簡化Newton法和弦截法解下面方程的根，并和法和弦截法解下面方程的根，并和Newton 迭代法比較迭代法比較0133xx13)(3xxxf設(shè)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法法由弦截法由弦截法要達(dá)到精度要達(dá)到精度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是否收斂均與初值的位置有關(guān)是否收斂均與初值的位置有關(guān). .20 x若若取取初初值值x0 =1x1 = -0.5708x2 = 0.1169x3 = -0.0011x4 = 7.963110-10 x5 = 0收斂收斂發(fā)散發(fā)散10 x若若取取初初值值牛頓下山法牛頓下山法 一般地說，牛頓法的收斂性依賴于初值 的選取，如果 偏離 較遠(yuǎn)，則牛頓法可能發(fā)散。 為了防止發(fā)散，通常對(duì)迭代過程再附加一項(xiàng)要求，即保證函數(shù)值單調(diào)下降： 滿足這項(xiàng)要求的算法稱為下山法下山法。 牛頓下山法牛頓下山法采用以下迭代公式：其

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次才達(dá)到精度要求2.用Newton下山法,結(jié)果如下k=0 x0 =-0.99