計(jì)算方法第七章

1、第第第第第第7 7 7 7 7 7章章章章章章 非線性方程與方程組的非線性方程與方程組的非線性方程與方程組的非線性方程與方程組的非線性方程與方程組的非線性方程與方程組的數(shù)值解法數(shù)值解法數(shù)值解法數(shù)值解法數(shù)值解法數(shù)值解法7.17.1方程求根與二分法方程求根與二分法7.27.2不動(dòng)點(diǎn)迭代法及其收斂性不動(dòng)點(diǎn)迭代法及其收斂性 7.37.3迭代收斂的加速方法迭代收斂的加速方法* *7.47.4牛頓法牛頓法7.57.5弦截法與拋物線法弦截法與拋物線法7.67.6求根問(wèn)題的敏感性與多項(xiàng)式的零點(diǎn)求根問(wèn)題的敏感性與多項(xiàng)式的零點(diǎn)* *7.77.7非線性方程組的數(shù)值解法非線性方程組的數(shù)值解法* *2 在科學(xué)研究和工程

2、設(shè)計(jì)中在科學(xué)研究和工程設(shè)計(jì)中, 經(jīng)常會(huì)遇到的一大類經(jīng)常會(huì)遇到的一大類問(wèn)題是非線性方程問(wèn)題是非線性方程f(x)=0 (7.1)的求根問(wèn)題，其中的求根問(wèn)題，其中f(x)為為非線性函數(shù)非線性函數(shù)。 方程方程f(x)=0的根的根, 亦稱為函數(shù)亦稱為函數(shù)f(x)的的零點(diǎn)零點(diǎn)。 如果如果f(x)可以分解成可以分解成 , ,其中其中m為為正整數(shù)且正整數(shù)且 , ,則稱則稱x* *是是f(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)

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

4、數(shù)方程, ,當(dāng)當(dāng)n n1 1時(shí)時(shí), ,方程顯然是非線性的方程顯然是非線性的 一般稍微復(fù)雜的一般稍微復(fù)雜的3 3次以上的代數(shù)方程或超越方程次以上的代數(shù)方程或超越方程, ,很難甚至無(wú)法求得精確解。本章將介紹常用的求解很難甚至無(wú)法求得精確解。本章將介紹常用的求解非線性方程的近似根的幾種數(shù)值解法非線性方程的近似根的幾種數(shù)值解法 4求根步驟求根步驟5二分法二分法 二分法又稱二分區(qū)間法二分法又稱二分區(qū)間法, ,是求解方程是求解方程(7.1)(7.1)的近的近似根的一種常用的簡(jiǎn)單方法。似根的一種常用的簡(jiǎn)單方法。 設(shè)函數(shù)設(shè)函數(shù)f( (x) )在閉區(qū)間在閉區(qū)間 a,b 上連續(xù)上連續(xù), ,且且f( (a) )f(

5、 (b)0,)0,根據(jù)連續(xù)函數(shù)的性質(zhì)可知根據(jù)連續(xù)函數(shù)的性質(zhì)可知, , f( (x)= 0)= 0在在( (a,b) )內(nèi)必有實(shí)內(nèi)必有實(shí)根根, ,稱區(qū)間稱區(qū)間 a,b 為有根區(qū)間。為明確起見(jiàn)為有根區(qū)間。為明確起見(jiàn), ,假定方程假定方程f( (x)=0)=0在區(qū)間在區(qū)間 a,b 內(nèi)有惟一實(shí)根內(nèi)有惟一實(shí)根x* *。 二分法的基本思想二分法的基本思想是是: : 首先確定有根區(qū)間首先確定有根區(qū)間, ,將區(qū)將區(qū)間二等分間二等分, , 通過(guò)判斷通過(guò)判斷f( (x) )的符號(hào)的符號(hào), , 逐步將有根區(qū)間縮逐步將有根區(qū)間縮小小, , 直至有根區(qū)間足夠地小直至有根區(qū)間足夠地小, , 便可求出滿足精度要便可求出滿足

