非線性方程論文

1、本本 科科 專專 業(yè)業(yè) 學(xué)學(xué) 年年 論論 文文題題 目：目：非線性方程求解比較非線性方程求解比較姓姓 名名： 何 娟 專專 業(yè)業(yè)： 計算機(jī)科學(xué)技術(shù)系 班班 級級： 08 級本科（2）班 指指 導(dǎo)導(dǎo) 老老 師師： 劉 曉 娜 完成日期：完成日期： 2010 年年 11 月月 21 日日題題 目：目：非線性方程求解比較非線性方程求解比較摘摘 要要 本文給出了三種求解非線性方程的方法，分別是二分法，牛頓迭代法，割弦法。二分法巧妙地利用插值得到的點以及有根區(qū)間中點這兩點處的函數(shù)值，縮小隔根區(qū)間，以期望得到更快的收斂速度。牛頓迭代法是非線性方程根的一種常見的數(shù)值方法,對于非線性方程的單重零點來說，牛頓迭

2、代法一般具有局部二階收斂性,但是當(dāng)所求的根 X*是 F(X)的 M 重根時,M 是大于等于 2 的整數(shù),此時牛頓迭代法只有一階收斂性。弦截法是將牛頓迭代公式中用差商 F()-F()kx1kx/ （- ）代替導(dǎo)數(shù)。本文給出了算法改進(jìn)的具體步驟及算法流程圖kx1kx()kF x相關(guān)的數(shù)值結(jié)果也說明了方法的有效性。關(guān)關(guān) 鍵鍵 詞詞 : : 二分法；牛頓迭代法；割弦法；非線性方程 目目 錄錄第一章 緒 論1 第二章 求解非線性方程的三種常見算法 2 2.1 二分法二分法2 2.2 牛頓迭代法牛頓迭代法3 2.3 割弦法割弦法5 第三章 求解非線性方程的三種算法比較6 3.1 二分法求解方法二分法求解方

3、法6 3.2 牛頓迭代法求解牛頓迭代法求解 8 3.3 割弦法求解割弦法求解9 參參 考考 文文 獻(xiàn)獻(xiàn) 12第一章第一章 緒緒 論論 在科技飛速發(fā)展的今天，計算機(jī)已經(jīng)成為我們生活中不可缺少的一部分了，在我們生活與生產(chǎn)中扮演越來越重要的角色，而科學(xué)計算已經(jīng)成為科學(xué)計算的重要方法之一，其應(yīng)用范圍已滲透到所有科學(xué)領(lǐng)域，作為科學(xué)與工程計算的數(shù)學(xué)工具，計算方法已成為高等院校數(shù)學(xué)與應(yīng)用數(shù)學(xué)，信息與計算科學(xué)，應(yīng)用物理學(xué)等必修課。 在永恒變化發(fā)展的自然界與人類社會中，在研究其內(nèi)部規(guī)律的各個科學(xué)領(lǐng)域中，更深刻、更精確地描述其內(nèi)部規(guī)律的數(shù)學(xué)工具之一，就是非線性方程。非線性代數(shù)是研究大規(guī)模離散數(shù)據(jù)的運算處理與內(nèi)在性

4、狀的數(shù)學(xué)科學(xué)，科學(xué)技術(shù)離不開數(shù)據(jù)處理與數(shù)據(jù)分析，因此非線性代數(shù)具有廣泛的應(yīng)用。無論在物理學(xué)、力學(xué)、化學(xué)、控制論等科學(xué)領(lǐng)域中，非線性方程屢見不鮮。就是在生命科學(xué)領(lǐng)域中，也是用非線性方程來描述生命過程中的能量、信息、物質(zhì)等傳遞過程的。因此，對非線性方程的求解自然就是一個非常重要了。然而求解非線性方程有很多種方法，每種方法都有自己的優(yōu)缺點。目前已有的數(shù)學(xué)軟件可以幫助我們實現(xiàn)上機(jī)計算，基本上已經(jīng)將數(shù)值分析的主要內(nèi)容設(shè)計成簡單的函數(shù)，只要調(diào)用這些函數(shù)進(jìn)行運算便可得到數(shù)值結(jié)果。非線性代數(shù)中許多數(shù)值計算與計算機(jī)結(jié)合，才能得到更很好，更快，更精準(zhǔn)的結(jié)果。為了將計算機(jī)與線性代數(shù)方程組更好的結(jié)合在一起，本文做了比

