第2章非線性方程求根

1、1例例. 1 xr求求球球體體沒沒入入水水中中的的深深度度的的球球體體浸浸入入水水中中，密密度度為為將將一一半半徑徑為為 ，3 43)3( 32 rxrx 解解：根據(jù)阿基米德定律，排出的水質(zhì)量應(yīng)等：根據(jù)阿基米德定律，排出的水質(zhì)量應(yīng)等于球體自身的質(zhì)量：于球體自身的質(zhì)量：2. 043)( 323 rrxxxf即即0)1(4)(2,0(0) 3 rrff因因?yàn)闉?2x(0 0)2(3)( rrxxxf 且且的存在唯一。所以方程 0)( xf現(xiàn)代科學(xué)技術(shù)或工程技術(shù)領(lǐng)域的許多實(shí)際問題，常?？梢詺w結(jié)為求解函數(shù)方程：( )0f x ，: fRR其中函數(shù)一般是非線性的.如果函數(shù) 能寫成如下形式如果有使得( )

2、0f，則稱 為方程( )0,1,gm且有( )0f x 的根根， 或稱 為函數(shù) 的零點(diǎn)零點(diǎn)。( )f x( )0 xmf則稱 為的 重根，mf或函數(shù)的 重零點(diǎn)。f( )()( )mf xxg x3如：如：1110( ).0, 1.nnnnf xa xaxa xan ( )sin0.xf xex 當(dāng)f (x)為代數(shù)方程時(shí)，理論上已經(jīng)證明，大于五次 的多項(xiàng)式一般沒有代數(shù)解法。 當(dāng)f(x)為超越方程時(shí)，一般不能用代數(shù)方法求其根。 所以，超越方程(含有指數(shù)和對(duì)數(shù)等)代數(shù)方程（多項(xiàng)式）對(duì)于一般的非線性方程，只能用數(shù)值方法數(shù)值方法求解。4方程求根的問題分成兩步：第二步：根的隔離確定根所在的區(qū)間，使方程在這

3、個(gè)小區(qū)間內(nèi)僅有一個(gè)根，該區(qū)間叫隔根區(qū)間。第三步：根的精確化已知根的一個(gè)近似值后，用某種方法對(duì)其進(jìn)行加工，使之滿足給定的精度要求。第一步：根的存在性5求隔根區(qū)間的一般方法理論依據(jù)： ( ) , ( )( )0( )0 , f xa bf af bf xa b設(shè)在上連續(xù)，且，則 在內(nèi)至少有一個(gè)實(shí)根 ； ( ) , ( )0 , f xa bf xa b若在內(nèi)嚴(yán)格單調(diào)，則 在內(nèi)只有一個(gè)根。6本章主要介紹二分法二分法與迭代法迭代法（包括Newton迭代法及其變型、弦割法等）二分法是方程求根最常用而且也是最保險(xiǎn)的方法之一。一、算法的基本思想將區(qū)間對(duì)分，保留有根的區(qū)間，舍去無(wú)根的區(qū)間。如此往復(fù)，以逐步逼近

4、方程的根。 ( ) , ( ) ( )0.f xa bf a f b 假設(shè)在上連續(xù)且基本條件：基本條件：700000000(1)., , ().2 ()0( ) , ()0ababa bxfxfxfxa bfx令，取中點(diǎn)，求若，則得到在上的一個(gè)零點(diǎn)；若，則作下一步。01100101()()0()( )0.fxfaaabxfxf baxbb(2).若， 則 令，；若， 則 令，1100 ( )0,f xa bab這樣，我們得到 的一個(gè)新的含根區(qū)間，其長(zhǎng)度是原區(qū)間長(zhǎng)度的一半。,( )kkabf x(3). 對(duì)新的含根區(qū)間重復(fù)上述步驟，我們可以得到一個(gè)區(qū)間序列，序列中的每一個(gè)區(qū)間都是函數(shù)的含根區(qū)間且

5、區(qū)間的程度依次減半。二、算法的步驟8a x0 b( )f x a1 b1三、算法的收斂性 11 , ,.,.kka ba ba b二分法產(chǎn)生一個(gè)含根區(qū)間序列：11,11 ().().22kkkkkkka bbababa其中區(qū)間的長(zhǎng)度為： k (2)kkkf xabx因此，當(dāng)足夠大時(shí)，我們可以用作為函數(shù)的一個(gè)根 的近似值。1.22kkkkbabax此時(shí)有誤差估計(jì)誤差估計(jì)：常用來估計(jì)k的值9四、算法的優(yōu)點(diǎn)與缺點(diǎn) 缺點(diǎn)：缺點(diǎn)：不能求偶數(shù)重根及復(fù)根；收斂速度非常緩慢，與以1/2為公比的等比級(jí)數(shù)相同；沒有充分利用函數(shù)值。因此一般不單獨(dú)使用，但往往可以為其它快速方法提供初值。優(yōu)點(diǎn)優(yōu)點(diǎn)：計(jì)算簡(jiǎn)單且必收斂，是

6、一種可靠的算法；對(duì)函數(shù)性質(zhì)要求低，只要求函數(shù)f(x)連續(xù)就可以了。用二分法求方程 3( )1 0f xxx 在1,1.5內(nèi)的實(shí)根， 要求 0.005.解解111.5 1|0.00522kkkb ax 6.k 即可推出所需的迭代次數(shù)滿足 在區(qū)間1, 1.5上至少存在一個(gè)根。 ( )(1)1 0,( )(1.5) 0.875 0,f aff bf 其具體過程如下： 例例2.1.1由于因而( )0f x 由誤差估計(jì)式1061.5 11.32420.0039. 0.00572x11例例2.1.22.1.232( )4100 .f xxx4求 在區(qū)間1,2上的根，使得誤差不超過10解解4112 1|10

7、22kkkb ax 12.3,k 即可推出所需的迭代次數(shù)滿足 因而函數(shù) 在區(qū)間1, 2上存在惟一的零點(diǎn)。 ( )(1)5 0,( )(2) 14 0f aff bf 由于以及2( )380,1,2,fxxxx 由誤差估計(jì)式( )f xk因此可取 =13.12二分法的一種修正是試位法試位法。在二分法中，原來區(qū)間的中點(diǎn)為新的區(qū)間的一個(gè)端點(diǎn)。因此，每迭代一步，區(qū)間的長(zhǎng)度均減半。在試位法中，不用中點(diǎn)，而用過點(diǎn) 與 的直線的零點(diǎn)作為新區(qū)間的一個(gè)端點(diǎn)。在實(shí)際計(jì)算中，試位法比二分法往往收斂得要快。(,()kkaf a(,()kkbf b在試位法的每一步計(jì)算中，有( ),0,1,.( )( )kkkkkkkb

8、axbf bkf bf a13等價(jià)變換等價(jià)變換( )xx( )0f x ( ) 0f x 的根( ) x的不動(dòng)點(diǎn)迭代法是一種逐步逼近的方法: 首先給出一個(gè)粗糙的初值，反復(fù)利用同一個(gè)迭代公式，逐步逼近精確解。 用迭代法求方程根的基本步驟如下：第一步：化為同解方程 且連續(xù)14第二步：產(chǎn)生迭代序列先建立適當(dāng)?shù)牡袷剑旱袷剑? , .xa b再取適當(dāng)?shù)某踔?()kkxx，012,.,.kxx xx利用上述格式可產(chǎn)生一列數(shù)：1()( )( )( )m 0likkkkkxxxxf xx若迭代序列收斂，則由可得，因而是的不動(dòng)點(diǎn)，也即若就是，的根。第三步：取極限limkkx 一定收斂嗎？15xy0 x1

9、x2xyx( )yx在直角坐標(biāo)系中同時(shí)作 和 兩條曲線，如圖所示，則這兩條曲線的交點(diǎn)的橫坐標(biāo)就是方程 的根 ，也就是 的根。迭代格式 由 求 ，相當(dāng)于過曲線上 作水平線與直線 相交，過交點(diǎn)作x軸的垂線，此時(shí)垂足至原點(diǎn)距離等于 ，故垂足橫坐標(biāo)為 。yx( )yx( )xx( ) 0f x 1()kkxxkx1kx(, ()kkxxyx1kx()kx 迭代法的幾何解釋：16由上圖可見，曲線斜率 時(shí)迭代序列收斂，且 越小收斂越快；反之，若 ，則迭代序列發(fā)散。|( )| 1x|( )|x|( )| 1xxyy = xxyy = xx0p0 x1p1 x0p0 x1p1( )xx( )xx在根附近，曲線

10、的切線不說明能太陡！17例例2.2.12.2.130( )10 1.5.f xxxx 求方程 在附近的根解解3311 0 1 2 . 7 8 1.51.35721 1.33086. 1.324721.1132472kkkkxxxxx（ ） 將方程改寫為由此建立迭代公式得迭代收斂。3312 0 1 2 .1.52.37512.39.1.1kkkxxxxkx（ ） 若將方程改寫為建立迭代公式 得迭代不收斂。18下面給出簡(jiǎn)單迭代法的一個(gè)收斂性定理。1 ( ) , , ;(2), , ,( ) , , , ()( )01( )( ) .kkkaxbLxyxa bxa bx ya bxxa bxa bx

11、xL xyx0存在唯一的根設(shè)函數(shù)在區(qū)間上滿足條件:(1)對(duì)任意，都有存在常數(shù)使得對(duì)一切都有則定理2.2方程在上且對(duì)任何初值由迭代格式產(chǎn)生的迭代序列并收斂于有誤差估計(jì)式，.110 1kkLxxxL。Lipschitz條件保證迭代不中斷，連續(xù)時(shí)保證有解壓縮映像19 存在唯一性證明證明做輔助函數(shù)( )( )xxx，則有( )0,( )0,ab所以，存在點(diǎn)( )0( ). ，使，即若又有*( *) ，則有*( )( *)*.L 所以*. 收斂性任取初值0 , ,xa b則110| ()( )|.,kkkkxxL xLx 所以，任意的初值都收斂。20 誤差估計(jì)11110()().,kkkkkkkxxxx

12、L xxL xx11.kpkkpkpkkxxxxxx 110.kpkLLxx 10101.11kpkLLLxxxxLL10.1kkLxxxLpp 由 的任意性，令，可得證畢2111 ( ) , 1 , ;( )0(2), , , ( ) , , , , ()(0,1,.) 1( ). kkxC a,ba bxa bxa bxxa bxa bxaxbLLkxx0設(shè)函數(shù)在區(qū)間上滿足條件（ ）對(duì)任意，都有存在常數(shù)使得對(duì)一切都有則方程在內(nèi)有唯一的根且對(duì)任何初值迭代序列均收斂于推，并有論10 .1kkLxxxL1 ()()()(),xCa,bxyxyxy當(dāng) 函 數(shù)()時(shí) ， 由 微 分 中 值 定 理

13、得 ：其 中在和之 間 。 由 此 不 難 推 出 下 述 結(jié) 論 。2210 1( )( ) , 1.kkLxxxLxxaLb注常數(shù) 越小，簡(jiǎn)單迭代法收斂越快。誤差估計(jì)式表明:因而構(gòu)造迭代函數(shù)的原則是使在有根區(qū)間上有盡可能小的上界。給出了精度要求，可用上述誤差估計(jì)式來確定所需的注2.迭代次數(shù)。101kkxLkxxL設(shè)所要求的精度為 ，即要求 ，只需迭代次數(shù) 滿足 ,即滿足10(1)ln/ ln.|LkLxx231| |kkxx可通過檢查來判斷迭代過程應(yīng)因否終止而。p對(duì)任意正注 .整數(shù)3，有1121| | . |kpkkpkpkpkpkkxxxxxxxx 12111(. 1)|,1ppkkkk

14、LLxxxxL11 |.1kkkpxxxL 令，得24例例2.2.32.2.32 ( )9sin10 f xxx 求在0,1內(nèi)的一個(gè)根。解解 (0)10, (1)8sin 10 0,1 ff 由 于，因 而為 有 根 區(qū) 間 。1sin1.31( )sin1. 3110sin 01( )sin111,331| cos|1( ).66sin1xxxxxxxx將方程化為等價(jià)方程：此時(shí)，在區(qū)間0,1上，且1000,10 1), (kkxxxx根據(jù)定理，任取，由簡(jiǎn)單迭代格式所產(chǎn)生的迭代序列收斂于方程在中的根。比如取0.4.也可化為等價(jià)方程也可化為等價(jià)方程 . .但此時(shí)定理?xiàng)l件不成立，迭代序但此時(shí)定理?xiàng)l

