非方程的數(shù)值解法

1、教學(xué)目的教學(xué)目的 1. 掌握解非線性方程（組）的二分法和插值法；掌握解非線性方程（組）的二分法和插值法； 2. 掌握解非線性方程（組）的一般迭代法及有關(guān)收斂性掌握解非線性方程（組）的一般迭代法及有關(guān)收斂性的證明與牛頓法；的證明與牛頓法； 3. 掌握解非線性方程（組）的牛頓法掌握解非線性方程（組）的牛頓法 4. 了解加速收斂的方法。了解加速收斂的方法。教學(xué)重點(diǎn)及難點(diǎn)教學(xué)重點(diǎn)及難點(diǎn) 重點(diǎn)重點(diǎn)是解非線性方程（組）的牛頓法；是解非線性方程（組）的牛頓法；難點(diǎn)難點(diǎn)是迭代法的收斂性的證明。是迭代法的收斂性的證明。 第七章第七章 非線性方程非線性方程的數(shù)值解法的數(shù)值解法 代數(shù)方程求根問題是一個(gè)古老的數(shù)學(xué)問題

2、代數(shù)方程求根問題是一個(gè)古老的數(shù)學(xué)問題. .早在早在1616世紀(jì)就找到了三次，四次方程的求根公式世紀(jì)就找到了三次，四次方程的求根公式. .但直到但直到1919世世紀(jì)才證明了紀(jì)才證明了n5 5次的一般代數(shù)方程式不能用代數(shù)公式求次的一般代數(shù)方程式不能用代數(shù)公式求解解. .因此需要研究用數(shù)值方法求得滿足一定精度的代數(shù)因此需要研究用數(shù)值方法求得滿足一定精度的代數(shù)方程式的近似解方程式的近似解. . 而在工程和科學(xué)技術(shù)中許多問題常歸結(jié)為求解非而在工程和科學(xué)技術(shù)中許多問題常歸結(jié)為求解非線性方程式問題。例如在控制系統(tǒng)的設(shè)計(jì)領(lǐng)域中，在線性方程式問題。例如在控制系統(tǒng)的設(shè)計(jì)領(lǐng)域中，在研究人口增長率等問題中都最后可化為

3、方程求根的問研究人口增長率等問題中都最后可化為方程求根的問題。題。非線性方程的數(shù)值解法非線性方程的數(shù)值解法 求解非線性方程的根，就是求解求解非線性方程的根，就是求解高次方程高次方程或或超越方程超越方程(含有指數(shù)和對(duì)數(shù)等含有指數(shù)和對(duì)數(shù)等)，因?yàn)檫@類方程沒有固定的求根公式。，因?yàn)檫@類方程沒有固定的求根公式。 用用 f(x)表示方程左端的函數(shù)，則一般的非線性方程可表示表示方程左端的函數(shù)，則一般的非線性方程可表示為為 f (x) = 0. 本節(jié)的任務(wù)就是上述方程的本節(jié)的任務(wù)就是上述方程的根根或或函數(shù)的零點(diǎn)函數(shù)的零點(diǎn)。7.1 7.1 引言引言如果如果f(x)可以分解成可以分解成 , 其中其中m為正整數(shù)為

