數(shù)值分析－非線性方程的數(shù)值解法PPT課件

1、 y a+1 a -50 O 50 x 50,502)(xeeayaxax第1頁/共78頁記筆記 由題設知曲線的最底點由題設知曲線的最底點(0,y(0)(0,y(0)與最高點與最高點(50,y(50)(50,y(50)之間的高度差為之間的高度差為1m,1m,所以應有所以應有y(50)=y(0)+1,y(50)=y(0)+1,即即 12)(5050aeeaaxa y a+1 a -50 O 50 x 要計算電纜的長度要計算電纜的長度, ,必必須先求出上述方程中須先求出上述方程中的的a ,a ,由于它是關于由于它是關于a a的非線性方程的非線性方程, ,沒有現(xiàn)沒有現(xiàn)成的公式可用成的公式可用,因此只

2、能尋求其他解法因此只能尋求其他解法. .第2頁/共78頁 10 xxxyxy1lgxx1lg第3頁/共78頁 10 xx010 xx第4頁/共78頁 RTbVVap)(20)()(2RTbVVapVf本章將介紹求解這種類型方程的近本章將介紹求解這種類型方程的近似解的數(shù)值方法似解的數(shù)值方法第5頁/共78頁2.1 引言引言 在科學研究和工程設計中在科學研究和工程設計中, 經常會遇到的一大類經常會遇到的一大類問題是非線性方程問題是非線性方程f(x)=0 (2.1)的求根問題，其中的求根問題，其中f(x)為非線性函數(shù)。為非線性函數(shù)。方程方程f(x)=0的根的根, 亦稱為函數(shù)亦稱為函數(shù)f(x)的零點的零

3、點 如果如果f(x)可以分解成可以分解成 , ,其中其中m為正為正整數(shù)且整數(shù)且 , ,則稱則稱x x* *是是f(x)f(x)的的m重零點重零點, ,或稱方或稱方程程f(x)=0的的m重根。當重根。當m=1時稱時稱x x* *為單根。若為單根。若f(x)存在存在m階導數(shù)階導數(shù), ,則是方程則是方程f(x)的的m重根重根( (m1) 當且僅當當且僅當)()()(*xgxxxfm0)(*xg0)(,0)()()(*)(*)1(*xfxfxfxfmm第6頁/共78頁記筆記 當當f(x)f(x)不是不是x x的線性函數(shù)時，稱對應的函數(shù)方程的線性函數(shù)時，稱對應的函數(shù)方程為非線性方程。如果為非線性方程。如

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

5、根的幾種數(shù)值解法 第7頁/共78頁記筆記 第8頁/共78頁 遠在公元前遠在公元前1700年的古巴比倫人就已有關于一、年的古巴比倫人就已有關于一、二次方程的解法。九章算術二次方程的解法。九章算術(公元前公元前50100年年)其中其中“方程術方程術”有聯(lián)立一次方程組有聯(lián)立一次方程組的一般解法。的一般解法。 1535年意大利數(shù)學家坦特格里亞年意大利數(shù)學家坦特格里亞(TorTaglia)發(fā)發(fā)現(xiàn)了三次方程的解法，卡當現(xiàn)了三次方程的解法，卡當(HCardano)從他從他那里得到了這種解法，于那里得到了這種解法，于1545年在其名著大年在其名著大法中公布了三次方程的公式解，稱為卡當算法。法中公布了三次方程的

6、公式解，稱為卡當算法。 后來卡當?shù)膶W生弗瑞里后來卡當?shù)膶W生弗瑞里(Ferrari)又提出了四次又提出了四次方程的解法。此成果更激發(fā)了數(shù)學家們的情緒，方程的解法。此成果更激發(fā)了數(shù)學家們的情緒，但在以后的二個世紀中，求索工作始終沒有成效，但在以后的二個世紀中，求索工作始終沒有成效，導致人們對高次代數(shù)方程解的存在性產生了懷疑。導致人們對高次代數(shù)方程解的存在性產生了懷疑。第9頁/共78頁 1799年，高斯證明了代數(shù)方程必有一個實根或年，高斯證明了代數(shù)方程必有一個實根或復根的定理，稱此為代數(shù)基本定理，并由此可以復根的定理，稱此為代數(shù)基本定理，并由此可以立刻推理立刻推理n次代數(shù)方程必有次代數(shù)方程必有n個實

7、根或復根。個實根或復根。 但在以后的幾十年中仍然沒有找出高次代數(shù)方程但在以后的幾十年中仍然沒有找出高次代數(shù)方程的公式解。一直到的公式解。一直到18世紀，法國數(shù)學家拉格朗世紀，法國數(shù)學家拉格朗日用根置換方法統(tǒng)一了二、三、四方程的解法。日用根置換方法統(tǒng)一了二、三、四方程的解法。 但求解五次方程時未能如愿但求解五次方程時未能如愿,開始意識到有潛藏開始意識到有潛藏其中的奧妙其中的奧妙, 用現(xiàn)代術語表示就是置換群理論問用現(xiàn)代術語表示就是置換群理論問題。題。 在繼續(xù)探索在繼續(xù)探索5次以上方程解的艱難歷程中，第一次以上方程解的艱難歷程中，第一個重大突破的是挪威數(shù)學家阿貝爾個重大突破的是挪威數(shù)學家阿貝爾(NA

8、bel1802-1829) 1824年阿貝爾發(fā)表了年阿貝爾發(fā)表了“五次方程代數(shù)解法不可能存在五次方程代數(shù)解法不可能存在”的論文，但并的論文，但并未受到重視，連數(shù)學大師高斯也未理解這項成果未受到重視，連數(shù)學大師高斯也未理解這項成果的重要意義。的重要意義。第10頁/共78頁 1828年年17歲的法國數(shù)學家伽羅華歲的法國數(shù)學家伽羅華(EGalois 1811-1832)寫出了劃時代的論文寫出了劃時代的論文“關于五次方關于五次方程的代數(shù)解法問題程的代數(shù)解法問題”，指出即使在公式中容許用，指出即使在公式中容許用n次方根，并用類似算法求五次或更高次代數(shù)方次方根，并用類似算法求五次或更高次代數(shù)方程的根是不可

9、能的程的根是不可能的 文章呈交法蘭西科學院后，因輩份太低遭到冷遇，文章呈交法蘭西科學院后，因輩份太低遭到冷遇，且文稿丟失。且文稿丟失。1830年伽羅華再進科學院遞稿，年伽羅華再進科學院遞稿，得到泊松院士的判詞得到泊松院士的判詞“完全不能理解完全不能理解”。 后來伽羅華命運不佳，投考名校巴黎工科大學落后來伽羅華命運不佳，投考名校巴黎工科大學落榜，屈就高等師院，并卷入政事兩次入獄，被開榜，屈就高等師院，并卷入政事兩次入獄，被開除學籍，又決斗受傷，死于除學籍，又決斗受傷，死于1832年。決斗前，年。決斗前，他把關于五次代數(shù)求解的研究成果寫成長信，留他把關于五次代數(shù)求解的研究成果寫成長信，留了下來。了

10、下來。第11頁/共78頁 十四年后，法國數(shù)學家劉維爾十四年后，法國數(shù)學家劉維爾(JLiouville)整整理并發(fā)表了伽羅華的遺作，人們才意識到這項理并發(fā)表了伽羅華的遺作，人們才意識到這項近代數(shù)學發(fā)展史上的重要成果的寶貴。近代數(shù)學發(fā)展史上的重要成果的寶貴。 38年后，即年后，即1870年，法國數(shù)學家若當年，法國數(shù)學家若當(CJordan)在專著論置換與代數(shù)方程中闡在專著論置換與代數(shù)方程中闡發(fā)了伽羅華的思想，一門現(xiàn)代數(shù)學的分支發(fā)了伽羅華的思想，一門現(xiàn)代數(shù)學的分支群群論誕生了。論誕生了。 在前幾個世紀中，曾開發(fā)出一些求解代數(shù)方程在前幾個世紀中，曾開發(fā)出一些求解代數(shù)方程的有效算法，它們構成了數(shù)值分析中

11、的古典算的有效算法，它們構成了數(shù)值分析中的古典算法。至于超越方程則不存在一般的求根方式。法。至于超越方程則不存在一般的求根方式。第12頁/共78頁本章介紹方程的迭代解法，它既可以本章介紹方程的迭代解法，它既可以用來求解代數(shù)方程，也可以用來解超用來求解代數(shù)方程，也可以用來解超越方程，并且僅限于求方程的實根。越方程，并且僅限于求方程的實根。運用迭代法求解方程的根應解決以下運用迭代法求解方程的根應解決以下兩個問題：兩個問題：確定根的初值確定根的初值;將進一步精確化到所需要的精度。將進一步精確化到所需要的精度。記筆記第13頁/共78頁2.2 二分法二分法 二分法又稱二分區(qū)間法二分法又稱二分區(qū)間法, ,

12、是求解方程是求解方程(2.1)(2.1)的近似的近似根的一種常用的簡單方法。根的一種常用的簡單方法。 設函數(shù)設函數(shù)f(x)f(x)在閉區(qū)間在閉區(qū)間 a,ba,b上連續(xù)上連續(xù), ,且且f(f(a)f()f(b)0,)0,根據(jù)連續(xù)函數(shù)的性質可知根據(jù)連續(xù)函數(shù)的性質可知, , f( (x)= 0)= 0在在( (a,b)a,b)內必有實根內必有實根, ,稱區(qū)間稱區(qū)間 a,ba,b為有根區(qū)間。為明確為有根區(qū)間。為明確起見起見, ,假定方程假定方程f(x)=0f(x)=0在區(qū)間在區(qū)間 a,ba,b內有惟一實根內有惟一實根x x* *。 二分法的基本思想是二分法的基本思想是: : 首先確定有根區(qū)間首先確定有

13、根區(qū)間, ,將區(qū)將區(qū)間二等分間二等分, , 通過判斷通過判斷f(x)f(x)的符號的符號, , 逐步將有根區(qū)間逐步將有根區(qū)間縮小縮小, , 直至有根區(qū)間足夠地小直至有根區(qū)間足夠地小, , 便可求出滿足精度便可求出滿足精度要求的近似根。要求的近似根。第14頁/共78頁確定有根區(qū)間的方法確定有根區(qū)間的方法 為了確定根的初值，首先必須圈定根所在的范圍，為了確定根的初值，首先必須圈定根所在的范圍， 稱為稱為圈定根或根的隔離圈定根或根的隔離。 在上述基礎上，采取適當?shù)臄?shù)值方法確定具有一在上述基礎上，采取適當?shù)臄?shù)值方法確定具有一定定 精度要求的初值。精度要求的初值。 對于代數(shù)方程，其根的個數(shù)（實或復的）與