15、件不成立，迭代序列不能保證收斂。列不能保證收斂。2arcsin(91)xx25例例2.2.42.2.42 ( )10 f xxx 用簡(jiǎn)單迭代法求方程的根。解解 (1.5)0.250, (2)10 1.5,2 ff 由于，因而為有根區(qū)間。1111( ) 1.51.5 1( )2 12111( )3.1622112 2.5xxxxxx 且（因）22222111 1( ) 1.51( )1221.5111 (2 ( )1.5)2.25xxxxxx 因且0 1.5,2,x 根據(jù)定理，任取由這兩種等價(jià)方程所構(gòu)造的簡(jiǎn)單迭代方法都收斂，且第一種所產(chǎn)生的迭代序列收斂較快。26由于定理中條件(1)一般難于驗(yàn)證，

16、而且在大區(qū)間上，這些條件也不一定都成立。所以實(shí)際使用迭代法總是在根的鄰近進(jìn)行。*( )( ,)( )1.xOx 如果函數(shù)在其不動(dòng)點(diǎn) 的一鄰域定內(nèi)連理2.2.2續(xù)可微，且*01, ()kkxxx 則存在正數(shù)使得對(duì)任意，由迭代格式產(chǎn)生的迭代序列收斂于 ，且其誤差估計(jì)式與定理2.2.1中的相同。|( )| 1 實(shí)際上只要即可表明收斂性與初值的選擇有關(guān)！27*( )(,)( )1,1, ( )1.xOxLxxL 因在內(nèi)連續(xù)，且故存在正數(shù)使得對(duì)，有證 實(shí)際用迭代法計(jì)算時(shí)，先用二分法求得較好的初值，然后再進(jìn)行迭代。1(), ( )( )()( ),().kkxxL xxxx 另一方面，由又有即。由定理2.

