1、School of Automation Engineering自自 動動 化化 工工 程程 學學 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt引言引言 在科學研究和工程設計中在科學研究和工程設計中, 經常會遇到的一大類問題是非經常會遇到的一大類問題是非線性方程線性方程 f(x)=0 (4.1)的求根問題，其中的求根問題，其中f(x)為非線性函數。為非線性函數。f(x)=0的根的根, 亦稱為函數亦稱為函數f(x)的零點的零點 如果如果f(x)可以分解成可以分解成 ,其中其中m為正整數為正整數且且 ,則稱則稱x*是是f(x)的的m重零點重零點,或稱方程或稱方程f(x)=0的的

2、m重根。重根。當當m=1時稱時稱x*為單根。若為單根。若f(x)存在存在m階導數階導數,則是方程則是方程f(x)的的m重重根根(m1) 當且僅當當且僅當)()()(*xgxxxfm0)(*xg0)(,0)()()(*)(*)1(*xfxfxfxfmm第四章第四章 方程求根的迭代法方程求根的迭代法School of Automation Engineering自自 動動 化化 工工 程程 學學 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt記筆記記筆記 當當f(x)不是不是x的線性函數時，稱對應的函數方程為非線性方的線性函數時，稱對應的函數方程為非線性方程。如果程。如果f(x)

3、是多項式函數，則稱為代數方程，否則稱為超越是多項式函數，則稱為代數方程，否則稱為超越方程（三角方程，指數、對數方程等）。一般稱方程（三角方程，指數、對數方程等）。一般稱n次多項式構次多項式構成的方程成的方程 )0(00111nnnnnaaxaxaxa為為n次代數方程次代數方程,當當n1時時,方程顯然是非線性的。方程顯然是非線性的。 一般稍微復雜的一般稍微復雜的3次以上的代數方程或超越方程次以上的代數方程或超越方程,很難甚至很難甚至無法求得精確解。本章將介紹常用的求解非線性方程的近似無法求得精確解。本章將介紹常用的求解非線性方程的近似根的幾種數值解法根的幾種數值解法 。School of Aut

4、omation Engineering自自 動動 化化 工工 程程 學學 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理pptSchool of Automation Engineering自自 動動 化化 工工 程程 學學 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理pptn本章介紹方程的迭代解法，它既可以用來求解代數方程，本章介紹方程的迭代解法，它既可以用來求解代數方程，也可以用來解超越方程，并且僅限于求方程的實根。也可以用來解超越方程，并且僅限于求方程的實根。n運用迭代法求解方程的根應解決以下兩個問題：運用迭代法求解方程的根應解決以下兩個問題：q確定根的初值確定

5、根的初值;q將進一步精確化到所需要的精度。將進一步精確化到所需要的精度。School of Automation Engineering自自 動動 化化 工工 程程 學學 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt4.1 二分法二分法 二分法又稱二分區間法二分法又稱二分區間法,是求解方程是求解方程(4.1)的近似根的一種的近似根的一種常用的簡單方法。常用的簡單方法。 設函數設函數f(x)在閉區間在閉區間a,b上連續上連續,且且f(a)f(b)0,根據連續函根據連續函數的性質可知數的性質可知, f(x)= 0在在(a,b)內必有實根內必有實根,稱區間稱區間a,b為有根區為有

6、根區間。為明確起見間。為明確起見,假定方程假定方程f(x)=0在區間在區間a,b內有惟一實根內有惟一實根x*。 二分法的基本思想是二分法的基本思想是: 首先確定有根區間首先確定有根區間,將區間二等分將區間二等分, 通過判斷通過判斷f(x)的符號的符號, 逐步將有根區間縮小逐步將有根區間縮小, 直至有根區間足夠直至有根區間足夠地小地小, 便可求出滿足精度要求的近似根。便可求出滿足精度要求的近似根。School of Automation Engineering自自 動動 化化 工工 程程 學學 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt4.1.1確定有根區間的方法確定有根區

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

8、x)與與 x軸交點的橫坐標。軸交點的橫坐標。School of Automation Engineering自自 動動 化化 工工 程程 學學 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt 由高等數學知識知由高等數學知識知, 設設f (x)為區間為區間a,b上的單值連續上的單值連續, 如果如果f (a)f (b)0 , 則則a,b中至少有一個實根。如果中至少有一個實根。如果f (x)在在a,b上上還是單調地遞增或遞減，則僅有一個實根。還是單調地遞增或遞減，則僅有一個實根。記筆記記筆記n由此可大體確定根所在子區間，方法有：由此可大體確定根所在子區間，方法有： (1) 畫圖法畫