5、較全面的的解說。本文比較全面的介紹了現(xiàn)代計算機(jī)科學(xué)與工程計算中常見的數(shù)值計算方法，對這些數(shù)值計算方法的基本理論與實際計算機(jī)實踐應(yīng)用進(jìn)行了詳細(xì)的分析，同時還簡要的分析了這些數(shù)值算法的計算效果，穩(wěn)定性，收斂效果，適用范圍以及優(yōu)劣性與特點。本文著重于化抽象為具體，引用一個具體的非線性方程用發(fā)散性的思維對其進(jìn)行徹底的分析，主要有： 引入一個非線性方程，分別運用三種思想進(jìn)行分析，得到三種解法的根本思想； 把數(shù)學(xué)方法與數(shù)學(xué)思想提出來，并進(jìn)行簡潔易懂的理論證明，既突出了線性代數(shù)的理論和基本思想，又可以幫助讀者對該數(shù)學(xué)方法的理解； 給出各種算法的循環(huán)思想以及流程圖，展現(xiàn)出一個清新的框架在讀者面前； 基于 c

6、語言的基礎(chǔ)上，寫出可執(zhí)行的代碼。 對各種算法得到的結(jié)果進(jìn)行比較分析。 第二章第二章 求解非線性方程的三種常見算法求解非線性方程的三種常見算法2.1 二分法二分法單變量函數(shù)方程： f（x）=0其中，f(x)在閉區(qū)間a，b上連續(xù)、單調(diào)，且 f(a)*f(b)0,則有函數(shù)的介值定理可知，方程 f（x）=0 在（a，b）區(qū)間內(nèi)有且只有一個解，二分法是通過函數(shù)在*x區(qū)間端點的符號來確定所在區(qū)域，將有根區(qū)間縮小到充分小，從而可以求出*x滿足給定精度的根的近似值。*x下面研究二分法的幾何意義： 設(shè)=1, =b, 區(qū)間，中點= 及，若=0，則，1a1b11,ba1x211ba 1xf 1xf*x若 f()*f

