第二章非線性方程的數(shù)值解法

1、2.1 2.1 引言引言 方程方程f(x)=0f(x)=0的根的根, , 亦稱為函數(shù)亦稱為函數(shù)f(x)f(x)的零點(diǎn)的零點(diǎn) 如果如果f(x)f(x)可以分解成可以分解成 , ,其中其中m m為正整數(shù)為正整數(shù)且且 , , 則稱則稱x x* *是是f(x)f(x)的的m m重零點(diǎn)重零點(diǎn), ,或方程或方程f(x)=0f(x)=0的的m m重根。重根。 當(dāng)當(dāng)m=1m=1時(shí)稱時(shí)稱x x* *為單根。為單根。 若若f(x)f(x)存在存在m m階導(dǎo)數(shù)階導(dǎo)數(shù), , x*是方程是方程f(x)f(x)的的m m重根重根( (m1) m1) 當(dāng)且當(dāng)且僅當(dāng)僅當(dāng))()()(*xgxxxfm0)(*xg0)(,0)()

2、()(*)(*)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次代數(shù)方程,當(dāng)n1時(shí),方程顯然是非線性的. 一般稍微復(fù)雜的3次以上的代數(shù)方程或超越方程,很難甚至無(wú)法求得精確解。本章將介紹常用的求解非線性方程的近似根的

3、幾種數(shù)值解法 通常方程根的數(shù)值解法大致分為三個(gè)步驟：判定根的存在性。即方程有沒有根？如果有根，有 幾個(gè)根？確定根的分布范圍。即將每一個(gè)根用區(qū)間隔 離開來（該區(qū)間稱為有根區(qū)間），這個(gè)過程目的是 獲得方程各根的初始近似值。 根的精確化。將根的初始近似值按某種方法逐步 精確化，直到滿足預(yù)先要求的精度為止。 根的存在性：n 方程的根幾何上講是曲線 y=f (x)與x軸交點(diǎn)的橫坐標(biāo)。n代數(shù)方程，其根的個(gè)數(shù)（實(shí)或復(fù)的）與其次數(shù)相同。n非代數(shù)方程，其根可能是一個(gè)、幾個(gè)或無(wú)解。n高等數(shù)學(xué)關(guān)于根在特定區(qū)間上的存在性 f(xf(x) )為區(qū)間為區(qū)間 a,ba,b上的單值連續(xù)上的單值連續(xù), , 如果如果f(a)f(

4、a)f(bf(b)0 , )0 , 則則 a,ba,b中至少有一個(gè)實(shí)根。如果中至少有一個(gè)實(shí)根。如果f(xf(x) )在在 a,ba,b上還是單調(diào)地遞增上還是單調(diào)地遞增或遞減，則僅有一個(gè)實(shí)根。或遞減，則僅有一個(gè)實(shí)根。y=f(x)aby有根區(qū)間：n根據(jù)介質(zhì)定理n一般選擇區(qū)間長(zhǎng)度較小的單根區(qū)間n確定有根區(qū)間的方法：(1)(1)畫圖法畫圖法畫出畫出y = f (x)y = f (x)的略圖，從而看出曲線與的略圖，從而看出曲線與x x軸交點(diǎn)的大致位軸交點(diǎn)的大致位置。置。也可將也可將f (x)=0f (x)=0分解為分解為 1 1( (x)= x)= 2 2(x)(x)的形式，的形式， 1 1( (x)x

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

6、) (2) 搜索法搜索法 對(duì)于給定的對(duì)于給定的f (x)f (x)和區(qū)間和區(qū)間A,B,A,B,從從x x0 0=A=A出發(fā)出發(fā), ,以步以步長(zhǎng)長(zhǎng)h=(B-A)/n(nh=(B-A)/n(n是正整數(shù)是正整數(shù)),),在在 A,BA,B內(nèi)取定節(jié)點(diǎn)內(nèi)取定節(jié)點(diǎn): :x xi i=x=x0 0ih (i=0,1,2,ih (i=0,1,2,n),n),從左至右檢查從左至右檢查f (xf (xi i) )的符號(hào)的符號(hào), ,如發(fā)現(xiàn)如發(fā)現(xiàn)x xi i與端點(diǎn)與端點(diǎn)x xi-1i-1的函數(shù)值異號(hào)的函數(shù)值異號(hào)( (相鄰兩點(diǎn)函數(shù)值異相鄰兩點(diǎn)函數(shù)值異號(hào)號(hào)),),則得到一個(gè)縮小的有根子區(qū)間則得到一個(gè)縮小的有根子區(qū)間x xi