14、其次對于代數(shù)方程，其根的個數(shù)（實或復的）與其次數(shù)數(shù) 相同。至于超越方程，其根可能是一個、幾個或相同。至于超越方程，其根可能是一個、幾個或無無 解，并沒有什么固定的圈根方法解，并沒有什么固定的圈根方法 求方程根的問題，就幾何上講求方程根的問題，就幾何上講,是求曲線是求曲線 y=f (x)與與 x軸交點的橫坐標。軸交點的橫坐標。第15頁/共78頁 由高等數(shù)學知識知由高等數(shù)學知識知, 設設f (x)為區(qū)間為區(qū)間a,b上的上的單值連續(xù)單值連續(xù), 如果如果f (a)f (b)0 , 則則a,b中至少中至少有一個實根。如果有一個實根。如果f (x)在在a,b上還是單調地遞上還是單調地遞增或遞減，則僅有一個

15、實根。增或遞減，則僅有一個實根。記筆記n由此可大體確定根所在子區(qū)間，方法有：由此可大體確定根所在子區(qū)間，方法有： (1) 畫圖法畫圖法 (2) 逐步搜索法逐步搜索法y=f(x)abyx第16頁/共78頁(1) 畫圖法畫圖法 畫出畫出y = f (x)的略圖，從而看出曲線與的略圖，從而看出曲線與x軸交點的軸交點的 大致位置。大致位置。 也可將也可將f (x) = 0分解為分解為 1(x)= 2(x)的形式，的形式， 1(x) 與與 2(x)兩曲線交點的橫坐標所在的子區(qū)間即為兩曲線交點的橫坐標所在的子區(qū)間即為含根含根 區(qū)間。區(qū)間。例如例如 xlogx-1= 0= 0可以改寫為可以改寫為logx=

