第三章方程的近似解法.

1、3.1 引言引言 在科學(xué)研究和工程設(shè)計(jì)中在科學(xué)研究和工程設(shè)計(jì)中, 經(jīng)常會(huì)遇到的一大類經(jīng)常會(huì)遇到的一大類問題是非線性方程問題是非線性方程f(x)=0 (3.1)的求根問題，其中的求根問題，其中f(x)為非線性函數(shù)。為非線性函數(shù)。方程方程f(x)=0的根的根, 亦稱為函數(shù)亦稱為函數(shù)f(x)的零點(diǎn)的零點(diǎn) 如果如果f(x)可以分解成可以分解成 , ,其中其中m為為正整數(shù)且正整數(shù)且 , ,則稱則稱x x* *是是f(x)f(x)的的m重零點(diǎn)重零點(diǎn), ,或稱或稱方程方程f(x)=0的的m重根。當(dāng)重根。當(dāng)m=1時(shí)稱時(shí)稱x x* *為單根。若為單根。若f(x)存在存在m階導(dǎo)數(shù)階導(dǎo)數(shù), ,則是方程則是方程f(x

2、)的的m重根重根( (m1) 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng))()()(*xgxxxfm0)(*xg0)(, 0)()()(*)(*)1(*xfxfxfxfmm記筆記記筆記 當(dāng)當(dāng)f(x)f(x)不是不是x x的線性函數(shù)時(shí)，稱對(duì)應(yīng)的函數(shù)方程的線性函數(shù)時(shí)，稱對(duì)應(yīng)的函數(shù)方程為非線性方程。如果為非線性方程。如果f(x)f(x)是多項(xiàng)式函數(shù)，則稱為代數(shù)是多項(xiàng)式函數(shù)，則稱為代數(shù)方程，否則稱為超越方程（三角方程，指數(shù)、對(duì)數(shù)方方程，否則稱為超越方程（三角方程，指數(shù)、對(duì)數(shù)方程等）。一般稱程等）。一般稱n n次多項(xiàng)式構(gòu)成的方程次多項(xiàng)式構(gòu)成的方程 )0(00111nnnnnaaxaxaxa為為n n次代數(shù)方程次代數(shù)方程, ,當(dāng)當(dāng)

3、n n1 1時(shí)時(shí), ,方程顯然是非線性的方程顯然是非線性的 一般稍微復(fù)雜的一般稍微復(fù)雜的3 3次以上的代數(shù)方程或超越方程次以上的代數(shù)方程或超越方程, ,很難甚至無法求得精確解。本章將介紹常用的求解很難甚至無法求得精確解。本章將介紹常用的求解非線性方程的近似根的幾種數(shù)值解法非線性方程的近似根的幾種數(shù)值解法 記筆記記筆記 本章介紹方程的迭代解法，它既可以用來求解代本章介紹方程的迭代解法，它既可以用來求解代數(shù)方程，也可以用來解超越方程，并且僅限于求數(shù)方程，也可以用來解超越方程，并且僅限于求方程的實(shí)根。方程的實(shí)根。運(yùn)用迭代法求解方程的根應(yīng)解決以下兩個(gè)問題：運(yùn)用迭代法求解方程的根應(yīng)解決以下兩個(gè)問題：n確

4、定根的初值確定根的初值;n將進(jìn)一步精確化到所需要的精度。將進(jìn)一步精確化到所需要的精度。記筆記記筆記3.2 二分法二分法 二分法又稱二分區(qū)間法二分法又稱二分區(qū)間法, ,是求解方程是求解方程(2.1)(2.1)的近的近似根的一種常用的簡單方法。似根的一種常用的簡單方法。 設(shè)函數(shù)設(shè)函數(shù)f(x)f(x)在閉區(qū)間在閉區(qū)間 a,ba,b上連續(xù)上連續(xù), ,且且f(f(a)f()f(b)0,)0,根據(jù)連續(xù)函數(shù)的性質(zhì)可知根據(jù)連續(xù)函數(shù)的性質(zhì)可知, , f( (x)= 0)= 0在在( (a,b)a,b)內(nèi)必有實(shí)根內(nèi)必有實(shí)根, ,稱區(qū)間稱區(qū)間 a,ba,b為有根區(qū)間。為明確為有根區(qū)間。為明確起見起見, ,假定方程假

5、定方程f(x)=0f(x)=0在區(qū)間在區(qū)間 a,ba,b內(nèi)有惟一實(shí)根內(nèi)有惟一實(shí)根x x* *。 二分法的基本思想是二分法的基本思想是: : 首先確定有根區(qū)間首先確定有根區(qū)間, ,將區(qū)將區(qū)間二等分間二等分, , 通過判斷通過判斷f(x)f(x)的符號(hào)的符號(hào), , 逐步將有根區(qū)間逐步將有根區(qū)間縮小縮小, , 直至有根區(qū)間足夠地小直至有根區(qū)間足夠地小, , 便可求出滿足精度便可求出滿足精度要求的近似根。要求的近似根。3.2.1確定有根區(qū)間的方法確定有根區(qū)間的方法 為了確定根的初值，首先必須圈定根所在的范圍，為了確定根的初值，首先必須圈定根所在的范圍， 稱為稱為圈定根或根的隔離圈定根或根的隔離。 在上

6、述基礎(chǔ)上，采取適當(dāng)?shù)臄?shù)值方法確定具有一定在上述基礎(chǔ)上，采取適當(dāng)?shù)臄?shù)值方法確定具有一定 精度要求的初值。精度要求的初值。 對(duì)于代數(shù)方程，其根的個(gè)數(shù)（實(shí)或復(fù)的）與其次數(shù)對(duì)于代數(shù)方程，其根的個(gè)數(shù)（實(shí)或復(fù)的）與其次數(shù) 相同。至于超越方程，其根可能是一個(gè)、幾個(gè)或無相同。至于超越方程，其根可能是一個(gè)、幾個(gè)或無 解，并沒有什么固定的圈根方法解，并沒有什么固定的圈根方法 求方程根的問題，就幾何上講求方程根的問題，就幾何上講,是求曲線是求曲線 y=f (x)與與 x軸交點(diǎn)的橫坐標(biāo)。軸交點(diǎn)的橫坐標(biāo)。 由高等數(shù)學(xué)知識(shí)知由高等數(shù)學(xué)知識(shí)知, 設(shè)設(shè)f (x)為區(qū)間為區(qū)間a,b上的單上的單值連續(xù)值連續(xù), 如果如果f (a)

