c語言計算機編程三種方法求解非線性方程.doc

本 科 專 業 學 年 論 文題 目非線性方程求解比較姓 名 何 娟 專 業 計算機科學技術系 班 級 08 級本科(2)班 指 導 老 師 劉 曉 娜 完成日期 2010 年 11 月 21 日計算機學年專業論文 非線性方程求解- 1 -題 目非線性方程求解比較摘 要本文給出了三種求解非線性方程的方法，分別是二分法，牛頓迭代法，割弦法。二分法巧妙地利用插值得到的點以及有根區間中點這兩點處的函數值，縮小隔根區間，以期望得到更快的收斂速度。牛頓迭代法是非線性方程根的一種常見的數值方法,對于非線性方程的單重零點來說，牛頓迭代法一般具有局部二階收斂性,但是當所求的根 X*是 FX的 M 重根時,M 是大于等于 2 的整數,此時牛頓迭代法只有一階收斂性。弦截法是將牛頓迭代公式中用差商 F -F kx1/ ( - )代替導數 。本文給出了算法改進的具體步驟及算法流程圖kx1kFx相關的數值結果也說明了方法的有效性。關 鍵 詞 二分法；牛頓迭代法；割弦法；非線性方程計算機學年專業論文 非線性方程求解- 2 -目 錄第一章 緒 論 1 第二章 求解非線性方程的三種常見算法 2 2.1 二分法 2 2.2 牛頓迭代法 3 2.3 割弦法 5 第三章 求解非線性方程的三種算法比較 6 3.1 二分法求解方法 6 3.2 牛頓迭代法求解 8 3.3 割弦法求解 9 參 考 文 獻 12計算機學年專業論文 非線性方程求解- 3 -第一章 緒 論在科技飛速發展的今天，計算機已經成為我們生活中不可缺少的一部分了，在我們生活與生產中扮演越來越重要的角色，而科學計算已經成為科學計算的重要方法之一，其應用范圍已滲透到所有科學領域，作為科學與工程計算的數學工具，計算方法已成為高等院校數學與應用數學，信息與計算科學，應用物理學等必修課。 在永恒變化發展的自然界與人類社會中，在研究其內部規律的各個科學領域中，更深刻、更精確地描述其內部規律的數學工具之一，就是非線性方程。非線性代數是研究大規模離散數據的運算處理與內在性狀的數學科學，科學技術離不開數據處理與數據分析，因此非線性代數具有廣泛的應用。無論在物理學、力學、化學、控制論等科學領域中，非線性方程屢見不鮮。就是在生命科學領域中，也是用非線性方程來描述生命過程中的能量、信息、物質等傳遞過程的。因此，對非線性方程的求解自然就是一個非常重要了。然而求解非線性方程有很多種方法，每種方法都有自己的優缺點。目前已有的數學軟件可以幫助我們實現上機計算，基本上已經將數值分析的主要內容設計成簡單的函數，只要調用這些函數進行運算便可得到數值結果。非線性代數中許多數值計算與計算機結合，才能得到更很好，更快，更精準的結果。為了將計算機與線性代數方程組更好的結合在一起，本文做了比較全面的的解說。本文比較全面的介紹了現代計算機科學與工程計算中常見的數值計算方法，對這些數值計算方法的基本理論與實際計算機實踐應用進行了詳細的分析，同時還簡要的分析了這些數值算法的計算效果，穩定性，收斂效果，適用范圍以及優劣性與特點。本文著重于化抽象為具體，引用一個具體的非線性方程用發散性的思維對其進行徹底的分析，主要有 引入一個非線性方程，分別運用三種思想進行分析，得到三種解法的根本思想； 把數學方法與數學思想提出來，并進行簡潔易懂的理論證明，既突出了線性代數的理論和基本思想，又可以幫助讀者對該數學方法的理解； 給出各種算法的循環思想以及流程圖，展現出一個清新的框架在讀者面前； 基于 c 語言的基礎上，寫出可執行的代碼。 對各種算法得到的結果進行比較分析。計算機學年專業論文 非線性方程求解- 4 -第二章 求解非線性方程的三種常見算法2.1 二分法單變量函數方程f(x)0其中，fx在閉區間a，b上連續、單調，且 fa*fb0，000f則由牛頓法產生的迭代序列 收斂于 fx0 的根 ，且nx*x21limfk定理 2對于方程 fx0，設 f(x)在a，b上有二階連續導數且滿足下述條件(1)fafb* *xf0,當 【 -, 】時，由牛頓迭代法 (k0,1,2 ，)式產0 xx1kkfx生的序列 是以不低于二階的收斂速度收斂到 .n *2.3 割弦法 設 , 為方程 fx0 的兩個近似根。用差商得f -f / - ，kx1 kx1kx1代替牛頓迭代公式中的導數 f ， 于是得到如下的迭代公式 kx - 。下面研究割弦法的幾何意義1kx11kkkxff經過點( ,f )及點( ,f )兩點作割線，其點斜式方程為1kx計算機學年專業論文 非線性方程求解- 7 -Yf( )- ，其零點為 X - kx1kkxxffkx把 X 用 表示即得到迭代格式，它又稱為雙點弦割11kkkff 1k法，需要兩個初值此割線與 X 軸交點的橫坐標就是新的近似值 ，所以弦截法又稱為割線1kx法，如圖所示。 下面三個定理為弦割法收斂定理定理 1設 f(x)在其零點 的鄰域 U( ， ) - ， 0*x*x*x*內有二階連續導數， ，則當 U( ， )時，由割弦法式產生的0f0序列 收斂于 ，且收斂的階為 1.618。nx*定理 2設 在區間a,b 上連續，且滿足下述三點f(1)fafb0內有二階連續導*x*xx數，fx 0 則當 U , 時，由弦割 -01k 11kkkxff計算機學年專業論文 非線性方程求解- 8 -式產生的序列 收斂于 ，且收斂的階為 1.618。nx*第三章 求解非線性方程的三種算法比較本章主要通過具體實例比較了第二章中三種算法的優缺點，并得到相應結論，求解非線性方程 x*x*x4*x*x-100 在1,2上，x01.5 附近的解精確到0.000 000 001。3.1 二分法求解方法二分法是求方程近似根的方法中行之有效的最簡單的方法，它的遞推過程簡單，便于計算機上實現，實現二分法的基本步驟如下。1 輸入有根區間的端點 a,b 及預先給定的精度 exp ；2 計算 xab/2 ；3 若 fa*fx1e-6;0 xprintf“The root is f“, ;0運行結果 n 有根區間a,b f 的符號nxnx1 1.0,2.0 1.5 2 1.0,1.5 1.25 _3 1.25,1.5 1.375 4 1.25,1.375 1.3125 _5 1.3125,1.375 1.343 75 _6 1.3475,1.375 1.359 375 _7 1.359375,1.375 1.367 185 計算機學年專業論文 非線性方程求解- 10 -The root is 1.3652303.2 牛頓迭代法求解步驟1 給出初始近似根 及精度 exp ；0 x2 計算 -f /f ；1x03 若 | - |1e-6;0 xprintf“The root is f“, ;0運行結果The root is 1.3652313.3 割弦法求解步驟1 選擇迭代初值 , 及精度 esp ；0 x12 計算 -(f * - / f -f )；210 x10 x3 若| - |include define eps 0.00001 /* 容許誤差 */define N 100 /* 最大迭代次數 N */float ffloat x /* 定義函數 fx */ float y;y x*x*x4*x*x-10;returny;void main float ,x1, ;0 x2int i;printf“ , “;01scanf“f,f“,xfori1;iN;i -f * - /f -f ; /* 弦截法迭代公式 */2x1101x0iffabs - eps fabsf eps /*滿足精度要求輸出近似根并退出*/2 printf“nRoot of equation is8.6fn“, ;2xreturn; ; /* 準備下一次迭代的初值 */0 x1 ;2計算機學年專業論文 非線性方程求解- 13 -printf“nAfter d repeat, no solved.n“,N; /* 輸出無解信息 */運行結果K f kxkx0 1.0 -5.01 2.0 14.02 1.263 157 895 -1.602274 3843 1.338 827 839 -0.430 364 7444 1.366 616 395 -0.022 909 4275 1.365 211 903 -2.990 671*pow10,-46 1.365 200 01 -2.0416*pow10,-77 1.365 230 013 0.08 1.365 230 013 0.0Root of equation is 1.365230小結二分法的優點是計算簡單，方法可靠，誤差容易估計，只要求連續，且總是收斂的，因此對函數的性質要求較低。它的缺點是不能求偶數重根，也不能求復根，且收斂較慢。故一般不單獨將其用于求根，只用其為根求得一個較好的近似值。 牛頓迭代法是多項式求根的一種效率很高的算法，收斂速度快(對單根) 。算法簡單是迭代法中較好者，但是它有兩個缺點第一每次只能求出一個 根，求其它根時若采用降次處理又會產生精度降低的問題。第二有時會遇到由于初始點選擇不當而使算法失效。，牛法和割弦法都是先將 fx線性化，然后求根，但線性化的方式不同從分析的角度說，牛頓法是在根 *x 鄰近點處的切線函數作為 fx的近似，而割弦法是在* x 鄰近用 fx的一次插值函數作為 fx的近似函數，它們本質的區別在于，牛頓迭代法在計算 時，只用到前一步的值 ，弦截法需要用兩1k kx個猜測值 ， ， 因此使用這種方法必須先給出兩個初始值 , 。1k 10根據以上三種方法的優缺點，我們在使用非線性方程求根時，應根據實際方程選出一種或者多種方法進行綜合求解，以便快速，便捷的求出最佳精確值。計算機學年專業論文 非線性方程求解- 14 -參 考 文 獻1 郭曦娟，Jacobi 和 Gauss-Seidel 迭代法收斂性的判定【J】,東北重型機械學院學報，199519(1) 。2 郝福華，侯建強，孟晉忠，迭代法在編程中的應用【J】,山西水利科技，1995109(5) 。3 趙艷霞，非線性方程求根的迭代法研究【J】,雞西大學學報。20088(2) 。4 黃憶潭，王德明，割線法向牛頓法德過度格式【J】 ，哈爾濱工業大學學報，199527(4) 。5 吳新元，解非線性方程的二階收斂指數迭代法【J】,計算方法，199820(4) 。6 程小力，牛頓法的收斂性【J】,浙江工業大學學報，199725(3) 。7 倪攸穎，求解非線性方程的一種半隱式迭代法【J】,哈爾濱理工大學學報，19983(2) 。8 高虹倪，曹澤陽，一種新的非線性方法的求根迭代法【J】,空軍工程大學學報，20023(2)