第2章迭代法

1、第2章 方程求根1 二分法二分法2 簡(jiǎn)單迭代法簡(jiǎn)單迭代法3 切線法切線法(牛頓法牛頓法)4 弦截法弦截法 圖 2.3 二分法適合單二分法適合單根，不能求復(fù)根，不能求復(fù)根和偶數(shù)重根，根和偶數(shù)重根，且收斂速度慢，且收斂速度慢，可以為其他方可以為其他方法提供一個(gè)初法提供一個(gè)初值，用其他方值，用其他方法精確化。法精確化。預(yù)備定理預(yù)備定理介值定理介值定理 函數(shù)函數(shù) f(x)f(x)在在 a,ba,b 上單調(diào)連續(xù)，且上單調(diào)連續(xù)，且f(a)f(b)f(a)f(b)00，則方程，則方程f(x)=0f(x)=0在區(qū)間在區(qū)間 a,ba,b 上有且僅有上有且僅有一個(gè)實(shí)根一個(gè)實(shí)根x x* *。 微分中值定理 如果函數(shù)

2、( )f x在 , a b連續(xù)，在a,b（)可微，則在a,b（)內(nèi)至少有一點(diǎn)存在，使 ( )( )( )()f bf afba ab 2 迭代法迭代法 迭代法的基本思想是:首先將方程(2.1)改寫(xiě)成某種等價(jià)形式,由等價(jià)形式構(gòu)造相應(yīng)的迭代公式,然后選取方程的某個(gè)初始近似根x0,代入迭代公式反復(fù)校正根的近似值,直到滿足精度要求為止。迭代法是一種數(shù)值計(jì)算中重要的逐次逼近方法。 迭代法是一種逐次逼近的方法，用某種固定格式反復(fù)校正根的近似值，使之逐步精確，最后達(dá)到滿意的效果。 例 求310 xx 在01.5x 附近的根。 解 將上式寫(xiě)成等價(jià)方程31xx，當(dāng)用根x代入時(shí)，有 3*1xx 設(shè)01.5x 是其

3、根，代入時(shí)，有 35721. 115 . 113301xx 再設(shè)11.35721x 是其根，代入時(shí)，有 33086. 1135721. 113312xx， 依次可得 41.32494,x 561.32476,1.32473xx781.32472,1.32472xx k kx 1kkxx 0 1 2 3 4 5 6 7 8 1. 5 1. 35721 1. 33086 1. 32588 1. 32494 1. 32476 1. 32473 1. 32472 1. 32472 計(jì)算結(jié)果見(jiàn)下表計(jì)算結(jié)果見(jiàn)下表 對(duì)于一般形式的方程(2.1),首先我們?cè)O(shè)法將其化為下列等價(jià)形式 x=g(x) (2.7) 然

4、后按(2.7)構(gòu)造迭代公式 (2.8) 從給定的初始近似根x0出發(fā),按迭代公式(2.8)可以得到一個(gè)數(shù)列 x0,x1,x2,xk, 若這個(gè)數(shù)列xk有極限,則迭代公式(2.8)是收斂的。此時(shí)數(shù)列的極限1(),0,1,2,kkxg xklimkkxx 就是原方程(2.1)的根。 雖然迭代法的基本思想很簡(jiǎn)單,但效果并不總是令人滿意的。對(duì)于上例,若按方程寫(xiě)成另一種等價(jià)形式 x=x3-1 (2.9) 建立迭代公式 xk+1=x3k-1, k=0,1,2, 仍取初始值x0=1.5, 則迭代結(jié)果為 x1=2.375 x2=12.3976 迭代法的幾何意義:把方程(2.1)求根的問(wèn)題改寫(xiě)成(2.7)變?yōu)榍髷?shù)列