16、=1/x畫出對數(shù)曲線畫出對數(shù)曲線y=logx, ,與雙曲線與雙曲線y= 1/x,它們它們交交 點的橫坐標位于區(qū)間點的橫坐標位于區(qū)間2,32,3內內第17頁/共78頁(1) 畫圖法畫圖法xy1gxy 023yx第18頁/共78頁n對于某些看不清根的函數(shù)，可以擴大一下曲線對于某些看不清根的函數(shù)，可以擴大一下曲線y0 xy=f(x)y=kf(x)記筆記第19頁/共78頁y0 xABa1b1a2b2(2) 逐步搜索法(2) (2) 搜索法搜索法 對于給定的對于給定的f (x),設有根區(qū)間為設有根區(qū)間為A, ,B,從從x0=A出出發(fā)發(fā), ,以步長以步長h=(B-A)/n(n是是正整數(shù)正整數(shù)),在在A,

17、,B內取定節(jié)內取定節(jié)點點: :xi=x0ih (i=0,1,2, ,n),從左至右檢查從左至右檢查f (xi)的符的符號號, ,如發(fā)現(xiàn)如發(fā)現(xiàn)xi與端點與端點x0的函數(shù)值異號的函數(shù)值異號, ,則得到一個縮小則得到一個縮小的有根子區(qū)間的有根子區(qū)間xi-1, ,xi。第20頁/共78頁例例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為步長向右

