不動點迭代法及其收斂定理PPT教學(xué)PPT學(xué)習(xí)教案

1、會計學(xué)1不動點迭代法及其收斂定理不動點迭代法及其收斂定理PPT教學(xué)課教學(xué)課件件一、迭代法原理-(2)將非線性方程 f (x) = 0 化為一個同解方程)(xx為連續(xù)函數(shù)并且假設(shè))(x得的右端代入任取一個初值,)2(,0 x)(01xx)(12xx)(1kkxx繼續(xù)-(3),2,1 ,0(k稱(3)式為求解非線性方程(2)的簡單迭代法第1頁/共56頁( ),kxxk 稱稱為為迭迭代代函函數(shù)數(shù) 稱稱為為第第 步步迭迭代代值值*,kxx如如果果存存在在一一點點使使得得迭迭代代序序列列滿滿足足*limxxkk則稱迭代法則稱迭代法(3)收斂收斂,否則稱為發(fā)否則稱為發(fā)散散-(4)例1.0123 xx用迭代

2、法求解方程解:123xx(1) 將原方程化為等價方程得由迭代法如果取初值),3(,00 x第2頁/共56頁12301xx112312xx312323xx5500 x顯然迭代法發(fā)散321xx(2) 如果將原方程化為等價方程第3頁/共56頁00 x30121xx仍取初值3217937.031221xx327937.19644.0 x2 = 0.9644x3 = 0.9940 x4 = 0.9990 x5 = 0.9998x6 = 1.0000 x7 = 1.0000依此類推,得已經(jīng)收斂,故原方程的解為0000.1x同樣的方程不同的迭代格式有不同的結(jié)果什么形式的迭代法 能夠收斂呢?迭代函數(shù)的構(gòu)造有關(guān)

3、第4頁/共56頁012*xxxxO)(xyxy 0231*xxxxxO)(xyxy 如果將(2)式表示為)(xyxy 與方程(2)同解收斂附近較平緩在*)(xx*012xxxxO)(xyxy 2013*xxxxxO)(xyxy 發(fā)散附近較陡峭在*)(xx第5頁/共56頁定理1.( ) , ,xa b 設(shè)迭代函數(shù)在上連續(xù) 且滿足設(shè)迭代函數(shù)在上連續(xù) 且滿足(1) , ,();xa baxb 當(dāng)當(dāng)時時(2),01, , ,LLxa b 存存在在一一正正數(shù)數(shù)滿滿足足且且有有Lx|)(|1 .( ) , *oxxa bx 則則方方程程在在內(nèi)內(nèi)有有唯唯一一解解012 . , ,()*okkxa bxxx

4、對對于于任任意意初初值值迭迭代代法法均均收收斂斂于于13 .*1okkkLxxxxL 104 .*1kokLxxxxL -(5)-(6)-(7)(局部收斂性)迭代過程的收斂性迭代過程的收斂性第6頁/共56頁證:由條件(1),()(xxxf設(shè))()(aaaf0)()(bbbf0上連續(xù)可導(dǎo)在則,)(baxf由根的存在定理,上至少有一個根在方程,0)(baxf第7頁/共56頁證:1|)(|Lx由)(1)(xxf0,)(上單調(diào)遞增在則baxf上僅有一個根在,0)(baxf*,)(.1xbaxxo內(nèi)有唯一解在方程所以第8頁/共56頁),(.21kkoxx對于迭代法*1xxk*)()(xxk*)(xxk由

5、微分中值定理kkxx1)()(1kkxx)(1kkxxkkxx11kkxxLLx|)(|由于第9頁/共56頁*1xxk*xxLkkkxx11kkxxL)(*11kkkxxxxL)(*11kkkxxLxxLkkkxxLLxx111*第10頁/共56頁11*kkkxxLLxx2121kkxxLL011xxLLk,1L由于*)(limxxkk0*)(,10 xxxxkk均收斂于迭代法因此對任意初值11*kkkxxLLxx011xxLLk證畢.第11頁/共56頁定理1指出,|( ) |1xL只要構(gòu)造的迭代函數(shù)滿足就收斂迭代法)(1kkxx第12頁/共56頁11kkxxLL由(6)式,只要因此,當(dāng)LLx

6、xkk11迭代就可以終止,可以作為方程的近似解kx對于預(yù)先給定的誤差限|*|xxk即要求-(8)第13頁/共56頁定義定義1：如果存在 的某個鄰域 ，使迭代過程 對于任意初值 均收斂，則稱迭代過程 在根 鄰近具有局部收斂性。*x*:xxR)(1kkxxRx 0)(1kkxx*x*1,0 |()| 1,(2).kkxxxxxx若 是 的不動點在 的某鄰域上存在若 是 的不動點在 的某鄰域上存在且連續(xù) 并滿足則迭代過程且連續(xù) 并滿足則迭代過程 在 的鄰域是線性 在 的鄰域是線性理理收斂的收斂的定定第14頁/共56頁例2.用迭代法求方程的近似解,精確到小數(shù)點后6位0210 xex解:,0 xe由于0

7、102x則2 .0 x,0時x,10 xe2102x第15頁/共56頁本題迭代函數(shù)有兩種構(gòu)造形式102)(1xexx)102ln()(2xxx|)(|1x10 xe|)(|2xx102101102 .0e102)(1xexx因此采用迭代函數(shù)為有根區(qū)間因此2 .0 ,05由于第16頁/共56頁00 x取初值10201xex1 .0d1 = 0.1000000d2 = -0.0105171d3 = 0.1156e-002d4 = -0.1265e-003d5 = 0.1390e-004d6 = -0.1500e-005d7 = 0.1000e-006由于|d7| =0.1000e-0061e-6因

8、此原方程的解為x7 = 0.090525*xx1 = 0.1000000 x2 = 0.0894829x3 = 0.0906391x4 = 0.0905126x5 = 0.0905265x6 = 0.0905250 x7 = 0.0905251第17頁/共56頁由定理1的(7)式出,|)(|上越小在或baxL*xxekk設(shè)迭代法收斂就越快定義1. 10pc 若若存存在在實實數(shù)數(shù)和和滿滿足足pkkkee1limc,1,1,2pppp 則則稱稱迭迭代代法法 階階收收斂斂 當(dāng)當(dāng)時時稱稱為為線線性性收收斂斂時時稱稱為為超超線線性性收收斂斂時時稱稱為為平平方方收收斂斂收斂速度也就越快越大顯然, p-(9

9、)迭代法收斂速度第18頁/共56頁從而確定收斂階呢？如何確定那么,p( )*,xx 如如果果迭迭代代函函數(shù)數(shù)在在精精確確解解處處充充分分光光滑滑即即處處處處可可導(dǎo)導(dǎo)有展開作在將,*)(Taylorxx 2*)(! 2*)(*)*)(*)()(xxxxxxxxppppxxpxxxpx*)(!*)(*)()!1(*)()(1)1(第19頁/共56頁0*)()1(xp *)(*)(xx如果0*)()(xp而*)()(xxppxxpx*)(!*)()()(1kkxxpkpxxpxx*)(!*)(*)()(pkpxxpx*)(!*)()(*1xxk1)1(*)()!1(*)(pkpxxpx第20頁/共5

10、6頁定理3. pkkxxxx*1*)()!1(*)(!*)()1()(xxpxpxkpppxxkk的收斂階是即迭代法)(1附近滿足：在根如果迭代法迭代函數(shù)*)(xx階導(dǎo)數(shù)切連續(xù)；存在px)()1(,0*)()1(xp *)(*)()2(xx0*)()(xp而pxxkk的收斂階是則迭代法)(1)( ,!*)()(kpxp第21頁/共56頁0123 xx用迭代法求解方程本題迭代函數(shù)有兩種構(gòu)造形式本題迭代函數(shù)有兩種構(gòu)造形式)x(xx1312 ,迭代法發(fā)散迭代法發(fā)散. 10 x121223,)x(),x(xx 可可驗驗證證迭代法收斂迭代法收斂.第22頁/共56頁Newton 迭代法迭代法將將f(x)f

11、(x)在點在點xn作作TaylorTaylor展開展開: : )( )( )()()(! 2)()( )( )()(2nnnnnnnnxxxfxfxfxxxfxxxfxfxf TaylorTaylor展開線性化展開線性化f(x)=0 近似于近似于 f(xn)+ f(xn)(x-xn)=0 (1)從從(1)解出解出x, 記為記為xn+1 , ,則則1() (n0,1,.) (2)()nnnnf xxxfx第23頁/共56頁它對應(yīng)的迭代方程為 顯然是f(x)=0的同解方程，故其迭代函數(shù)為 在 f(x)=0的根 x* 的某個鄰域 內(nèi), 在 x* 的鄰域R 內(nèi)，對任意初值 ，應(yīng)用應(yīng)用公式（2）來解方程

12、的方法就稱為來解方程的方法就稱為牛頓迭代法牛頓迭代法。它。它是解代數(shù)方程和超越方程的有效方法之一是解代數(shù)方程和超越方程的有效方法之一.)(xR0)(xf0 x)()()(xfxfxx1)()()()(2 Lxfxfxfx)()(xfxfxx)0)( xf第24頁/共56頁 )()( )(nnnxxxfxfy 與與x軸軸(y=0)的交點的交點x,x,作為下一個迭代點作為下一個迭代點xn+1 , ,即即 )( )(1nnnnxfxfxx 用用f(x)f(x)在在 xn 處處的切線的切線Newton迭代法又稱切線法迭代法又稱切線法.第25頁/共56頁用用NewtonNewton迭代法求下面方程的一個

13、正根迭代法求下面方程的一個正根, ,計計算結(jié)果精確到算結(jié)果精確到7 7位小數(shù)位小數(shù). .02010223 xxx322 ( )21020,(0)200,(2)160.0,2 , ( ) 34x 100, ( )6404.2. f xxxxfffxxfxx 設(shè)在上滿足定理的條件由由NewtonNewton迭代法迭代法)()(1kkkkxfxfxx322210203410kkkkkkxxxxxx 第26頁/共56頁由由NewtonNewton迭代法迭代法 得得取取初初值值,x2020 x1 1 = 1.4666667 ,x4 4 = 1.3688081x5 5 = 1.3688081迭代迭代5 5

14、次次精度達精度達10-7x* * 1.3688081kx*x)( xfy kx第27頁/共56頁（1）Newton迭代公式在單根情況下至少迭代公式在單根情況下至少2階收階收斂斂; （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(f

15、nnnnnnnnnnnnnnn 注意到注意到 n n 在在xn 及及x*之間之間,及及 , 故故*xxnnlim 第28頁/共56頁 所以，所以，Newton法至少二階收斂法至少二階收斂. )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()kxkxx

16、fxxxfx第29頁/共56頁例3.證明迭代法重根的是方程設(shè),)2(0)(*mxfx)()(1kkkkxfxfxx為線性收斂證明:故重根的是方程因為,0)(*mxfx)(*)()(xgxxxfm2,0*)(mxg且所以)(xf )(*)()(*)(1xgxxxgxxmmm)(*)()(*)()(*)(1kmkkmkkmkkxgxxxgxxmxgxxx)()(1kkkkxfxfxx)(*)()()(*)(kkkkkkxgxxxmgxgxxx第30頁/共56頁*1xxk)(*)()()(1*)(kkkkkxgxxxmgxgxx*lim1xxxxkkk)(*)()()(1(limkkkkkxgxxx

17、mgxgm11011 ,2mm時重根是線性收斂的該迭代法對)2(m例4.證明迭代法且設(shè),0)(,0)(afaf)()(1kkkkxfxfxx至少是平方收斂的由定義1第31頁/共56頁注意例4與例3的迭代法是相同的,兩例有何區(qū)別?證明:令)()()(xfxfxx)(x則22)()()()(1xfxfxfxf 2)()()(xfxfxf 0)( a所以由定理2該迭代法至少是平方收斂的第32頁/共56頁 Newton迭代公式是一種特殊的不動點迭代迭代公式是一種特殊的不動點迭代,其迭代其迭代矩陣為矩陣為: Newton迭代是局部線性化方法迭代是局部線性化方法,它在單根附近它在單根附近具有較高的收斂速度

18、具有較高的收斂速度. 方法有效前提方法有效前提: ( )( )( )f xxxfx()0kfx第33頁/共56頁ckxc20 xc112kkkcxxxc/kc x00 x 第34頁/共56頁牛頓迭代法的優(yōu)缺點牛頓迭代法的優(yōu)缺點 優(yōu)點：優(yōu)點： 在單根附近在單根附近, 牛頓迭代法具有平方收斂的牛頓迭代法具有平方收斂的速速 度，所以在迭代過程中只要迭代幾次就會得到很度，所以在迭代過程中只要迭代幾次就會得到很精精 確解確解。 缺點缺點:1. 重根情形下為局部線性收斂重根情形下為局部線性收斂; 2. 牛頓迭代法計算量比較大牛頓迭代法計算量比較大:因每次迭代除因每次迭代除 計算函數(shù)值外還要計算微商值計算函

19、數(shù)值外還要計算微商值; 3. 選定的初值要接近方程的解，否則有可能選定的初值要接近方程的解，否則有可能得得 不到收斂的結(jié)果不到收斂的結(jié)果;第35頁/共56頁牛頓迭代法的改進牛頓迭代法的改進缺點克服缺點克服: 1. 局部線性收斂局部線性收斂-改進公式或加速改進公式或加速 2.每步都要每步都要計算微商值計算微商值-簡化簡化Newton迭代法迭代法 或弦截法或弦截法 3. 初值近似問題初值近似問題-二分法求初值或二分法求初值或”下山算法下山算法”第36頁/共56頁1()()kkkkf xxxmfx( )*( )( ),()0f xfxxxmx( )( )( )f xF xfx12()()()()()

20、()()kkkkkkkkkkF xf xfxxxxF xfxf xfx第37頁/共56頁)()(1kkkkxfxfxxNewtonNewton迭代法迭代法需要求每個迭代點處的導(dǎo)數(shù)需要求每個迭代點處的導(dǎo)數(shù) f (xk)復(fù)雜！復(fù)雜！得中的近似替代用,)(0kkxxfx)()(01xfxfxxkkk這種格式稱為這種格式稱為簡化簡化NewtonNewton迭代法迭代法精度稍低精度稍低第38頁/共56頁則則NewtonNewton迭代法變?yōu)榈ㄗ優(yōu)?()()()(111kkkkkkkxxxfxfxfxx這種格式稱為這種格式稱為弦截法弦截法收斂階約為收斂階約為1.6181.618)(kxf 如果用數(shù)值導(dǎo)

21、數(shù)代替11)()()(kkkkkxxxfxfxf第39頁/共56頁用簡化用簡化Newton法和弦截法解下面方程的根，并和法和弦截法解下面方程的根，并和Newton 迭代法比較迭代法比較0133xx13)(3xxxf設(shè)33)(2xxf由簡化由簡化Newton法法)()(01xfxfxxkkk3313203xxxxkkk由弦截法由弦截法)()()()(111kkkkkkkxxxfxfxfxx由由Newton迭代法迭代法)()(1kkkkxfxfxx331323kkkkxxxx第40頁/共56頁x0= 0.5x1= 0.3333333333x2 = 0.3497942387x3 = 0.346868

22、3325x4 = 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簡化簡化Newton法法由弦截法由弦截法要達到精度要達到精度10-8 簡化簡化Newton法迭代法迭代11次次弦截

23、法迭代弦截法迭代5次次Newton迭代法迭代迭代法迭代4次次x0 =0.5;x1 =0.3333333333x2 =0.3472222222x3 =0.3472963532x4 =0.3472963553由由Newton迭代法迭代法第41頁/共56頁無論哪種迭代法：無論哪種迭代法：NewtonNewton迭代法迭代法簡化簡化NewtonNewton法法弦截法弦截法00 *x,)xarctan()x(f精精確確解解用用NewtonNewton迭代法求解迭代法求解: :)1(arctan21kkkkxxxxx0 = 2x1 = -3.54x2 = 13.95x3 = -279.34x4 = 122

24、017是否收斂均與初值的位置有關(guān)是否收斂均與初值的位置有關(guān). .20 x若若取取初初值值x0 =1x1 = -0.5708x2 = 0.1169x3 = -0.0011x4 = 7.963110-10 x5 = 0收斂收斂發(fā)散發(fā)散10 x若若取取初初值值第42頁/共56頁1kkf xf x011kkkkf xxxfx0 x0 x*x牛頓下山法只有線性收斂牛頓下山法只有線性收斂.的選取方式的順序，按322121211成立為止直到|)(|)(|1kkxfxf第43頁/共56頁例7.30( )0,0.993xf xxx 求解方程取初值5110|nnxx解:1.先用Newton迭代法1)(2xxf)(

25、)(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次才達到精度要求第44頁/共56頁2.用Newton下山法,結(jié)果如下k=0 x0 =-0.99 fx0 =0.666567k = 1

26、 x1 =32.505829 f(x) = 11416.4 w =0.5 x1 =15.757915 f(x) = 1288.5 w =0.25 x1 =7.383958 f(x) =126.8 w =0.125 x1 =3.196979 f(x) =7.69 w = 0.0625 x1 =1.103489 f(x)=-0.655k = 2 x2 = 4.115071 f(x) =19.1 w = 0.5 x2 = 2.60928 f(x)=3.31 w =0.25 x2 =1.85638 f(x)=0.27k = 3 x3 =1.74352 f(x)=0.023k = 4 x4 = 1.73216 f(x)=0.00024k = 5 x5 = 1.73205 f(x)=0.00000k = 6 x6 = 1.73205 f(x)=0.000000)(kkxfxk下山因子第45頁/共56頁0有重根在區(qū)間,0)(.2baxf2*,0)(