5、xn的極限,實(shí)際上是把求根問(wèn)題轉(zhuǎn)化為求( )yxyg x 圖 2.4 迭代過(guò)程(2.8)就是在x軸取初始近似值x0,過(guò)x0作y軸的平行線交曲線y=g(x)于p0,p0的橫坐標(biāo)為x0,縱坐標(biāo)為g(x0)(g(x0)=x1),也即 p0(x0,x1) 再在x軸上取x1作為新的近似值,過(guò)x1作y軸的平行線交曲線y=g(x)于p1,p1的橫坐標(biāo)為x1,縱坐標(biāo)為 g(x1)(g(x1)=x2),也即 p1(x1,x2) 而這相當(dāng)于過(guò)p0引平行于x軸的直線交y=x于 Q1(x1,x2) 再過(guò)Q1引平行于y軸的直線交曲線y=g(x)于 p1(x1,x2) 仿此可得到點(diǎn)列 p0(x0,x1),p1(x1,x2

6、),p2(x2,x3), 若limlimkkkkppxx 則迭代法收斂,見(jiàn)圖2.4(a);否則迭代法發(fā)散,見(jiàn)圖2.4(b)。 必須說(shuō)明兩點(diǎn): 若g(x)可微,可用充分條件( )1g xq這里q1是非常重要的條件,否則不能保證迭代收斂。 對(duì)于收斂的迭代過(guò)程,誤差估計(jì)式(2.11)說(shuō)明迭代值的偏差xk-xk-1相當(dāng)小,就能保證迭代誤差x-xk足夠小。因此在具體計(jì)算時(shí)常常用條件 xk-x k-1 (2.15) 來(lái)控制迭代過(guò)程結(jié)束。 迭代法的突出優(yōu)點(diǎn)是算法的邏輯結(jié)構(gòu)簡(jiǎn)單,且在計(jì)算時(shí),中間結(jié)果若有擾動(dòng),仍不會(huì)影響計(jì)算結(jié)果。其計(jì)算步驟為: (1)確定方程f(x)=0的等價(jià)形式x=g(x),為確保迭代過(guò)程的

7、收斂,要求g(x)滿足g(x)q1 (2)選取初始值x0,按公式 x k+1=g(xk), k=0,1,2, 進(jìn)行迭代; (3)若x k+1-xk,則停止計(jì)算,xx k+1。 例2 求方程 x= e-x 在x=0.5附近的一個(gè)根。按五位小數(shù)計(jì)算,計(jì)算結(jié)果 的精度要求為=10-3。 解 過(guò)x=0.5以步長(zhǎng)h=0.1計(jì)算 f(x)=x-e-x 由于 f(0.5)0,f(0.6)0 故所求的根在區(qū)間(0.5,0.6)內(nèi),且在x=0.5附近 (2)()0.61xe 5488. 0606. 06 . 05 . 06 . 05 . 0eex 圖 2.5 表表 23 因此用迭代公式 由表可見(jiàn)10 xxxxe

8、為方程 kkxex1例 對(duì)方程0123 xx在區(qū)間1.4，1.6建立兩種收斂的迭代格式，并用其中一種求解，精確到 5 位有效數(shù)字。 方法1： 取方程等價(jià)形式211xx ， 對(duì)應(yīng)迭代格式1211kkxx ，0,1,k 。其中21( )1xx ， 則32( )xx 。 由于3322( )0.72911.4xx，(1.4,1.6)x，因而迭代收斂。 方法 2：取等價(jià)形式321xx ，故收斂格式2311kkxx，0,1,k 。其中32( )1xx，則2232( )(1)3xxx 由于：2232 1.6( )0.5174113 (1 1.4 )x，(1.4,1.6)x，因而迭代收斂。且第二種迭代格式比第

9、一種迭代格式收斂得更快。 取初值01.5x ，用第二種迭代格式計(jì)算過(guò)程如下表所示。 k kx 1kkxx 0 1. 50000 1 1. 14812 1. 50000 2 1. 47271 0. 35188 3 1. 46882 0. 32458 4 1. 46709 0. 00389 5 1. 46624 0. 00177 6 1. 46588 0. 00081 7 1. 46571 0. 00037 8 1. 46563 0. 00008 9 1. 46560 0. 00003 由于 ，故取x x9=1.46560 54981310102xx定義定義 如果存在*x的某個(gè)鄰域：*xx，使迭代