7、f (b)0 , 則則a,b中至少有一個(gè)中至少有一個(gè)實(shí)根。如果實(shí)根。如果f (x)在在a,b上還是單調(diào)地遞增或遞減，上還是單調(diào)地遞增或遞減，則僅有一個(gè)實(shí)根。則僅有一個(gè)實(shí)根。記筆記記筆記n由此可大體確定根所在子區(qū)間，方法有：由此可大體確定根所在子區(qū)間，方法有： (1) 畫圖法畫圖法 (2) 逐步搜索法逐步搜索法y=f(x)abyx(1) 畫圖法畫圖法 畫出畫出y = f (x)的略圖，從而看出曲線與的略圖，從而看出曲線與x軸交點(diǎn)的軸交點(diǎn)的 大致位置。大致位置。 也可將也可將f (x) = 0分解為分解為 1(x)= 2(x)的形式，的形式， 1(x) 與與 2(x)兩曲線交點(diǎn)的橫坐標(biāo)所在的子區(qū)間

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

9、從從x0=A出發(fā)出發(fā), ,以步長以步長h=(B-A)/n(n是是正整數(shù)正整數(shù)),在在A, ,B內(nèi)取內(nèi)取定節(jié)點(diǎn)定節(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 1 方程方程f(x)=xf(x)=x3 3-x-1=0 -x-1=0 確定其有根區(qū)間確定其有根區(qū)間解：用試湊的方法，不難發(fā)現(xiàn)解：用試湊的方法，不難發(fā)現(xiàn) f(0)0f(0)0 在區(qū)間（在區(qū)間（0 0，2 2）內(nèi)至少有一個(gè)實(shí)根）內(nèi)至少有一個(gè)實(shí)根 設(shè)

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

11、小該含根子區(qū)間基礎(chǔ)上采用對(duì)分法繼續(xù)縮小該含根子區(qū)間 二分法可以看作是搜索法的一種改進(jìn)。二分法可以看作是搜索法的一種改進(jìn)。 取有根區(qū)間取有根區(qū)間a,b之中點(diǎn)之中點(diǎn), 將它分為兩半將它分為兩半,分點(diǎn)分點(diǎn) ,這樣就可縮小有根區(qū)間這樣就可縮小有根區(qū)間3.2.2 二分法求根過程二分法求根過程 設(shè)方程設(shè)方程f(x)=0在區(qū)間在區(qū)間a,b內(nèi)有根內(nèi)有根,二分法就是逐二分法就是逐步收縮有根區(qū)間，最后得出所求的根。步收縮有根區(qū)間，最后得出所求的根。具體過程如下具體過程如下 20bax y y=f(x) y=f(x) x* a x1 x* x0 b a x0 x1 b a1 b1 a1 b1 a2 b2 a2 b2

12、 對(duì)壓縮了的有根區(qū)間對(duì)壓縮了的有根區(qū)間 施行同樣的手法施行同樣的手法, , 即取中點(diǎn)即取中點(diǎn) , ,將區(qū)間將區(qū)間 再分為兩半再分為兩半, ,然然 后再確定有根區(qū)間后再確定有根區(qū)間 , ,其長度是其長度是 的的 二分之一二分之一 如此反復(fù)下去如此反復(fù)下去, ,若不出現(xiàn)若不出現(xiàn) , ,即可得出一即可得出一 系列有根區(qū)間序列：系列有根區(qū)間序列： 上述每個(gè)區(qū)間都是前一個(gè)區(qū)間的一半上述每個(gè)區(qū)間都是前一個(gè)區(qū)間的一半, ,因此因此 的長度的長度11,ba2111bax11,ba22,ba11,ba0)(kxfkkbabababa,2211kkba ,)(21)(2111abababkkkkk 當(dāng)當(dāng)k時(shí)趨于零

13、時(shí)趨于零, ,這些區(qū)間最終收斂于一點(diǎn)這些區(qū)間最終收斂于一點(diǎn)x x* * 即為即為 所求的根所求的根 。每次二分后每次二分后, ,取有根區(qū)間取有根區(qū)間 的中點(diǎn)的中點(diǎn)作為根的近似值，得到一個(gè)近似根的序列作為根的近似值，得到一個(gè)近似根的序列 該序列以根該序列以根x x* *為極限為極限 只要二分足夠多次只要二分足夠多次( (即即k足夠大足夠大),),便有便有這里這里為給定精度為給定精度, ,由于由于 , ,則則 11122kkkkkababab1*22kkkkababxxkkba ,)(21kkkbax,210kxxxxkxx*kkbax,*當(dāng)給定精度當(dāng)給定精度0 0后后, ,要想要想 成立成立,

14、,只要只要取取k滿足滿足 即可，亦即當(dāng)即可，亦即當(dāng): kxx*)(211abk12lglg)lg(abk時(shí)時(shí), ,做到第做到第k+1次二分次二分, ,計(jì)算得到的計(jì)算得到的 就是就是滿足精度要求的近似根滿足精度要求的近似根 。 在程序中通常用相鄰的在程序中通常用相鄰的 與與 的差的絕的差的絕對(duì)值或?qū)χ祷?與與 的差的絕對(duì)值是否小于的差的絕對(duì)值是否小于來來決定二分區(qū)間的次數(shù)。決定二分區(qū)間的次數(shù)。 kxkx1kxkakb y n 開 始 輸 入 a , b, (a+b)/2 x f(a) f(x )0 ? xb x a |b-a|0 輸 出 x 結(jié) 束 y n 二分法算法實(shí)現(xiàn)二分法算法實(shí)現(xiàn)例例 求求