7、()0，令=，=，則根 ,中，這樣就得到長度縮1a1x2a1a2b1x*x2a2b小一半的有根區(qū)間,，若 f()*f()0，令=，=，則根 ,2a2b1b1x2a1x2b1b*x2a中，這樣就得到長度縮小一半的有根區(qū)間,即 f()f()0,此時-2b2a2b2a2b2b=,對有根區(qū)間,重復(fù)上述步驟，即分半求中點，判斷中電處符號，2a211ab 2a2b則可得長度有縮小一半的有根區(qū)間,2a2b 如圖所示： 重復(fù)上述過程，第 n 步就得到根的近似序列及包含的區(qū)間套，如*x nx*x下：（1）.,.,2211nnbababa（2）, 0)()(*nnnnbaxbfaf（3）-=nanb)(1121n

8、nba12nab(4) 且|-| (n=1,2,3.),2nnnbax*xnx12nab顯然 lim，且以等比數(shù)列的收斂速度收斂于，因此用二分法求nxnx*xf（x）=0 的實根可以達(dá)到任意指定精度。*x2.2 牛頓迭代法牛頓迭代法設(shè)方程 f(x)=0 在其根的某個領(lǐng)域 U(，)內(nèi)有一階連續(xù)導(dǎo)數(shù)，且 f() *x*x*x0。求 f(x)=0 的根，首先要將 f(x)=0 轉(zhuǎn)化為等價形式，并使 (x)滿*x( )xx足不動點迭代的一般理論。 于是我們令 (x)=x+h(x)f(x),可由 ()=0 來確定 h(x)的結(jié)構(gòu)，根據(jù)1x(x)=1+h()f()+h()f(x1)=1+h()f()=0

9、可得*x*x*x*x*xh()=-1/f() ，由于 f(x) 0，且 f(x) 連續(xù)，因此當(dāng) h(x)=-1/f(x) 時， h(x1)*x*x=0，即令 (x)=x-f(x)/f(x)， 從而有迭代格式 = （k=0,1,2，.）1kx)( )(kkkxfxfx 由于, , .都在 U 領(lǐng)域里，從而當(dāng) B 比較小時，可用 f()可近似代替1x2x3x0 xf(),= - ，此方法稱為牛頓迭代法kx1kxkx)()(0 xfxfk下面研究牛頓法的幾何意義：設(shè) r 是方程 f（x）=0 的根，選取作為的 r 初始近似值，經(jīng)過(,f()做曲線0 x0 x0 xy=f(x)的切線的方程：y=f()

10、+f()(x- )，求出 L 與 x 的交點的橫坐標(biāo)= 0 x0 x0 x1x-f()/f(),稱為 r 的一次近似值經(jīng)過點（,f()）做切線 y=f(x)的切線，0 x0 x0 x1x1x1x并求出該切線與 x 軸的交點橫坐標(biāo)：= -f()/f(),稱為 r 的二次近似值，2x1x1x1x2x重復(fù)以上操作可以得到 r 的近似值序列。下述三個定理分別討論了牛頓法的收斂性質(zhì)：定理定理 1：對于方程 f(x)=0，設(shè) f（x）在a，b上有二階連續(xù)導(dǎo)數(shù)且滿足下述條件：（1）f(a)f(b)0，0 x0 x)(0 xf 則由牛頓法產(chǎn)生的迭代序列收斂于 f(x)=0 的根，且 nx*x)(2)()(*2

11、*1limxfxfxxxxkkk 定理定理 2：對于方程 f(x)=0，設(shè) f（x）在a，b上有二階連續(xù)導(dǎo)數(shù)且滿足下述條件：（1）f(a)f(b)0;（2）對任意的 xa,b， f(x) 0, 0)(xf （3）b-a, *x*x)(xf 0,當(dāng)【-,+】時，由牛頓迭代法 = （k=0,1,2，.）式產(chǎn)0 x*x*x1kx)( )(kkkxfxfx 生的序列是以不低于二階的收斂速度收斂到. nx*x2.3 割弦法割弦法 設(shè),為方程 f(x)=0 的兩個近似根。用差商得：f()-f()/ - ，kx1kxkx1kxkx1kx代替牛頓迭代公式中的導(dǎo)數(shù) f()， 于是得到如下的迭代公式： kx=-。

12、下面研究割弦法的幾何意義：1kxkx)()()()(11kkkkkxxxfxfxf經(jīng)過點（,f()）及點（,f()）兩點作割線，其點斜式方程為：kxkx1kx1kx Y=f（）- ，其零點為 X=- kx)()()(11kkkkkxxxxxfxfkx把 X 用表示即得到迭代格式，它又稱為雙點弦割)()()()(11kkkkkxxxfxfxf1kx法，需要兩個初值此割線與 X 軸交點的橫坐標(biāo)就是新的近似值 ，所以弦截法又稱為割線1kx法，如圖所示。 下面三個定理為弦割法收斂定理：定理定理 1：設(shè) f（x）在其零點的鄰域 U（，）= -， + ( 0)*x*x*x*x內(nèi)有二階連續(xù)導(dǎo)數(shù)，則當(dāng)U（，）

13、時，由割弦法式產(chǎn)生的0)(* xf0 x*x序列收斂于，且收斂的階為 1.618。 nx*x定理定理 2：設(shè)在區(qū)間a,b 上連續(xù)，且滿足下述三點)(xf （1）f(a)f(b)0)內(nèi)有二階連續(xù)導(dǎo)*x*x*x*x數(shù)，f(x) 0 則當(dāng) U(,)時，由弦割=-0 x*x1kxkx)()()()(11kkkkkxxxfxfxf式產(chǎn)生的序列收斂于，且收斂的階為 1.618。 nx*x第三章第三章 求解非線性方程的三種算法比較求解非線性方程的三種算法比較本章主要通過具體實例比較了第二章中三種算法的優(yōu)缺點，并得到相應(yīng)結(jié)論，求解非線性方程 x*x*x+4*x*x-10=0 在1,2上，x0=1.5 附近的解

14、精確到0.000 000 001。3.1 二分法求解方法二分法求解方法二分法是求方程近似根的方法中行之有效的最簡單的方法，它的遞推過程簡單，便于計算機(jī)上實現(xiàn)，實現(xiàn)二分法的基本步驟如下。(1) 輸入有根區(qū)間的端點 a,b 及預(yù)先給定的精度 exp ；(2) 計算 x=(a+b)/2 ；(3) 若 f(a)*f(x)0,則 b=x；否則 a=x ；(4) 若 |b-a|exp，則輸出方程滿足精度要求的根 x，則計算結(jié)束；否則轉(zhuǎn)(2)。 二分法算法流程圖：二分法算法流程圖： c 語言代碼：#include stdio.h#include math.hfloat function(float x)fl

15、oat f;f=(float) x*x*x+4*x*x-10；return f;void main()float , ,f,f,f;1x2x0 x1x2x0 x=10;x2=-10;1xf()=function();1x1xf()=function();2x2xdo=(+)/2; /*計算中點*/0 x1x2xf()=function(); /*計算中點處的函數(shù)值*/0 x0 xif(f()*f()=1e-6);0 xprintf(The root is %f,);0 x 運行結(jié)果： n有根區(qū)間a,bf()的符號nxnx11.0,2.01.5+21.0,1.51.25_31.25,1.51.3

16、75+41.25,1.3751.3125_51.3125,1.3751.343 75_61.3475,1.3751.359 375_71.359375,1.375 1.367 185+The root is 1.365230 3.2 牛頓迭代法求解牛頓迭代法求解步驟： (1) 給出初始近似根 及精度 exp ；0 x (2) 計算=-f()/f() ；1x0 x0 x0 x (3) 若 |-|=1e-6);0 xprintf(The root is %f,);0 x 運行結(jié)果：The root is 1.3652313.3 割弦法求解割弦法求解步驟:(1) 選擇迭代初值 , 及精度 esp ；