10、過(guò)程1()kkxx對(duì) 于 任 意 初 值0 x 均 收 斂 ， 則 稱 迭 代 過(guò) 程1()kkxx在根*x附近具有局部收斂性。 定理定理 設(shè)( )x在( )xx的根*x附近連續(xù)，且有 ()1x 則迭代格式1()kkxx在根*x附近具有局部收斂性。 迭代法的迭代法的局部收斂性局部收斂性由于在實(shí)際應(yīng)用中根由于在實(shí)際應(yīng)用中根 x* 事先不知道，故條件事先不知道，故條件 | (x* )| 1無(wú)法驗(yàn)證。但已知根的初值無(wú)法驗(yàn)證。但已知根的初值x0在根在根 x*鄰域，又根據(jù)鄰域，又根據(jù) (x)的連續(xù)性，則的連續(xù)性，則可采用可采用 | (x0 )| 1 來(lái)代替來(lái)代替| (x* )| 1，判斷迭代的收斂性。，

11、判斷迭代的收斂性。 例例求方程求方程 x=e x在在x=0.5附近的一個(gè)根，按附近的一個(gè)根，按5位小數(shù)計(jì)算，位小數(shù)計(jì)算，結(jié)果的精度要求為結(jié)果的精度要求為=10 3.解解迭代公式迭代公式 xk+1=e xk ，取取 (x)=e x,0.50.5|(0.5)| |(e) | e0.61 1迭代公式迭代公式 xk+1=e xk 收斂。收斂。迭代結(jié)果迭代結(jié)果: 0 1 2 3 4 5 0. 5 0. 606 53 0. 545 24 0. 579 70 0. 560 07 0. 571 17 0. 106 53 0. 061 29 0. 034 46 0. 019 63 0. 011 10 6 7 8