15、方程方程f( (x)=)=x3 3- -x-1=0 -1=0 在區(qū)間在區(qū)間1.0,1.5,1.5內(nèi)內(nèi) 的一的一 個(gè)實(shí)根個(gè)實(shí)根, 使誤差不超過使誤差不超過0.510-2。P19例例 證明方程證明方程 在區(qū)間在區(qū)間2, 3內(nèi)有一個(gè)根內(nèi)有一個(gè)根 , 使用二分法求誤差不超過使用二分法求誤差不超過0.510-3 的根要二的根要二 分多少次？分多少次？證明證明 令令 0523 xx52)(3xxxf016)3(, 01)2(ff且且f(x)f(x)在在2, 3上連續(xù)上連續(xù), ,故方程故方程f(x)=0f(x)=0在在2,32,3內(nèi)至少內(nèi)至少有一個(gè)根。又有一個(gè)根。又 當(dāng)時(shí)當(dāng)時(shí)時(shí)，時(shí)， , ,故故f(x)f(

16、x)在在2, 32, 3上是單調(diào)遞增函數(shù)上是單調(diào)遞增函數(shù), ,從而從而f(x)f(x)在在2, 32, 3上有且僅有一根。上有且僅有一根。23)(2xxf3 , 2x0)( xf 給定誤差限給定誤差限 0.510-3 , ,使用二分法時(shí)使用二分法時(shí) 誤差限為誤差限為 只要取只要取k滿足滿足 )(211*abxxkk311021)(21 abk即可，亦即即可，亦即 3102 k97.92110lg3gk所以需二分所以需二分1010次便可達(dá)到要求。次便可達(dá)到要求。 二分法的優(yōu)點(diǎn)是不管有根區(qū)間二分法的優(yōu)點(diǎn)是不管有根區(qū)間 多大多大, ,總總能求出滿足精度要求的根能求出滿足精度要求的根, ,且對(duì)函數(shù)且對(duì)

17、函數(shù)f(x)f(x)的要求不高的要求不高, ,只要連續(xù)即可只要連續(xù)即可, ,計(jì)算亦簡單計(jì)算亦簡單; ;它的局限性是只能用于它的局限性是只能用于求函數(shù)的實(shí)根求函數(shù)的實(shí)根, ,不能用于求復(fù)根及重根不能用于求復(fù)根及重根, ,它的收斂速它的收斂速度與比值為度與比值為 的等比級(jí)數(shù)相同。的等比級(jí)數(shù)相同。 ba ,213.3 迭代法迭代法 對(duì)于一般的非線性方程對(duì)于一般的非線性方程, ,沒有通常所說的求根沒有通常所說的求根公式求其精確解公式求其精確解, ,需要設(shè)計(jì)近似求解方法需要設(shè)計(jì)近似求解方法, ,即迭代法。即迭代法。它是一種逐次逼近的方法它是一種逐次逼近的方法, ,用某個(gè)固定公式反復(fù)校正用某個(gè)固定公式反復(fù)

18、校正根的近似值根的近似值, ,使之逐步精確化，最后得到滿足精度要使之逐步精確化，最后得到滿足精度要求的結(jié)果。求的結(jié)果。3.3.1 3.3.1 迭代法的基本思想迭代法的基本思想 為求解非線性方程為求解非線性方程f(x)=0f(x)=0的根，先將其寫成便的根，先將其寫成便于迭代的等價(jià)方程于迭代的等價(jià)方程 (3.3) (3.3)其中其中 為為x x的連續(xù)函數(shù)的連續(xù)函數(shù))(x)(xx3.3 迭代法迭代法即如果數(shù)即如果數(shù) 使使f(x)=0, 則也有則也有 , 反之反之, 若若 , 則也有則也有 , 稱稱 為迭代函數(shù)為迭代函數(shù) 任任取一個(gè)初值取一個(gè)初值 , 代入式代入式 的右端的右端, 得到得到 *x)(

19、*xx)(*xx0)(*xf)(x0 x)(xx)(01xx再將再將 代入式代入式 的右端的右端, 得到得到 ,依此類推依此類推, 得到一個(gè)數(shù)列得到一個(gè)數(shù)列 ， 其一般表示其一般表示 1x)(xx)(12xx)(23xx), 2 , 1 , 0()(1kxxkk式式(3.4)(3.4)稱為求解非線性方程的稱為求解非線性方程的簡單迭代法簡單迭代法。 (3.4)(3.4)如果由迭代格式如果由迭代格式 產(chǎn)生的序列產(chǎn)生的序列 收斂收斂, ,即即 nx)(1kkxx*limxxnn則稱迭代法收斂。則稱迭代法收斂。 實(shí)際計(jì)算中當(dāng)然不可能也沒必要無窮多步地做實(shí)際計(jì)算中當(dāng)然不可能也沒必要無窮多步地做下去下去,

20、 , 對(duì)預(yù)先給定的精度要求對(duì)預(yù)先給定的精度要求，只要某個(gè)只要某個(gè)k k滿足滿足1kkxx即可結(jié)束計(jì)算并取即可結(jié)束計(jì)算并取 kxx* 當(dāng)然，迭代函數(shù)當(dāng)然，迭代函數(shù) 的構(gòu)造方法是多種多樣的。的構(gòu)造方法是多種多樣的。)( x例例4 用迭代法求方程用迭代法求方程 在在x=1.5附近的一個(gè)根附近的一個(gè)根解解 將方程改寫成如下兩種等價(jià)形式將方程改寫成如下兩種等價(jià)形式 013 xx1)(1)(3231xxxxxx相應(yīng)地可得到兩個(gè)迭代公式相應(yīng)地可得到兩個(gè)迭代公式1)(1)(321311kkkkkkxxxxxx如果取初始值如果取初始值 1.51.5，用上述兩個(gè)迭代公，用上述兩個(gè)迭代公式分別迭代，試給出計(jì)算結(jié)果式

21、分別迭代，試給出計(jì)算結(jié)果0 x3.3.2 迭代法的幾何意義迭代法的幾何意義 通常將方程通常將方程f(x)=0f(x)=0化為與它同解的方程化為與它同解的方程的方法不止一種的方法不止一種, ,有的收斂有的收斂, ,有的不收斂有的不收斂, ,這取決于這取決于 的性態(tài)的性態(tài), ,方程方程 的求根問題在幾何上就是確定曲的求根問題在幾何上就是確定曲線線y= 與直線與直線y=x的交點(diǎn)的交點(diǎn)P*的橫坐標(biāo)的橫坐標(biāo)( (圖圖3-3所示所示) ) )(xx)(x)(xx)(x y=x y y=)(x y=x 1)(0*x 0)(1*x P0 P2P* Q1 Q2 x1 x0 x2 x* x y x0 x x1 x

22、2 x3 x* y=)(x)(x P* P1 (a)(b) y=x y y=x y=)(x 1)(* x 1)(* x （c） （d） P* x1 x0 x y x0 x x1 x2 x3 x* y=)(x)(x x* x2 P* 圖圖3-3 迭代法的幾何意義迭代法的幾何意義 3.3.3 迭代法收斂的條件迭代法收斂的條件 對(duì)方程對(duì)方程f(x)=0可以構(gòu)造不同的迭代公式可以構(gòu)造不同的迭代公式, 但但迭代公式迭代公式并非總是收斂。那么并非總是收斂。那么, ,當(dāng)?shù)瘮?shù)當(dāng)?shù)瘮?shù) 滿足什滿足什么條件時(shí)，相應(yīng)的迭代公式才收斂呢？即使迭么條件時(shí)，相應(yīng)的迭代公式才收斂呢？即使迭代收斂時(shí)，我們也不可能迭代很

