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

1、1第二章 非線性方程的數(shù)值解法醫(yī)學技術(shù)學院醫(yī)學信息工程教研室賴小波 博士，副教授，碩士研究生導師第第2章章 非線性方程的數(shù)值解法非線性方程的數(shù)值解法 本章主要內(nèi)容：本章主要內(nèi)容：1 1、方程有根區(qū)間的確定、方程有根區(qū)間的確定2 2、二分法、迭代法、牛頓迭代法、弦截法求方程、二分法、迭代法、牛頓迭代法、弦截法求方程 基本原理與方法基本原理與方法（重點）（重點） 。3 3、迭代的構(gòu)造及其收斂性判定、迭代的構(gòu)造及其收斂性判定（重點）（重點）4 4、迭代過程的加速、迭代過程的加速5 5、非線性方程組的迭代解法、非線性方程組的迭代解法 工程實際與科學計算中都遇到大量求解非線工程實際與科學計算中都遇到大量

2、求解非線性方程的問題。設非線性方程性方程的問題。設非線性方程 f(x)=0 (2.1) (2.1)求數(shù)求數(shù)x* *, ,使使f (x*)00，的求根問題，其中，的求根問題，其中f(x)f(x)為非為非線性函數(shù)。線性函數(shù)。則稱則稱x x* *為方程（為方程（2.12.1）的根）的根, , 或稱或稱為函數(shù)為函數(shù)f(x)f(x)的零點的零點 常見的非線性方程有，代數(shù)方程（二次、常見的非線性方程有，代數(shù)方程（二次、三次等）、超越方程（三角方程，指數(shù)、對數(shù)三次等）、超越方程（三角方程，指數(shù)、對數(shù)方程等）。方程等）。2.1 2.1 引言引言 RTbVVap)(20)()(2RTbVVapVf本章將介紹求解

3、這種類型方程的近似解的數(shù)本章將介紹求解這種類型方程的近似解的數(shù)值方法值方法 在工程和科學技術(shù)領域中，經(jīng)常會遇到求解在工程和科學技術(shù)領域中，經(jīng)常會遇到求解 一元非線性方程的問題。一元非線性方程的問題。02736xxx0sin xex 前者是一個前者是一個6次代數(shù)方程，后者是一個超越方次代數(shù)方程，后者是一個超越方程。這些方程看似簡單，但理論上已證明，對于次程。這些方程看似簡單，但理論上已證明，對于次數(shù)大于等于數(shù)大于等于5的代數(shù)方程，一般不能用代數(shù)方法求的代數(shù)方程，一般不能用代數(shù)方法求其準確根。而在實際問題中，只要能獲得滿足一定其準確根。而在實際問題中，只要能獲得滿足一定精確度的近似根即可。所以研究

4、一元非線性方程近精確度的近似根即可。所以研究一元非線性方程近似根的數(shù)值解法，具有重要的現(xiàn)實意義。似根的數(shù)值解法，具有重要的現(xiàn)實意義。10 xxxyxy1lgxx1lg010 xxab( )yf x oxy 如果如果f(x)=0f(x)=0在區(qū)間在區(qū)間a,ba,b上僅有一個根，則稱上僅有一個根，則稱a,ba,b為方程的單根區(qū)間；為方程的單根區(qū)間； 如果如果f(x)=0f(x)=0在區(qū)間在區(qū)間a,ba,b有多個根，則稱有多個根，則稱a,ba,b為為方程的多根區(qū)間；方程的多根區(qū)間；求方程求方程2x2x5 55x5x2 21=01=0在實數(shù)范圍內(nèi)的根。在實數(shù)范圍內(nèi)的根。在實數(shù)范圍內(nèi)有三個實根在實數(shù)范圍

5、內(nèi)有三個實根3 3個有根區(qū)間縮小為個有根區(qū)間縮小為(0,1)、( (2,2,1)1)和和( (1,0)1,0)如果如果f(x)f(x)可以分解成可以分解成 , ,其中其中m m為正整為正整數(shù)且數(shù)且 , ,則稱則稱x x* *是是f(x)f(x)的的m m重零點重零點, ,或稱方程或稱方程f(x)=0f(x)=0的的m m重根。當重根。當m=1m=1時稱時稱x x* *為單根。為單根。)()()(*xgxxxfm0)(*xg0)(,0)()()(*)(*)1(*xfxfxfxfmm 方程的單根區(qū)間和多根區(qū)間統(tǒng)稱為方程的有根區(qū)方程的單根區(qū)間和多根區(qū)間統(tǒng)稱為方程的有根區(qū)間。為了研究方便，我們主要研究

6、方程在單根區(qū)間上間。為了研究方便，我們主要研究方程在單根區(qū)間上的求解方法。的求解方法。 若若f(x)f(x)存在存在m m階導數(shù)階導數(shù), ,則是方程則是方程f(x)f(x)的的m m重根重根( (m1)m1) 當且僅當當且僅當02*)2510()(50202)(22234xxxxfxxxxf顯然顯然x=-5x=-5為其二重根為其二重根且且g(-5)0g(-5)0記筆記記筆記 當當f(x)f(x)不是不是x x的線性函數(shù)時，稱對應的函數(shù)方程的線性函數(shù)時，稱對應的函數(shù)方程為非線性方程。如果為非線性方程。如果f(x)f(x)是多項式函數(shù)，則稱為代數(shù)是多項式函數(shù)，則稱為代數(shù)方程，否則稱為超越方程（三角

7、方程，指數(shù)、對數(shù)方方程，否則稱為超越方程（三角方程，指數(shù)、對數(shù)方程等）。一般稱程等）。一般稱n n次多項式構(gòu)成的方程次多項式構(gòu)成的方程 )0(00111nnnnnaaxaxaxa為為n n次代數(shù)方程次代數(shù)方程, ,當當n n1 1時時, ,方程顯然是非線性的方程顯然是非線性的 一般稍微復雜的一般稍微復雜的3 3次以上的代數(shù)方程或超越方程次以上的代數(shù)方程或超越方程, ,很難甚至無法求得精確解。本章重點介紹常用的求很難甚至無法求得精確解。本章重點介紹常用的求解非線性方程的近似根的幾種數(shù)值解法解非線性方程的近似根的幾種數(shù)值解法 記筆記記筆記2.1.1 2.1.1 確定有根區(qū)間的方法確定有根區(qū)間的方法

8、v 為了確定根的初值，首先必須圈定根所在的范圍，為了確定根的初值，首先必須圈定根所在的范圍， 稱為稱為圈定根或根的隔離圈定根或根的隔離。v 在上述基礎上，采取適當?shù)臄?shù)值方法確定具有一定在上述基礎上，采取適當?shù)臄?shù)值方法確定具有一定 精度要求的初值。精度要求的初值。v 對于代數(shù)方程，其根的個數(shù)（實或復的）與其次數(shù)對于代數(shù)方程，其根的個數(shù)（實或復的）與其次數(shù) 相同。至于超越方程，其根可能是一個、幾個或無相同。至于超越方程，其根可能是一個、幾個或無 解，并沒有什么固定的圈根方法解，并沒有什么固定的圈根方法v 求方程根的問題，就幾何上講求方程根的問題，就幾何上講, ,是求曲線是求曲線 y=f (x) y