18、進行根為步長向右進行根的的 搜索搜索, ,列表如下列表如下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內必有一根內必有一根第21頁/共78頁 用逐步搜索法進行實根隔離的關鍵是選取步長用逐步搜索法進行實根隔離的關鍵是選取步長h 要選擇適當要選擇適當h ，使之既能把根隔離開來，工作量，使之既能把根隔離開來，工作量 又不太大。又不太大。 為獲取指定精度要求的初值為獲取指定精度要求的初值, ,可在以上隔離根的可在以上隔離根的 基礎上采用對分法繼續(xù)縮小該含根子區(qū)間基礎上采用對分法繼續(xù)縮小該含根子區(qū)間

19、 二分法可以看作是搜索法的一種改進。二分法可以看作是搜索法的一種改進。第22頁/共78頁 取有根區(qū)間取有根區(qū)間a,b之中點之中點, 將它分為兩半將它分為兩半,分點分點 ,這樣就可縮小有根區(qū)間這樣就可縮小有根區(qū)間 二分法求根過程二分法求根過程 設方程設方程f(x)=0在區(qū)間在區(qū)間a,b內有根內有根,二分法就是逐步二分法就是逐步收縮有根區(qū)間，最后得出所求的根。收縮有根區(qū)間，最后得出所求的根。具體過程如下具體過程如下 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 第23頁/共78頁 對壓縮了的有根區(qū)間對

20、壓縮了的有根區(qū)間 施行同樣的手法施行同樣的手法, , 即取中點即取中點 , ,將區(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ū)間