23、多次，而是迭代收斂時(shí)，我們也不可能迭代很多次，而是迭代有限次后就停止，這就需要估計(jì)迭代值的誤代有限次后就停止，這就需要估計(jì)迭代值的誤差，以便適時(shí)終止迭代差，以便適時(shí)終止迭代 ),2, 1 ,0()(1kxxkk)(x定理定理3.1 設(shè)函數(shù)設(shè)函數(shù) 在在a,b上具有連續(xù)的一階導(dǎo)上具有連續(xù)的一階導(dǎo) 數(shù)數(shù), 且滿足且滿足 （1）對(duì)所有的）對(duì)所有的xa,b 有有 a,b （2）存在存在 0 L 1 ,使所有的使所有的xa,b有有 L則方程則方程 在在a,b上的解上的解 存在且唯一存在且唯一，對(duì)任意的，對(duì)任意的 a ,b ，迭代過程迭代過程均收斂于均收斂于 。并有誤差估計(jì)式。并有誤差估計(jì)式 )(x)(x)

24、(x)(xx*x0 x)(1kkxx*x1*1kkkxxLLxx01*1xxLLxxkk 由連續(xù)函數(shù)介值定理知由連續(xù)函數(shù)介值定理知, 必有必有 a, b, 使使 所以有解存在所以有解存在, 即即假設(shè)有兩個(gè)解假設(shè)有兩個(gè)解 和和 , , a, b，則則 ，由微分中值定理有由微分中值定理有其中其中是介于是介于x*和和 之間的點(diǎn)之間的點(diǎn) 從而有從而有a,b，進(jìn)進(jìn)而有而有 由條件由條件(2)有有 1, 所所以以 - =0，即，即 = ，解唯一。，解唯一。證證: 構(gòu)造函數(shù)構(gòu)造函數(shù) ,由條件對(duì)任意的由條件對(duì)任意的xa, b a, b有有xxx)()(0)()(0)()(bbbaaa)(x*x0)()(*xx

25、x*xx*xx)(*xx)(xx)()()(*xxxxxxx0)(1)(*xx)(x*xx*xx按迭代過程按迭代過程 ,有有 )(1kkxx)()()(1*1*kkkxxxxxx1*1*)(kkkxxLxxxx0*2*21*xxLxxLxxLxxkkkk 由于由于L1,L1,所以有所以有 , ,可見可見L L越小越小, ,收斂越快收斂越快 *limxxkk再證誤差估計(jì)式再證誤差估計(jì)式 1*1kkkxxLLxx01*1xxLLxxkk 1*1*kkkkkxxxxLxxLxx)(1*kkkxxxxL1*)1 (kkkxxLxxL1*1kkkxxLLxx 即即 得證。得證。 2121211)()()