9、=f (x)與與 x x軸交點的橫坐標。軸交點的橫坐標。 由高等數(shù)學知識知由高等數(shù)學知識知, , 設設f (x)f (x)為區(qū)間為區(qū)間 a,ba,b上的單上的單值連續(xù)值連續(xù), , 如果如果f (a)f (a)f (b)0 ,f (b)0 ,則則 a,ba,b中至少有一中至少有一點點使使f()=0, ,即方程的根即方程的根( (零點定理零點定理),),如果如果f(x)f(x)在在 a,ba,b上還是單調(diào)地遞增或上還是單調(diào)地遞增或遞減遞減，則僅有一個實根。，則僅有一個實根。記筆記記筆記n由此可大體確定根所在子區(qū)間，方法有：由此可大體確定根所在子區(qū)間，方法有：(1) (1) 畫圖法畫圖法(2) (2

10、) 逐步搜索法逐步搜索法y=f(x)abyx(1) (1) 畫圖法畫圖法 畫出畫出y=f(x)的略圖，從而看出曲線與的略圖，從而看出曲線與x x軸交點的軸交點的大致位置。大致位置。 例如例如 xlogx-1= 0 xlogx-1= 0可以改寫為可以改寫為logx=1/xlogx=1/x 畫出對數(shù)曲線畫出對數(shù)曲線y=logx,y=logx,與雙曲線與雙曲線y= 1/x,y= 1/x,它們交它們交 點的橫坐標位于區(qū)間點的橫坐標位于區(qū)間2,32,3內(nèi)內(nèi) 也可將也可將f (x) = 0分解為分解為 1 1(x)= (x)= 2 2(x)(x)的形式，的形式， 1 1(x)(x) 2 2 (x)(x)兩

11、曲線交點的橫坐標所在的子區(qū)間即為兩曲線交點的橫坐標所在的子區(qū)間即為含根區(qū)間含根區(qū)間。(1) (1) 畫圖法畫圖法xy1gxy023yxy0 xABa1b1a2b2(2) (2) 逐步搜索法逐步搜索法 對于給定的對于給定的f(x),設有根區(qū)間為設有根區(qū)間為 A,B,A,B,從從x x0 0=A=A出發(fā)出發(fā), ,以步長以步長h=(B-A)/n(nh=(B-A)/n(n是正整數(shù)是正整數(shù)),),在在 A,BA,B內(nèi)取定節(jié)內(nèi)取定節(jié)點點: :x xi i=x=x0 0ih (i=0,1,2,ih (i=0,1,2,n),n),從左至右檢查從左至右檢查f(xi)的的符號符號, ,如發(fā)現(xiàn)如發(fā)現(xiàn)x xi i與端

12、點與端點x x0 0的函數(shù)值異號的函數(shù)值異號, ,則得到一個縮則得到一個縮小的有根子區(qū)間小的有根子區(qū)間x xi-1i-1,x,xi i。求初始近似根的逐步搜索算法：求初始近似根的逐步搜索算法： （設（設a,ba,b內(nèi)有根）內(nèi)有根）(1) x(1) x0 0a; a; (2) (2) 若若f(xf(x0 0 )f(x )f(x0 0 +h)0 +h)0則結(jié)束；否則做下步。則結(jié)束；否則做下步。(3) x(3) x0 0 x x0 0 +h +h，轉(zhuǎn)，轉(zhuǎn)(2) (2) （其中（其中h h為預選的步長）為預選的步長）例例2.1 2.1 方程方程f(x)=xf(x)=x3 3-x-1=0 -x-1=0

13、確定其有根區(qū)間確定其有根區(qū)間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)必有一根解：用試湊的方法，不難發(fā)現(xiàn)解：用試湊的方法，不難發(fā)現(xiàn) f(0)0f(0)0 在區(qū)間（在區(qū)間（0 0，2 2）內(nèi)至少有一個實根）內(nèi)至少有一個實根 設從設從x=0 x=0出發(fā)出發(fā), ,取取h=0.5h=0.5為步長向右進行根的為步長向右進行根的 搜索搜索, ,列表如下列表如下v 用逐步搜索法進行實根隔離的關(guān)鍵是選取步長用逐步搜索法進行實根隔離的關(guān)鍵是選取步長h hv 要選擇適當要選擇適當h h ，使之既