21、最終收斂于一點這些區(qū)間最終收斂于一點x x* * 即為即為 所求的根所求的根 。第24頁/共78頁每次二分后每次二分后, ,取有根區(qū)間取有根區(qū)間 的中點的中點作為根的近似值，得到一個近似根的序列作為根的近似值，得到一個近似根的序列 該序列以根該序列以根x x* *為極限為極限 只要二分足夠多次只要二分足夠多次( (即即k足夠大足夠大),),便有便有這里這里為給定精度為給定精度, ,由于由于 , ,則則 11122kkkkkababab1*22kkkkababxxkkba ,)(21kkkbax,210kxxxxkxx*kkbax,*第25頁/共78頁當給定精度當給定精度0 0后后, ,要想要想

22、 成立成立, ,只要只要取取k滿足滿足 即可，亦即當即可，亦即當: kxx*)(211abk12lglg)lg(abk時時, ,做到第做到第k+1次二分次二分, ,計算得到的計算得到的 就是滿就是滿足精度要求的近似根足精度要求的近似根 。 在程序中通常用相鄰的在程序中通常用相鄰的 與與 的差的絕的差的絕對值或對值或 與與 的差的絕對值是否小于的差的絕對值是否小于來來決定二分區(qū)間的次數(shù)。決定二分區(qū)間的次數(shù)。 kxkx1kxkakb第26頁/共78頁 y n 開 始 輸 入 a , b, (a+b)/2 x f(a) f(x )0 ? xb x a |b-a|0 輸 出 x 結 束 y n 二分法

23、算法實現(xiàn)二分法算法實現(xiàn)第27頁/共78頁例例 求求方程方程f( (x)=)=x3 3- -x-1=0 -1=0 在區(qū)間在區(qū)間1.0,1.5,1.5內內 的一的一 個實根個實根, 使誤差不超過使誤差不超過0.510-2。P19例例 證明方程證明方程 在區(qū)間在區(qū)間2, 3內有一個根內有一個根 , 使用二分法求誤差不超過使用二分法求誤差不超過0.510-3 的根要二的根要二 分多少次？分多少次？證明證明 令令 0523 xx52)(3xxxf016)3(, 01)2(ff且且f(x)f(x)在在2, 3上連續(xù)上連續(xù), ,故方程故方程f(x)=0f(x)=0在2,32,3內至少內至少有一個根。又有一個

24、根。又 當時當時時，時， , ,故故f(x)f(x)在在2, 32, 3上是單調遞增函數(shù)上是單調遞增函數(shù), ,從而從而f(x)f(x)在在2, 32, 3上有且僅有一根。上有且僅有一根。23)(2xxf3 , 2x0)( xf 給定誤差限給定誤差限 0.510-3 , ,使用二分法時使用二分法時第28頁/共78頁 誤差限為誤差限為 只要取只要取k滿足滿足 )(211*abxxkk311021)(21 abk即可，亦即即可，亦即 3102 k97.92110lg3gk所以需二分所以需二分1010次便可達到要求。次便可達到要求。 二分法的優(yōu)點是不管有根區(qū)間二分法的優(yōu)點是不管有根區(qū)間 多大多大, ,

25、總總能求出滿足精度要求的根能求出滿足精度要求的根, ,且對函數(shù)且對函數(shù)f(x)f(x)的要求不高的要求不高, ,只要連續(xù)即可只要連續(xù)即可, ,計算亦簡單計算亦簡單; ;它的局限性是只能用于它的局限性是只能用于求函數(shù)的實根求函數(shù)的實根, ,不能用于求復根及重根不能用于求復根及重根, ,它的收斂速它的收斂速度與比值為度與比值為 的等比級數(shù)相同。的等比級數(shù)相同。 ba ,21第29頁/共78頁2.3 迭代法迭代法 對于一般的非線性方程對于一般的非線性方程, ,沒有通常所說的求根沒有通常所說的求根公式求其精確解公式求其精確解, ,需要設計近似求解方法需要設計近似求解方法, ,即迭代法。即迭代法。它是一

26、種逐次逼近的方法它是一種逐次逼近的方法, ,用某個固定公式反復校正用某個固定公式反復校正根的近似值根的近似值, ,使之逐步精確化，最后得到滿足精度要使之逐步精確化，最后得到滿足精度要求的結果。求的結果。 為求解非線性方程為求解非線性方程f(x)=0f(x)=0的根，先將其寫成便的根，先將其寫成便于迭代的等價方程于迭代的等價方程 (2.3) (2.3)其中其中 為為x x的連續(xù)函數(shù)的連續(xù)函數(shù))(x)(xx第30頁/共78頁2.3 迭代法迭代法即如果數(shù)即如果數(shù) 使使f(x)=0, 則也有則也有 , 反之反之, 若若 , 則也有則也有 , 稱稱 為迭代函數(shù)為迭代函數(shù) 任任取一個初值取一個初值 , 代

27、入式代入式 的右端的右端, 得到得到 *x)(*xx)(*xx0)(*xf)(x0 x)(xx)(01xx再將再將 代入式代入式 的右端的右端, 得到得到 ,依此類推依此類推, 得到一個數(shù)列得到一個數(shù)列 ， 其一般表示其一般表示 1x)(xx)(12xx)(23xx), 2 , 1 , 0()(1kxxkk式式(2.4)(2.4)稱為求解非線性方程的稱為求解非線性方程的簡單迭代法簡單迭代法。 (2.4)(2.4)第31頁/共78頁如果由迭代格式如果由迭代格式 產生的序列產生的序列 收斂收斂, ,即即 nx)(1kkxx*limxxnn則稱迭代法收斂。則稱迭代法收斂。 實際計算中當然不可能也沒必

28、要無窮多步地做實際計算中當然不可能也沒必要無窮多步地做下去下去, , 對預先給定的精度要求對預先給定的精度要求，只要某個只要某個k k滿足滿足1kkxx即可結束計算并取即可結束計算并取 kxx* 當然，迭代函數(shù)當然，迭代函數(shù) 的構造方法是多種多樣的。的構造方法是多種多樣的。)( x第32頁/共78頁例例4 用迭代法求方程用迭代法求方程 在在x=1.5附近的一個根附近的一個根解解 將方程改寫成如下兩種等價形式將方程改寫成如下兩種等價形式 013 xx1)(1)(3231xxxxxx相應地可得到兩個迭代公式相應地可得到兩個迭代公式1)(1)(321311kkkkkkxxxxxx如果取初始值如果取初

29、始值 1.51.5，用上述兩個迭代公，用上述兩個迭代公式分別迭代，計算結果見式分別迭代，計算結果見P P2121 0 x第33頁/共78頁2.3.2 迭代法的幾何意義迭代法的幾何意義 通常將方程通常將方程f(x)=0f(x)=0化為與它同解的方程化為與它同解的方程的方法不止一種的方法不止一種, ,有的收斂有的收斂, ,有的不收斂有的不收斂, ,這取決于這取決于 的性態(tài)的性態(tài), ,方程方程 的求根問題在幾何上就是確定曲的求根問題在幾何上就是確定曲線線y= 與直線與直線y=x的交點的交點P*的橫坐標的橫坐標( (圖圖2-3所示所示) ) )(xx)(x)(xx)(x y=x y y=)(x y=x

30、 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)第34頁/共78頁 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* 圖圖2-3 迭代法的幾何意義迭代法的幾何意義 第35頁/共78頁2.3.3 迭代法收斂的條件迭代法收斂的條件 對方程對方程f(x)=0可以構造不同的迭代公式可以構造不同的迭代公式, 但但迭代公式迭代公式并非總是收斂。那么并非總是收斂。那么,