26、(kkkkkkkkxxLxxxxxx012121*1111xxLLxxLLxxLxxkkkkkk即即 得證。得證。 10)(xx 開 始 輸 入 x0,N 1 kk+ 1 k x1 x0 輸 出 近 似 根 x1 |x1- x0|? 輸 出 迭 代 失 敗 標(biāo) 志 結(jié) 束 n k0c0），），使使 )(1kkxx)(xx*xkkxxe*ceepkkk1lim則稱序列則稱序列 是是 p 階收斂的階收斂的, ,c稱漸近誤差常數(shù)。稱漸近誤差常數(shù)。特別地特別地, ,p=1=1時(shí)稱為線性收斂時(shí)稱為線性收斂, ,p=2=2時(shí)稱為平方收時(shí)稱為平方收斂。斂。1 1 p 2 0 xn+1X*ayx0Bf(x)0

27、a=x0yx0B=x0f(x)0ayx0Bf(x)0a =x0 3.4.3 牛頓迭代法的收斂性牛頓迭代法的收斂性yx10 x0X*0 x0X*x2 不滿足迭代條件時(shí)，可能導(dǎo)致迭代值遠(yuǎn)離不滿足迭代條件時(shí)，可能導(dǎo)致迭代值遠(yuǎn)離根的情況而找不到根或死循環(huán)的情況根的情況而找不到根或死循環(huán)的情況3.4.3 牛頓迭代法的收斂性牛頓迭代法的收斂性 ?0)(0 xf 1000)()(xxfxfx ?01 xx 開 始 輸 入 x0,N 1 k k+ 1 k x1 x0 輸 出 x1 輸 出 迭 代 失 敗 標(biāo) 志 結(jié) 束 n k N ? n n y 輸 出 奇 異 標(biāo) 志 y y 牛頓迭代法的算法實(shí)現(xiàn)牛頓迭代法

28、的算法實(shí)現(xiàn)例例 11 用用求求 x=e-x的根的根,=10-4解：因解：因 f (xk)= x ex 1 , f (xk)=ex ( x+1)建立迭代公式建立迭代公式nxnnnxxnnnxexxxeexxxnnn 1)1 (11取取x0=0.5,逐次計(jì)算得逐次計(jì)算得 x1=0.57102, x2=0.56716， x3=0.56714對(duì)于方程 ，由于它的根在迭代前并不知道，因而定理3.4的條件不易驗(yàn)證。為此，下面給出判定牛頓法收斂的一個(gè)充分條件，并給出初始值的選取原則(見p77定理2 )。)(xx3.5 弦截法弦截法 牛頓迭代法雖然具有收斂速度快的優(yōu)點(diǎn)，牛頓迭代法雖然具有收斂速度快的優(yōu)點(diǎn)，但每

29、迭代一次都要計(jì)算導(dǎo)數(shù)但每迭代一次都要計(jì)算導(dǎo)數(shù) , 當(dāng)當(dāng) 比較比較復(fù)雜時(shí)復(fù)雜時(shí), 不僅每次計(jì)算不僅每次計(jì)算 帶來很多不便，而帶來很多不便，而且還可能十分麻煩，如果用不計(jì)算導(dǎo)數(shù)的迭且還可能十分麻煩，如果用不計(jì)算導(dǎo)數(shù)的迭代方法，往往只有線性收斂的速度。本節(jié)介代方法，往往只有線性收斂的速度。本節(jié)介紹的弦截法便是一種不必進(jìn)行導(dǎo)數(shù)運(yùn)算的求紹的弦截法便是一種不必進(jìn)行導(dǎo)數(shù)運(yùn)算的求根方法。弦截法在迭代過程中不僅用到前一根方法。弦截法在迭代過程中不僅用到前一步步 處的函數(shù)值，而且還使用處的函數(shù)值，而且還使用 處的函數(shù)處的函數(shù)值來構(gòu)造迭代函數(shù)，這樣做能提高迭代的收值來構(gòu)造迭代函數(shù)，這樣做能提高迭代的收斂速度。斂速度

30、。)(kxf )(xf)(kxfkx1kx 3.5.1 弦截法的基本思想弦截法的基本思想 為避免計(jì)算函數(shù)的導(dǎo)數(shù)為避免計(jì)算函數(shù)的導(dǎo)數(shù) ，使用差商，使用差商 替代牛頓公式中的導(dǎo)數(shù)替代牛頓公式中的導(dǎo)數(shù) ,便得到迭代公式便得到迭代公式 稱為弦截迭代公式，稱為弦截迭代公式， 相應(yīng)的迭代法稱為弦截法相應(yīng)的迭代法稱為弦截法。)()()(11kkkkxxxfxf)(kxf )()()()(111kkkkkkkxxxfxfxfxx),2, 1(k)(kxf 3.5.2 弦截法幾何意義弦截法幾何意義弦截法也稱割線法弦截法也稱割線法, ,其幾何意義是用過曲線上兩其幾何意義是用過曲線上兩點(diǎn)點(diǎn) 、 的割線來代替曲線的割

31、線來代替曲線, ,用割用割線與線與x軸交點(diǎn)的橫座標(biāo)作為方程的近似根軸交點(diǎn)的橫座標(biāo)作為方程的近似根 再過再過P1點(diǎn)和點(diǎn)點(diǎn)和點(diǎn) 作割線求出作割線求出 , ,再再過過P2點(diǎn)和點(diǎn)點(diǎn)和點(diǎn) 作割線求出作割線求出 , ,余余此類推，當(dāng)收斂時(shí)此類推，當(dāng)收斂時(shí)可求出滿足精度要可求出滿足精度要求的求的 P1 y=f(x) x0 x2 x3 x1 x* P3 P0 P2 )(,(000 xfxP)(,(111xfxP2x)(,(222xfxP3x)(,(333xfxP4xkx 可以證明，弦截法具有超線性收斂，收斂可以證明，弦截法具有超線性收斂，收斂的階約為的階約為1.618，它與前面介紹的一般迭代法，它與前面介紹的一般迭代法一樣都是線性化方法，但也有區(qū)別。即一般迭一樣都是線性化方法，但也有區(qū)別。即一般迭代法在計(jì)算代法在計(jì)算 時(shí)只用到前一步的值時(shí)只用到前一步的值 ，故稱，故稱之為單點(diǎn)迭代法；而弦截法在求之