14、能把根隔離開來，工作量，使之既能把根隔離開來，工作量 又不太大。又不太大。 v 為獲取指定精度要求的初值為獲取指定精度要求的初值, ,可在以上隔離根的可在以上隔離根的 基礎上采用對分法繼續(xù)縮小該含根子區(qū)間基礎上采用對分法繼續(xù)縮小該含根子區(qū)間 二分法可以看作是搜索法的一種改進。二分法可以看作是搜索法的一種改進。2.2 2.2 二分法二分法 二分法又稱二分區(qū)間法二分法又稱二分區(qū)間法, ,是求解方程是求解方程f(x)=0f(x)=0的近的近似根的一種常用的簡單方法。似根的一種常用的簡單方法。 設函數(shù)設函數(shù)f(x)f(x)在閉區(qū)間在閉區(qū)間 a,ba,b上連續(xù)上連續(xù), ,且且f(f(a a)f()f(b

15、 b)0,)0,根據(jù)連續(xù)函數(shù)的性質(zhì)可知根據(jù)連續(xù)函數(shù)的性質(zhì)可知, , f f( (x x)= 0)= 0在在( (a,b)a,b)內(nèi)必有實根內(nèi)必有實根, ,稱區(qū)間稱區(qū)間 a,ba,b為有根區(qū)間。為明確為有根區(qū)間。為明確起見起見, ,假定方程假定方程f(x)=0f(x)=0在區(qū)間在區(qū)間 a,ba,b內(nèi)有惟一實根內(nèi)有惟一實根x x* *。 )(xfy x21bax 1b2112xba 2a3a 1a32xba 2b3b11,a b22,ab33,a b以此類推以此類推 二分法的基本思想是二分法的基本思想是: : 首先確定有根區(qū)間首先確定有根區(qū)間, ,將將區(qū)間二等分區(qū)間二等分, , 通過判斷通過判斷f

16、(x)f(x)的符號的符號, , 逐步將有根逐步將有根區(qū)間縮小區(qū)間縮小, , 直至有根區(qū)間足夠地小直至有根區(qū)間足夠地小, , 便可求出滿便可求出滿足精度要求的近似根。足精度要求的近似根。有根區(qū)間只能是下面三種情況之一有根區(qū)間只能是下面三種情況之一: :f(a)f(a)f(x)0,f(x)0,此時我們有此時我們有x x* *a,xa,x；f(x)f(x)f(b)0,f(b)0,此時我們有此時我們有x x* *x,bx,b；f(x)=0,f(x)=0,此時此時x x即為問題的精確解即為問題的精確解. . 可見可見, ,二分法就是逐步收縮有根區(qū)間，最后得出二分法就是逐步收縮有根區(qū)間，最后得出所求的根

17、。具體過程歸納如下所求的根。具體過程歸納如下 取有根區(qū)間取有根區(qū)間 a,ba,b之中點之中點, , 將它分為兩半將它分為兩半, ,分點分點 , ,這樣就可縮小有根區(qū)間這樣就可縮小有根區(qū)間20bax 對壓縮了的有根區(qū)間對壓縮了的有根區(qū)間 施行同樣的手法施行同樣的手法, , 即取中點即取中點 , ,將區(qū)間將區(qū)間 再分為兩半再分為兩半, ,然然 后再確定有根區(qū)間后再確定有根區(qū)間 , ,其長度是其長度是 的的 二分之一二分之一 如此反復下去如此反復下去, ,若不出現(xiàn)若不出現(xiàn) , ,即可得出一即可得出一 系列有根區(qū)間序列：系列有根區(qū)間序列： 上述每個區(qū)間都是前一個區(qū)間的一半上述每個區(qū)間都是前一個區(qū)間的一

18、半, ,因此因此 的長度的長度11,ba2111bax11,ba22,ba11,ba0)(kxfkkbabababa,2211kkba ,)(21)(2111abababkkkkk 當當kk時趨于零時趨于零, ,這些區(qū)間最終收斂于一點這些區(qū)間最終收斂于一點x x* * 即為即為 所求的根所求的根 。11122kkkkkababab1*22kkkkababxx每次二分后每次二分后, ,取有根區(qū)間取有根區(qū)間 的中點的中點作為根的近似值，得到一個近似根的序列作為根的近似值，得到一個近似根的序列 該序列以根該序列以根x x* *為極限為極限 只要二分足夠多次只要二分足夠多次( (即即k k足夠大足夠大

19、),),便有便有這里這里為給定精度為給定精度, ,由于由于 , ,則則 kkba ,)(21kkkbax,210kxxxxkxx*kkbax,*當給定精度當給定精度0 0后后, ,要想要想 成立成立, ,只要只要取取k k滿足滿足 即可，亦即當即可，亦即當: : kxx*)(211abk12lglg)lg(abk時時, ,做到第做到第k+1k+1次二分次二分, ,計算得到的計算得到的 就是滿就是滿足精度要求的近似根足精度要求的近似根 。 在程序中通常用相鄰的在程序中通常用相鄰的 與與 的差的絕的差的絕對值或?qū)χ祷?與與 的差的絕對值是否小于的差的絕對值是否小于來來決定二分區(qū)間的次數(shù)。決定二分區(qū)