31、,當?shù)瘮?shù)當?shù)瘮?shù) 滿足什滿足什么條件時，相應的迭代公式才收斂呢？即使迭么條件時，相應的迭代公式才收斂呢？即使迭代收斂時，我們也不可能迭代很多次，而是迭代收斂時，我們也不可能迭代很多次，而是迭代有限次后就停止，這就需要估計迭代值的誤代有限次后就停止，這就需要估計迭代值的誤差，以便適時終止迭代差，以便適時終止迭代 ),2, 1 ,0()(1kxxkk)(x第36頁/共78頁定理定理2.1 設函數(shù)設函數(shù) 在在a,b上具有連續(xù)的一階導上具有連續(xù)的一階導 數(shù)數(shù), 且滿足且滿足 （1）對所有的）對所有的xa,b 有有 a,b （2）存在存在 0 L 1 ,使所有的使所有的xa,b有有 L則方程則方程

32、 在在a,b上的解上的解 存在且唯一存在且唯一，對任意的，對任意的 a ,b ，迭代過程迭代過程均收斂于均收斂于 。并有誤差估計式。并有誤差估計式 )(x)(x)(x)(xx*x0 x)(1kkxx*x1*1kkkxxLLxx01*1xxLLxxkk 第37頁/共78頁由連續(xù)函數(shù)介值定理知由連續(xù)函數(shù)介值定理知, 必有必有 a, b, 使使 所以有解存在所以有解存在, 即即假設有兩個解假設有兩個解 和和 , , a, b，則則 ，由微分中值定理有由微分中值定理有其中其中是介于是介于x*和和 之間的點之間的點 從而有從而有a,b，進進而有而有 由條件由條件(2)有有 1, 所以所以 - =0，即，

33、即 = ，解唯一。，解唯一。證證: 構造函數(shù)構造函數(shù) ,由條件對任意的由條件對任意的xa, b a, b有有xxx)()(0)()(0)()(bbbaaa)(x*x0)()(*xxx*xx*xx)(*xx)(xx)()()(*xxxxxxx0)(1)(*xx)(x*xx*xx第38頁/共78頁按迭代過程按迭代過程 ,有有 )(1kkxx)()()(1*1*kkkxxxxxx1*1*)(kkkxxLxxxx0*2*21*xxLxxLxxLxxkkkk 由于由于L1,L1,所以有所以有 , ,可見可見L L越小越小, ,收斂越快收斂越快 *limxxkk再證誤差估計式再證誤差估計式 1*1kkkx

34、xLLxx01*1xxLLxxkk 第39頁/共78頁 1*1*kkkkkxxxxLxxLxx)(1*kkkxxxxL1*)1 (kkkxxLxxL1*1kkkxxLLxx 即即 得證。得證。 2121211)()()(kkkkkkkkxxLxxxxxx012121*1111xxLLxxLLxxLxxkkkkkk即即 得證。得證。 第40頁/共78頁 10)(xx 開 始 輸 入 x0,N 1 kk+ 1 k x1 x0 輸 出 近 似 根 x1 |x1- x0|? 輸 出 迭 代 失 敗 標 志 結 束 n k0c0），），使使 )(1kkxx)(xx*xkkxxe*ceepkkk1lim則

35、稱序列則稱序列 是是 p 階收斂的階收斂的, ,c稱漸近誤差常數(shù)。稱漸近誤差常數(shù)。特別地特別地, ,p=1=1時稱為線性收斂時稱為線性收斂, ,p=2=2時稱為平方收時稱為平方收斂。斂。1 1 p 2 0 xn+1X*ayx0Bf(x)0a=x0yx0B=x0f(x)0ayx0Bf(x)0a =x0 牛頓迭代法的收斂性牛頓迭代法的收斂性第59頁/共78頁 牛頓迭代法對初值牛頓迭代法對初值x0的選取要求比較高。的選取要求比較高。 x0必必須充分靠近須充分靠近x*才能保證局部收斂。才能保證局部收斂。定理定理2.5 如果在有根區(qū)間如果在有根區(qū)間a,b上上連續(xù)且不變號，在連續(xù)且不變號，在a,b上取初始

36、近似根上取初始近似根x0滿足，滿足，則牛頓迭代法產生的迭代序列單調收斂于方程則牛頓迭代法產生的迭代序列單調收斂于方程f(x)=0在該區(qū)間上的唯一解。在該區(qū)間上的唯一解。證明證明 （ 略略 ）)(, 0)(, 0)()(xfxfbfaf 0)()(00 xfxf第60頁/共78頁yx10 x0X*0 x0X*x2 不滿足迭代條件時，可能導致迭代值遠離不滿足迭代條件時，可能導致迭代值遠離根的情況而找不到根或死循環(huán)的情況根的情況而找不到根或死循環(huán)的情況 牛頓迭代法的收斂性牛頓迭代法的收斂性第61頁/共78頁 ?0)(0 xf 1000)()(xxfxfx ?01 xx 開 始 輸 入 x0,N 1

37、k k+ 1 k x1 x0 輸 出 x1 輸 出 迭 代 失 敗 標 志 結 束 n k N ? n n y 輸 出 奇 異 標 志 y y 2. .4. .4 牛頓迭代法的算法實現(xiàn)牛頓迭代法的算法實現(xiàn)第62頁/共78頁例例2.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.56714第63頁/共78頁2. .4. .5 牛頓下山法牛

38、頓下山法 通常通常, ,牛頓迭代法的收斂性依賴于初始值牛頓迭代法的收斂性依賴于初始值 的選取的選取, ,如果如果 偏離所求的根偏離所求的根 比較遠比較遠, ,則牛頓法可能發(fā)散。則牛頓法可能發(fā)散。為了防止迭代發(fā)散為了防止迭代發(fā)散, ,我們對牛頓迭代法的迭代過程再附我們對牛頓迭代法的迭代過程再附加一項要求加一項要求, ,即具有單調性即具有單調性 0 x0 x*x)()(1kkxfxf 將牛頓迭代法與下山法結合起來使用將牛頓迭代法與下山法結合起來使用, ,即在下山即在下山法保證函數(shù)值下降的前提下法保證函數(shù)值下降的前提下, ,用牛頓迭代法加快收斂用牛頓迭代法加快收斂速度。把這一算法稱為牛頓下山法。即速

39、度。把這一算法稱為牛頓下山法。即滿足這項要求的算法稱下山法。滿足這項要求的算法稱下山法。)()(1kkkkxfxfxx其中其中(01)(01)為下山因子為下山因子 第64頁/共78頁 下山因子的選擇是個逐步探索的過程，設從下山因子的選擇是個逐步探索的過程，設從=1開始反復將開始反復將減半進行試算減半進行試算, 即逐次取即逐次取為為從中挑選下山因子，直至找到其中某個從中挑選下山因子，直至找到其中某個使單調性使單調性條件條件成立，則稱成立，則稱“下山成功下山成功”，否則，否則“下山失敗下山失敗”，這時需另選初值重算。這時需另選初值重算。,21,21,12)()(1kkxfxf第65頁/共78頁2.

40、5 弦截法弦截法 牛頓迭代法雖然具有收斂速度快的優(yōu)點，牛頓迭代法雖然具有收斂速度快的優(yōu)點，但每迭代一次都要計算導數(shù)但每迭代一次都要計算導數(shù) , 當當 比較比較復雜時復雜時, 不僅每次計算不僅每次計算 帶來很多不便，而帶來很多不便，而且還可能十分麻煩，如果用不計算導數(shù)的迭且還可能十分麻煩，如果用不計算導數(shù)的迭代方法，往往只有線性收斂的速度。本節(jié)介代方法，往往只有線性收斂的速度。本節(jié)介紹的弦截法便是一種不必進行導數(shù)運算的求紹的弦截法便是一種不必進行導數(shù)運算的求根方法。弦截法在迭代過程中不僅用到前一根方法。弦截法在迭代過程中不僅用到前一步步 處的函數(shù)值，而且還使用處的函數(shù)值，而且還使用 處的函數(shù)處的

41、函數(shù)值來構造迭代函數(shù)，這樣做能提高迭代的收值來構造迭代函數(shù)，這樣做能提高迭代的收斂速度。斂速度。)(kxf )(xf)(kxfkx1kx第66頁/共78頁弦截法的基本思想弦截法的基本思想 為避免計算函數(shù)的導數(shù)為避免計算函數(shù)的導數(shù) ，使用差商，使用差商 替代牛頓公式中的導數(shù)替代牛頓公式中的導數(shù) ,便得到迭代公式便得到迭代公式 稱為弦截迭代公式，稱為弦截迭代公式， 相應的迭代法稱為弦截法相應的迭代法稱為弦截法。)()()(11kkkkxxxfxf)(kxf )()()()(111kkkkkkkxxxfxfxfxx),2, 1(k)(kxf 第67頁/共78頁弦截法幾何意義弦截法幾何意義弦截法也稱割

42、線法弦截法也稱割線法, ,其幾何意義是用過曲線上兩其幾何意義是用過曲線上兩點點 、 的割線來代替曲線的割線來代替曲線, ,用割用割線與線與x軸交點的橫座標作為方程的近似根軸交點的橫座標作為方程的近似根 再過再過P1點和點點和點 作割線求出作割線求出 , ,再再過過P2點和點點和點 作割線求出作割線求出 , ,余余此類推，當收斂時此類推，當收斂時可求出滿足精度要可求出滿足精度要求的求的 P1 y=f(x) x0 x2 x3 x1 x* P3 P0 P2 )(,(000 xfxP)(,(111xfxP2x)(,(222xfxP3x)(,(333xfxP4xkx第68頁/共78頁 可以證明，弦截法具

43、有超線性收斂，收斂可以證明，弦截法具有超線性收斂，收斂的階約為的階約為1.618，它與前面介紹的一般迭代法一，它與前面介紹的一般迭代法一樣都是線性化方法，但也有區(qū)別。即一般迭代樣都是線性化方法，但也有區(qū)別。即一般迭代法在計算法在計算 時只用到前一步的值時只用到前一步的值 ，故稱之，故稱之為單點迭代法；而弦截法在求為單點迭代法；而弦截法在求 時要用到前兩時要用到前兩步的結果步的結果 和和 ，使用這種方法必須給出兩，使用這種方法必須給出兩個初始近似根個初始近似根 ，這種方法稱為多點迭代，這種方法稱為多點迭代法法。 1kxkx1kx1kxkx10,xx第69頁/共78頁例例2.12 用弦截法求方程用

44、弦截法求方程 在在 初始初始 值鄰近的一個根。要求值鄰近的一個根。要求解：取解：取 , , 令令 利用弦截迭代公式利用弦截迭代公式 計算結果見計算結果見P34列表，列表， 易見取近似根易見取近似根 則可滿足精度要求。則可滿足精度要求。xex5 . 00 x0001. 01kkxx5 . 00 x6.01xxexxf)()()()()(1111kkxxkkxkkkxxeexxexxxkkk56714. 04x第70頁/共78頁2. .5. .3 弦截法算法實現(xiàn)弦截法算法實現(xiàn) ?0)(0 xf ?0)(1xf ?0)()(01xfxf 2010111)()()()(xxxxfxfxfx ?12 xx 輸 入 x0, x1,N 1 k k+ 1 k x1 x0 x2 x1 f(x1)f(x0) f(x2) f(x1) 輸 出 x2 輸 出 迭 代 失 敗 標 志 結 束 n k N ? n n y 輸 出 奇