7、-1i-1,x,xi i。例例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è)從設(shè)從x=0 x=0出發(fā)出發(fā), ,取取h=0.5h=0.5為步長(zhǎng)向右進(jìn)行根的為步長(zhǎng)向右進(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)必有一根 注意事項(xiàng)注意事項(xiàng)n用逐步

8、搜索法進(jìn)行實(shí)根隔離的關(guān)鍵是選取步長(zhǎng)用逐步搜索法進(jìn)行實(shí)根隔離的關(guān)鍵是選取步長(zhǎng)hn 要選擇適當(dāng)要選擇適當(dāng)h ，使之既能把根隔離開來，工作量，使之既能把根隔離開來，工作量 又不太大。又不太大。 問題問題n在獲取有根區(qū)間后，如何獲取指定精度要求的初值？在獲取有根區(qū)間后，如何獲取指定精度要求的初值？n注意，在隔根區(qū)間上，函數(shù)是單調(diào)連續(xù)的注意，在隔根區(qū)間上，函數(shù)是單調(diào)連續(xù)的n二分法可以在隔根區(qū)間上求得滿意值。二分法可以在隔根區(qū)間上求得滿意值。2.2 二分法二分法 二分法又稱二分區(qū)間法,是求解方程(2.1)的近似根的一種常用的簡(jiǎn)單方法。 二分法的基本思想是: 首先確定有根區(qū)間（單根區(qū)間）,將區(qū)間二等分, 通

9、過判斷f(x)在二等分點(diǎn)的符號(hào), 逐步將有根區(qū)間縮小, 直至有根區(qū)間足夠地?。ㄐ〉皆搮^(qū)間的長(zhǎng)度小于要求的精度）, 便可求出滿足精度要求的近似根（取最后一個(gè)區(qū)間的二等分點(diǎn)作為近似值）。 取區(qū)間取區(qū)間a,b之中點(diǎn)之中點(diǎn), 第一次將它分為兩半第一次將它分為兩半,分點(diǎn)分點(diǎn) ,這樣可得縮小的有根區(qū)間這樣可得縮小的有根區(qū)間a1,b12.2.1 二分法求根過程 設(shè)方程f(x)=0在區(qū)間a,b內(nèi)有唯一根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 對(duì)壓縮了的有根區(qū)間對(duì)壓縮了的有根區(qū)間 施行同樣的手法：施行同樣的手