9、圖法 (2) 逐步搜索法逐步搜索法y=f(x)abyxSchool of Automation Engineering自自 動動 化化 工工 程程 學學 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt(1) 畫圖法畫圖法n 畫出畫出y = f (x)的略圖，從而看出曲線與的略圖，從而看出曲線與x軸交點的軸交點的 大致位置。大致位置。n 也可將也可將f (x) = 0分解為分解為 1(x)= 2(x)的形式，的形式， 1(x) 與與 2(x)兩曲線交點的橫坐標所在的子區間即為含根兩曲線交點的橫坐標所在的子區間即為含根 區間。區間。例如例如 xlogx-1= 0可以改寫為可以改寫

10、為logx=1/x畫出對數曲線畫出對數曲線y=logx,與雙曲線與雙曲線y= 1/x,它們交點的橫坐標它們交點的橫坐標位于區間位于區間2,3內內School of Automation Engineering自自 動動 化化 工工 程程 學學 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt(1) 畫圖法畫圖法xy1gxy 023yxSchool of Automation Engineering自自 動動 化化 工工 程程 學學 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理pptn對于某些看不清根的函數，可以擴大一下曲線對于某些看不清根的函數，可以擴大一下曲線y

11、0 xy=f(x)y=kf(x)記筆記記筆記School of Automation Engineering自自 動動 化化 工工 程程 學學 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppty0 xABa1b1a2b2(2) 逐步搜索法逐步搜索法 對于給定的對于給定的f (x),設有根區間為設有根區間為A,B,從從x0=A出發出發,以步長以步長h=(B-A)/n(n是正整數是正整數),在在A,B內取定節點內取定節點:xi=x0ih (i=0,1,2,n),從左至右檢查從左至右檢查f (xi)的符號的符號,如發現如發現xi與端點與端點x0的函的函數值異號數值異號,則得到一個縮小

12、的有根子區間則得到一個縮小的有根子區間xi-1,xi。School of Automation Engineering自自 動動 化化 工工 程程 學學 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt例例4.1 方程方程f(x)=x3-x-1=0 確定其有根區間確定其有根區間解：用試湊的方法，不難發現解：用試湊的方法，不難發現 f(0)0 在區間（在區間（0，2）內至少有一個實根）內至少有一個實根 設從設從x=0出發出發,取取h=0.5為步長向右進行根的為步長向右進行根的 搜索搜索,列表如下列表如下xf(x)0 0.5 1.0 1.5 2 + +可以看出，在可以看出，在1.0

13、,1.5內必有一根。內必有一根。School of Automation Engineering自自 動動 化化 工工 程程 學學 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理pptn 用逐步搜索法進行實根隔離的關鍵是選取步長用逐步搜索法進行實根隔離的關鍵是選取步長h。n 要選擇適當要選擇適當h ，使之既能把根隔離開來，工作量，使之既能把根隔離開來，工作量 又不太大。又不太大。 n 為獲取指定精度要求的初值為獲取指定精度要求的初值,可在以上隔離根的可在以上隔離根的 基礎上采用對分法繼續縮小該含根子區間。基礎上采用對分法繼續縮小該含根子區間。 二分法可以看作是搜索法的一種改進。二分

14、法可以看作是搜索法的一種改進。School of Automation Engineering自自 動動 化化 工工 程程 學學 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt 取有根區間取有根區間a,b之中點之中點, 將它分為兩半將它分為兩半,分點分點 ,這樣就這樣就可縮小有根區間可縮小有根區間4.2.2 二分法求根過程二分法求根過程 設方程設方程f(x)=0在區間在區間a,b內有根內有根,二分法就是逐步收縮有根二分法就是逐步收縮有根區間，最后得出所求的根。具體過程如下區間，最后得出所求的根。具體過程如下 :20bax y y=f(x) y=f(x) x* a x1 x*