4、正整數(shù)且且 ,則稱則稱x*是是f(x)的的m重零點(diǎn)重零點(diǎn),或稱方程或稱方程f(x)=0的的m重根。重根。當(dāng)當(dāng)m=1時(shí)稱時(shí)稱x*為單根。若為單根。若f(x)存在存在m階導(dǎo)數(shù)階導(dǎo)數(shù),則是方程則是方程f(x)的的m重重根根(m1) 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng))()()(*xgxxxfm0)(*xg0)(,0)()()(*)(*)1(*xfxfxfxfmm 本章介紹方程的迭代解法，它既可以用來求解代數(shù)方程，本章介紹方程的迭代解法，它既可以用來求解代數(shù)方程，也可以用來解超越方程，并且僅限于求方程的實(shí)根。也可以用來解超越方程，并且僅限于求方程的實(shí)根。 運(yùn)用迭代法求解方程的根應(yīng)解決以下兩個(gè)問題：運(yùn)用迭代法求解方程的根

5、應(yīng)解決以下兩個(gè)問題：確定根的初值確定根的初值; ;將進(jìn)一步精確化到所需要的精度。將進(jìn)一步精確化到所需要的精度。 由高等數(shù)學(xué)知識(shí)知由高等數(shù)學(xué)知識(shí)知, 設(shè)設(shè)f (x)為區(qū)間為區(qū)間a,b上的單值連續(xù)上的單值連續(xù), 如果如果f (a)f (b)0 , 則則a,b中至少有一個(gè)實(shí)根。如果中至少有一個(gè)實(shí)根。如果f (x)在在a,b上還上還是單調(diào)地遞增或遞減，則僅有一個(gè)實(shí)根。是單調(diào)地遞增或遞減，則僅有一個(gè)實(shí)根。n由此可大體確定根所在子區(qū)間，方法有：由此可大體確定根所在子區(qū)間，方法有： (1) (1) 畫圖法畫圖法 (2) (2) 逐步搜索法逐步搜索法y=f(x)abyx(1) (1) 畫圖法畫圖法 畫出y =

6、 f (x)的略圖，從而看出曲線與x軸交點(diǎn)的 大致位置。 也可將f (x) = 0分解為1(x)= 2(x)的形式，1(x) 與 2(x)兩曲線交點(diǎn)的橫坐標(biāo)所在的子區(qū)間即為含根區(qū)間。例如 xlogx-1= 0可以改寫為logx=1/x畫出對(duì)數(shù)曲線y=logx,與雙曲線y= 1/x,它們交 點(diǎn)的橫坐標(biāo)位于區(qū)間2,3內(nèi)畫圖法畫圖法xy1ylogx 023yxn對(duì)于某些看不清根的函數(shù)，可以擴(kuò)大一下曲線對(duì)于某些看不清根的函數(shù)，可以擴(kuò)大一下曲線y0 xy=f(x)y=kf(x)y0 xABa1b1a2b2(2) 逐步搜索法逐步搜索法(2) 搜索法搜索法 對(duì)于給定的對(duì)于給定的f (x), 設(shè)有根區(qū)間為設(shè)有

7、根區(qū)間為A,B, 從從x0=A出發(fā)出發(fā),以步長以步長h=(B-A)/n(n是正整數(shù)是正整數(shù)), 在在A,B內(nèi)取定節(jié)點(diǎn)內(nèi)取定節(jié)點(diǎn):xi=x0ih (i=0,1,2,n), 從左至右檢查從左至右檢查f (xi)的符號(hào)的符號(hào), 如發(fā)現(xiàn)如發(fā)現(xiàn)xi與端點(diǎn)與端點(diǎn)x0的的函數(shù)值異號(hào)函數(shù)值異號(hào),則得到一個(gè)縮小的有根子區(qū)間則得到一個(gè)縮小的有根子區(qū)間xi-1,xi。例例1 方程方程f(x)=x3-x-1=0 確定其有根區(qū)間確定其有根區(qū)間解：用試湊的方法，不難發(fā)現(xiàn)解：用試湊的方法，不難發(fā)現(xiàn) f(0)0 在區(qū)間在區(qū)間（0,2）內(nèi)至少有一個(gè)實(shí)根內(nèi)至少有一個(gè)實(shí)根 設(shè)從設(shè)從x=0出發(fā)出發(fā),取取h=0.5為為步長向右進(jìn)行根的

8、搜索步長向右進(jìn)行根的搜索,列表如下列表如下xf(x)0 0.5 1.0 1.5 2 + +可以看出，在可以看出，在1.0,1.5內(nèi)必有一根內(nèi)必有一根w 用逐步搜索法進(jìn)行實(shí)根隔離的關(guān)鍵是選取步長用逐步搜索法進(jìn)行實(shí)根隔離的關(guān)鍵是選取步長h要選擇適當(dāng)要選擇適當(dāng)h ，使之既能把根隔離開來，工作量又不太大。，使之既能把根隔離開來，工作量又不太大。 w 為獲取指定精度要求的初值為獲取指定精度要求的初值,可在以上隔離根的基礎(chǔ)上采用可在以上隔離根的基礎(chǔ)上采用對(duì)分法繼續(xù)縮小該含根子區(qū)間對(duì)分法繼續(xù)縮小該含根子區(qū)間 w 下面的二分法可以看作是搜索法的一種改進(jìn)。下面的二分法可以看作是搜索法的一種改進(jìn)。(3)方程求根的

9、二分法方程求根的二分法(對(duì)分法或分半法對(duì)分法或分半法) (bisection method)ba2ba *x);(21)1(000bax 找找中中點(diǎn)點(diǎn)：令令；即即中中點(diǎn)點(diǎn)的的函函數(shù)數(shù)值值計(jì)計(jì)算算：)()2(00 xff (3) 生成含根區(qū)間：生成含根區(qū)間：,0)(0*0 xxxf ，則則若若, 0)()(00 afxf若若,0101bbxa 取取, 0)()(010100 xbaaafxf 取取若若,00abhbbaa 令令首首先先滿足下式滿足下式: :生成含根區(qū)間生成含根區(qū)間.,11ba,11ba,)1(0011baba 2)2(11hab 0)()()3(11 bfaf .,220011b

10、ababa得得繼繼續(xù)續(xù)以以上上過過程程取取代代以以例例1 ,102 在在x012 x不能求出所有根不能求出所有根,(,(即有可能漏根即有可能漏根) )。例例如圖如圖該點(diǎn)可求出該點(diǎn)可求出, ,注注1 :1 :改進(jìn)的方法，改進(jìn)的方法，試位法（比例求根法）。試位法（比例求根法）。xab但漏掉了四個(gè)點(diǎn)但漏掉了四個(gè)點(diǎn)2.2.不能用于求偶重根、復(fù)根；不能推廣到多元方程組求解；不能用于求偶重根、復(fù)根；不能推廣到多元方程組求解；缺點(diǎn)缺點(diǎn): : 的等比級(jí)數(shù)的收斂速度的等比級(jí)數(shù)的收斂速度相同。相同。1.1.收斂速度不快收斂速度不快, ,僅與公比為僅與公比為 21即是線性收斂的。即是線性收斂的。3( )101 1.

11、5fxxx求 方 程在 區(qū) 間，內(nèi) 的 一 個(gè)實(shí)根，要求準(zhǔn)確到小數(shù)點(diǎn)后的第實(shí)根，要求準(zhǔn)確到小數(shù)點(diǎn)后的第2位。位。1,1.5,()0,( )0,abfafba b這 里.取的, 0)(,25.100 xfbax二等分，由于將區(qū)間中點(diǎn)0010111()()1.25,1.5,61fafxxaxbbab即與同 號(hào) ， 故 在的 右 側(cè) 有 方 程 的 一 個(gè)實(shí) 根 ， 這 時(shí) ， 令而 新 的有 限 區(qū) 間 為。 二 分 過 程 可 如 此 反 復(fù) 下 去計(jì) 算 結(jié) 果 如 表。解解例例k)(kkkkxfxba1.32031.32811.3242-1.31251.32811.3203-1.31251.

12、34381.3281+1.31251.3751.3438+1.251.3751.3125-1.251.51.375+11.51.25-6543210表表6-1 1() / 20 .0 0 5kba我 們 現(xiàn) 在 預(yù) 估 所 要 二 分 的 次 數(shù) 。 令可*6ln ()ln16 ,ln 20 .0 0 5,bakxx得 則 二 分 6 次 就 能 達(dá) 到 預(yù) 定 的精 度與 實(shí) 際 計(jì) 算 結(jié) 果 相 符 。 上述二分法的優(yōu)點(diǎn)是算法簡單上述二分法的優(yōu)點(diǎn)是算法簡單,而且在有限區(qū)間內(nèi)而且在有限區(qū)間內(nèi),收斂性總能得到保證收斂性總能得到保證.值得注意的是值得注意的是,為了求出足夠精確為了求出足夠精確的

13、近似解的近似解,往往需要計(jì)算很多次函數(shù)值往往需要計(jì)算很多次函數(shù)值,是一種收斂較慢是一種收斂較慢的方法的方法,通常用通常用二分法二分法給出根的大致范圍給出根的大致范圍,再利用下面將再利用下面將介紹的更有效的方法求解方程介紹的更有效的方法求解方程.另一方面，二分法只使另一方面，二分法只使用于求一元方程的奇數(shù)重實(shí)根用于求一元方程的奇數(shù)重實(shí)根. 7.3 一元方程的不動(dòng)點(diǎn)迭代法一元方程的不動(dòng)點(diǎn)迭代法7.3.2 局部收斂性和加速收斂法局部收斂性和加速收斂法7.3.1 不動(dòng)點(diǎn)迭代法及其收斂性不動(dòng)點(diǎn)迭代法及其收斂性 迭代法是一種迭代法是一種逐次逼近法逐次逼近法。它是求解代數(shù)方程，超。它是求解代數(shù)方程，超越方程

14、及方程組的一種基本方法，但越方程及方程組的一種基本方法，但存在收斂性及收斂存在收斂性及收斂快慢的問題快慢的問題。 為用迭代法求解為用迭代法求解f (x)=0的近似根，首先需將此方程的近似根，首先需將此方程化為等價(jià)的方程化為等價(jià)的方程 x=(x) (7.3.1) 然而將然而將 f (x)=0 化為等價(jià)方程化為等價(jià)方程（7.3.1）的方法是很多的。的方法是很多的。3( )10f xxx 例例1轉(zhuǎn)換成兩種等價(jià)形式把0)(xf3132 ( )1, ( )1,xxxxxx或 簡單迭代法簡單迭代法又稱為又稱為不動(dòng)點(diǎn)迭代法不動(dòng)點(diǎn)迭代法，基本思想是首先構(gòu)造不基本思想是首先構(gòu)造不動(dòng)點(diǎn)方程動(dòng)點(diǎn)方程 x= (x)，

15、即由方程，即由方程 f(x)=0變換為等價(jià)形式變換為等價(jià)形式 x= (x), 式式中中(x)稱為稱為迭代函數(shù)。然后建立迭代格式：迭代函數(shù)。然后建立迭代格式：xk+1 = (xk)稱為不稱為不動(dòng)點(diǎn)迭代格式。動(dòng)點(diǎn)迭代格式。1limlim()(lim)kkkkkkxxx 知知a= (a)，即，即xk收斂于方程的根收斂于方程的根 a。 a稱為函數(shù)稱為函數(shù) (x)的的不動(dòng)點(diǎn)不動(dòng)點(diǎn) 當(dāng)給定初值當(dāng)給定初值x0 后后, 由迭代格式由迭代格式xk+1 = (xk)可求得數(shù)列可求得數(shù)列xk。如果如果xk收斂于收斂于a，且，且(x)在在a連續(xù)，連續(xù)，則則a就是不動(dòng)點(diǎn)方程的根。就是不動(dòng)點(diǎn)方程的根。因?yàn)椋阂驗(yàn)椋豪?