10、法： 取中點(diǎn)取中點(diǎn) , ,將區(qū)間將區(qū)間 再分為兩半再分為兩半, ,然然 后再確定有根區(qū)間后再確定有根區(qū)間 , ,其長(zhǎng)度是其長(zhǎng)度是 的的 二分之一二分之一 如此反復(fù)下去如此反復(fù)下去, ,若不出現(xiàn)若不出現(xiàn) , ,即可得出一即可得出一 系列有根區(qū)間序列：系列有根區(qū)間序列： 上述每個(gè)區(qū)間都是前一個(gè)區(qū)間的一半上述每個(gè)區(qū)間都是前一個(gè)區(qū)間的一半, ,因此因此 的長(zhǎng)度的長(zhǎng)度11,ba2111bax11,ba22,ba11,ba0)(kxfkkbabababa,2211kkba ,)(21)(2111abababkkkkk 當(dāng)k時(shí)趨于零,這些區(qū)間最終收斂于一點(diǎn)x* 即為 所求的根 。K K次二分后次二分后, ,

11、有根區(qū)間有根區(qū)間 的中點(diǎn)為的中點(diǎn)為 對(duì)給定精度對(duì)給定精度，只要，只要K K足夠大，就可以使足夠大，就可以使11122kkkkkababab1*22kkkkbabaxxkkba ,)(21kkkbaxkxx*kkbax,*當(dāng)給定精度當(dāng)給定精度0 0后后, ,要想要想 成立成立, ,只要只要取取k k滿足滿足 即可，亦即當(dāng)即可，亦即當(dāng): : kxx*)(211abk12lglg)lg(abk時(shí)（時(shí)（本質(zhì)是取第本質(zhì)是取第K K個(gè)區(qū)間的中點(diǎn)個(gè)區(qū)間的中點(diǎn)）, ,做到第做到第k k次二分次二分, ,計(jì)算得到計(jì)算得到的的 就是滿足精度要求的近似根就是滿足精度要求的近似根 。 在程序中通常用相鄰的在程序中通常

12、用相鄰的 與與 的差的絕對(duì)值或的差的絕對(duì)值或 與與 的差的絕對(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|01,1.5f(x)0，即，即f(xf(x) )在在1.0,1.51.0,1.5上單調(diào)連續(xù)。又上單調(diào)連續(xù)。又f(1)0f(1)0，故，故f(Xf(X) )0 0在在1.0,1.51.0,1.5上有唯一根。列表計(jì)算如下上有唯一根。列表計(jì)算如下kxkf(xk)有根區(qū)間誤差限01.2500-1.2500,1.50000.5/211.

13、3750+1.2500,1.37500.5/421.3125-1. 3125,1.37500.5/831.3438+1. 3125,1.34380.5/1641.3281+1. 3125, 1.32810.5/3251.3203-1. 3203, 1.32810.5/6461.32420.5/12852)(3xxxf016)3(, 01)2(ff且且f(x)f(x)在在2, 32, 3上連續(xù)上連續(xù), ,故方程故方程f(x)=0f(x)=0在在2,32,3內(nèi)至少內(nèi)至少有一個(gè)根。又有一個(gè)根。又 當(dāng)當(dāng)時(shí)，時(shí)， , ,故故f(x)f(x)在在2, 32, 3上是單調(diào)遞增函數(shù)上是單調(diào)遞增函數(shù), ,從而從

14、而f(x)f(x)在在2, 32, 3上有且僅有一根。上有且僅有一根。23)(2xxf3 , 2x0)( xf 給定誤差限給定誤差限 0.5 0.51010-3 -3 , ,使用二分法時(shí)使用二分法時(shí)例例 證明方程證明方程 在區(qū)間在區(qū)間2, 32, 3內(nèi)有一個(gè)內(nèi)有一個(gè)根根, , 使用二分法求誤差不超過使用二分法求誤差不超過0.50.51010-3 -3 的根要二的根要二分多少次？分多少次？證明證明 令令 0523 xx 誤差限為誤差限為 只要取只要取k k滿足滿足 )(211*abxxkk311021)(21 abk即可，亦即即可，亦即 3102 k97.92110lg3gk所以需二分所以需二分

15、1010次便可達(dá)到要求。次便可達(dá)到要求。 二分法的優(yōu)點(diǎn)是不管有根區(qū)間二分法的優(yōu)點(diǎn)是不管有根區(qū)間 多大多大, ,總總能求出滿足精度要求的根能求出滿足精度要求的根, ,且對(duì)函數(shù)且對(duì)函數(shù)f(x)f(x)的要求不高的要求不高, ,只要連續(xù)即可只要連續(xù)即可, ,計(jì)算亦簡(jiǎn)單計(jì)算亦簡(jiǎn)單; ;它的局限性是只能用于它的局限性是只能用于求函數(shù)的實(shí)根求函數(shù)的實(shí)根, ,不能用于求復(fù)根及重根不能用于求復(fù)根及重根, ,它的收斂速它的收斂速度與比值為度與比值為 的等比級(jí)數(shù)相同的等比級(jí)數(shù)相同。 ba ,212.3 迭代法迭代法 迭代法是一種逐次逼近的方法,用某個(gè)固定公式反復(fù)校正根的近似值,使之逐步精確化，最后得到滿足精度要求

16、的結(jié)果。2.3.1 2.3.1 迭代法的基本思想迭代法的基本思想 為求解非線性方程為求解非線性方程f(x)=0f(x)=0的根，先將其寫成便的根，先將其寫成便于迭代的等價(jià)方程于迭代的等價(jià)方程 (2.3) (2.3)其中其中 為為x x的連續(xù)函數(shù)的連續(xù)函數(shù))(x)(xx 如果數(shù)如果數(shù) 使使f(x)=0, 則也有則也有 , 反之反之, 若若 , 則也有則也有 , 稱稱 為迭代函數(shù)為迭代函數(shù) .任任取一個(gè)初值取一個(gè)初值 , 代入式代入式 的右端的右端, 得到得到 *x)(*xx)(*xx0)(*xf)(x0 x)(xx)(01xx再將再將 代入式代入式 的右端的右端, 得到得到 ,依此類推依此類推,

17、 得到一個(gè)數(shù)列得到一個(gè)數(shù)列其一般表示其一般表示 1x)(xx)(12xx012,.,.kx x xx), 2 , 1 , 0()(1kxxkk用式用式(2.4)(2.4)求根的方法稱為求解非線性方程的簡(jiǎn)單迭求根的方法稱為求解非線性方程的簡(jiǎn)單迭代法。代法。 (2.4)(2.4)如果由迭代格式如果由迭代格式 產(chǎn)生的序列產(chǎn)生的序列 收斂收斂, ,即即 nx)(1kkxx*, limnnxRxx ，則稱，則稱迭代法收斂迭代法收斂。 實(shí)際計(jì)算中實(shí)際計(jì)算中, ,對(duì)預(yù)先給定的精度要求對(duì)預(yù)先給定的精度要求，只要某個(gè)只要某個(gè)k k滿足滿足 1kkxx即結(jié)束計(jì)算并取即結(jié)束計(jì)算并取 kxx*所以所以 *()xx由于

18、由于 1limlim()( lim)nnnnnnxxx 所以所以 *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é)果見式分別迭代，計(jì)算結(jié)果見P P2121 0 x2.3.2 迭代法的幾何意義迭代法的幾何意義 將方程將方程f(x)=0f(x)=0化為與它

19、同解的方程化為與它同解的方程，方程，方程 的求根問題在幾何上就是確定曲線的求根問題在幾何上就是確定曲線y= y= 與與直線直線y=xy=x的交點(diǎn)的交點(diǎn)P P* *的橫坐標(biāo)的橫坐標(biāo)( (圖圖2-32-3所示所示) )。 的性態(tài)對(duì)的性態(tài)對(duì)求根有直接影響。求根有直接影響。)(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 x2 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

20、 x x1 x2 x3 x* y=)(x)(x x* x2 P* 圖圖2-3 迭代法的幾何意義迭代法的幾何意義 2.3.3 2.3.3 迭代法收斂的條件迭代法收斂的條件 定理定理2.1 2.1 設(shè)函數(shù)設(shè)函數(shù) 在在 a,ba,b上具有連續(xù)的一階導(dǎo)上具有連續(xù)的一階導(dǎo)數(shù)數(shù), , 且滿足且滿足 （1 1）對(duì)所有的）對(duì)所有的xa,b xa,b 有有 a,ba,b （2 2）存在存在 0 0 L 1 ,L 1 ,使所有的使所有的xa,bxa,b有有 L L則方程則方程 在在 a,ba,b上的解上的解 存在且唯一存在且唯一，對(duì)任意的，對(duì)任意的 a ,b a ,b ，迭代過程迭代過程均收斂于均收斂于 。并有誤

21、差估計(jì)式。并有誤差估計(jì)式 )(x)(x)(x)(xx*x0 x)(1kkxx*x1*1kkkxxLLxx01*1xxLLxxkk 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ù)。特別地,p=1時(shí)稱為線性收斂,p=2時(shí)稱為平方收斂。1 p 0 xn+1X*ayx0Bf(x)0a=x0yx0B=x0f(x)0ayx0Bf(x)0a =x0 2.4.3 牛頓迭代