6、精度要求的近似根。求的近似根。6有根區(qū)間的確定有根區(qū)間的確定 為了確定根的初值，首先必須圈定根所在的范圍，為了確定根的初值，首先必須圈定根所在的范圍， 稱為稱為圈定根或根的隔離圈定根或根的隔離。 在上述基礎(chǔ)上，采取適當(dāng)?shù)臄?shù)值方法確定具有一定在上述基礎(chǔ)上，采取適當(dāng)?shù)臄?shù)值方法確定具有一定 精度要求的初值。精度要求的初值。 對(duì)于代數(shù)方程，其對(duì)于代數(shù)方程，其根的個(gè)數(shù)根的個(gè)數(shù)（實(shí)或復(fù)的）與其次數(shù)（實(shí)或復(fù)的）與其次數(shù) 相同。至于超越方程，其根可能是一個(gè)、幾個(gè)或無(wú)相同。至于超越方程，其根可能是一個(gè)、幾個(gè)或無(wú) 解，并沒(méi)有什么固定的圈根方法解，并沒(méi)有什么固定的圈根方法 求方程根的問(wèn)題，就求方程根的問(wèn)題，就幾何上

7、幾何上講講,是求曲線是求曲線 y=f (x)與與 x軸交點(diǎn)的橫坐標(biāo)。軸交點(diǎn)的橫坐標(biāo)。7有根區(qū)間的確定有根區(qū)間的確定 由高等數(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)地遞增或遞減，則僅有上還是單調(diào)地遞增或遞減，則僅有一個(gè)實(shí)根。一個(gè)實(shí)根。y=f(x)abyxn大體確定根所在子區(qū)間的方法有：大體確定根所在子區(qū)間的方法有： (1) 畫圖法畫圖法 (2) 逐步搜索法逐步搜索法8畫圖法畫圖法 畫出畫出y = f (x)的略圖，從而看出曲線與

8、的略圖，從而看出曲線與x軸交點(diǎn)的軸交點(diǎn)的 大致位置。大致位置。 也可將也可將f (x) = 0分解為分解為 1(x)= 2(x)的形式，的形式， 1(x) 與與 2(x)兩曲線交點(diǎn)的橫坐標(biāo)所在的子區(qū)間即為含根兩曲線交點(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)9畫圖法畫圖法xy1gxy 023yx10y0 xABa1b1a2b2 對(duì)于給定的對(duì)于給定的f (x),設(shè)有根區(qū)間為設(shè)有根區(qū)間為A

9、, ,B,從從x0=A出出發(fā)發(fā), ,以步長(zhǎng)以步長(zhǎng)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è)則得到一個(gè)縮小的有根子區(qū)間縮小的有根子區(qū)間xi-1, ,xi。搜索法搜索法11例題例題例例7.1 7.1 方程方程f(x)=x3-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)至

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

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