17、2.1知，迭代序列收斂于28性質(zhì)性質(zhì) 1. 若方程 x=(x) 在處有根，則當(dāng)|()|1時(shí)，稱為超線性收斂；當(dāng)p =2時(shí)，稱為平方收斂或二次收斂。顯然，迭代序列的收斂階越高，它的收斂速度就越快。311( )0kkxx 對(duì)于簡(jiǎn)單迭代格式，當(dāng)線性時(shí)只能達(dá)到收斂階。1|( ) |( )() |kkkxxx )1|( )|,|kk 1|lim|( )|0.|kkk 因?yàn)?，由?kxx其中 介于 與 之間。設(shè))連續(xù)，則有32 在實(shí)際使用中收斂的階有時(shí)很難直接確定，常常采用一些其它的方法來確定收斂的階。使用Taylor展開式是一種常用的方法。如果 在根 處充分光滑(各階導(dǎo)數(shù)存在)，則可對(duì) 在 處進(jìn)行Tay

18、lor展開，得1(1)21()()()()()()()().()2!(1)!( )() .!kkkppkkppkxxxxxpxp ( )x( )x33(1)( )( ).( )0,p 如果()11( )()() ,!ppkkkxxxp 則( )( )0,p但是()1|( ) |.|!pkpkxxp即11()()|limlim|( ) |() |lim.!kkppkkkkppkxxpp上式說明迭代法為 p 階收斂的。34()1()lim.!pkpkkp ( )( )xxx中的定理2迭代函數(shù)在不動(dòng)點(diǎn)如附.2.4果近滿足：( )xp(1)存在 階導(dǎo)數(shù)且連續(xù)；(1)( )(2)( )( ).( )0,