16、1對(duì)應(yīng)的迭代法分別為對(duì)應(yīng)的迭代法分別為3131 1, 1,0,1,.kkkxxxxk或。0( )0( )( )kfxxxxxx顯然在由方程轉(zhuǎn)化為等價(jià)的方程時(shí)，選擇不同的迭代函數(shù)，就會(huì)產(chǎn)生不同的序列即使初值選擇一樣 且這些序列的收斂情況也不會(huì)相同。0*(1)1,(2)5,( )1 21 21.5,721.32471795724475由于既連續(xù)函數(shù)在區(qū)間 ，內(nèi)變號(hào)從而 ，為有根區(qū)間。取它的中點(diǎn)為初值，既令迭代結(jié)果列于表。此方程有唯一實(shí)根。顯然第一個(gè)迭代法收斂，第二個(gè)迭代法發(fā)散。fff xxx 表表 7-2012111.51.51.357208812.375000001.3308609612.396

17、48441.324717961133kkxxk1( )01( )()2kkkkf xg xxg xxx因此對(duì)用迭代法求方程近似根需要研究下述問題：（）如何選取迭代函數(shù)使迭代過程收斂（ ）若收斂較慢時(shí)，怎樣加速收斂。迭代法的幾何意義：1( )( )*,( )( )*()kkxxyxyxxxxxxx從幾何意義看，求方程根的問題，是求曲線與直線交點(diǎn)橫坐標(biāo)當(dāng)?shù)瘮?shù)的導(dǎo)數(shù)函數(shù)在根處滿足下述幾種條件時(shí)，從幾何上來看迭代過程的收斂情況如下圖。數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析記記y1=x , y2=(x) , 它們交點(diǎn)的橫坐標(biāo)它們交點(diǎn)的橫坐標(biāo)即為方程的根即為方程的根xy 1)(2xy )(,(00 xx )

18、(,(11xx ),(22xx)(,(22xx ),(11xx0 x2x1x pxy00 x1x2x )(2xy xy 1xy0數(shù)值分析數(shù)值分析數(shù)值分析數(shù)值分析xyy = xxyy = xxyy = xxyy = xx*x*x*x*y=(x)y=(x)y=(x)y=(x)x0p0 x1p1 x0p0 x1p1 x0p0 x1p1x0p0 x1p1, a b從以上迭代函數(shù)的圖像可以初步看出,如果迭代函數(shù)在區(qū)間是具有壓縮性質(zhì),則迭代法收斂,否則發(fā)散. , , , | ( )( )| |, ( )1. , ( ). .x ya bxyk xykxyxkxa bx 所謂壓縮性質(zhì)是指對(duì)任意的其中 為小于

19、1的常數(shù).將上式兩邊同除以則不難推出如果 則一定具有壓縮性質(zhì)為此有下述關(guān)于迭代法收斂性的定理 ( ),(a) ( )a,bba,b( )a,b, (c) ( )( )1, , , 定理7.1設(shè)有方程 設(shè)于一階導(dǎo)數(shù)存在，（ ）當(dāng)時(shí)，有滿足條件：則有：xxxxxxxLxa b *0*1k*1*101 ( ) , ,(2) , ,() (k0,1,.) lim ;1(3) 1(4) ,(1,2,.)1kkkkkkkxxa bxxa bxxxxxxxxLLxxxxkL（ ）在上有唯一解對(duì)任意選取初始值迭代過程 收斂,即誤差估計(jì)(4)(3),(2), : 只證證明,.)2 , 1(,2).2(0kbax

20、baxk時(shí)，則有），當(dāng)取由定理?xiàng)l件（由中值定理有：記誤差,*kkxxe*1()()( )()kkkxxxxc xx）有：又由條件（之間，即與在其中3,*bacxxckyxy=x0y=(x)aabb*x*1( )kkkxxcxxL xx由此遞推可得：0*2*21*.xxLxxLxxLxxkkkk*k01,limLxx由故1(3).()kkxx由迭代公式有：1111()()( )()kkkkkkkkxxxxc xxL xx于是之間與在其中.1kkxxc*111*() -L x(1-L) kkkkkkkkkxxxxxxxxxxxxxxx11*111kkkkkxxLLxxLxx即11(4).:kkkk

21、xxL xx由上面反復(fù)利用代入上式中有0121211*1.1L 111xxLLxxLxxLLxxLxxkkkkkkkkLxxxxkkk11,3*1則誤差時(shí)相鄰兩次迭代滿足條件）可知，當(dāng)計(jì)算得到的由定理結(jié)果（.,1.*11仍然可能很大誤差很小即使時(shí)但要注意來控制算法終止因此在計(jì)算機(jī)上可利用kkkkkxxxxLxx由事實(shí)上數(shù)精度要求所需要迭代次可確定使誤差達(dá)到給定結(jié)果利用定理時(shí)及給定精度要求及當(dāng)已知另外,)4(,) 1(,10kLLxx01*1xxLLxxkk:解得(4) ln/ )1ln(ln01LLxxk 若從任何可取的初值出發(fā)都能保證收斂，則稱它為若從任何可取的初值出發(fā)都能保證收斂，則稱它為

22、大范大范圍收斂圍收斂。如若為了保證收斂性必須選取初值充分接近于所要。如若為了保證收斂性必須選取初值充分接近于所要求的根，則稱它為求的根，則稱它為局部收斂局部收斂。 通常局部收斂方法比大范圍收斂方法收斂得快。因此，通常局部收斂方法比大范圍收斂方法收斂得快。因此，一個(gè)合理的算法是先用一種大范圍收斂方法求得接近于根的一個(gè)合理的算法是先用一種大范圍收斂方法求得接近于根的近似值（如對(duì)分法），再以其作為新的初值使用局部收斂法近似值（如對(duì)分法），再以其作為新的初值使用局部收斂法（如迭代法）。（如迭代法）。 這里討論迭代法的收斂性時(shí)，均指的是局部收斂性。這里討論迭代法的收斂性時(shí)，均指的是局部收斂性。( )1,

23、 , ,.定理7.1條件在一般情況下 可能對(duì)大范圍的含根區(qū)間不滿足而在根的鄰近是成立的為此有下述迭代過程的局部收斂性結(jié)果xLxa b7.3.2 局部收斂性局部收斂性*01*1: (),( ),(, ),0,(, ),()(, ),()kkkkkxxxU xxxxU xxxxU xxxx定義迭代法的局部收斂 設(shè) 為的不動(dòng)點(diǎn) 若存在的一個(gè)鄰域使得對(duì)任何初值由迭代法生成的序列滿足且收斂到則稱迭代法是局部收斂的.定理定理3 3 （迭代法的局部收斂定理）（迭代法的局部收斂定理）設(shè)設(shè)a是方程是方程x=(x)的根，如果的根，如果(1)迭代函數(shù)迭代函數(shù)(x)在在a的鄰域可導(dǎo)；的鄰域可導(dǎo)； (2)(2)在在a的

24、某個(gè)鄰域的某個(gè)鄰域S= =x:|:|x- - a | | , ,對(duì)于任對(duì)于任 意的意的 x S 有有1| )( | Lx 則對(duì)于任意的初值則對(duì)于任意的初值 x0 0 S S ，迭代公式，迭代公式xn+1 1= =( (xn) ) 產(chǎn)生的數(shù)列產(chǎn)生的數(shù)列 xn ，收斂于方程的根，收斂于方程的根a 。1*對(duì)于例的兩種迭代法，討論它們的收斂性。解233111( )1, ( )(1)3xxxx(1)對(duì)于迭代函數(shù)其導(dǎo)數(shù)。有容易驗(yàn)證，對(duì)任意2 , 1 x。121. 0)(,2 , 1 45. 1 ,26. 1 )(11xx01*1,2,( )12xxx因此，對(duì)于任何初值由給出的迭代法都收斂到區(qū)間，上的唯一不

25、動(dòng)點(diǎn) 。3222( )1, ( )3xxxx(2)對(duì)于迭代函數(shù)其導(dǎo)數(shù)。顯然，22*01,2( )0 7 ( )1,7.1,對(duì)有，不滿足定理的條件。從幾何上可以說明，只要初值該迭代法發(fā)散。xxxxx: ( )ln(2)0f xxx例2 由迭代法解方程*12: (1)(0)(2)0, (-1.9)(-1)0 0,2-1.9,-1,.ffffx x解顯然有即知方程于及內(nèi)有根,記為YxY=x0-2-112*1x*2x0111111(2).0,2 ln(2),( )ln(2),(0)ln(2)0.6930,(2)ln(4)1.3682,( )02( )2,kkxxxxxxxx先考察取初值迭代過程的收斂性

26、 其中迭代函數(shù)為顯然及為增函數(shù)，則當(dāng)時(shí)，0又由111( )(0)1 (0,2).22xxx 則有1( )2xxYxY=x0-2-112*1x*2x01*1*610,2 ln(2)110 )2kkkxxxxxx于是由前一定理可知，當(dāng)初值時(shí),迭代過程收斂，如果要求 近似根準(zhǔn)確到小數(shù)第位（即要求71514*71141410 .1/2.1.1461931,()0.8 10 xxLxxf x由計(jì)算結(jié)果可知且則k00.010.6931471820.99071046 .14 1.146193115 1.1461932*112*1002*2(3) 1.91.1 ln(2),( )()1,2 ln(2)( 1.

27、9, 1,).kkkkxxxxxxxxxxx 再討論求， 內(nèi)方程的根由迭代方程顯然所以迭代過程初值不能保證收斂于2222 201*0212812 e22( )( )( )( 1)0.3861.( 1.9, 1( ) 1.9, 1, 1.9, 12.1,121.841405660,()0.2 10 .kxxxxkxxexxexxxxxexxxf x 若將方程轉(zhuǎn)化為等價(jià)方程或則,且時(shí)）,所以當(dāng)選取時(shí),迭代過程收斂如取則迭代次有且1 ( )0,( )()kkkf xxxxx 由此例1*可見，對(duì)于方程迭代函數(shù)取不同形式，相應(yīng)的迭代法產(chǎn)生的收斂情況也不一樣，因此，我們應(yīng)該選擇迭代函數(shù)使構(gòu)造的迭代過程收斂

28、，且收斂較快。 有時(shí)，對(duì)于一些不滿足定理有時(shí)，對(duì)于一些不滿足定理7.1的條件問題，可以的條件問題，可以通過轉(zhuǎn)化，化為適合于迭代的形式。這要針對(duì)具體情通過轉(zhuǎn)化，化為適合于迭代的形式。這要針對(duì)具體情況進(jìn)行討論況進(jìn)行討論。3例試問如何滿足的已知, 13)( )( )(xxxx解，可得由)(xx,3)(3xxxx即可得等價(jià)方程。)(3(21xxx因此，令)(3(21)(xxx則有,21)( 321)(xx)(1kkxx因此，迭代式收斂。), 1 , 0(k( )x利用構(gòu)造一個(gè)收斂的簡單迭代函數(shù)？7.3.3 7.3.3 迭代法的收斂速度迭代法的收斂速度 一種迭代法具有實(shí)用價(jià)值，首先要求它是收斂的，其次還

29、一種迭代法具有實(shí)用價(jià)值，首先要求它是收斂的，其次還要求它收斂得比較快。要求它收斂得比較快。定義定義7.27.2 設(shè)迭代過程設(shè)迭代過程 收斂于收斂于 的根的根 , ,記迭代記迭代誤差誤差 , ,若存在常數(shù)若存在常數(shù)p（p1）和和c（c0），使使 )(1kkxx)(xx*xkkxxe*ceepkkk1lim則稱序列則稱序列 是是 p 階收斂的階收斂的, ,c稱漸近誤差常數(shù)。特別地稱漸近誤差常數(shù)。特別地, ,p=1=1時(shí)時(shí)稱為稱為線性收斂線性收斂, ,p=2=2時(shí)稱為時(shí)稱為平方收斂平方收斂。p 1時(shí)稱為時(shí)稱為超線性收斂超線性收斂。 kx 數(shù)數(shù)p 的大小反映了迭代法收斂的速度的快慢，的大小反映了迭代法

30、收斂的速度的快慢，p愈大，則愈大，則收斂的速度愈快，故迭代法的收斂階是對(duì)迭代法收斂速度的收斂的速度愈快，故迭代法的收斂階是對(duì)迭代法收斂速度的一種一種度量度量。 定理定理 設(shè)迭代過程設(shè)迭代過程 , 若若 在所求根在所求根 的鄰域連續(xù)且的鄰域連續(xù)且 則迭代過程在則迭代過程在 鄰域是鄰域是p階收斂的。階收斂的。)(1kkxx)()(xp*x*(1)*()()()0,pxxx*x0)(* x*x1)(* x)(1kkxx)(kx*xpkpkkkxxpxxxxxxxx)(!1)(! 21)()()(*)(2* 根據(jù)已知條件得根據(jù)已知條件得 pkpkxxpxx)(!1)()(*)(*由迭代公式由迭代公式

31、)(1kkxx及及)(*xx有有pkpkxxpxx)(!)(*)(*10!)(lim*)(1pxeeppkkk( )*()0px證證: 由于由于 即在即在 鄰域鄰域 , 所以所以 有局部收斂性有局部收斂性, 將將 在在 處泰勒展開處泰勒展開 ( ) , ( )0 xxa bx上定理表明迭代過程的收斂速度依賴于迭代函數(shù)的選取，如果時(shí)。則迭代過程只可能是線性收斂的。例例5 已知迭代公已知迭代公式式 收斂于收斂于 證明該迭代公式平方收斂證明該迭代公式平方收斂.證證: 迭代公式相應(yīng)的迭代函數(shù)為迭代公式相應(yīng)的迭代函數(shù)為21132kkkxxx3*3x2132)(xxx436)(232)(xxxx ，將將

32、代入代入，根據(jù)定理可知，迭代公式平方收斂。根據(jù)定理可知，迭代公式平方收斂。3*3x032336)(0)(33* xx，為了使迭代過程收斂或提高收斂的速度為了使迭代過程收斂或提高收斂的速度, 可設(shè)法可設(shè)法 提高提高初值的精度初值的精度以減少迭代的次數(shù)以減少迭代的次數(shù) 提高收斂的階數(shù)提高收斂的階數(shù) pSteffensen迭代格式 0limlim112nCeeeennnnnnnnneeee112*211nnnnxxxxxxxx*nxx 對(duì)于線性收斂的迭代法，收斂很慢，所以要在這些迭代法的基礎(chǔ)上考慮加速收斂的方法。設(shè)xk 線性收斂到x*，則迭代誤差en 滿足當(dāng)n充分大時(shí)有 即nnnnnnxxxxxxx

33、1221*2)(2*121*2)(2)(xxxxxxxxnnnn2*1212*2*2)(2)(xxxxxxxxxxxnnnnnn*121*2*22xxxxxxxxxnnnnnn21212*)2(nnnnnnxxxxxxx展開有：n已知 ，則 ，n改成nx)(1nnxx)(2nnxx nnnnnnnnnnnxyzxyxxyzxy2)()()(21 n=0，1，2，Steffensen迭代格式n也可以改寫成n其中迭代函數(shù),.)1 , 0()(1nxxnnxxxxxxx)(2)()()(2Steffensen迭代法收斂的充要條件n定理7.4.1 ,)(*1xxCx，設(shè)函數(shù)。件是的不動(dòng)點(diǎn)的充分必要條是

34、)()(*xxxxx，則為足夠小的正數(shù)，且1)(* xSteffensen迭代法收斂的充要條件n證明：必要性的不動(dòng)點(diǎn)，是因?yàn)?(*xxx)(2)()()(2xxxxxxx由于，所以0)(lim*xxxx，故有0)(lim*xxxx)(*xx即的不動(dòng)點(diǎn)。是所以)(*xxxSteffensen迭代法收斂的充要條件n充分性的不動(dòng)點(diǎn)有是由)(*xxxxxxxxxxxxxx)(2)()(lim)(lim2*1)(2)()( 1)()( 2lim*xxxxxxxxoo型0 1)( 1)()( 2lim2*xxxxxx的不動(dòng)點(diǎn)。是所以)(*xxxSteffensen算法的收斂速度n定理7.4.2 在定理7.

35、4.2假設(shè)下，若 產(chǎn)生的序列 至少平方收斂到 。,.2, 1 ,02)()()(21nxyzxyxxyzxySteffensennnnnnnnnnnn迭代格式則由 2C)(x0nx*x*xSteffensen算法的收斂速度的不動(dòng)點(diǎn)，是證明：)(*xxx。即)(*xx1)(11)(lim)(lim*xxxxxxxxooxx型又因?yàn)镾teffensen算法的收斂速度 *)(2)(lim*xxxxxxx及) 1)(2)()(lim*xxxxxoo型1)(2)()(*xxx2* 1)(xSteffensen算法的收斂速度 *)()(lim)(*xxxxxxx于是有*2)(2)()(lim*xxxxxx

36、xxxxx*2*)(2)()(lim1*xxxxxxxxxxx0 1)( 1)(12*2*xxSteffensen算法的收斂速度 由定理7.4.2知 至少以平方速度收斂到 。 也就是說：簡單迭代法是線性收斂；Steffensen迭代至少平方以上收斂（加速收斂）。0nx*x例題n例7.9試用Steffensen算法求解方程n解法一、取 ，由013 xx31)(xxnnnnnnnnnnnxyzxyxxyzxy2)()()(21 n = 0，1，2，例題n取初值 ，計(jì)算結(jié)果如下：5 . 10 xN XnYnZn0 1.51.3572088081.3308609591 1.3248991811.324

37、7523791.3247244962 1.3247179571.3247179571.324717957例題n解法二、取 ，由n對(duì)于該迭代函數(shù)在一般迭代法中是發(fā)散的，而Steffensen格式卻是收斂的。1)(3 xxnnnnnnnnnnnxyzxyxxyzxy2)()()(21 n=0，1，2，例題n取初值 ，計(jì)算結(jié)果如下：N XnYnZn0 1.52.3751.2396484371 1.4162929751.8409219155.2388727692 1.3556504421.4913982792.3172706993 1.3289487771.3470628831.4443512244

38、1.3248044891.3251735441.3271172815 1.3247179441.3247181521.3247189806 1.3247179575 . 10 xSteffensen迭代格式幾何解釋 Steffensen迭代算法 11002001200100210:)3(;)4);2/()()3;3|2|)2);();() 1| )(|while)2(;,) 1 (xendwhilexxxyzxyxxthenxyzifyzxyxxx輸出步做第做輸入Steffensen迭代算法 1.1.理解理解收斂性、收斂階收斂性、收斂階的概念及的概念及二分法二分法思想方法思想方法。 2.2.會(huì)

39、求會(huì)求用用二分法二分法解解非線性方程時(shí)的非線性方程時(shí)的執(zhí)行次數(shù)執(zhí)行次數(shù)k 。ln() ln1.ln2b ak0 為給定的誤差界為給定的誤差界. . 3.3.理解簡單迭代法的理解簡單迭代法的思想方法，幾何意義，壓縮不動(dòng)點(diǎn)定理。思想方法，幾何意義，壓縮不動(dòng)點(diǎn)定理。 4. 掌握簡單迭代法的收斂掌握簡單迭代法的收斂( (局部局部) )定理定理（定理證明，會(huì)判斷簡單（定理證明，會(huì)判斷簡單迭代法是否收斂）迭代法是否收斂）。7.4.2 割線法與拋物線法割線法與拋物線法7.4.1 Newton迭代法迭代法 7.4 一元方程的常用迭代法一元方程的常用迭代法 用迭代法可逐步精確方程用迭代法可逐步精確方程 根的近似

40、值根的近似值，但必須但必須要找到要找到 的等價(jià)方程的等價(jià)方程 , ,如果如果 選得不合適選得不合適, ,不僅影響收斂速度不僅影響收斂速度, ,而且有可能造成迭代格式發(fā)散。能否找到而且有可能造成迭代格式發(fā)散。能否找到一種迭代方法一種迭代方法, ,既結(jié)構(gòu)簡單既結(jié)構(gòu)簡單, ,收斂速度快收斂速度快, ,又不存在發(fā)散的問題又不存在發(fā)散的問題。這就是本節(jié)要介紹的牛頓迭代法。這就是本節(jié)要介紹的牛頓迭代法. .1 1 牛頓迭代法的基本思想牛頓迭代法的基本思想 牛頓迭代法一種重要和常用的迭代法牛頓迭代法一種重要和常用的迭代法, , 它的基本思想是將它的基本思想是將非線性函數(shù)非線性函數(shù)f(x)逐步線性化逐步線性化

41、, , 從而將非線性方程從而將非線性方程f( (x)=0)=0近似地近似地轉(zhuǎn)化為線性方程求解。轉(zhuǎn)化為線性方程求解。0)(xf0)(xf)(xx)(x7.4.1 Newton迭代法迭代法 對(duì)于方程對(duì)于方程 , ,設(shè)其近似根為設(shè)其近似根為 , , 函數(shù)函數(shù)f (x)可可在在 附近作泰勒展開附近作泰勒展開 0)(xfkxkx 2)(21)()()(kkkkkxxxfxxxfxfxf忽略高次項(xiàng)忽略高次項(xiàng), ,用其線性部分作為函數(shù)用其線性部分作為函數(shù) f (x)的近似，的近似， )()()(kkkxxxfxfxf 設(shè)設(shè) 的根的根 , ,則有則有 , ,即即 0)(xf*x0)(*xf0)()(*kkkx

42、xxfxf)()(*kkkxfxfxx將右端取為將右端取為 , ,即即 是比是比 更接近于更接近于 的近似值的近似值 )()(1kkkkxfxfxx)2,1 ,0(k1kx1kxkx*x這就是著名的牛頓迭代公式這就是著名的牛頓迭代公式（7.4.2）（7.4.1）3 3 牛頓迭代法的幾何解釋牛頓迭代法的幾何解釋yx0b )(xfy a0 x1x2x任取初始值任取初始值 ， bax,0 )(xfy 上過點(diǎn)上過點(diǎn) 的切線方程的切線方程為：為：)(,(00 xfx)()(000 xxxfxfy 與與 軸交于點(diǎn)軸交于點(diǎn)1xx)()(0001xfxfxx 過點(diǎn)過點(diǎn) 的切線方程為的切線方程為)(,(11xf

43、x)()(111xxxfxfy 與與 軸交于點(diǎn)軸交于點(diǎn)x2x)()(1112xfxfxx 如此下去得牛頓迭代公如此下去得牛頓迭代公式式:)()(1kkkkxfxfxx 用切線代替曲線，用用切線代替曲線，用線性函數(shù)的零點(diǎn)作為線性函數(shù)的零點(diǎn)作為 f(x)的零點(diǎn)的近似值。的零點(diǎn)的近似值。牛頓迭代法也牛頓迭代法也稱切線法稱切線法因此牛頓法產(chǎn)生的序列xk如下圖所示。 x0 x2x1過過P0的切線的切線過過P1的切線的切線將將(7.4.2)寫成一般的不動(dòng)點(diǎn)迭代寫成一般的不動(dòng)點(diǎn)迭代(7.3.3)的形式的形式,有有,)()()(xfxfxx 2)()()()(xfxfxfx 所以有所以有 ， Newton迭代

44、法是超線迭代法是超線性收斂的。更準(zhǔn)確地，從性收斂的。更準(zhǔn)確地，從(7.4.1)和和(7.4.2)可得下面的定理可得下面的定理.)0)( , 0)(* xfx （收斂的充分條件收斂的充分條件）設(shè)）設(shè) f C2a, b，若，若(1) f (a) f (b) 0； 則則Newtons Method產(chǎn)生的序列產(chǎn)生的序列 xk 收斂到收斂到f (x) 在在 a, b 的唯一根。的唯一根。產(chǎn)生的序列單調(diào)有產(chǎn)生的序列單調(diào)有界，保證收斂。界，保證收斂。定理定理13 3 牛頓迭代法的收斂性牛頓迭代法的收斂性證明： 根的存在性 根的唯一性內(nèi)至少有一個(gè)根。在知）及由條件（),(0)(,)(1baxfbaCxf。記此

45、根為內(nèi)有唯一根在上嚴(yán)格單調(diào)函數(shù)，因此是故保號(hào)，知及由*,),(0)(,)()(,bCa,)(, 0)(xbaxfbaxfxfxfxf)()(0)()(0)(, 0)(, 0)(,0)()(0)(, 0)(, 0)(, 0)(010000001000*000 xxxfxfxxfxfxxxfxfxfbxxxfxfxfxfbfaf 即有，所以知，由，不妨設(shè)收斂性繼續(xù)上述推理有代替。再以因此有兩式相減展式由另一方面0101*20*01*20*0*00*0)()()(21)(21)()()(0 Taylor,xxxxxxxxffxxxxfxxxfxfxf 。，由根的唯一性知可得時(shí)當(dāng)由。故必有極限，記。是

46、單調(diào)減有下界的序列故序列*10011*0)(,.2 , 1)()(lim.xaafnnxfxfxxaxxxxxxxnnnnnnnnnyx0ba x00)( xf0)( xfyx0bax00)( xf0)( xfyx0bax00)( xf0)( xfyx0Ba x00)( xf0)( xf例例1 用迭代法求用迭代法求 在隔根區(qū)間在隔根區(qū)間1.4,1.51.4,1.50123 xx內(nèi)的根，要求準(zhǔn)確到小數(shù)點(diǎn)后第內(nèi)的根，要求準(zhǔn)確到小數(shù)點(diǎn)后第4 4位。位。（1 1）牛頓迭代公式為牛頓迭代公式為nnnnnnnnnnnnnxxxxxxxxxxfxfxx2312231)()(2232231 （2 2）2 .

47、0)4 . 1( f2 . 0)5 . 1( f 5 . 1 , 4 . 1 x當(dāng)當(dāng) 時(shí)有，時(shí)有，023)(2 xxxf06)( xxf因因 , ,故取故取 , ,牛頓迭代法收斂。牛頓迭代法收斂。0)5 . 1()5 . 1( ff5 . 10 x 推論 在定理1條件下， Newton迭代法具有平方收斂速度。*2*12*1()()()1()lim02()n 1證明類似定理 證明，一般有12其中，介于 與 之間，則故結(jié)論成立。nnnnnnnnfxxxxfxxxefxefx 12*( *)lim( *)2( *)kkkxxfxxxfx （局部收斂性局部收斂性）設(shè)）設(shè) f C2a, b，若，若 x*

48、 為為 f (x) 在在a, b上的根，且上的根，且 f (x*) 0，則存在，則存在 x* 的鄰域的鄰域 使得任取初使得任取初值值 ，若，若Newtons Method產(chǎn)生的序列產(chǎn)生的序列 xk 收斂到收斂到x*，則至少二階收斂，且，則至少二階收斂，且*)(xB *)(0 xBx 定理定理2function y=newton(fname,dfname,x0,e,N)y=x0;x0=y+2*e;k=0;while abs(x0-y)e&k0,都有都有 ,并且并且 非增非增.因此因此 是有下界的非增序列是有下界的非增序列 ，從而有極限，從而有極限x*。對(duì)。對(duì)（7.4.3）的兩邊取極限）的

49、兩邊取極限,得到得到 -a=0,因?yàn)橐驗(yàn)?0，故有，故有x*= 。） ,2,1(kaxk0 xkxkxa 2*xkx211,0 , 1 ,22kkkkkkxaaxxxkxx由此可知由此可知證證 對(duì)對(duì)f(x)= -a, f(x)=2x, Newton迭代法為迭代法為2x例例2 設(shè)設(shè)a0,對(duì)方程對(duì)方程 -a=0. 試證試證:取任何初值取任何初值 0，Newton迭代法都收斂到算術(shù)根迭代法都收斂到算術(shù)根 。a0 x2x（7.4.3）練習(xí)練習(xí)1 用Newton法求 的近似解。解：由零點(diǎn)定理。0cos)(xxxf內(nèi)有根。在)2, 0(0cosxx迭代公式得及由Newtonxxfsin1)(,.1 , 0

50、sin1cos1nxxxxxnnnnn085133739. 0739085133. 0739085133. 0739085178. 0;73936133. 044*43210 xxxxxxx故取得取練習(xí)練習(xí)n練習(xí)2 用Newton法計(jì)算 。解：220)(2aaxxf其中迭代公式得及由Newtonxxf2)(,.1 , 0)2(212221nxxxxxxnnnnnn。有十位有效數(shù)的近似值是已的精確值相比，。與，則取332102414213562. 1414215686. 11.416666675 . 1xxxxx設(shè)設(shè)x*是是f(x)=0的的m重根重根,，即，即2 m.0)(),()()(* xg

51、xgxxxfm在前個(gè)定理中在前個(gè)定理中,要要求求f(x*)=0 , 即即 是是方程的單根時(shí)方程的單根時(shí), Newton法至少具有二階局部收斂性。法至少具有二階局部收斂性。下下面討論重根的情形面討論重根的情形.,0)(* xf*x由由Newton迭代函數(shù)迭代函數(shù) 的導(dǎo)數(shù)表達(dá)式的導(dǎo)數(shù)表達(dá)式,)(x.11)(*mx 從而，從而， 。因此只要。因此只要 ，這時(shí)的，這時(shí)的Newton迭代法線性收斂。迭代法線性收斂。*0()1x0)( kxf容易求出容易求出( )( ),( )f xxxfx為了改善重根時(shí)為了改善重根時(shí)Newton法的收斂性，有如下兩種方法法的收斂性，有如下兩種方法。(1) 若改為取若改為

52、取)()()(xfxmfxx 容易驗(yàn)證容易驗(yàn)證 。 迭代至少二階收斂迭代至少二階收斂.0)(*x(2)若令若令 ,由由x*是是f(x)的的m重零點(diǎn)，有重零點(diǎn)，有)()()(xfxfx .)()()()()()()()(2xfxfxfxfxfxxxxx 這種方法也是至少二階收斂的這種方法也是至少二階收斂的.所以，所以，x*是是 的單零點(diǎn)的單零點(diǎn).可將可將Newton法的迭代函數(shù)修改為法的迭代函數(shù)修改為)(x)()()()()()(*xgxxxmgxgxxx 1( )0(),()(0).():kkkkf xma mZf xxxmkfx 若若方方程程有有 重重根根試試證證明明牛牛頓頓迭迭代代法法是是

53、線線性性收收斂斂的的 而而改改用用修修改改的的格格式式才才是是局局部部平平方方收收斂斂的的例例1( )(1)( )( )0( )()( ),( )0.( )()( )()( )() ( )( )( ):)mmmf xxxfxf xmf xxah xh afxm xah xxah xxa h xxxmh xxah x 對(duì)對(duì)牛牛頓頓格格式式, , 迭迭代代函函數(shù)數(shù) ( (因因有有重重根根, ,故故有有且且代代入入迭迭代代函函數(shù)數(shù)式式( (證證明明( )1( )()( )( )()()( )()( )h xxmh xxa h xdh xxadx mh xxa h x ( (111,( )10.,(

54、)()( ()( )( )()()|1( )10lim|.kkkkkkkkxaamaxaxxaaxao xaaxCaaxm 代代入入有有于于是是 由由得得到到故故這這種種牛牛頓頓迭迭代代法法只只有有線線性性收收斂斂速速度度 212( )(2)( )() ( )( )()( )( )1( )()( )( )()()( )()( ),)01)21)2kkkkkkf xxxmfxxa h xxxmmh xxa h xmh xxmh xxa h xdh xm xadx mh xxa h xaaxaxaxaax 對(duì)對(duì)修修改改的的牛牛頓頓格格式式, , 迭迭代代函函數(shù)數(shù) ( ( ( (此此時(shí)時(shí)( (再再由

55、由( ( ( (12|11|)|)|0|22.kkkaxCaax 得得到到( ( (因因此此修修改改后后的的牛牛頓頓格格式式是是平平方方收收斂斂的的例例7.9 方程方程 的根的根 是二重根是二重根.用三用三種方法求解種方法求解.04424 xx2* x解解 (1)用用Newton法有法有.4221kkkkxxxx (2)由由(7.4.4),m=2迭代公式為迭代公式為.2221kkkkxxxx(3) 由由(7.4.5)確定的修改方法，迭代公式化簡為確定的修改方法，迭代公式化簡為.2)2(221kkkkkxxxxx 三種方法均取三種方法均取 =1.5,計(jì)算結(jié)果列于表計(jì)算結(jié)果列于表6-7.方法（方法

56、（2）和方）和方法法(3)都是二階方法，都是二階方法， 都達(dá)到了誤差限為都達(dá)到了誤差限為 的精確度的精確度,而普通而普通的的Newton法是一階的法是一階的,要近要近30次迭代才有相同精度的結(jié)果次迭代才有相同精度的結(jié)果.0 x0 x910 Xk X0 X1 X2 X3方法(1) 1.5 1.458333333 1.436607143 1.425497619方法(2) 1.5 1.416666667 1.414215686 1.414213562方法(3) 1.5 1.411764706 1.414211438 1.414213562表表7-7Newton法的每步計(jì)算都要求提供函數(shù)的導(dǎo)數(shù)值，當(dāng)函

57、數(shù)法的每步計(jì)算都要求提供函數(shù)的導(dǎo)數(shù)值，當(dāng)函數(shù)f(x) 比較復(fù)雜時(shí)，提供它的導(dǎo)數(shù)值往往是有困難的。此時(shí)，比較復(fù)雜時(shí)，提供它的導(dǎo)數(shù)值往往是有困難的。此時(shí)，在在Newton迭代法（迭代法（7.4.2）中，可用）中，可用 或常數(shù)或常數(shù)D取代取代 迭代式變?yōu)榈阶優(yōu)?(0 xf),(kxf)()(01xfxfxxkkk.)(1Dxfxxkkk或或這稱為這稱為簡化簡化Newton法法。其迭代函數(shù)為。其迭代函數(shù)為?；駾xfxxxfxfxx)()()( )()(0簡化簡化Newton法一般為線性收斂。法一般為線性收斂。*()0 x通常* 牛頓下山法牛頓下山法* * * 通常通常,牛頓迭代法的收斂性依賴于初始

58、值牛頓迭代法的收斂性依賴于初始值 的選取的選取,如果如果 偏離偏離所求的根所求的根 比較遠(yuǎn)比較遠(yuǎn),則牛頓法可能發(fā)散。為了防止迭代發(fā)散則牛頓法可能發(fā)散。為了防止迭代發(fā)散,我們我們對(duì)牛頓迭代法的迭代過程再附加一項(xiàng)要求對(duì)牛頓迭代法的迭代過程再附加一項(xiàng)要求,即具有單調(diào)性即具有單調(diào)性0 x0 x*x)()(1kkxfxf 將牛頓迭代法與下山法結(jié)合起來使用將牛頓迭代法與下山法結(jié)合起來使用,即在下山法保證即在下山法保證函數(shù)函數(shù)值下降值下降的前提下的前提下,用牛頓迭代法加快收斂速度。把這一算法稱用牛頓迭代法加快收斂速度。把這一算法稱為為牛頓下山法牛頓下山法。即。即滿足這項(xiàng)要求的算法稱下山法。滿足這項(xiàng)要求的算法

59、稱下山法。)()(1kkkkxfxfxx其中其中(01)為下山因子為下山因子 . 下山因子的選擇是個(gè)逐步探索的過程，設(shè)從下山因子的選擇是個(gè)逐步探索的過程，設(shè)從=1開始反開始反復(fù)將復(fù)將減半進(jìn)行試算減半進(jìn)行試算, 即逐次取即逐次取為為從中挑選下山因子，直至找到其中某個(gè)從中挑選下山因子，直至找到其中某個(gè)使單調(diào)性條件使單調(diào)性條件成立，則稱成立，則稱“下山成功下山成功”，否則，否則“下山失敗下山失敗”，這時(shí)需另選初值重算。這時(shí)需另選初值重算。,21,21,12)()(1kkxfxf7.4.2 割線法與拋物線法割線法與拋物線法 111 ,0(), (), ()( )( )00kkk rkkk rrrkx

60、xxf xf xf xf xP xP xf xx設(shè)是的一組近似根，利用對(duì)應(yīng)的函數(shù)值，構(gòu)造插值多項(xiàng)式，適當(dāng)選取的一個(gè)根作為的新的近似根。1( ), (),( )kkkf xf xf x下面設(shè)法多利用以前各次計(jì)算的函數(shù)值來回避導(dǎo)數(shù)值計(jì)算，導(dǎo)出這種求根方法的基本原理是插值法。1()()( ),( )kkkkkkf xfxNewtonxxf xf xf法每迭代一次計(jì)算函數(shù)值導(dǎo)數(shù)值各一次，當(dāng) 函數(shù)本身比較復(fù)雜時(shí)，求導(dǎo)數(shù)值更加困難。11, ,1(2(kkkk rgxg x xxrr。這樣就確定了一個(gè)迭代過程，記迭代函數(shù)為 ，則下面具體考察弦截法）與拋物線）兩種情形。1. 割線法割線法/弦截法弦截法11111111