17、0 x1x(2) 計算 =-（f() *(-)/ f()-f()）；2x1x1x1x0 x1x0 x(3) 若|-|0，轉(zhuǎn)向(4)；否則 =,= ，轉(zhuǎn)向(2)；2x1x0 x1x1x2x(4) 輸出滿足精度的根 ，結(jié)束2x算法流程圖：c 語言代碼：#include #include #define eps 0.00001 /* 容許誤差 */#define N 100 /* 最大迭代次數(shù) N */float f(float x) /* 定義函數(shù) f(x) */ float y; y= x*x*x+4*x*x-10; return(y);void main() float ,x1, ;0 x2x

18、 int i; printf(input ,=);0 x1x scanf(%f,%f,&,&);0 x1x for(i=1;i=N;i+) =-(f()*(-)/(f()-f(); /* 弦截法迭代公式 */2x1x1x1x0 x1x0 x if(fabs(-)eps | fabs(f()eps) /*滿足精度要求輸出近似根并退出*/2x1x2x printf(nRoot of equation is:%8.6fn,);2x return; =; /* 準(zhǔn)備下一次迭代的初值 */0 x1x =;1x2x printf(nAfter %d repeat, no solved.n,

19、N); /* 輸出無解信息 */ 運行結(jié)果：Kf()kxkx01.0-5.012.014.021.263 157 895 -1.602274 38431.338 827 839-0.430 364 74441.366 616 395 -0.022 909 42751.365 211 903-2.990 671*pow(10,-4)61.365 200 01-2.0416*pow(10,-7)71.365 230 0130.081.365 230 0130.0 Root of equation is: 1.365230小結(jié)： 二分法的優(yōu)點是計算簡單，方法可靠，誤差容易估計，只要求連續(xù)，且總是收斂的，因此對函數(shù)的性質(zhì)要求較低。它的缺點是不能求偶數(shù)重根，也不能求復(fù)根，且收斂較慢。故一般不單獨將其用于求根，只用其為根求得一個較好的近似值。 牛頓迭代法是多項式求根的一種效率很高的算法，收斂速度快（對單根） 。算法簡單是迭代法中較好者，但是它有兩個缺點：第一每次只能求出一個 根，求其它根時若采用降次處理又會產(chǎn)生精度降低的問題。第二有時會遇到由于初