20、間的次數(shù)。 kxkx1kxkakb2.2.1 2.2.1 實現(xiàn)二分法的基本步驟實現(xiàn)二分法的基本步驟 二分法是求方程近似根的方法中行之有效的最二分法是求方程近似根的方法中行之有效的最簡單的方法，它的遞推過程簡單，便于計算機上實簡單的方法，它的遞推過程簡單，便于計算機上實現(xiàn)，實現(xiàn)二分法的基本步驟如下?，F(xiàn)，實現(xiàn)二分法的基本步驟如下。(1) (1) 輸入有根區(qū)間的端點輸入有根區(qū)間的端點 及預先給定的精及預先給定的精 度度 ；(2) (2) 計算計算 ；(3) (3) 若若 ，則，則 ；否則；否則 ；(4) (4) 若若 ，則輸出方程滿足精度要求的根，則輸出方程滿足精度要求的根 ， 計算結(jié)束；否則轉(zhuǎn)計算

21、結(jié)束；否則轉(zhuǎn)(2)(2)。ba,2/ )(bax0)()(xfafxb xa abx y n 開 始 輸 入 a , b, (a+b)/2 x f(a) f(x )0 ? xb x a |b-a|0 輸 出 x 結(jié) 束 y n 二分法算法實現(xiàn)二分法算法實現(xiàn)例2.2 求 在 的根解：因為 所以根存在32( )410f xxx1,2(1)5f (2)14fn有根區(qū)間11.0,2.01.52.37521.0,1.51.25-1.7968731.25,1.51.3750.1621141.25,1.3751.3125-0.8483951.3125,1.3751.34375-0.3509861.34375

22、,1.3751.359375 0.0964171.359375,1.3751.3671875 -0.0323681.359375,1.36718751.363281250.03215nx()nf x例例2.3 2.3 用二分法求方程用二分法求方程在在(1(1，2)2)內(nèi)的根，取內(nèi)的根，取02010)(3xxxf410#include #include #include #include #define f(x) (x#define f(x) (x* *x+10)x+10)* *x-20)x-20)#define eps 0.0001 /#define eps 0.0001 /* * 容許誤差容

23、許誤差 * */ /main()main() float a,b,y,x; float a,b,y,x; int k=0; int k=0; printf(a,b=); printf(a,b=); scanf(%f,%f ,&a,&b); scanf(%f,%f ,&a,&b); if(f(a) if(f(a)* *f(b)=0) /f(b)=0) /* * 判斷區(qū)間內(nèi)是否有實根判斷區(qū)間內(nèi)是否有實根 * */ / printf(Not root); return; printf(Not root); return; do do x=(a+b)/2; x=(a+b

24、)/2; k+; k+; if(f(a) if(f(a)* *f(x)0) /f(x)0) /* * 如果如果f(a)f(a)* *f(x)0,f(x)eps);/ while(fabs(b-a)eps);/* *判斷精度要求判斷精度要求* */ / x=(a+b)/2; / x=(a+b)/2; /* * 取小區(qū)間中點作為根的近似值取小區(qū)間中點作為根的近似值 * */ / printf(n The root is x=%f, k=%dn,x,k); printf(n The root is x=%f, k=%dn,x,k);程序運行結(jié)果：程序運行結(jié)果： a,b=1,2 The root is

25、 x=1.594574, k=14例例2.32.3 求方程求方程f(x)=xf(x)=x3 3-x-1=0 -x-1=0 在區(qū)間在區(qū)間1.01.0,1.5,1.5內(nèi)的一內(nèi)的一 個實根個實根, , 使誤差不超過使誤差不超過0.50.51010-2-2。P P1919例例2.42.4 證明方程證明方程 在區(qū)間在區(qū)間2, 32, 3內(nèi)有一個根內(nèi)有一個根 , , 使用二分法求誤差不超過使用二分法求誤差不超過0.50.51010-3 -3 的根要二的根要二 分多少次？分多少次？0523 xx且且f(x)f(x)在在2, 32, 3上連續(xù)上連續(xù), ,故方程故方程f(x)=0f(x)=0在在2,32,3內(nèi)至

26、少內(nèi)至少有一個根。又有一個根。又 當時當時時，時， , ,故故f(x)f(x)在在2, 32, 3上是單調(diào)遞增函數(shù)上是單調(diào)遞增函數(shù), ,從而從而f(x)f(x)在在2, 32, 3上有且僅有一根。上有且僅有一根。23)(2xxf3 , 2x0)( xf 給定誤差限給定誤差限 0.5 0.51010-3 -3 , ,使用二分法時使用二分法時52)(3xxxf016)3(, 01)2(ff證明證明: :令令 誤差限為誤差限為 只要取只要取k k滿足滿足 )(211*abxxkk311021)(21 abk即可，亦即即可，亦即 3102 k97.92110lg3gk所以需二分所以需二分1010次便可

27、達到要求。次便可達到要求。簡單簡單; 對對f (x) 要求不高要求不高(只要連續(xù)即可只要連續(xù)即可) .無法求復根及偶重根無法求復根及偶重根收斂慢收斂慢 用二分法求根，最好先給出 f (x) 草圖以確定根的大概位置?；蛴盟阉鞒绦颍瑢, b分為若干小區(qū)間，對每一個滿足 f (ak)f (bk) 0 的區(qū)間調(diào)用二分法程序，可找出區(qū)間a, b內(nèi)的多個根，且不必要求 f (a)f (b) 0 。優(yōu)點優(yōu)點缺點缺點2.3 2.3 迭代法迭代法 迭代法的基本思想是逐次逼近，即首先給出方迭代法的基本思想是逐次逼近，即首先給出方程的根的一個近似初始值，然后反復使用迭代公式程的根的一個近似初始值，然后反復使用迭代

28、公式校正這個初始值，使之逐步精確化，直到滿足預先校正這個初始值，使之逐步精確化，直到滿足預先給出的精度要求為止。給出的精度要求為止。2.3.1 2.3.1 迭代法原理迭代法原理 等價變換等價變換 f f(x) = 0 (2.3) (x) = 0 (2.3) f f(x)(x)的根的根 的根的根)(xx)(xx如果迭代序列收斂于如果迭代序列收斂于 , ,則當則當 連續(xù)時連續(xù)時, ,便是方便是方程程 的根。的根。0 x)(01xx1x)(12xx ,210nxxxx*x對預先給定的精度要求對預先給定的精度要求 ，只要某個，只要某個k 滿足滿足 即可結(jié)束計算并取即可結(jié)束計算并取 01kkxxkxx*

29、), 2 , 1 , 0()(1 kxxkk)(x0)(xf然后按式然后按式(2.3)(2.3)構(gòu)造迭代公式構(gòu)造迭代公式(2.4)在有根區(qū)間在有根區(qū)間a,ba,b上取一點上取一點 作為方程作為方程 根的初始近似根，代入式根的初始近似根，代入式(2.4)(2.4)右端，求得右端，求得 再把再把 作為預測值，進一步得到作為預測值，進一步得到 ，如，如此反復進行下去，得到一個近似根的序列此反復進行下去，得到一個近似根的序列0)(xf(2.4) (2.4) 稱為求解非線稱為求解非線性方程的簡單迭代法性方程的簡單迭代法例例2.5 2.5 用迭代法求方程用迭代法求方程 在在x=1.5x=1.5附近的一個根

30、附近的一個根解解 將方程改寫成如下兩種等價形式將方程改寫成如下兩種等價形式 013 xx1)(1)(3231xxxxxx相應地可得到兩個迭代公式相應地可得到兩個迭代公式1)(1)(321311kkkkkkxxxxxx如果取初始值如果取初始值 1.51.5，用上述兩個迭代公，用上述兩個迭代公式分別迭代，計算結(jié)果見式分別迭代，計算結(jié)果見P P2121 0 x例例2.6 已知方程已知方程 在在 上有一個根上有一個根324100 xx1 2 , 可以選取幾種迭代格式呢？可以選取幾種迭代格式呢？1)1)32410 xxxx 即即104)(23xxxx2)2)23410 xx 1321102xx 即即21

