第二章非線性方程的數值解法

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

2、()(*)(*)1(*xfxfxfxfmm記筆記記筆記 當當f(x)f(x)不是不是x x的線性函數時，稱對應的函數方程為的線性函數時，稱對應的函數方程為非線性非線性方程方程。 如果如果f(x)f(x)是多項式函數，則稱為代數方程，否則稱為超是多項式函數，則稱為代數方程，否則稱為超越方程（三角方程，指數、對數方程等）。越方程（三角方程，指數、對數方程等）。n n次多項式構成的次多項式構成的方程方程 )0(00111nnnnnaaxaxaxa為n次代數方程,當n1時,方程顯然是非線性的. 一般稍微復雜的3次以上的代數方程或超越方程,很難甚至無法求得精確解。本章將介紹常用的求解非線性方程的近似根的

3、幾種數值解法 通常方程根的數值解法大致分為三個步驟：判定根的存在性。即方程有沒有根？如果有根，有 幾個根？確定根的分布范圍。即將每一個根用區(qū)間隔 離開來（該區(qū)間稱為有根區(qū)間），這個過程目的是 獲得方程各根的初始近似值。 根的精確化。將根的初始近似值按某種方法逐步 精確化，直到滿足預先要求的精度為止。 根的存在性：n 方程的根幾何上講是曲線 y=f (x)與x軸交點的橫坐標。n代數方程，其根的個數（實或復的）與其次數相同。n非代數方程，其根可能是一個、幾個或無解。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中至少有一個實根。如果中至少有一個實根。如果f(xf(x) )在在 a,ba,b上還是單調地遞增上還是單調地遞增或遞減，則僅有一個實根?；蜻f減，則僅有一個實根。y=f(x)aby有根區(qū)間：n根據介質定理n一般選擇區(qū)間長度較小的單根區(qū)間n確定有根區(qū)間的方法：(1)(1)畫圖法畫圖法畫出畫出y = f (x)y = f (x)的略圖，從而看出曲線與的略圖，從而看出曲線與x x軸交點的大致位軸交點的大致位置。置。也可將也可將f (x)=0f (x)=0分解為分解為 1 1( (x)= x)= 2 2(x)(x)的形式，的形式， 1 1( (x)x

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

6、) (2) 搜索法搜索法 對于給定的對于給定的f (x)f (x)和區(qū)間和區(qū)間A,B,A,B,從從x x0 0=A=A出發(fā)出發(fā), ,以步以步長長h=(B-A)/n(nh=(B-A)/n(n是正整數是正整數),),在在 A,BA,B內取定節(jié)點內取定節(jié)點: :x xi i=x=x0 0ih (i=0,1,2,ih (i=0,1,2,n),n),從左至右檢查從左至右檢查f (xf (xi i) )的符號的符號, ,如發(fā)現(xiàn)如發(fā)現(xiàn)x xi i與端點與端點x xi-1i-1的函數值異號的函數值異號( (相鄰兩點函數值異相鄰兩點函數值異號號),),則得到一個縮小的有根子區(qū)間則得到一個縮小的有根子區(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）內至少有一個實根）內至少有一個實根 設從設從x=0 x=0出發(fā)出發(fā), ,取取h=0.5h=0.5為步長向右進行根的為步長向右進行根的 搜索搜索, ,列表如下列表如下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用逐步

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

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

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

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

12、用相鄰的 與與 的差的絕對值或的差的絕對值或 與與 的差的絕對值是否小于的差的絕對值是否小于來決定二分區(qū)間的次數。來決定二分區(qū)間的次數。 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上單調連續(xù)。又上單調連續(xù)。又f(1)0f(1)0，故，故f(Xf(X) )0 0在在1.0,1.51.0,1.5上有唯一根。列表計算如下上有唯一根。列表計算如下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內至少內至少有一個根。又有一個根。又 當當時，時， , ,故故f(x)f(x)在在2, 32, 3上是單調遞增函數上是單調遞增函數, ,從而從

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

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

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

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

18、由于 1limlim()( lim)nnnnnnxxx 所以所以 *x，即，即 是解是解 例例4 用迭代法求方程用迭代法求方程 在在x=1.5附近的一個根附近的一個根解解 將方程改寫成如下兩種等價形式將方程改寫成如下兩種等價形式 013 xx1)(1)(3231xxxxxx相應地可得到兩個迭代公式相應地可得到兩個迭代公式1)(1)(321311kkkkkkxxxxxx如果取初始值如果取初始值 1.51.5，用上述兩個迭代公，用上述兩個迭代公式分別迭代，計算結果見式分別迭代，計算結果見P P2121 0 x2.3.2 迭代法的幾何意義迭代法的幾何意義 將方程將方程f(x)=0f(x)=0化為與它

19、同解的方程化為與它同解的方程，方程，方程 的求根問題在幾何上就是確定曲線的求根問題在幾何上就是確定曲線y= y= 與與直線直線y=xy=x的交點的交點P P* *的橫坐標的橫坐標( (圖圖2-32-3所示所示) )。 的性態(tài)對的性態(tài)對求根有直接影響。求根有直接影響。)(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 設函數設函數 在在 a,ba,b上具有連續(xù)的一階導上具有連續(xù)的一階導數數, , 且滿足且滿足 （1 1）對所有的）對所有的xa,b xa,b 有有 a,ba,b （2 2）存在存在 0 0 L 1 ,L 1 ,使所有的使所有的xa,bxa,b有有 L L則方程則方程 在在 a,ba,b上的解上的解 存在且唯一存在且唯一，對任意的，對任意的 a ,b a ,b ，迭代過程迭代過程均收斂于均收斂于 。并有誤

21、差估計式。并有誤差估計式 )(x)(x)(x)(xx*x0 x)(1kkxx*x1*1kkkxxLLxx01*1xxLLxxkk 10)(xx 開 始 輸 入 x0,N 1 kk+ 1 k x1 x0 輸 出 近 似 根 x1 |x1- x0|? 輸 出 迭 代 失 敗 標 志 結 束 n k0c0），），使使 )(1kkxx)(xx*xkkxxe*ceepkkk1lim則稱序列 是 p 階收斂的,c稱漸近誤差常數。特別地,p=1時稱為線性收斂,p=2時稱為平方收斂。1 p 0 xn+1X*ayx0Bf(x)0a=x0yx0B=x0f(x)0ayx0Bf(x)0a =x0 2.4.3 牛頓迭代

22、法的收斂性牛頓迭代法的收斂性yx10 x0X*0 x0X*x2 不滿足迭代條件時，可能導致迭代值遠離不滿足迭代條件時，可能導致迭代值遠離根的情況而找不到根或死循環(huán)的情況根的情況而找不到根或死循環(huán)的情況2.4.3 牛頓迭代法的收斂性牛頓迭代法的收斂性 ?0)(0 xf 1000)()(xxfxfx ?01 xx 開 始 輸 入 x0,N 1 k k+ 1 k x1 x0 輸 出 x1 輸 出 迭 代 失 敗 標 志 結 束 n k N ? n n y 輸 出 奇 異 標 志 y y 2. .4. .4 牛頓迭代法的算法實現(xiàn)牛頓迭代法的算法實現(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,逐次計算得逐次計算得 x1=0.57102, x2=0.56716， x3=0.567142. .4. .5 牛頓下山法牛頓下山法 通常通常, ,牛頓迭代法的收斂性依賴于初始值牛頓迭代法的收斂性依賴于初始值 的選取的選取, ,如果如果 偏離所求的根偏離所求的根 比較遠比較遠, ,則牛頓法可能發(fā)散。則牛頓法可能發(fā)散。為了防止迭代發(fā)散為了防止迭代發(fā)散, ,我們對牛頓迭代法的迭代過程再附我們對牛頓迭代法的迭代過程再附加一項要求加一項要求, ,即具有單調性即具有單調性 0 x0 x*x)()(1kkxfxf 將牛頓迭代法與下山法結合起來使用將牛頓迭代法與下山法結合起來使用, ,即在下山即在下山法保證函數值下降的前提下法保證函數值下降的前提下, ,用牛頓迭代法加快收斂用牛頓迭代法加快收斂