12、a2 b2 a2 b2 14二分法求根過(guò)程二分法求根過(guò)程 對(duì)壓縮了的有根區(qū)間對(duì)壓縮了的有根區(qū)間 施行同樣的手法施行同樣的手法, , 即取中點(diǎn)即取中點(diǎn) , ,將區(qū)間將區(qū)間 再分為兩半再分為兩半, ,然然 后再確定有根區(qū)間后再確定有根區(qū)間 , ,其長(zhǎng)度是其長(zhǎng)度是 的的 二分之一二分之一 如此反復(fù)下去如此反復(fù)下去, ,若不出現(xiàn)若不出現(xiàn) , ,即可得出一即可得出一 系列有根區(qū)間序列：系列有根區(qū)間序列： 11,ba2111bax11,ba22,ba11,ba0)(kxfkkbabababa,2211 上述每個(gè)區(qū)間都是前一個(gè)區(qū)間的一半上述每個(gè)區(qū)間都是前一個(gè)區(qū)間的一半, ,因此因此 的長(zhǎng)度的長(zhǎng)度kkba ,

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

14、分法求根過(guò)程二分法求根過(guò)程11122kkkkkababab當(dāng)給定精度當(dāng)給定精度0 0后后, ,要想要想 成立成立, ,只要只要取取k滿足滿足 即可，亦即當(dāng)即可，亦即當(dāng): kxx*)(211abk)2.7(12lglg)lg(abk時(shí)時(shí), ,做到第做到第k+1次二分次二分, ,計(jì)算得到的計(jì)算得到的 就是滿就是滿足精度要求的近似根足精度要求的近似根 。kx17二分法求根過(guò)程二分法求根過(guò)程時(shí)時(shí), ,做到第做到第k+1次二分次二分, ,計(jì)算得到的計(jì)算得到的 就是滿就是滿足精度要求的近似根足精度要求的近似根 。 在程序中通常用相鄰的在程序中通常用相鄰的 與與 的差的絕的差的絕對(duì)值或?qū)χ祷?與與 的差的絕