19、( )0.pp 1 ()kkxxp則迭代法為 階收斂且有補(bǔ)充35例例2.2.62.2.6( )0( )0ff設(shè)，證明由( )( )( )f xxxxfx建立的迭代法至少是平方收斂的。證明證明根據(jù)上述定理，只需證明( )0. 222( )( )( )( )( )1( )( )( )( )0.( )xxxf xfxf x fxxfxfxf x fxfx 因?yàn)楣试摰ㄖ辽偈瞧椒绞諗康?。Newton迭代法36 迭代法的加速11(),0,1,2.( ),( )( )( )(1)(2.().)kkkkxxkxxxxxxxx 簡(jiǎn)單迭代過程的收斂速度與迭代函數(shù)有關(guān)，在許多情況下 可以在此基礎(chǔ)上構(gòu)造新的迭代公

20、式，使得方程與有相同的根由新的迭代公式產(chǎn)生的迭代序列比原來的迭代公式產(chǎn)生的迭代序列收斂得快這加方法稱為速技巧種37( )( )( ( )xxxx l 令新的迭代函數(shù)為1 其中是待定參數(shù)。選取使得( *)( *)( ( *) 1)0 xxx 構(gòu)造加速迭代序列即()( *)1( *)1()1kkkkxxxx1()( ()1kkkkkkxxxx38 迭代法的埃特金加速法1lim( )( )| 1.kkkkxxx 如果迭代序列線性收斂于 ，則且0|211 .kkkkkxxxx當(dāng)適當(dāng)大時(shí)，有39221212kkkkkkx xxxxx由此解出.2121()2kkkkkkxxxxxx重新整理得21+121(

21、).2kkkkkkkxxxxxxx定義序列此迭代方法稱為?？梢宰C明：此序列比原來的序列更快地收埃特金加速斂于法。40211, kkkkkxxxcxx定迭代序列收斂于理2.2.3且如，果lim0.kkkxx則41(1). 21()()()2kkkkkkkkkkkyxzyyxxxzyx k=0，1，2，埃特金迭代格式可改寫成：(2). 1()(0,1,.)kkxxk2( ( )( ).( ( )2 ( )xxxxxxx 其中迭代函數(shù)42 小結(jié)1. 2 3 4 迭代法的基本思想.迭代法收斂的條件及誤差估計(jì).迭代法的收斂速度.迭代法的加速43用迭代法解非線性方程時(shí)，如何構(gòu)造迭代函數(shù)是非常重要的，那么怎

22、樣構(gòu)造的迭代函數(shù)才能保證迭代法收斂呢？一、Newton迭代法將非線性方程線性化，以線性方程的解逐步逼近非線性方程的解。 基本思想基本思想非線性問題的最簡(jiǎn)單解法是線性近似！440200000( ) ()( )()()()().2f x xTaylorfxf xf xfxx- xxx!Taylor將在近似值處展開成級(jí)數(shù)展：開：；00001()0 ()()0 )( fxxxf xfxxf x =x若，則有解，取 作為的根的新的近似值，記為求；解：000( ) ()()()0 f xf xfxxx線性化?。壕€性部分作為的近似，有； 迭代格式迭代格式451211().()fxxxfx1()()kkkkf

23、 xxxfx上述格式稱為NewtonNewton迭代格式迭代格式。這樣一直下去，可以得到一列迭代序列 ，其迭代格式為：類似地，同樣可以得到kx46幾何意義幾何意義,1()( )()() ()kkkkkkxf xyf xyf xfxxxxx過點(diǎn)作函數(shù)的切線，其方程為，因此，就是該切線與 軸交點(diǎn)的坐標(biāo)。xy1x2x0 x( )yf xNewton迭代法又稱為切線法切線切線 原來是以直線代替原來是以直線代替曲線的近似方法啊曲線的近似方法啊!47 局部收斂性局部收斂性( )( ).( )f xxxfxNewto迭n代函數(shù)迭代法的為x對(duì) ( )求導(dǎo),有222( ) )( ) ( )( )( )( )1,

24、( )( )fxfx f xf x fxxfxfx 222( )( )( )( )( )( )( )( )( )( )fxfxfxxf xfxf xfxfxfx482( )( )()( )0( )( )()( )( )( )0.( )( )( )0( )( )()( )0f xg x xgfxg xxg xfgf xfffff 且，此時(shí)，故所以，(1) 當(dāng) 是的單根時(shí):.Newton( )0( )0f 因而，法在根 的至少是二階收斂的鄰近；當(dāng)時(shí)，所以恰為二階收斂的。4911( )( )()()0( )()( )()( )( )( )( )()( )()( )( )0)(2)( )()( )(:

25、( )()mmmmmmf xg xxgfxm xg xxgxf xxxfxxg xxm xg xxgxxg xxfmg xxxxmgm(2)當(dāng)是的，且，此時(shí)，重根時(shí)，50()lim( ),( )()()lim()( )( )()( )lim( )1lim 11.( )()( )xxxxxxxxg xxmg xxgxxg xmg xxgxm 2()0Newtonm 當(dāng)時(shí)，所以法線在根性的鄰近是收斂的。改進(jìn)：改進(jìn)：1(),()kkkkf xxxmf x則至少是二階收斂的。511( ) 0( )0( )Newton()()( )0kkkkfff xf xxxfxf設(shè) ，且在 鄰域內(nèi)具有二階連續(xù)導(dǎo)數(shù)，

26、則由法產(chǎn)生的迭代序列局部定理2.3.1收斂到 ，且收斂階至少為2。又當(dāng)時(shí)，收斂階恰為2。缺點(diǎn)：缺點(diǎn)：對(duì)初值要求較高，計(jì)算量較大。優(yōu)點(diǎn)優(yōu)點(diǎn)：收斂速度快，精度高，格式簡(jiǎn)單，應(yīng)用廣泛。 優(yōu)點(diǎn)與缺點(diǎn)優(yōu)點(diǎn)與缺點(diǎn) 52下圖表明Newton法收斂性依賴于初值x0 的選取。x0 x0 x0總之，Newton法具有收斂快，穩(wěn)定性好，精度高等優(yōu)點(diǎn)，是求解非線性方程的有效方法之一。但它每次迭代均需計(jì)算函數(shù)值與導(dǎo)數(shù)值，故計(jì)算量較大。而且當(dāng)導(dǎo)數(shù)值提供有困難時(shí)，Newton法無(wú)法進(jìn)行。此外，由于它是局部收斂的，因而對(duì)初值要求較高，只有初值選得充分靠近根時(shí)，才能保證序列收斂。53注注1 1：使用牛頓迭代法存在從一個(gè)根跳到另

27、一個(gè)根的情況。注注2 2：如果f(x)=0沒有實(shí)根，則牛頓迭代序列不收斂。54例例2.3.1 用Newton法解方程f(x)=x(x+1)2-1=0在0.4附近的根。解解 將函數(shù)f(x)求導(dǎo)，得到210( )(1)(31)()(1)1,()(1)(31)0.4,kkkkkkkkkfxxxf xxxxxxfxxxxNewton迭代格式為取計(jì)算結(jié)果如下k 0 1 2 3 xk 0.4 0.47013 0.46539 0.46537所以，取根為0.4654.55 全局收斂性全局收斂性( )Newtonf x如果函數(shù)在某一個(gè)含根區(qū)間滿足一定的單調(diào)性和凸凹性，則得到迭代法的全局收斂性。定理定理2.3.2

28、 2( ) , f xCa b設(shè)函數(shù)且滿足如下條件：0001)( ) ( )0;2)( ) , ;3)( ) , ()()0.f a f bfxa bfxa bxf xfx在上不等于零在上恒正或恒負(fù);4)初值滿足條件Newton( )0 , .kxf xa b則由迭代法產(chǎn)生的序列單調(diào)收斂于在區(qū)間內(nèi)的唯一根保證了根的存在性保證了根的存在性 函數(shù)單調(diào)，根唯一函數(shù)單調(diào)，根唯一函數(shù)圖形的凸向不變函數(shù)圖形的凸向不變 , ( ) , xa bxa b保證時(shí)，56例例2.3.22Newton 9sin10 xx 用迭代求在0,1內(nèi)的一個(gè)根。解解21 ( )9sin1 (1)0, ( )0 31,13f xx