22、法的收斂性牛頓迭代法的收斂性yx10 x0X*0 x0X*x2 不滿足迭代條件時(shí)，可能導(dǎo)致迭代值遠(yuǎn)離不滿足迭代條件時(shí)，可能導(dǎo)致迭代值遠(yuǎn)離根的情況而找不到根或死循環(huán)的情況根的情況而找不到根或死循環(huán)的情況2.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 2. .4. .4 牛頓迭代法的算法實(shí)現(xiàn)牛頓迭代法的算法實(shí)現(xiàn)例例2.11 用用求求 x=e-x的根的根,=10-4

23、解：因解：因 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.567142. .4. .5 牛頓下山法牛頓下山法 通常通常, ,牛頓迭代法的收斂性依賴于初始值牛頓迭代法的收斂性依賴于初始值 的選取的選取, ,如果如果 偏離所求的根偏離所求的根 比較遠(yuǎn)比較遠(yuǎn), ,則牛頓法可能發(fā)散。則牛頓法可能發(fā)散。為了防止迭代發(fā)散為了防止迭代發(fā)散, ,我們對(duì)牛頓迭代法的迭代過程再附我們對(duì)牛頓迭代法的迭代過程再附加一項(xiàng)要求加一項(xiàng)要求, ,即具有單調(diào)性即具有單調(diào)性 0 x0 x*x)()(1kkxfxf 將牛頓迭代法與下山法結(jié)合起來使用將牛頓迭代法與下山法結(jié)合起來使用, ,即在下山即在下山法保證函數(shù)值下降的前提下法保證函數(shù)值下降的前提下, ,用牛頓迭代法加快收斂用牛頓迭代法加快收斂