15、對(duì)值是否小于的差的絕對(duì)值是否小于來(lái)來(lái)決定二分區(qū)間的次數(shù)。決定二分區(qū)間的次數(shù)。 kxkx1kxkakb18二分法算法實(shí)現(xiàn)二分法算法實(shí)現(xiàn) y n 開 始 輸 入 a , b, (a+b)/2 x f(a) f(x )0 ? xb x a |b-a|0 輸 出 x 結(jié) 束 y n 19例題例題例例7.2 7.2 證明方程證明方程 在區(qū)間在區(qū)間2, 3內(nèi)有一個(gè)內(nèi)有一個(gè)根根 , 使用二分法求誤差不超過(guò)使用二分法求誤差不超過(guò)0.510-3 的根要二分的根要二分多少次？多少次？證明證明: 令令 0523 xx, 52)(3xxxf016)3(, 01)2(ff且且f( (x) )在在2, 3上連續(xù)上連續(xù),

16、,故方程故方程f(x)=0 0在在2,32,3內(nèi)至少有內(nèi)至少有一個(gè)根。又一個(gè)根。又 當(dāng)當(dāng) 時(shí)，時(shí)， , ,故故f( (x) )在在2, 32, 3上是單調(diào)遞增函數(shù)上是單調(diào)遞增函數(shù), ,從而從而f( (x) )在在2, 32, 3上有且僅有一根。上有且僅有一根。23)(2xxf3 , 2x0)( xf 給定誤差限給定誤差限 0.510-3 , ,使用二分法時(shí)使用二分法時(shí)20例題例題 誤差限為誤差限為 只要取只要取k滿足滿足 )(211*abxxkk311021)(21 abk即可，亦即即可，亦即 3102 k97.92110lg3gk所以需二分所以需二分1010次便可達(dá)到要求。次便可達(dá)到要求。2

17、1小結(jié)小結(jié) 二分法的優(yōu)點(diǎn)是不管有根區(qū)間二分法的優(yōu)點(diǎn)是不管有根區(qū)間 多大多大, ,總總能求出滿足精度要求的根能求出滿足精度要求的根, ,且對(duì)函數(shù)且對(duì)函數(shù)f( (x) )的要求不高的要求不高, ,只要連續(xù)即可只要連續(xù)即可, ,計(jì)算亦簡(jiǎn)單計(jì)算亦簡(jiǎn)單; ;它的局限性是只能用于它的局限性是只能用于求函數(shù)的實(shí)根求函數(shù)的實(shí)根, ,不能用于求復(fù)根及重根不能用于求復(fù)根及重根, ,它的收斂速它的收斂速度與比值為度與比值為 的等比級(jí)數(shù)相同。的等比級(jí)數(shù)相同。ba ,21227.2 不動(dòng)點(diǎn)迭代法及其收斂性不動(dòng)點(diǎn)迭代法及其收斂性 對(duì)于一般的非線性方程對(duì)于一般的非線性方程, ,沒(méi)有通常所說(shuō)的求根沒(méi)有通常所說(shuō)的求根公式求其精

18、確解公式求其精確解, ,需要設(shè)計(jì)近似求解方法需要設(shè)計(jì)近似求解方法, ,即迭代法。即迭代法。它是一種逐次逼近的方法它是一種逐次逼近的方法, ,用某個(gè)固定公式反復(fù)校正用某個(gè)固定公式反復(fù)校正根的近似值根的近似值, ,使之逐步精確化，最后得到滿足精度要使之逐步精確化，最后得到滿足精度要求的結(jié)果。求的結(jié)果。23不動(dòng)點(diǎn)迭代法的基本思想不動(dòng)點(diǎn)迭代法的基本思想即如果數(shù)即如果數(shù) 使使f(x)=0, 則也有則也有 , 反之反之, 若若 , 則也有則也有 , 稱稱 為迭代函數(shù)。為迭代函數(shù)。 任取一個(gè)初值任取一個(gè)初值 , 代入式代入式 的右端的右端, 得得到到 *x)(*xx)(*xx0)(*xf)(x0 x)(xx

19、)(01xx 為求解非線性方程為求解非線性方程f(x)=0 0的根，先將其寫成便于的根，先將其寫成便于迭代的等價(jià)方程迭代的等價(jià)方程 (7.3)(7.3)其中其中 為為x的連續(xù)函數(shù)的連續(xù)函數(shù))(x)(xx24不動(dòng)點(diǎn)迭代法的基本思想不動(dòng)點(diǎn)迭代法的基本思想再將再將 代入式代入式 的右端的右端, 得到得到 ,依此類推依此類推, 得到一個(gè)數(shù)列得到一個(gè)數(shù)列 ， 其一般表示其一般表示 1x)(xx)(12xx)(23xx), 2 , 1 , 0()(1kxxkk式式(7.4)(7.4)稱為求解非線性方程的稱為求解非線性方程的簡(jiǎn)單迭代法簡(jiǎn)單迭代法。 (7.4)(7.4)如果由迭代格式如果由迭代格式 產(chǎn)生的序列

20、產(chǎn)生的序列 收斂收斂, ,即即 nx)(1kkxx*limxxnn則稱迭代法收斂。則稱迭代法收斂。 25迭代法的基本思想迭代法的基本思想 實(shí)際計(jì)算中當(dāng)然不可能也沒(méi)必要無(wú)窮多步地做實(shí)際計(jì)算中當(dāng)然不可能也沒(méi)必要無(wú)窮多步地做下去下去, , 對(duì)預(yù)先給定的精度要求對(duì)預(yù)先給定的精度要求，只要某個(gè)，只要某個(gè)k k滿足滿足1kkxx即可結(jié)束計(jì)算并取即可結(jié)束計(jì)算并取 kxx* 當(dāng)然，迭代函數(shù)當(dāng)然，迭代函數(shù) 的構(gòu)造方法是多種多樣的。的構(gòu)造方法是多種多樣的。)( x26“不動(dòng)點(diǎn)不動(dòng)點(diǎn)”不動(dòng)點(diǎn)不動(dòng)點(diǎn)，是一個(gè)函數(shù)術(shù)語(yǔ)，在數(shù)學(xué)中是指，是一個(gè)函數(shù)術(shù)語(yǔ)，在數(shù)學(xué)中是指“被這個(gè)被這個(gè)函數(shù)函數(shù)映射映射到其自身一個(gè)點(diǎn)到其自身一個(gè)點(diǎn)”

21、。例如：例如： 定義在實(shí)數(shù)上的函數(shù)定義在實(shí)數(shù)上的函數(shù)f f， f(x) = x2 - 3x + 4 f(x) = x2 - 3x + 4，則則2 2是函數(shù)是函數(shù)f f的一個(gè)不動(dòng)點(diǎn)，因?yàn)榈囊粋€(gè)不動(dòng)點(diǎn)，因?yàn)閒(2) = 2f(2) = 2。27例題例題例例7.37.3 用迭代法求方程用迭代法求方程 中的根。中的根。解解 將方程改寫成如下等價(jià)形式將方程改寫成如下等價(jià)形式 xexx)(相應(yīng)地可得到迭代公式相應(yīng)地可得到迭代公式kxkkexx)(12ln,210 xex在在取初始值取初始值 0.50.5，用上述迭代公式迭代，用上述迭代公式迭代，計(jì)算結(jié)果見(jiàn)表計(jì)算結(jié)果見(jiàn)表0 x28例題例題 k01234xk0

22、.50.606531 0.545239 0.579703 0.560065 k56789xk0.571172 0.564863 0.568438 0.566410 0.567560 k1011121314xk0.566907 0.567278 0.567067 0.567187 0.56711929迭代法的幾何意義迭代法的幾何意義 通常將方程通常將方程f(x)=0f(x)=0化為與它同解的方程化為與它同解的方程的方法不止一種的方法不止一種, ,有的收斂有的收斂, ,有的不收斂有的不收斂, ,這取決于這取決于 的性態(tài)的性態(tài), ,方程方程 的求根問(wèn)題在幾何上就是確定曲的求根問(wèn)題在幾何上就是確定曲線

23、線y= 與直線與直線y=x的交點(diǎn)的交點(diǎn)P*的橫坐標(biāo)的橫坐標(biāo)( (如圖所示如圖所示) ) )(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)30迭代法的幾何意義迭代法的幾何意義 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* 31迭代法收斂的條件迭代法收斂的條件 對(duì)方程對(duì)方程f(x)=0可以構(gòu)造不同的