15、x0 b a x0 x1 b a1 b1 a1 b1 a2 b2 a2 b2 School of Automation Engineering自自 動動 化化 工工 程程 學學 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt 對壓縮了的有根區間對壓縮了的有根區間 施行同樣的手法施行同樣的手法, 即取中點即取中點 ,將區間將區間 再分為兩半再分為兩半,然后再確定有根區間然后再確定有根區間 ，其長度是，其長度是 的二分之一。的二分之一。 如此反復下去如此反復下去,若不出現若不出現 ,即可得出一系列有根即可得出一系列有根 區間序列：區間序列： 上述每個區間都是前一個區間的一半上述每

16、個區間都是前一個區間的一半,因此因此 的長度的長度11,ba2111bax11,ba22,ba11,ba0)(kxfkkbabababa,2211kkba ,)(21)(2111abababkkkkk 當當k時趨于零時趨于零,這些區間最終收斂于一點這些區間最終收斂于一點x* 即為所求的根即為所求的根 。School of Automation Engineering自自 動動 化化 工工 程程 學學 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt 每次二分后每次二分后,取有根區間取有根區間 的中點的中點作為根的近似值，得到一個近似根的序列作為根的近似值，得到一個近似根的序列

17、該序列以根該序列以根x*為極限。為極限。 只要二分足夠多次只要二分足夠多次(即即k足夠大足夠大),便有便有這里這里為給定精度為給定精度,由于由于 ,則則 11122kkkkkababab1*22kkkkababxxkkba ,)(21kkkbax,210kxxxxkxx*kkbax,*School of Automation Engineering自自 動動 化化 工工 程程 學學 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt當給定精度當給定精度0后后,要想要想 成立成立,只要取只要取k滿足滿足 即可，亦即當即可，亦即當: kxx*)(211abk12lglg)lg(abk

18、時時,做到第做到第k+1次二分次二分,計算得到的計算得到的 就是滿足精度要求的近就是滿足精度要求的近似根似根 。 在程序中通常用相鄰的在程序中通常用相鄰的 與與 的差的絕對值或的差的絕對值或 與與 的差的絕對值是否小于的差的絕對值是否小于來決定二分區間的次數。來決定二分區間的次數。 kxkx1kxkakbSchool of Automation Engineering自自 動動 化化 工工 程程 學學 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt y n 開 始 輸 入 a , b, (a+b)/2 x f(a) f(x )0 ? xb x a |b-a|0 輸 出 x 結

19、 束 y n 二分法算法實現二分法算法實現School of Automation Engineering自自 動動 化化 工工 程程 學學 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt例例4.2 證明方程證明方程 在區間在區間2, 3內有一個根內有一個根, 使用二使用二分法求誤差不超過分法求誤差不超過0.510-3 的根要二分多少次？的根要二分多少次？證明：證明： 令令 0523 xx52)(3xxxf016)3(, 01)2(ff且且f(x)在在2, 3上連續上連續,故方程故方程f(x)=0在在2,3內至少有一個根。又內至少有一個根。又 當時當時時，時， ,故故f(x)

20、在在2, 3上是單調遞增函數上是單調遞增函數,從而從而f(x)在在2, 3上有且僅有一根。上有且僅有一根。23)(2xxf3 , 2x0)( xf 給定誤差限給定誤差限 0.510-3 ,使用二分法時使用二分法時School of Automation Engineering自自 動動 化化 工工 程程 學學 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt 誤差限為誤差限為 只要取只要取k滿足滿足 )(211*abxxkk311021)(21 abk即可，亦即即可，亦即 3102 k97.92110lg3gk所以需二分所以需二分10次便可達到要求。次便可達到要求。 二分法的優

21、點是不管有根區間二分法的優點是不管有根區間 多大多大,總能求出滿足總能求出滿足精度要求的根精度要求的根,且對函數且對函數f(x)的要求不高的要求不高,只要連續即可只要連續即可,計算亦計算亦簡單簡單;它的局限性是只能用于求函數的實根它的局限性是只能用于求函數的實根,不能用于求復根及不能用于求復根及重根重根,它的收斂速度與比值為它的收斂速度與比值為 的等比級數相同。的等比級數相同。 ba ,21School of Automation Engineering自自 動動 化化 工工 程程 學學 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt4.3 迭代法迭代法 對于一般的非線性方程

22、對于一般的非線性方程,沒有通常所說的求根公式求其沒有通常所說的求根公式求其精確解精確解,需要設計近似求解方法需要設計近似求解方法,即迭代法。它是一種逐次逼即迭代法。它是一種逐次逼近的方法近的方法,用某個固定公式反復校正根的近似值用某個固定公式反復校正根的近似值,使之逐步精使之逐步精確化，最后得到滿足精度要求的結果。確化，最后得到滿足精度要求的結果。4.3.1 迭代法的基本思想迭代法的基本思想 為求解非線性方程為求解非線性方程f(x)=0的根，先將其寫成便于迭代的等的根，先將其寫成便于迭代的等價方程價方程 (4.3)其中其中 為為x的連續函數。的連續函數。)(x)(xxSchool of Aut

23、omation Engineering自自 動動 化化 工工 程程 學學 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt即如果數即如果數 使使f(x)=0, 則也有則也有 , 反之反之, 若若 , 則則也有也有 , 稱稱 為迭代函數任取一個初值為迭代函數任取一個初值 , 代入式代入式 的右端的右端, 得到得到 *x)(*xx)(*xx0)(*xf)(x0 x)(xx)(01xx再將再將 代入式代入式 的右端的右端, 得到得到 ,依此類推依此類推, 得得到一個數列到一個數列 ， 其一般表示其一般表示 1x)(xx)(12xx)(23xx), 2 , 1 , 0()(1kxxkk

24、式式(4.4)稱為求解非線性方程的簡單迭代法。稱為求解非線性方程的簡單迭代法。 (4.4)School of Automation Engineering自自 動動 化化 工工 程程 學學 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt如果由迭代格式如果由迭代格式 產生的序列產生的序列 收斂收斂,即即 nx)(1kkxx*limxxnn則稱迭代法收斂。則稱迭代法收斂。 實際計算中當然不可能也沒必要無窮多步地做下去實際計算中當然不可能也沒必要無窮多步地做下去, 對預對預先給定的精度要求先給定的精度要求，只要某個，只要某個k滿足滿足1kkxx即可結束計算并取即可結束計算并取 kx

25、x* 當然，迭代函數當然，迭代函數 的構造方法是多種多樣的。的構造方法是多種多樣的。)( xSchool of Automation Engineering自自 動動 化化 工工 程程 學學 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt例例4.3 用迭代法求方程用迭代法求方程 在在x=1.5附近的一個根。附近的一個根。解解 將方程改寫成如下兩種等價形式將方程改寫成如下兩種等價形式 013 xx1)(1)(3231xxxxxx相應地可得到兩個迭代公式相應地可得到兩個迭代公式1)(1)(321311kkkkkkxxxxxx如果取初始值如果取初始值 1.5，用上述兩個迭代公式分別

26、迭代，計，用上述兩個迭代公式分別迭代，計算結果。算結果。 0 xSchool of Automation Engineering自自 動動 化化 工工 程程 學學 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt4.3.2 迭代法的幾何意義迭代法的幾何意義 通常將方程通常將方程f(x)=0化為與它同解的方程化為與它同解的方程 的方法不止的方法不止一種一種,有的收斂有的收斂,有的不收斂有的不收斂,這取決于這取決于 的性態的性態,方程方程 的求根問題在幾何上就是確定曲線的求根問題在幾何上就是確定曲線y= 與直線與直線y=x的交點的交點P*的橫坐標。的橫坐標。)(xx)(x)(xx)