12、 9 10 0. 564 86 0. 568 44 0. 566 41 0. 567 56 0. 566 91 0. 006 31 0. 003 58 0. 002 03 0. 001 15 0. 000 65kxkxk xk-1xk xk-1k xk|x10 - x9 |=0.00065，故故 x*x10 0.567x0=0.5, x2=e x1=0.54524,.x1=e x0=0.60653,xk+1=e xk例： 迭代過(guò)程)5(21kkkxcxx， 當(dāng)局部收斂到5時(shí)，確定c的值。 解：迭代函數(shù) )5()(2xcxx，cxx21)(，當(dāng) 局 部 收 斂 到5時(shí) ，1521)5(c，152

13、11c，有051c。 迭代的計(jì)算步驟迭代的計(jì)算步驟 （1）確定( )0f x 的等價(jià)形式( )xx，選初值0 x，判斷收斂性01x（ ）。 （2）由公式10()xx計(jì)算1x。 （3）如果10 xx則停止計(jì)算，取*1xx；否則令01xx，重復(fù)步驟 2 和 3，直到計(jì)算停止。 迭代法計(jì)算框圖的說(shuō)明迭代法計(jì)算框圖的說(shuō)明0 x，N, k 10 xx 2.2.3 迭代過(guò)程的收斂速度迭代過(guò)程的收斂速度定義定義 設(shè)迭代過(guò)程設(shè)迭代過(guò)程1()kkxx收斂于收斂于( )xx的根的根*x，迭代誤差，迭代誤差*kkexx，如果，如果存在常數(shù)存在常數(shù)p（1p ）和不等于零的常數(shù)）和不等于零的常數(shù)c使使 1limkpkk

14、ece 則則稱序列稱序列kx是是p階收斂的。階收斂的。c稱漸進(jìn)誤差常數(shù)。稱漸進(jìn)誤差常數(shù)。特別地，特別地，1p 稱為線性收斂，稱為線性收斂，2p 稱為平方稱為平方收斂，收斂，1p 時(shí)稱為超線性收斂。時(shí)稱為超線性收斂。 迭代函數(shù)的導(dǎo)數(shù)和收斂階。 定理 對(duì)迭代過(guò)程1()kkxx，若()( )px在所求根*x鄰近連續(xù)，且 *(1)*()()()0pxxx()*()0px 則迭代格式1()kkxx在*x鄰近是p階收斂的。 證明 *()0 x，迭代過(guò)程1()kkxx有局部收斂性。 *21()()()()()()2kkkxxxxxxxx (1)*(1)()11()()( )()(1)!ppppkkxxxxx

15、pp *()11( )()!ppkkxxxxp，得證。 例：迭代過(guò)程)5(21kkkxcxx，至少平方收斂到5時(shí)，確定c的值。 解： 2( )(5)xxc x，( )12xcx ， 當(dāng)()0 x時(shí)，至少平方收斂，所以取1250c，12 5c 例 設(shè)方程0cos2312xx的迭代法kkxxcos3241，證明 對(duì) Rx 0，均有*limxxkk，其中*x為方程的根；取40 x，求此迭代法的近似根，使誤差不超過(guò) 10-3 ；證明此迭代法的收斂階。 證證 kkxxcos3241，迭代函數(shù)xxcos324)(是連續(xù)函數(shù) 324cos324324x,22( )4,4(,)33x 2max( )sin1,

16、lim*3kkx Rxxxx 已知初值40 x，計(jì)算結(jié)果如下表所示。 k kx 1kkxx 0 4 1 3. 5642 0. 4358 2 3. 3920 0. 1722 3 3. 3541 0. 0379 4 3. 3483 0. 0058 5 3. 3475 0. 0008 6 3. 3474 0. 0001 7 3. 3474 0. 0000 取近似根*x3474. 37x。 取3474. 3*x，則3.34742( *)|sin(3.3474)0.1362403x ,所以迭代法 1 階收斂（線性收斂） 。 1 1 加加權(quán)權(quán)法法：設(shè) kx是根x的某近似值，取1(),()kkxxxx，由中

17、值定理 1()()( )()kkkxxxxxx 其中,kxx，假定( ) 變化不大，設(shè)( )c ，有 1()kkxxc xx，1kkxcxxcx 1111kkLxxxcc，取11111kkkLxxxcc，即 11 (1kkkxxcxc 2.2.4 迭代的加速埃特金加速法：埃特金加速法：設(shè) kx是根x的某近似值，取 )(1kkxx )(12kkxx 和加權(quán)法同理有)(*1*kkxxcxx)(1*2*kkxxcxx， 將上二式聯(lián)立，有 1*2*1*kkkkxxxxxxxx kkkkkkxxxxxxx1221*2)( 2 埃特金加速法21(),()()2kkkkkkkkkkkyxzyyxxxzyx用

18、不動(dòng)點(diǎn)迭代法求函數(shù)2ln)(xxxf在區(qū)間（2，+）內(nèi)的零點(diǎn)，并用艾特肯森迭代法加速。 解解 設(shè), 02ln)(xxxf有等價(jià)方程, 2lnxx，取迭代函數(shù)( )ln2xx，此時(shí)2111( ), max( )12xxxxx 所以迭代過(guò)程2ln1kkxx局部收斂，取初值30 x，計(jì)算結(jié)果如下表所示。 k kx 1kkxx 0 3 1 3. 098612289 2 3. 130954363 3 3. 141337866 4 3. 144648781 5 3. 145702209 6 3. 146037143 不動(dòng)點(diǎn)迭代法不加速時(shí)，取146. 36x，有 4 位有效數(shù)字。 斯蒂芬森迭代法加速 2ln

19、kkxy， 2lnkkyz ， 21()2kkkkkkkyxxxzyx。 計(jì)算結(jié)果如下表所示。 k kx ky kz 0 3 3. 098612289 3. 130954363 1 3. 146738373 3. 146366479 3. 146248288 2 3. 146193227 3. 146193223 3. 146293221 3 3. 146193227 用斯蒂芬森迭代法加速后，146193227. 33x，有 10 位有效數(shù)字。 3 切線法切線法(牛頓法牛頓法) 切線法是求解方程(2.1)的一種重要迭代方法。如圖2.6,曲線y=f(x)與x軸的交點(diǎn)x就是方程(2.1)的根。 圖圖 2.6 與x軸的交點(diǎn)為x k+1,其方程為1()()()0()()()kkkkkkkyf xfxxxf xfxxx 點(diǎn)xk+1滿足該切線方程,即可得到切線迭代公式(或牛頓迭代公式)1(),0,1,2,()kkkkf xxxkfx(2.20) 切線法是非線性方程線性化的方法。其計(jì)算步驟為: 給出初始近似根x0及精度。 計(jì)算 若x1-x0,則轉(zhuǎn)向;否則x1 x0,轉(zhuǎn)向。 輸出滿足精度的根x1,結(jié)束。 切線法的計(jì)算