24、迭代公式可以構(gòu)造不同的迭代公式, 但但迭代公式迭代公式并非總是收斂。那么并非總是收斂。那么, ,當(dāng)?shù)瘮?shù)當(dāng)?shù)瘮?shù) 滿足什滿足什么條件時(shí)，相應(yīng)的迭代公式才收斂呢？即使迭么條件時(shí)，相應(yīng)的迭代公式才收斂呢？即使迭代收斂時(shí)，我們也不可能迭代很多次，而是迭代收斂時(shí)，我們也不可能迭代很多次，而是迭代有限次后就停止，這就需要估計(jì)迭代值的誤代有限次后就停止，這就需要估計(jì)迭代值的誤差，以便適時(shí)終止迭代差，以便適時(shí)終止迭代 ),2, 1 ,0()(1kxxkk)(x32迭代法收斂的條件迭代法收斂的條件定理定理7.1 設(shè)函數(shù)設(shè)函數(shù) 在在a,b上具有連續(xù)的一階導(dǎo)上具有連續(xù)的一階導(dǎo) 數(shù)數(shù), 且滿足且滿足 （1）對(duì)所

25、有的）對(duì)所有的xa,b 有有 a,b （2）存在）存在 0 L 1 ,使所有的使所有的xa,b有有 L則方程則方程 在在a,b上的解上的解 存在且唯一存在且唯一，對(duì)任意的，對(duì)任意的 a ,b ，迭代過(guò)程，迭代過(guò)程均收斂于均收斂于 。并有誤差估計(jì)式。并有誤差估計(jì)式 )(x)(x)(x)(xx*x0 x)(1kkxx*x33迭代法收斂的條件迭代法收斂的條件1*1kkkxxLLxx01*1xxLLxxkk 34迭代法收斂的條件迭代法收斂的條件由連續(xù)函數(shù)介值定理知由連續(xù)函數(shù)介值定理知, 必有必有 a, b, 使使 所以有解存在所以有解存在, 即即假設(shè)有兩個(gè)解假設(shè)有兩個(gè)解 和和 , , a, b，則，則

26、 ，證證: 構(gòu)造函數(shù)構(gòu)造函數(shù) ,由條件對(duì)任意的由條件對(duì)任意的xa, b a, b有有xxx)()(0)()(0)()(bbbaaa)(x*x0)()(*xxx*xx*xx)(*xx)(xx35迭代法收斂的條件迭代法收斂的條件由微分中值定理有由微分中值定理有其中其中 是介于是介于x*和和 之間的點(diǎn)之間的點(diǎn) 從而有從而有 a,b，進(jìn)而，進(jìn)而有有 由條件由條件(2)有有 1, 所以所以 - =0，即，即 = ，解唯一。，解唯一。)()()(*xxxxxxx0)(1)(*xx)(x*xx*xx按迭代過(guò)程按迭代過(guò)程 ,有有 )(1kkxx)()()(1*1*kkkxxxxxx1*1*)(kkkxxLxx

27、xx0*2*21*xxLxxLxxLxxkkkk 由于由于L1,L1,所以有所以有 , ,可見(jiàn)可見(jiàn)L L越小越小, ,收斂越快收斂越快 *limxxkk36迭代法收斂的條件迭代法收斂的條件再證誤差估計(jì)式再證誤差估計(jì)式 1*1kkkxxLLxx01*1xxLLxxkk 1*1*kkkkkxxxxLxxLxx)(1*kkkxxxxL1*)1 (kkkxxLxxL37迭代法收斂的條件迭代法收斂的條件1*1kkkxxLLxx 即即 得證。得證。 2121211)()()(kkkkkkkkxxLxxxxxx012121*1111xxLLxxLLxxLxxkkkkkk即即 得證。得證。 38迭代法的算法框

28、圖迭代法的算法框圖 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 2時(shí)稱為超線性收斂。時(shí)稱為超線性收斂。 kx44收斂速度收斂速度 數(shù)數(shù)p的大小反映了迭代法收斂的速度的快慢，的大小反映了迭代法收斂的

29、速度的快慢，p愈大，則收斂的速度愈快，故迭代法的收斂階愈大，則收斂的速度愈快，故迭代法的收斂階是對(duì)迭代法收斂速度的一種度量。是對(duì)迭代法收斂速度的一種度量。 45收斂階數(shù)收斂階數(shù)定理定理7.3 設(shè)迭代過(guò)程設(shè)迭代過(guò)程 , 若若 在所求根在所求根 的鄰域連續(xù)且的鄰域連續(xù)且 則迭代過(guò)程則迭代過(guò)程在在 鄰域是鄰域是p階收斂的。階收斂的。證證: 由于由于 即在即在 鄰域鄰域 , 所以所以 有局部收斂性有局部收斂性, 將將 在在 處泰勒展開處泰勒展開 )(1kkxx)()(xp*x0)(, 0)()()(*)(*) 1(* xxxxpp*x0)(* x*x1)(* x)(1kkxx)(kx*xpkpkkkx

30、xpxxxxxxxx)(!1)(! 21)()()(*)(2* 根據(jù)已知條件得根據(jù)已知條件得 pkpkxxpxx)(!1)()(*)(*46收斂階數(shù)收斂階數(shù)由迭代公式由迭代公式 )(1kkxx及及)(*xx有有pkpkxxpxx)(!)(*)(*10!)(lim*)(1pxeeppkkk47例題例題例例7.6 已知迭代公式已知迭代公式 收斂于收斂于 證明該迭代公式平方收斂。證明該迭代公式平方收斂。證證: 迭代公式相應(yīng)的迭代函數(shù)為迭代公式相應(yīng)的迭代函數(shù)為21132kkkxxx3*3x2132)(xxx436)(232)(xxxx ，將將 代入，代入，根據(jù)定理根據(jù)定理7.3可知，迭代公式平方收斂。

31、可知，迭代公式平方收斂。3*3x032336)(0)(33* xx，487.3 迭代收斂的加速方法迭代收斂的加速方法略略497.4 牛頓法牛頓法 用迭代法可逐步精確方程用迭代法可逐步精確方程 根的近似值根的近似值，但必須要找到，但必須要找到 的等價(jià)方程的等價(jià)方程 , ,如果如果 選得不合適選得不合適, ,不僅影響收斂速度不僅影響收斂速度, ,而且有可能造成迭代而且有可能造成迭代格式發(fā)散。能否找到一種迭代方法格式發(fā)散。能否找到一種迭代方法, ,既結(jié)構(gòu)簡(jiǎn)單既結(jié)構(gòu)簡(jiǎn)單, ,收斂收斂速度快速度快, ,又不存在發(fā)散的問(wèn)題。這就是本節(jié)要介紹的又不存在發(fā)散的問(wèn)題。這就是本節(jié)要介紹的牛頓迭代法牛頓迭代法。 0

32、)(xf0)(xf)(xx)(x牛頓迭代法一種重要和常用的迭代法牛頓迭代法一種重要和常用的迭代法, 它的基本思想它的基本思想是將非線性函數(shù)是將非線性函數(shù)f(x)逐步線性化逐步線性化, 從而將非線性方程從而將非線性方程f(x)=0近似地轉(zhuǎn)化為線性方程求解。近似地轉(zhuǎn)化為線性方程求解。50牛頓迭代公式牛頓迭代公式 對(duì)于方程對(duì)于方程 ,設(shè)其近似根為設(shè)其近似根為 , 函數(shù)函數(shù)f( (x) )可在可在 附近作泰勒展開附近作泰勒展開 0)(xfkxkx 2)(21)()()(kkkkkxxxfxxxfxfxf忽略高次項(xiàng)忽略高次項(xiàng), ,用其線性部分作為函數(shù)用其線性部分作為函數(shù)f(x)f(x)的近似，的近似，

33、)()()(kkkxxxfxfxf 設(shè)設(shè) 的根的根 , ,則有則有 , ,即即 0)(xf*x0)(*xf0)()(*kkkxxxfxf)()(*kkkxfxfxx將左端取為將左端取為 , ,即即 是比是比 更接近于更接近于 的近似值的近似值 )()(1kkkkxfxfxx)2,1 ,0(k1kx1kxkx*x牛頓迭代公式牛頓迭代公式51牛頓迭代法的幾何解釋牛頓迭代法的幾何解釋 方程方程f( (x)=0)=0的根的根x* *是曲線是曲線y= =f( (x) )與與x軸交點(diǎn)的橫坐軸交點(diǎn)的橫坐標(biāo)標(biāo), ,設(shè)設(shè)xk k是根是根x* *的某個(gè)近似值的某個(gè)近似值, ,過(guò)曲線過(guò)曲線y= =f( (x) )的

34、橫坐標(biāo)為的橫坐標(biāo)為xk k的點(diǎn)的點(diǎn)Pk=(xk, f (xk)引切線交引切線交x軸于軸于xk+1 , 并將其作為并將其作為x* * y y=f(x) Pk Pk+1 Pk+2 x* xk+2 xk+1 xk x 新的近似值新的近似值, ,重復(fù)重復(fù)上述過(guò)程上述過(guò)程, ,可見(jiàn)一可見(jiàn)一次次用切線方程來(lái)次次用切線方程來(lái)求解方程求解方程f( (x)=0)=0的的根根, ,所以亦稱為牛所以亦稱為牛頓切線法。頓切線法。52牛頓迭代法的收斂性牛頓迭代法的收斂性定理定理7.4 設(shè)設(shè) 是方程是方程 的單根的單根, 且且f(x)在在 的某的某鄰域內(nèi)有連續(xù)的二階導(dǎo)數(shù)鄰域內(nèi)有連續(xù)的二階導(dǎo)數(shù), 則牛頓法在則牛頓法在 附近

35、局部收附近局部收斂斂, 且至少二階收斂且至少二階收斂, 有有 *x0)(xf*x*x)(2)(limlim*2*1*1xfxfxxxxeekkkkkk 證證: 牛頓迭代公式對(duì)應(yīng)的迭代函數(shù)為牛頓迭代公式對(duì)應(yīng)的迭代函數(shù)為 若若 是方程是方程 的單根的單根,則有則有 , 從而從而 )()()(xfxfxx*x0)(xf0)(*xf0)(* xf0)()()()(2* xfxfxfx53牛頓迭代法的收斂性牛頓迭代法的收斂性由定理由定理7.2知知,牛頓迭代法在牛頓迭代法在 附近局部收斂。又由附近局部收斂。又由定理定理7.3知知, 迭代公式至少具有二階收斂速度。迭代公式至少具有二階收斂速度。 *x利用泰勒

36、公式利用泰勒公式kkkkkxxxxfxxxfxfxf,)(2)()()()(0*2* 2*)()(2)()()(kkkkkxxxffxfxfxx 2*)()(2)()()(kkkkkxxxffxxfxfx 54牛頓迭代法的收斂性牛頓迭代法的收斂性2*1)()(2)(kkkxxxffxx )(2)(lim*2*1*xfxfxxxxkkk 所以所以 證畢證畢55牛頓迭代法的收斂性牛頓迭代法的收斂性yx10 x0X*0 x0X*x2 不滿足迭代條件時(shí)，可能導(dǎo)致迭代值遠(yuǎn)離不滿足迭代條件時(shí)，可能導(dǎo)致迭代值遠(yuǎn)離根的情況而找不到根或死循環(huán)的情況根的情況而找不到根或死循環(huán)的情況56牛頓迭代法的算法實(shí)現(xiàn)牛頓迭代

37、法的算法實(shí)現(xiàn) ?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 57例題例題例例7.7 用用求求 x ex 1 =0的根的根,=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.5671458

38、7.5 弦截法弦截法牛頓迭代法雖然具有收斂速度快的優(yōu)點(diǎn)，但牛頓迭代法雖然具有收斂速度快的優(yōu)點(diǎn)，但每迭代一次都要計(jì)算導(dǎo)數(shù)每迭代一次都要計(jì)算導(dǎo)數(shù) , 當(dāng)當(dāng) 比較復(fù)比較復(fù)雜時(shí)雜時(shí), 不僅每次計(jì)算不僅每次計(jì)算 帶來(lái)很多不便，而且?guī)?lái)很多不便，而且還可能十分麻煩，如果用不計(jì)算導(dǎo)數(shù)的迭代還可能十分麻煩，如果用不計(jì)算導(dǎo)數(shù)的迭代方法，往往只有線性收斂的速度。本節(jié)介紹方法，往往只有線性收斂的速度。本節(jié)介紹的弦截法便是一種不必進(jìn)行導(dǎo)數(shù)運(yùn)算的求根的弦截法便是一種不必進(jìn)行導(dǎo)數(shù)運(yùn)算的求根方法。弦截法在迭代過(guò)程中不僅用到前一步方法。弦截法在迭代過(guò)程中不僅用到前一步 處的函數(shù)值處的函數(shù)值 ，而且還使用，而且還使用 處的函數(shù)值處的函數(shù)值來(lái)構(gòu)造迭代函數(shù)，這樣做能提高迭代的收斂來(lái)構(gòu)造迭代函數(shù)，這樣做能提高迭代的收斂速度。速度。)(kxf )(xf)(kxfkx1kx59弦截迭代公式弦截迭代公式 為避免計(jì)算函數(shù)的導(dǎo)數(shù)為避免計(jì)算函數(shù)的導(dǎo)數(shù) ，使用差商，使用差商 替代牛頓公式中的導(dǎo)數(shù)替代牛頓公式中的導(dǎo)數(shù) ,便得到迭代公式便得到迭代公式 稱為弦截迭代公式，稱為弦截迭代公式， 相