6.2 不動點(diǎn)迭代法及其收斂定理ppt課件

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

2、解方程解:123xx(1) 將原方程化為等價方程得由迭代法如果取初值),3(,00 x12301xx112312xx312323xx5500 x顯然迭代法發(fā)散321xx(2) 如果將原方程化為等價方程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)012*xxxxO)(xyxy 02

3、31*xxxxxO)(xyxy 如果將(2)式表示為)(xyxy 與方程(2)同解收斂附近較平緩在*)(xx*012xxxxO)(xyxy 2013*xxxxxO)(xyxy 發(fā)散附近較陡峭在*)(xx定理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 對對于于任任意意初初值值迭迭代代法法均均收收斂斂于于13 .*1ok

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

5、xx11kkxxL)(*11kkkxxxxL)(*11kkkxxLxxLkkkxxLLxx111*11*kkkxxLLxx2121kkxxLL011xxLLk,1L由于*)(limxxkk0*)(,10 xxxxkk均收斂于迭代法因此對任意初值11*kkkxxLLxx011xxLLk證畢.定理1指出,|( ) |1xL只要構(gòu)造的迭代函數(shù)滿足就收斂迭代法)(1kkxx11kkxxLL由(6)式,只要因此,當(dāng)LLxxkk11迭代就可以終止,可以作為方程的近似解kx對于預(yù)先給定的誤差限|*|xxk即要求-(8)定義定義1：如果存在 的某個鄰域 ，使迭代過程 對于任意初值 均收斂，則稱迭代過程 在根

6、鄰近具有局部收斂性。*x*:xxR)(1kkxxRx 0)(1kkxx*x*1,0 |()| 1,(2).kkxxxxxx若 是 的不動點(diǎn)在 的某鄰域上存在若 是 的不動點(diǎn)在 的某鄰域上存在且連續(xù) 并滿足則迭代過程且連續(xù) 并滿足則迭代過程 在 的鄰域是線性 在 的鄰域是線性理理收斂的收斂的定定例2.用迭代法求方程的近似解,精確到小數(shù)點(diǎn)后6位0210 xex解:,0 xe由于0102x則2 .0 x,0時x,10 xe2102x本題迭代函數(shù)有兩種構(gòu)造形式102)(1xexx)102ln()(2xxx|)(|1x10 xe|)(|2xx102101102 .0e102)(1xexx因此采用迭代函數(shù)

7、為有根區(qū)間因此2 .0 ,05由于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-0061),則利用m構(gòu)造新的迭代公式: 此時, , 至少2階收斂. 不實用: m往往不確定.方法二方法二. 取 ,再對函數(shù)F(x)用Newton迭代:此時,X*為F(x)的單根,所以是2階收斂. 但要用到二階導(dǎo)數(shù).1()()kkkkf xxxmfx( )*( )( ),()

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

9、.6181.618)(kxf 如果用數(shù)值導(dǎo)數(shù)代替11)()()(kkkkkxxxfxfxf用簡化用簡化Newton法和弦截法解下面方程的根，并和法和弦截法解下面方程的根，并和Newton 迭代法比較迭代法比較0133xx13)(3xxxf設(shè)33)(2xxf由簡化由簡化Newton法法)()(01xfxfxxkkk3313203xxxxkkk由弦截法由弦截法)()()()(111kkkkkkkxxxfxfxfxx由由Newton迭代法迭代法)()(1kkkkxfxfxx331323kkkkxxxxx0= 0.5x1= 0.3333333333x2 = 0.3497942387x3 = 0.346

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

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(arctan21kkkkxxxxx0 = 2x1 = -3.54x2 = 13.95x3 = -279.34x4 = 122017是否收

12、斂均與初值的位置有關(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ā)散，通常對迭代過程再附加一項要求，即保證函數(shù)值單調(diào)下降： 滿足這項要求的算法稱為下山法下山法。 牛頓下山法牛頓下山法采用以下迭代公式：其中 稱為下山因子。 1kkf xf x011kkkkf xxxfx0 x0 x*x牛頓下山法只有線性收斂牛頓

13、下山法只有線性收斂.的選取方式的順序，按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

14、x12= 1.73205x13= 1.73205)1(332223223xxxxx迭代13次才達(dá)到精度要求2.用Newton下山法,結(jié)果如下k=0 x0 =-0.99 fx0 =0.666567k = 1 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

15、 = 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下山因子0有重根在區(qū)間,0)(.2baxf2*,0)(mxmbaxf重根有在區(qū)間)(*)()(xgxxxfm因此可令0*)(xg且*)(xf *)(xf*)()1(xfm *)(xf 故有0*)()(xfm且由例3.)()

16、(1kkkkxfxfxx對于Newton迭代法趨于零,0)(kxf即使Newton迭代法也只是線性收斂此時Newton迭代法可能不收斂由定理2，迭代法)()(1kkkkxfxfmxx至少是二階收斂Steffensen方法 第第6章章 方程與方程組的迭代解法方程與方程組的迭代解法 簡單迭代公式的加速簡單迭代公式的加速 設(shè) 是根 的某個近似值，用迭代公式校正一次得假設(shè) ， 則有據(jù)此可導(dǎo)出如下加速公式：其一步分為兩個環(huán)節(jié)： 迭代: 改進(jìn):kx*x1kxq1kkxx*1kkxxq xx11111kkkqxxxqq1kkxx11111()111kkkkkkqqxxxxxxqqq11111()()()1n

17、nnnnnnxxxxxxxqqq：迭代次數(shù)大大減少，總的計算工作量減少，但涉及導(dǎo)數(shù)值的計簡單算不迭代便于法的實加速方案際應(yīng)用。埃特金迭代法求方程的實根2221221121()2()2kkkkkkkkkkkkkxxxxAitkenxxxxxxxxx：加速方案:避免了導(dǎo)數(shù)值的計算，但需要簡用單迭代法加兩次迭代值速方進(jìn)案的改進(jìn)行計算。定理定理 設(shè)序列 線性收斂于x*, 則 的Aitken序列 存在,且 即 比 更快收斂于x*.kx*0,0,kkkexx 且1limkkkece(0 | 1)c kx kxkx*lim0kkkxxxxkx222112*121212121*2*221:limlim()2()2(1)(1)1102121kkkkkkkkkkkkkkkkkkkkkkkk