27、(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)School of Automation Engineering自自 動動 化化 工工 程程 學學 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt 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* 圖圖4-1 迭代法的幾何意義迭代法的幾何意義 School

28、of Automation Engineering自自 動動 化化 工工 程程 學學 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt4.3.3 迭代法收斂的條件迭代法收斂的條件 對方程對方程f(x)=0可以構造不同的迭代公式可以構造不同的迭代公式, 但迭代公式但迭代公式并非總是收斂。那么并非總是收斂。那么,當迭代函數當迭代函數 滿足什么條件時，相應滿足什么條件時，相應的迭代公式才收斂呢？即使迭代收斂時，我們也不可能迭代的迭代公式才收斂呢？即使迭代收斂時，我們也不可能迭代很多次，而是迭代有限次后就停止，這就需要估計迭代值的很多次，而是迭代有限次后就停止，這就需要估計迭代值的誤差

29、，以便適時終止迭代誤差，以便適時終止迭代 。),2, 1 ,0()(1kxxkk)(xSchool of Automation Engineering自自 動動 化化 工工 程程 學學 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt定理定理4.1 設函數設函數 在在a,b上具有連續的一階導數上具有連續的一階導數, 且滿足且滿足 （1）對所有的）對所有的xa,b 有有 a,b （2）存在）存在 0 L 1 ,使所有的使所有的xa,b有有 L則方程則方程 在在a,b上的解上的解 存在且唯一，對任意的存在且唯一，對任意的 a ,b ，迭代過程，迭代過程 均收斂于均收斂于 。并有誤。

30、并有誤差估計式差估計式 )(x)(x)(x)(xx*x0 x)(1kkxx*x1*1kkkxxLLxx01*1xxLLxxkk School of Automation Engineering自自 動動 化化 工工 程程 學學 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt由連續函數介值定理知由連續函數介值定理知, 必有必有 a, b, 使使 所以有解存在所以有解存在, 即即假設有兩個解假設有兩個解 和和 ； , a, b，則，則 ，由微分中值定理有由微分中值定理有其中其中是介于是介于x*和和 之間的點，從而有之間的點，從而有a,b，進而有，進而有 由條件由條件(2)有有 1

31、, 所以所以 - =0，即，即 = ，解唯一。，解唯一。證證: 構造函數構造函數 ,由條件由條件對任意的對任意的xa, b a, b有有xxx)()(0)()(0)()(bbbaaa)(x*x0)()(*xxx*xx*xx)(*xx)(xx)()()(*xxxxxxx0)(1)(*xx)(x*xx*xxSchool of Automation Engineering自自 動動 化化 工工 程程 學學 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt按迭代過程按迭代過程 ,有有 )(1kkxx)()()(1*1*kkkxxxxxx1*1*)(kkkxxLxxxx0*2*21*xx

32、LxxLxxLxxkkkk 由于由于L1,所以有所以有 ,可見可見L越小越小,收斂越快收斂越快 *limxxkk再證誤差估計式再證誤差估計式 1*1kkkxxLLxx01*1xxLLxxkk School of Automation Engineering自自 動動 化化 工工 程程 學學 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt 1*1*kkkkkxxxxLxxLxx)(1*kkkxxxxL1*)1 (kkkxxLxxL1*1kkkxxLLxx 即即 得證。得證。 2121211)()()(kkkkkkkkxxLxxxxxx012121*1111xxLLxxLLxxL

33、xxkkkkkk即即 得證。得證。 School of Automation Engineering自自 動動 化化 工工 程程 學學 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt 10)(xx 開 始 輸 入 x0,N 1 kk+ 1 k x1 x0 輸 出 近 似 根 x1 |x1- x0|? 輸 出 迭 代 失 敗 標 志 結 束 n k0），使），使 )(1kkxx)(xx*xkkxxe*ceepkkk1lim則稱序列則稱序列 是是 p 階收斂的階收斂的,c稱漸近誤差常數。特別地稱漸近誤差常數。特別地,p=1時稱時稱為線性收斂為線性收斂,p=2時稱為平方收斂。時稱為

34、平方收斂。1 p 2時稱為超線性收斂。時稱為超線性收斂。 kx 數數p的大小反映了迭代法收斂的速度的快慢，的大小反映了迭代法收斂的速度的快慢，p愈大，則收斂愈大，則收斂的速度愈快，故迭代法的收斂階是對迭代法收斂速度的一種度量。的速度愈快，故迭代法的收斂階是對迭代法收斂速度的一種度量。 School of Automation Engineering自自 動動 化化 工工 程程 學學 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt定理定理4.3 設迭代過程設迭代過程 , 若若 在所求根在所求根 的鄰域連的鄰域連續且續且 則迭代過程在則迭代過程在 鄰域是鄰域是p階收斂的。階收斂的

35、。證證: 由于由于 即在即在 鄰域鄰域 , 所以所以 有局部收斂性有局部收斂性, 將將 在在 處泰勒展開處泰勒展開 )(1kkxx)()(xp*x0)(, 0)()()(*)(*) 1(* xxxxpp*x0)(* x*x1)(* x)(1kkxx)(kx*xpkpkkkxxpxxxxxxxx)(!1)(! 21)()()(*)(2* 根據已知條件得根據已知條件得 pkpkxxpxx)(!1)()(*)(*由迭代公式由迭代公式 )(1kkxx及及)(*xx有有pkpkxxpxx)(!)(*)(*10!)(lim*)(1pxeeppkkkSchool of Automation Engineer

36、ing自自 動動 化化 工工 程程 學學 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt例例4.7 已知迭代公式已知迭代公式 收斂于收斂于 證明該迭代公式平方收斂。證明該迭代公式平方收斂。證證: 迭代公式相應的迭代函數為迭代公式相應的迭代函數為21132kkkxxx3*3x2132)(xxx436)(232)(xxxx ，將將 代入，代入，根據定理根據定理4.3可知，迭代公式平方收斂。可知，迭代公式平方收斂。3*3x032336)(0)(33* xx，為了使迭代過程收斂或提高收斂的速度為了使迭代過程收斂或提高收斂的速度, 可設法可設法 提高初值的精度以減少迭代的次數提高初值的

37、精度以減少迭代的次數 提高收斂的階數提高收斂的階數 pSchool of Automation Engineering自自 動動 化化 工工 程程 學學 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt 用迭代法可逐步精確方程用迭代法可逐步精確方程 根的近似值，但必須要根的近似值，但必須要找到找到 的等價方程的等價方程 ,如果如果 選得不合適選得不合適,不僅影不僅影響收斂速度響收斂速度,而且有可能造成迭代格式發散。能否找到一種迭代而且有可能造成迭代格式發散。能否找到一種迭代方法方法,既結構簡單既結構簡單,收斂速度快收斂速度快,又不存在發散的問題。這就是本又不存在發散的問題。這就

38、是本節要介紹的牛頓迭代法節要介紹的牛頓迭代法2.4.1 牛頓迭代法的基本思想牛頓迭代法的基本思想 牛頓迭代法一種重要和常用的迭代法牛頓迭代法一種重要和常用的迭代法, 它的基本思想是將它的基本思想是將非線性函數非線性函數f(x)逐步線性化逐步線性化, 從而將非線性方程從而將非線性方程f(x)=0近似地轉近似地轉化為線性方程求解。化為線性方程求解。4.4 牛頓迭代法牛頓迭代法 0)(xf0)(xf)(xx)(xSchool of Automation Engineering自自 動動 化化 工工 程程 學學 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt 對于方程對于方程 ,設其

39、近似根為設其近似根為 ， 函數函數f(x)可在可在 附近作泰勒展開附近作泰勒展開 0)(xfkxkx 2)(21)()()(kkkkkxxxfxxxfxfxf忽略高次項忽略高次項,用其線性部分作為函數用其線性部分作為函數f(x)的近似，的近似， )()()(kkkxxxfxfxf 設設 的根的根 ,則有則有 ,即即 0)(xf*x0)(*xf0)()(*kkkxxxfxf)()(*kkkxfxfxx將右端取為將右端取為 ,即即 是比是比 更接近于更接近于 的近似值的近似值 )()(1kkkkxfxfxx)2,1 ,0(k1kx1kxkx*x這就是著名的牛頓迭代公式這就是著名的牛頓迭代公式Sch

40、ool of Automation Engineering自自 動動 化化 工工 程程 學學 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt2.4.2 牛頓迭代法的幾何解釋牛頓迭代法的幾何解釋 方程方程f(x)=0的根的根x*是曲線是曲線y=f(x)與與x軸交點的橫坐標軸交點的橫坐標,設設xk是根是根x*的某個近似值的某個近似值,過曲線過曲線y=f(x)的橫坐標為的橫坐標為xk的點的點Pk=(xk, f (xk)引切引切線交線交x軸于軸于xk+1 , 并將其作為并將其作為x* y y=f(x) Pk Pk+1 Pk+2 x* xk+2 xk+1 xk x 新的近似值新的近似值

41、,重復上述重復上述過程過程,可見一次次用切可見一次次用切線方程來求解方程線方程來求解方程f(x)=0的根的根,所以亦稱所以亦稱為牛頓切線法。為牛頓切線法。School of Automation Engineering自自 動動 化化 工工 程程 學學 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt（1） f(a) f(b)0,那么那么 Newton迭代法迭代法產生的數列產生的數列xn+1一定收斂一定收斂f(x)=0在在a,b中的唯一根中的唯一根。0)(, 0)(, 0)( 0 xfxfxf為例證明（其它情況類似）為例證明（其它情況類似） (). 設設 f(x)在在a,b滿足

42、下列條件滿足下列條件:以以School of Automation Engineering自自 動動 化化 工工 程程 學學 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt 將將f()在在 xn 處作處作2階階Taylor展開展開1212222 02 nnnnnnnnnnnnnnnnx)x()x( f)(fx)x()x( f)(f)x( f)x(fx)x(!)(f)x)(x( f)x(f)(f 說明數列說明數列 xn+1有下界有下界. 又又nnnnnxxfxfxx )( )(1所以所以xn+1收斂。設收斂。設 xxnnlim1則由則由Newton迭代法迭代法, x,)x(f,

43、)x( f)x(fxx0故故xn+1單調遞減。單調遞減。School of Automation Engineering自自 動動 化化 工工 程程 學學 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt2.4.3 牛頓迭代法的收斂性牛頓迭代法的收斂性定理定理4.4 設設 是方程是方程 的單根的單根, 且且f(x)在在 的某鄰域的某鄰域內有連續的二階導數內有連續的二階導數, 則牛頓法在則牛頓法在 附近局部收斂附近局部收斂, 且至少二且至少二階收斂階收斂, 有有 *x0)(xf*x*x)(2)(limlim*2*1*1xfxfxxxxeekkkkkk 證證: 牛頓迭代公式對應的迭

44、代函數為牛頓迭代公式對應的迭代函數為 若若 是方程是方程 的單根的單根,則有則有 , 從而從而 )()()(xfxfxx*x0)(xf0)(*xf0)(* xf0)()()()(2* xfxfxfx由定理由定理4.2知知,牛頓迭代法在牛頓迭代法在 附近局部收斂。又由定理附近局部收斂。又由定理4.3知知, 迭代公式至少具有二階收斂速度。迭代公式至少具有二階收斂速度。 *xSchool of Automation Engineering自自 動動 化化 工工 程程 學學 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt利用泰勒公式利用泰勒公式kkkkkxxxxfxxxfxfxf,)

45、(2)()()()(0*2* 2*)()(2)()()(kkkkkxxxffxfxfxx 2*)()(2)()()(kkkkkxxxffxxfxfx 2*1)()(2)(kkkxxxffxx )(2)(lim*2*1*xfxfxxxxkkk 所以所以 證畢證畢School of Automation Engineering自自 動動 化化 工工 程程 學學 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理pptyx0B=x0f (x)0 xn+1X*ayx0Bf (x)0a=x0yx0B=x0f (x)0ayx0Bf (x)0a =x0 4.4.3 牛頓迭代法的收斂性牛頓迭代法的收斂

46、性School of Automation Engineering自自 動動 化化 工工 程程 學學 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理pptyx10 x0X*0 x0X*x2 不滿足迭代條件時，可能導致迭代值遠離根的情況而找不不滿足迭代條件時，可能導致迭代值遠離根的情況而找不到根或死循環的情況到根或死循環的情況4.4.3 牛頓迭代法的收斂性牛頓迭代法的收斂性School of Automation Engineering自自 動動 化化 工工 程程 學學 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理pptNewton法的收斂性依賴于法的收斂性依賴于x0

47、的選取。的選取。x*x0 x0 x0School of Automation Engineering自自 動動 化化 工工 程程 學學 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt ?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 牛頓迭代法的算法實現牛頓迭代法的算法實現School of Automation Engineering自自 動動 化化 工工 程程 學學 院院第第 四四 章章

48、方程求根的迭代法方程求根的迭代法整理ppt例例4.11 用用求求 x=e-x的根的根,=10-4解：因解：因 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.56714School of Automation Engineering自自 動動 化化 工工 程程 學學 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt用用NewtonNewton迭代法求下面方程的一個正根迭代法求下

49、面方程的一個正根, ,計算結果精確計算結果精確到到7 7位小數位小數. .02010223 xxx322 ( )21020,(0)200,(2)160.0,2 ,( ) 34 x100, ( )640. f xxxxfffxxfxx 設在上滿足迭代定理的條件由由NewtonNewton迭代法迭代法 得得取取初初值值,x2020 x1 1 = 1.4666667 ,x4 4 = 1.3688081x5 5 = 1.3688081)()(1kkkkxfxfxx104310102223 kkkkkkkxxxxxxx迭代迭代5 5次次精度達精度達10-7x* * 1.3688081kx*x)(xfy

50、kxSchool of Automation Engineering自自 動動 化化 工工 程程 學學 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt4.4.5 牛頓下山法牛頓下山法 通常通常,牛頓迭代法的收斂性依賴于初始值牛頓迭代法的收斂性依賴于初始值 的選取的選取,如果如果 偏離所求的根偏離所求的根 比較遠比較遠,則牛頓法可能發散。為了防止迭代發散則牛頓法可能發散。為了防止迭代發散,我們對牛頓迭代法的迭代過程再附加一項要求我們對牛頓迭代法的迭代過程再附加一項要求,即具有單調性即具有單調性 0 x0 x*x)()(1kkxfxf 將牛頓迭代法與下山法結合起來使用將牛頓迭代法

51、與下山法結合起來使用,即在下山法保證函即在下山法保證函數值下降的前提下數值下降的前提下,用牛頓迭代法加快收斂速度。把這一算法用牛頓迭代法加快收斂速度。把這一算法稱為牛頓下山法。即稱為牛頓下山法。即滿足這項要求的算法稱下山法。滿足這項要求的算法稱下山法。)()(1kkkkxfxfxx其中其中(01)為下山因子為下山因子 School of Automation Engineering自自 動動 化化 工工 程程 學學 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt 下山因子的選擇是個逐步探索的過程，設從下山因子的選擇是個逐步探索的過程，設從=1開始反復開始反復將將減半進行試算減

52、半進行試算, 即逐次取即逐次取為為從中挑選下山因子，直至找到其中某個從中挑選下山因子，直至找到其中某個使單調性條件使單調性條件成立，則稱成立，則稱“下山成功下山成功”，否則，否則“下山失敗下山失敗”，這時需另選初值重算。這時需另選初值重算。,21,21,12)()(1kkxfxfSchool of Automation Engineering自自 動動 化化 工工 程程 學學 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt4.5 弦截法弦截法 牛頓迭代法雖然具有收斂速度快的優點，但每迭代一次都牛頓迭代法雖然具有收斂速度快的優點，但每迭代一次都要計算導數要計算導數 , 當當 比

53、較復雜時比較復雜時, 不僅每次計算不僅每次計算 帶帶來很多不便，而且還可能十分麻煩，如果用不計算導數的迭來很多不便，而且還可能十分麻煩，如果用不計算導數的迭代方法，往往只有線性收斂的速度。本節介紹的弦截法便是代方法，往往只有線性收斂的速度。本節介紹的弦截法便是一種不必進行導數運算的求根方法。弦截法在迭代過程中不一種不必進行導數運算的求根方法。弦截法在迭代過程中不僅用到前一步僅用到前一步 處的函數值，而且還使用處的函數值，而且還使用 處的函數值處的函數值來構造迭代函數，這樣做能提高迭代的收斂速度。來構造迭代函數，這樣做能提高迭代的收斂速度。)(kxf )(xf)(kxfkx1kxSchool o

54、f Automation Engineering自自 動動 化化 工工 程程 學學 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt 2.5.1 弦截法的基本思想弦截法的基本思想 為避免計算函數的導數為避免計算函數的導數 ，使用差商，使用差商 替代牛頓公式中的導數替代牛頓公式中的導數 ,便得到迭代公式便得到迭代公式 稱為弦截迭代公式，稱為弦截迭代公式， 相應的迭代法稱為弦截法相應的迭代法稱為弦截法。)()()(11kkkkxxxfxf)(kxf )()()()(111kkkkkkkxxxfxfxfxx),2, 1(k)(kxf School of Automation Engineering自自 動動 化化 工工 程程 學學 院院第第 四四 章章 方程求根的迭代法方程求根的迭代法整理ppt2.5.2 弦截法幾何意義弦截法幾何意義 弦截法也稱割線法弦截法也稱割線法,其幾何意義是用過曲線上兩其幾何意義是用過曲線上兩點點 、 的割線來代替曲線的割線來代