29、xff由于滿足，且在區(qū)間上滿足條件( )18cos610( )18sin180fxxxfxx，000001 ,1()()03()0NewtonNewtonxf xfxf xx故由定理可知：當(dāng)初值滿足，即時(shí)，迭代法收斂。如取0.4，按迭代格式計(jì)算.57 Newton迭代法的計(jì)算步驟迭代法的計(jì)算步驟000(),().0 xf xfxk123輸入精度 , ，最大迭代次數(shù)N，初值 ，計(jì)算令第一步：；()|kkfx3如果N或|，則輸出算法失敗標(biāo)志，并終第二步：止迭代；1()()kkkkf xxxfx第計(jì)算三步：；111()|:1kkkkxxf xxkk12如果|,或|,則終止迭代，并??；否則，并轉(zhuǎn)第四步

30、：第二步。58 程序框圖程序框圖112| ()|kkkxxf x或終止準(zhǔn)則：終止準(zhǔn)則：|()|kkNf x或|( )?|kkNf x或59例例2.3.3Newton0.cc 用法建立求的迭代格式,其中解解2( )( )0.f xxcf x作函數(shù)，則函數(shù)的正根即為 c21Newton()1().()22kkkkkkkkkf xxccxxxxfxxx迭代格式為0( )20( )20.xfxxfx因?yàn)楫?dāng)時(shí)，根據(jù)全局收斂性定理，對(duì)任何滿足200()0,f xxc00 xcx即的初值，上述Newton迭代產(chǎn)生的迭代序列. c均收斂于60二、簡(jiǎn)化Newton法10().()kkkf xxxfx0( )(

31、).()f xxxfx0Newton().()()().kkkfxfxfxfx迭代中每次都要計(jì)算如果較繁，工作量就很大。為了避免計(jì)算導(dǎo)數(shù)值，可將取為某個(gè)定點(diǎn)處的值近似替代，如取這時(shí)迭代式變?yōu)榇烁袷椒Q為簡(jiǎn)化簡(jiǎn)化NewtonNewton迭代迭代。迭代函數(shù)為kxx和切線法不同，此時(shí)的迭代序列為一系列平行直線與軸的交點(diǎn)。 迭代格式迭代格式6100(,()xf x0 x1x)(xfy 2x 幾何意義幾何意義00,1()()() ()( )()kkkkkxfxyfxfxxxyfxxxfx用 過 點(diǎn)且的 直 線來 代 替 曲 線， 取 該 直 線 與軸 交 點(diǎn)斜 率 為的橫 坐 標(biāo)作 為的 新 的 近 似

32、值 。621().kkkf xxxc( )( ),f xxxc()kfxc進(jìn)一步推廣，可以把取為任意常數(shù)， 迭代函數(shù)成為此格式稱為推廣的簡(jiǎn)化推廣的簡(jiǎn)化NewtonNewton迭代迭代。迭代格式為 進(jìn)一步簡(jiǎn)化進(jìn)一步簡(jiǎn)化由簡(jiǎn)單迭代的局部收斂條件|( )|1,xLx 收斂性與收斂速度收斂性與收斂速度630 x1x)(xfy 2x(NewtonNewto)nfx可 見 ， 當(dāng)時(shí) ， 推 廣 的簡(jiǎn) 化法 才 是的 。 因 此 ， 在 推廣 的 簡(jiǎn) 化迭 代 中 ， 常 數(shù) c至 少 應(yīng) 與 導(dǎo) 數(shù)同 號(hào)c與同 號(hào) 且 滿 足 上 式局 部 收 斂。 若 不 然 ， 迭 代 可 能 發(fā) 散 。( )fx右

33、 圖 中 c與反 號(hào) ， 結(jié) 果 發(fā) 散( )02.fxc得64推廣的簡(jiǎn)化Newton法收斂時(shí)，因?yàn)?| | ()( )| |( )|,kkkxxx ( )cf若，有1|( )|( )|10.|kkfc 所以，推廣的簡(jiǎn)化Newton法只有線性收斂速度。( )Newtoncf雖然如此，只有 選得好，比如很接近，收斂也是相當(dāng)快的。它的計(jì)算卻比法簡(jiǎn)單得多。kx其中位于與之間；65三、下山Newton迭代1(),()kkkkkf xxxfx在Newton迭代法中，若函數(shù)較復(fù)雜，初值的選取較困難時(shí)，為防止迭代發(fā)散，可改用如下的迭代式，以擴(kuò)大初值的選取范圍：01kk其中稱為。通過適當(dāng)選取下山下山因子因子，