31、3)10(21)(xx3)3)即即2104xxx 12104xxx 21410)(xxx4)4)即即12104xx 21410)(xx如果由迭代格式如果由迭代格式 產(chǎn)生的序列產(chǎn)生的序列 收斂收斂, ,即即 nx)(1kkxx*limxxnn則稱迭代法收斂。則稱迭代法收斂。 可見，將求非線性方程可見，將求非線性方程f(x)=0f(x)=0的根的根, ,先化為等價形式先化為等價形式)(xx然后構(gòu)造迭代公式然后構(gòu)造迭代公式 )2 , 1 , 0()(1kxxkk如何判定這種方法如何判定這種方法是收斂的呢？是收斂的呢？等價形式的構(gòu)等價形式的構(gòu)造多種多樣造多種多樣2.3.3 2.3.3 迭代法收斂的條件

32、迭代法收斂的條件 對方程對方程f(x)=0f(x)=0可以構(gòu)造不同的迭代公式可以構(gòu)造不同的迭代公式, , 但但迭代公式迭代公式并非總是收斂。那么并非總是收斂。那么, ,當?shù)瘮?shù)當?shù)瘮?shù) 滿足什么滿足什么條件時，相應的迭代公式才收斂呢？即使迭代收條件時，相應的迭代公式才收斂呢？即使迭代收斂時，我們也不可能迭代很多次，而是迭代有限斂時，我們也不可能迭代很多次，而是迭代有限次后就停止，這就需要估計迭代值的誤差，以便次后就停止，這就需要估計迭代值的誤差，以便適時終止迭代適時終止迭代 ),2, 1 ,0()(1kxxkk)(x定理定理2.12.1 設函數(shù)設函數(shù) 在在a,b上具有連續(xù)的一階導上具有連續(xù)

33、的一階導 數(shù)數(shù), 且滿足且滿足 （1）對所有的對所有的xa,b 有有 a,b （2）存在存在 0 L 1 ,使所有的使所有的xa,b有有 L則方程則方程 在在a,b上的解上的解 存在且唯一存在且唯一，對任意的對任意的 a ,b ，迭代過程迭代過程均收斂于均收斂于 。并有誤差估計式并有誤差估計式 )(x)(x)(x)(xx*x0 x)(1kkxx*x1*1kkkxxLLxx01*1xxLLxxkk 10)(xx 開 始 輸 入 x0,N 1 kk+ 1 k x1 x0 輸 出 近 似 根 x1 |x1- x0|? 輸 出 迭 代 失 敗 標 志 結(jié) 束 n k0c0），），使使)(1kkxx)(

34、xx*xkkxxe*ceepkkk1lim則稱序列則稱序列 是是 p p 階收斂的階收斂的, ,c c稱漸近誤差常數(shù)。特別稱漸近誤差常數(shù)。特別地地, ,p p=1=1時稱為線性收斂時稱為線性收斂, ,p p=2=2時稱為平方收斂。時稱為平方收斂。1 1 p p 2 2時稱為超線性收斂。時稱為超線性收斂。 kx 數(shù)數(shù)p p的大小反映了迭代法收斂的速度的快的大小反映了迭代法收斂的速度的快慢，慢，p p愈大，則收斂的速度愈快，故迭代法的愈大，則收斂的速度愈快，故迭代法的收斂階是對迭代法收斂速度的一種度量。收斂階是對迭代法收斂速度的一種度量。ceepkkk1lim定理定理2.32.3 設迭代過程設迭代

35、過程 , 若若 在所求根在所求根 的鄰域連續(xù)且的鄰域連續(xù)且 則迭代過程在則迭代過程在 鄰域是鄰域是p p階收斂的階收斂的。)(1kkxx)()(xp*x0)(, 0)()()(*)(*) 1(* xxxxpp*x例例2.2.1010 已知迭代公式已知迭代公式 收斂于收斂于 證明該迭代公式平方收斂。證明該迭代公式平方收斂。21132kkkxxx3*3x根據(jù)定理根據(jù)定理2.32.3可知，迭代公式平方收斂?？芍狡椒绞諗?。032336)(0)(33* xx，為了使迭代過程收斂或提高收斂的速度為了使迭代過程收斂或提高收斂的速度, , 可設法可設法 提高初值的精度以減少迭代的次數(shù)提高初值的精度以

36、減少迭代的次數(shù) 提高收斂的階數(shù)提高收斂的階數(shù) p p將將 代入代入，3*3x2132)(xxx436)(232)(xxxx ，證證: : 迭代公式相應的迭代函數(shù)為迭代公式相應的迭代函數(shù)為2.4 2.4 牛頓迭代法牛頓迭代法 用迭代法可逐步精確方程用迭代法可逐步精確方程 根的近似值根的近似值，但必須要找到，但必須要找到 的等價方程的等價方程 , ,如果如果 選得不合適選得不合適, ,不僅影響收斂速度不僅影響收斂速度, ,而且有可能造成迭代而且有可能造成迭代格式發(fā)散。我們希望找到一種迭代方法格式發(fā)散。我們希望找到一種迭代方法, ,既結(jié)構(gòu)簡單既結(jié)構(gòu)簡單, ,收斂速度快收斂速度快, ,又不存在發(fā)散的問

37、題。這就是牛頓迭代又不存在發(fā)散的問題。這就是牛頓迭代法法0)(xf0)(xf)(xx)(x2.4.1 2.4.1 牛頓迭代法的基本思想牛頓迭代法的基本思想(1)(1)原理：將非線性方程原理：將非線性方程 f f(x) = 0(x) = 0 逐步線性化而形成迭代公式逐步線性化而形成迭代公式. . 對于方程對于方程 ,設其近似根為設其近似根為 , 函數(shù)函數(shù)f(x)f(x)可在可在 附近作泰勒展開附近作泰勒展開 0)(xfkx 2)(21)()()(kkkkkxxxfxxxfxfxf 設設 的根的根 , ,則有則有 , ,即即 0)(xf0)(*xf0)()(*kkkxxxfxf)()(*kkkxf

38、xfxxkx忽略高次項忽略高次項, ,用其線性部分作為函數(shù)用其線性部分作為函數(shù)f(x)f(x)的近似，的近似， )()()(kkkxxxfxfxf*x將右端取為將右端取為 , ,即即 是比是比 更接近于更接近于 的近似值的近似值 1kx1kxkx*x)()(1kkkkxfxfxx)2,1 ,0(k這就是著名的牛頓迭代公式這就是著名的牛頓迭代公式2.4.2 2.4.2 牛頓迭代法的幾何解釋牛頓迭代法的幾何解釋 方程方程f f( (x x)=0)=0的根的根x x* *是曲線是曲線y y= =f f( (x x) )與與x x軸交點的橫坐軸交點的橫坐標標, ,設設x xk k是根是根x x* *的

39、某個近似值的某個近似值, ,過曲線過曲線y y= =f f( (x x) )的橫坐標為的橫坐標為x xk k的點的點Pk=(xk,f(xk)引切線交引切線交x x軸于軸于x xk+1 k+1 , ,并將其作為并將其作為x x* *牛頓迭代法如下牛頓迭代法如下圖所示圖所示x*xyxkPky=f(x)xk+1xk+2Pk+1Pk+2新的近似值新的近似值, ,重復上述過程重復上述過程, ,可見一次次用切線方程可見一次次用切線方程來求解方程來求解方程f(x)=0f(x)=0的根的根, ,所以亦稱為牛頓切線法。所以亦稱為牛頓切線法。2.4.3 2.4.3 實現(xiàn)牛頓迭代法的基本步驟實現(xiàn)牛頓迭代法的基本步驟

40、 實現(xiàn)牛頓迭代法的基本步驟如下：實現(xiàn)牛頓迭代法的基本步驟如下： (1) (1) 給出初始近似根給出初始近似根 及精度及精度 ； (2) (2) 計算計算 ； (3) (3) 若若 ，轉(zhuǎn)向，轉(zhuǎn)向(4)(4)；否則；否則 ，轉(zhuǎn)向，轉(zhuǎn)向(2)(2)； (4) (4) 輸出滿足精度的根輸出滿足精度的根 ，結(jié)束。，結(jié)束。 0 x)()(0001xfxfxx01xx10 xx 1x例例2.11 2.11 用牛頓迭代法求方程用牛頓迭代法求方程 在在1.01.0附近的實根，設初值附近的實根，設初值 ，精度要求，精度要求 為為 。 當當 時，時， 有有 。0654323xxx00001. 06543)(23xx

41、xxf589)( 2xxxf0 . 10 x#include #include #define eps 0.00001 /* 容許誤差容許誤差 */float f(float x) /* 定義函數(shù)定義函數(shù)f(x) */ return(-3*x+4)*x-5)*x+6; float f1(float x) /* 定義函數(shù)定義函數(shù)f(x)的導數(shù)的導數(shù) */ return (-9*x+8)*x-5; main() float x0,x1; int k=0; printf(x1=); scanf(%f,&x1); do x0=x1; /* 準備下一次迭代的初值準備下一次迭代的初值 */ x1=

42、x0-f(x0)/f1(x0); /* 牛頓迭代牛頓迭代 */ k+; /* 統(tǒng)計迭代次數(shù)統(tǒng)計迭代次數(shù) */ while(fabs(x1-x0)eps); /*滿足精度滿足精度,輸出近似根輸出近似根*/ printf(x=%f,k=%dn,x1,k);程序運行結(jié)果：程序運行結(jié)果：x=1.265328K=4x1=1 定理定理2.4 2.4 設設 是方程是方程 的單根的單根, , 且且f f( (x x) )在在 的某鄰域內(nèi)有連續(xù)的二階導數(shù)的某鄰域內(nèi)有連續(xù)的二階導數(shù), , 則牛則牛頓法在頓法在 附近局部收斂附近局部收斂, , 且至少二階收斂且至少二階收斂, , 有有 *x0)(xf*x2.4.2.

43、4.4 4 牛頓迭代法的收斂性牛頓迭代法的收斂性*x)(2)(limlim*2*1*1xfxfxxxxeekkkkkk 牛頓迭代法對初值牛頓迭代法對初值x x0 0的選取要求比較高。的選取要求比較高。 X X0 0 必必須充分靠近須充分靠近x x* *才能保證局部收斂。才能保證局部收斂。定理定理2.5 2.5 如果在有根區(qū)間如果在有根區(qū)間a,ba,b上上連續(xù)且不變號，在連續(xù)且不變號，在a,ba,b上取初始近似根上取初始近似根x x0 0滿足，滿足，則牛頓迭代法產(chǎn)生的迭代序列單調(diào)收斂于方程則牛頓迭代法產(chǎn)生的迭代序列單調(diào)收斂于方程f(x)=0f(x)=0在該區(qū)間上的唯一解。在該區(qū)間上的唯一解。證明

44、證明 （ 略略 ）)(, 0)(, 0)()(xfxfbfaf 0)()(00 xfxfyx10 x0X*0 x0X*x2 不滿足迭代條件時，可能導致迭代值遠離根的不滿足迭代條件時，可能導致迭代值遠離根的情況而找不到根或死循環(huán)的情況情況而找不到根或死循環(huán)的情況2.4.2.4.4 4 牛頓迭代法的收斂性牛頓迭代法的收斂性例例2.12.12 2 用用求求 x x= =e e-x-x的根的根, ,=10=10-4-4解：因解：因 f f ( (x xk k)= )= x x e ex x 1 , 1 , f f ( (x xk k)=e)=ex x ( ( x x+1)+1)建立迭代公式建立迭代公式

45、nxnnnxxnnnxexxxeexxxnnn 1)1 (11取取x x0 0=0.5,=0.5,逐次計算得逐次計算得 x x1 1=0.57102, =0.57102, x x2 2=0.56716=0.56716， x x3 3=0.56714=0.567142.5 2.5 弦截法弦截法 研究目的：在牛頓法基礎上，構(gòu)造既有較研究目的：在牛頓法基礎上，構(gòu)造既有較高的收斂速度，又不需計算導數(shù)的迭代公式。高的收斂速度，又不需計算導數(shù)的迭代公式。思想：用差商思想：用差商11)()(kkkkxxxfxf)(kxf 代替導數(shù)代替導數(shù)弦截迭代公式弦截迭代公式 , 2 , 1),()()()(111 kx

46、xxfxfxfxxkkkkkkkx0 x1需要需要2 2個初值個初值 x x0 0 和和 x x1 1。x22.5.2.5.1 1 弦截法幾何意義弦截法幾何意義弦截法也稱割線法弦截法也稱割線法, ,其幾何意義是用過曲線上兩其幾何意義是用過曲線上兩點點 、 的割線來代替曲線的割線來代替曲線, ,用割線用割線與與x x軸交點的橫座標作為方程的近似根軸交點的橫座標作為方程的近似根)(,(000 xfxP)(,(111xfxP2.5.2 2.5.2 實現(xiàn)弦截法的基本步驟實現(xiàn)弦截法的基本步驟實現(xiàn)弦截法的基本步驟如下實現(xiàn)弦截法的基本步驟如下: :(1) (1) 選擇迭代初值選擇迭代初值 及精度及精度 ；(

47、2) (2) 計算計算 ；(3) (3) 若若 ，轉(zhuǎn)向，轉(zhuǎn)向(4)(4)；否則；否則 ， ， 轉(zhuǎn)向轉(zhuǎn)向(2)(2)；(4) (4) 輸出滿足精度的根輸出滿足精度的根 ，結(jié)束。，結(jié)束。10,xx)()()()(0101112xxxfxfxfxx12xx10 xx 21xx 2x例例2.13 2.13 用弦截法求方程用弦截法求方程在區(qū)間在區(qū)間 內(nèi)的實根，取內(nèi)的實根，取 。0123 xx5 . 1 ,4 . 1510#include #include #include #include #define eps 0.00001 /#define eps 0.00001 /* * 容許誤差容許誤差 *

48、*/ /#define N 100 /#define N 100 /* * 最大迭代次數(shù)最大迭代次數(shù)N N * */ /float f(float x) /float f(float x) /* * 定義函數(shù)定義函數(shù)f(x) f(x) * */ / float y; float y; y=(x-1) y=(x-1)* *x x* *x-1;x-1; return(y); return(y); main()main() float x0,x1,x2; float x0,x1,x2; int i; int i; printf(input x0,x1=); printf(input x0,x1=);

49、 scanf(%f,%f,&x0,&x1); scanf(%f,%f,&x0,&x1); for(i=1;i=N;i+) for(i=1;i=N;i+) x2=x1-(f(x1) x2=x1-(f(x1)* *(x1-x0)/(f(x1)-f(x0); (x1-x0)/(f(x1)-f(x0); / /* * 弦截法迭代公式弦截法迭代公式 * */ / if(fabs(x2-x1)eps | fabs(f(x2)eps) if(fabs(x2-x1)eps | fabs(f(x2)eps) / /* *滿足精度要求輸出近似根并退出滿足精度要求輸出近似根并退出*

50、*/ / printf(nRoot of equation is:%8.6fn,x2); printf(nRoot of equation is:%8.6fn,x2); return; return; x0=x1; / x0=x1; /* * 準備下一次迭代的初值準備下一次迭代的初值 * */ / x1=x2; x1=x2; printf(nAfter %d repeat, no solved.n,N); printf(nAfter %d repeat, no solved.n,N); / /* * 輸出無解信息輸出無解信息 * */ / 程序運行結(jié)果：程序運行結(jié)果：input x1,x2=1

51、.4,1.5input x1,x2=1.4,1.5Root of equation is: Root of equation is: 1.4655711.465571 弦截法與牛頓迭代法都是線性化方法，但兩弦截法與牛頓迭代法都是線性化方法，但兩者有本質(zhì)的區(qū)別：者有本質(zhì)的區(qū)別： 牛頓迭代法與一般迭代法在計算牛頓迭代法與一般迭代法在計算 時只用到前一步時只用到前一步的值的值 ，故稱之為單點迭代法；而弦截法在求，故稱之為單點迭代法；而弦截法在求 時要時要用到前兩步的結(jié)果用到前兩步的結(jié)果 和和 ，使用這種方法必須給出兩，使用這種方法必須給出兩個初始近似根個初始近似根 ，這種方法稱為多點迭代法。，這種方

52、法稱為多點迭代法。 另外，弦截法比牛頓迭代法收斂速度較慢，但它的計另外，弦截法比牛頓迭代法收斂速度較慢，但它的計算量比牛頓迭代法小。算量比牛頓迭代法小。 kx1kx1kxkx10,xx1kx 可以證明，弦截法具有超線性收斂，收斂的階約可以證明，弦截法具有超線性收斂，收斂的階約為為1.6181.618，它與前面介紹的一般迭代法一樣都是線性化，它與前面介紹的一般迭代法一樣都是線性化方法，但也有區(qū)別。即一般迭代法在計算方法，但也有區(qū)別。即一般迭代法在計算 時只用到時只用到前一步的值前一步的值 ，故稱之為單點迭代法；而弦截法在求，故稱之為單點迭代法；而弦截法在求 時要用到前兩步的結(jié)果時要用到前兩步的結(jié)

53、果 和和 ，使用這種方，使用這種方法必須給出兩個初始近似根法必須給出兩個初始近似根 ，這種方法稱為多，這種方法稱為多點迭代法。點迭代法。 1kx1kx1kxkx10,xxkx例例2.12 2.12 用弦截法求方程用弦截法求方程 在初始值在初始值 鄰近的一個根。要求鄰近的一個根。要求xex5 . 00 x0001. 01kkxx解：取解：取 , , , , 令令5 . 00 x6.01xxexxf)()()()()(1111kkxxkkxkkkxxeexxexxxkkk 計算結(jié)果如下：計算結(jié)果如下： 易見取近似根易見取近似根 則可滿足精度要求。則可滿足精度要求。56714. 04x利用弦截迭代公

54、式利用弦截迭代公式補充補充 非線性方程組的數(shù)值解法非線性方程組的數(shù)值解法 二階非線性方程組：二階非線性方程組：0),(0),(21yxyxff方法：通過消元化為含有一個未知量的方程求方法：通過消元化為含有一個未知量的方程求 根問題，然后用牛頓法求解根問題，然后用牛頓法求解0) 13() 1(),(05),(2221xyxyxyxfyxf例：求解下列非方程組例：求解下列非方程組NewtonNewton法解方程組例法解方程組例由由 得得y=(3x+1)/(x+1) y=(3x+1)/(x+1) 將代入得將代入得f(x)=xf(x)=x2 2+(3x+1)+(3x+1)2 2/ (x+1)/ (x+

55、1)2 2-5=0 -5=0 化簡得化簡得f(x)=4xf(x)=4x4 4+ 2x+ 2x3 3 +5x+5x2 2-4x-4=0 -4x-4=0 然后用牛頓迭代法求出然后用牛頓迭代法求出x x的近似值作為的近似值作為x x* *, , 并將并將x x* *代代入或后，再用牛頓迭代法求出入或后，再用牛頓迭代法求出y y的近似值作為的近似值作為y y* * 即可。即可。0) 13() 1(),(05),(2221xyxyxyxfyxf例例2.12 2.12 求求 052),(032),(22yxyxvyxyx 在在( (x x0 0,y,y0 0)=(-1,2)=(-1,2)附近解附近解方法：

56、通過消元化為含有一個未知量的方程求方法：通過消元化為含有一個未知量的方程求根問題，然后用牛頓法求解根問題，然后用牛頓法求解解：由得解：由得x=3-2yx=3-2y并代入整理得：并代入整理得： 2 2（3-23-2y)y)2 2 +y+y2 2 5=05=0 9y 9y2 2 -24y+13=0y+13=0 f(y)= 9y f(y)= 9y2 2 24y+13 f24y+13 f (y)=18y(y)=18y 24 , 1 , 0,24181324921kyyyyykkkkky 0.74x 1.52例例2.12.13 3 求求 0sin2),(0cos2),(xyyxvyxyxkkkkkkyyyyyyyyyfyyyfyyyxvyxsin)cos21cos(212)cos21sin(2sin21)cos21cos(2)(0)cos21sin(2)(0)cos21sin(2),(2,cos2111）代入（）得由（ 非線性方程的解通常叫做方程的根非線性方程的解