34、使得1|()|()|kkf xf x成立，|()|kf x要求的即值單調(diào)下降。上述迭代方法稱為下山下山NewtonNewton法法。66211111,.2 2,|() |() |1kkkkxf xf xxk下山因子的確定一般。即由迭代得到計(jì)算值后，取不同的 值試算，例如，直到成立，則計(jì)算值即采用試算法取為第步的迭代值。12111,.,Newton222kxk再 取用 求 得 的與 下 山迭代 仿 照 前 面 的 過 程 計(jì) 算 第步 的 迭 代 值 。*012kkxx如 果 計(jì) 算 過 程 中 碰 到 一 個(gè) 迭 代 值取 不 到 滿 足要 求 的值 ， 則 稱 “” (一 般 給 出 下 山

35、因 子 的 下 界=)， 需 要 另 取 初 始 值， 仿 照上 述 過下 山 失 敗程 重 算 。112| ()|kkkf xxx或終止準(zhǔn)則：終止準(zhǔn)則：67例例2.3.52.3.53Newton 03xx用下山迭代法求的根。解解323120( )( )13Newton3.1Pkkkkkkxf xxfxxxxxxxx由于，下山迭代格式為取 初值=-0.99，計(jì)算結(jié)果見（曾金平）書37表2.3.2.NewtonNewtonNewton下山法當(dāng)1時(shí)，只有線性收斂速度，但對(duì)初值的選取卻放得很寬。某一個(gè)初值對(duì)迭代不收斂，對(duì)下山法卻可能收斂得很好。68四、弦割法 迭代格式迭代格式Newton()kfx用

36、上式替代迭代格式中的，化簡(jiǎn)得111()().()()kkkkkkkf xxxxxf xf x11()()(),kkkkkf xf xfxxxNewton( )( )( ).f xfxfx由于迭代法帶有的導(dǎo)數(shù)，使用起來不方便。為了不求導(dǎo)數(shù)，可用導(dǎo)數(shù)的近似式替代由上式定義的迭代算法稱為弦割法弦割法，也稱為割線法割線法。為什么稱為弦割法？是從它的幾何意義而言。1,( )0kkxxf x其中是的兩個(gè)近似根，69 幾何意義幾何意義1kxx就是割線由此與軸交可以看出，點(diǎn)的坐標(biāo)11()()()().kkkkkkf xf xyf xxxxx111,( )0(,(),(,()( )kkkkkkxxf xxf xxf xyf x設(shè)是的兩個(gè)近似根，過兩點(diǎn)作函數(shù)的割線，其方程為11()().()()kkkkkkf xxxxxf xf x0y 令，可得切線切線 割線割線 1kxkx1kx( )y f x還是以直線代替還是以直線代替曲線的近似方法啊曲線的近似方法啊!70 收斂性與收斂速度收斂性與收斂速度111(