非線性方程求解算法的程序設(shè)計(jì)及比對(duì) 課程設(shè)計(jì) 畢業(yè)設(shè)計(jì)

1、題 目：非線性方程求解算法的程序設(shè)計(jì)及比對(duì)摘要由于五次及其以上代數(shù)方程式大多不能用代數(shù)公式求解非線性方程的解.或者求解非常復(fù)雜。而在工程和科學(xué)技術(shù)中許多問(wèn)題常常歸結(jié)為求解非線性方程式問(wèn)題.所以需要研究非線性方程的數(shù)值解法的問(wèn)題是非常重要.來(lái)適應(yīng)我們社會(huì)的需要.本課題主要介紹非線性方程的數(shù)值解法是直接從方程出發(fā)，逐步縮小根的存在區(qū)間，或逐步將根的近似值精確化，直到滿足問(wèn)題對(duì)精度的要求，主要的方法有二分法，迭代法，牛頓法，弦截法等。并寫出這幾種非線性方程的數(shù)值解法的算法和程序及其優(yōu)缺點(diǎn)和計(jì)算條件.關(guān)鍵詞二分法;牛頓迭代法;弦截法法;程序框架圖;C語(yǔ)言編程目錄引言1第一章 非線性方程求解算法21.1

2、 二分法21.1.1 二分法的簡(jiǎn)介21.1.2 二分法的原理21.1.3 二分法的算法31.2 不動(dòng)點(diǎn)迭代法41.2.1不動(dòng)點(diǎn)迭代法的簡(jiǎn)介41.2.2不動(dòng)點(diǎn)迭代法的幾何意義41.2.3不動(dòng)點(diǎn)迭代法的算法51.3 牛頓迭代法61.3.1牛頓迭代法的簡(jiǎn)介61.3.2牛頓迭代法的原理61.3.3牛頓迭代法的算法71.4 弦截法81.4.1弦截法的簡(jiǎn)介81.4.2弦截法的原理81.4.3弦截法的算法9第二章 非線性方程求解的C語(yǔ)言算法對(duì)比112.1 C語(yǔ)言求解非線性方程的根11構(gòu)造非線性方程迭代公式11計(jì)算迭代公式112.2 C語(yǔ)言算法比較分析14參考文獻(xiàn)16附錄A17附錄B18引言代數(shù)方程求根問(wèn)題是

3、一個(gè)古老的數(shù)學(xué)問(wèn)題,早在16世紀(jì)就得到了三次、四次方程的求根公式.一般(五次及其以上)代數(shù)方程式不能用代數(shù)公式求解.在工程和科學(xué)技術(shù)中許多問(wèn)題常常歸結(jié)為求解非線性方程式問(wèn)題.因此,需要研究用數(shù)值方法求得滿足一定精度的代數(shù)方程式的近似解.根的數(shù)值方法,其中是連續(xù)的稱為非線性方程,此類方程除少數(shù)情形外,只能求近似解.例如,其根為 像這種方程是可以直接的方法求出解析解.但對(duì)于對(duì)于多項(xiàng)式方程當(dāng)時(shí),就不能得到解析解.對(duì)于更一般的情況（如超越方程）就更難求得解析解了,更就不存在根的解析表達(dá)式,在科學(xué)研究和科學(xué)計(jì)算中常常碰到非線性方程求解問(wèn)題.非線性方程的解一般不能解析求出.所以數(shù)值解法顯得非常重要,而數(shù)值

4、解法在實(shí)際中的實(shí)現(xiàn)則更為重要.本課題主要是應(yīng)用數(shù)值解法結(jié)合計(jì)算機(jī)語(yǔ)言來(lái)求解非線性方程的解,其中包括的數(shù)值解法有二分法、迭代法、牛頓法、弦截法等.主要用的計(jì)算機(jī)語(yǔ)言C語(yǔ)言、等.正好符合用計(jì)算機(jī)語(yǔ)言來(lái)處理復(fù)雜計(jì)算量的數(shù)學(xué)問(wèn)題,以此來(lái)分析幾種非線性數(shù)值解法的優(yōu)缺點(diǎn),計(jì)算量的大小.來(lái)選出更加適合的計(jì)算方法.第一章非線性方程求解的算法1.1二分法二分法的簡(jiǎn)介二分法又稱二分區(qū)間法,是求解方程的近似根的一種常用的簡(jiǎn)單方法.設(shè)函數(shù)在閉區(qū)間上連續(xù),且,根據(jù)連續(xù)函數(shù)的性質(zhì)可知,在內(nèi)必有實(shí)根,稱區(qū)間為有根區(qū)間.為明確起見(jiàn),假定方程在區(qū)間內(nèi)有惟一實(shí)根.二分法的基本思想是: 首先確定有根區(qū)間,將區(qū)間二等分, 通過(guò)判斷的

5、符號(hào), 逐步將有根區(qū)間縮小, 直至有根區(qū)間足夠地小, 便可求出滿足精度要求的近似根.二分法的原理設(shè)方程在區(qū)間內(nèi)有根,二分法就是逐步收縮有根區(qū)間,最后得出圖 1.1二分法原理圖所求的根,如上圖所示,我們可以寫出一下內(nèi)容.(1) 輸入有根區(qū)間的端點(diǎn)及預(yù)先給定的精度；(2) 計(jì)算 ；(3) 若,則;否則；(4) 若,則輸出方程滿足精度要求的根,計(jì)算結(jié)束；否則轉(zhuǎn)(2).繼續(xù)執(zhí)行前面的步驟.開(kāi) 始開(kāi) 始輸 入a,b,(a+b)/2xxb|b-a|eps);Step 7 Output the solution of equation: ; STOP.1.2 不動(dòng)點(diǎn)迭代法1.2.1不動(dòng)點(diǎn)迭代法的簡(jiǎn)介 迭代法

6、的基本思想是逐次逼近,即首先給出方程的根的一個(gè)近似初始值,然后反復(fù)使用迭代公式校正這個(gè)初始值,逐步精確化,直到滿足預(yù)先給出的精度要求為止. 首先設(shè)法把方程化為下列等價(jià)形式(稱為迭代函數(shù)) (1-1)然后按式(1-1)構(gòu)造迭代公式 (1-2) 在有根區(qū)間上取一點(diǎn)作為方程根的初始近似根,代入式（1-2)右端,求得,再把作為預(yù)測(cè)值,進(jìn)一步得到,如此反復(fù)進(jìn)行下去,得到一個(gè)近似根的序列如果迭代序列收斂于,則當(dāng)連續(xù)時(shí),便是方程的根. 對(duì)預(yù)先給定的精度要求,只要某個(gè)是滿足,即可結(jié)束計(jì)算并取. 不動(dòng)點(diǎn)迭代法的幾何意義用迭代法求方程在區(qū)間內(nèi)的實(shí)根.可以寫出一下下幾種迭代格式,用Mathematica 畫出它們的

7、圖形,以此來(lái)觀察它們的幾何意義. y x -2-112-2-11圖 1.3迭代幾何圖 -112-112圖 1.4 迭代幾何圖-2-11x-2246y圖 1.5迭代幾何圖 不動(dòng)點(diǎn)迭代法的算法由不動(dòng)點(diǎn)迭代法程序框架圖（見(jiàn)附錄A）寫出一下迭代算法給定初始近似值,求的解.輸入:初始近似值; 容許誤差TOL; 最大迭代次數(shù)Nmax.輸出: 近似解或失敗信息.Step 1 Set k = 1;Step 2 While ( kNmax) ; do steps 3-6Step 3 Set; /* 計(jì)算x */Step 4 If TOL then Output (x); /*成功*/STOP;Step 5 Se

8、t k+;Step 6 Set ; /* 更新 */Step 7 Output (The method failed after Nmax iterations); /*不成功 */STOP.1.3牛頓迭代法牛頓迭代法的簡(jiǎn)介簡(jiǎn)單的迭代法是用直接的方法從原方程中隱含地解出,從而確定出.而牛頓迭代法是用一種間接而特殊的方法來(lái)確定.牛頓迭代法的基本思想是,將非線性方程的求根問(wèn)題歸結(jié)為計(jì)算一系列線性方程的根.設(shè)是方程的一個(gè)近似根,將在附近作一階泰勒展開(kāi),則有,于是方程可近似表示成.這是一個(gè)線性方程式,設(shè),則上式的解為 , 取作為原方程的新的近似根,即令則稱上式為牛頓迭代公式. 牛頓迭代法的原理 y y

9、=f(x)PkPk+1Pk+2x* xk+2 xk+1 xk x圖 1.6牛頓迭代法程幾何意義圖從圖 1.6可以看出,方程的根是曲線與軸交點(diǎn)的橫坐標(biāo),設(shè)是根的某個(gè)近似值,由此來(lái)求出過(guò)曲線（圖 1.7）的橫坐標(biāo)為的點(diǎn)引切線交軸于, 并將其作為新的近似值,重復(fù)上述過(guò)程,我們可以得到可見(jiàn)一次次用切線方程來(lái)求解方程的根,所以亦稱為牛頓切線法.開(kāi) 始輸 入x0,N1k Nk+1 kx1 x0YynykN?n輸出輸出奇異標(biāo)志結(jié) 束輸出迭代失敗標(biāo)志圖 1.7牛頓迭代法程序框架圖1.3.3牛頓迭代法的算法從圖 1.7流程圖,寫出一下牛頓算法,并且用c語(yǔ)言編寫運(yùn)算程序.用Newton法求方程一個(gè)解.輸入 初始值

10、；誤差容限TOL；最大迭代次數(shù).輸出 近似解或失敗信息.Setp 1.Setp 2 對(duì) 做Setp 3-4 .Setp 3.Setp 4 若,則輸出,停機(jī),否則.Setp 5 輸出(Method failed);停機(jī)在第4步中的迭代終止準(zhǔn)則可用1.4 弦截法 弦截法的簡(jiǎn)介弦截法也稱為割線法.如果函數(shù)求導(dǎo)困難,則割線較切線更為實(shí)用.牛頓迭代法雖然具有收斂速度快的優(yōu)點(diǎn),但每迭代一次都要計(jì)算導(dǎo)數(shù),比較復(fù)雜時(shí),不僅每次計(jì)算帶來(lái)很多不便,而且還可能十分麻煩,如果用不計(jì)算導(dǎo)數(shù)的迭代方法,往往只有線性收斂的速度.弦截法便是一種不必進(jìn)行導(dǎo)數(shù)運(yùn)算的求根方法.弦截法在迭代過(guò)程中不僅用到前一步處的函數(shù)值,而且還使用

11、處的函數(shù)值來(lái)構(gòu)造迭代函數(shù),這樣能提高迭代的收斂速度.為避免計(jì)算函數(shù)的導(dǎo)數(shù),使用差商替代牛頓公式中的導(dǎo)數(shù),便得到迭代公式稱為弦截迭代公式,相應(yīng)的迭代法稱為弦截法. 弦截法的原理弦截法的幾何意義（如圖1.8）曲線上兩點(diǎn),的割線來(lái)代替曲線,然后用此割線與x軸交點(diǎn)的橫座標(biāo)作為方程的近似根再過(guò)P1點(diǎn)和作割線求出,再過(guò)P2點(diǎn)和點(diǎn)作割線求出,余此類推,當(dāng)收斂時(shí)可求出滿足精度要求的.P1y=f(x)x0 x2 x3 x1x*P3 P0 P2圖 1.8弦截法幾何意義圖開(kāi)始輸 入x0, x1,N1k yx0 x2nynx1 x2yk+1 kx1 x0x2 x1f(x1)f(x0)f(x2) f(x1)nykN?n

12、yn輸出x2輸出x2輸出奇異標(biāo)志結(jié) 束輸出迭代失敗標(biāo)志圖 1.9弦截法程序框架圖 弦截法的算法由圖 1.9弦截法的程序框架圖,寫出如下算法：用弦截法求方程的一個(gè)解.輸入 初始值,誤差容限TOL;最大迭代次數(shù)m.輸出 近似解,或失敗信息.Setp 1 ; ; ; ;Setp 2 對(duì)做Setp3,4.Setp 3 .Setp 4 若,則輸出,停機(jī).否則; ; ;Setp 5 輸出（”Method failed”）; 停機(jī).第二章 非線性方程求解的C語(yǔ)言算法對(duì)比2.1 C語(yǔ)言求解非線性方程的根2.1.1 構(gòu)造非線性方程迭代公式根據(jù)上一章的理論知識(shí),本章進(jìn)行數(shù)據(jù)計(jì)算,首先構(gòu)造幾種非線性方法解法的迭代公

13、式,舉下面的非線性方程為例,寫出幾種算法的迭代格式.并以此來(lái)計(jì)算它們各自的結(jié)果,來(lái)為下一小節(jié)的算法比較作為例證,所以本節(jié)的計(jì)算算法的正確與否決定下一節(jié)結(jié)論的正確與否.所以我們首先用數(shù)學(xué)軟件Mathematica 5來(lái)求取方程（2-1）在的根,用來(lái)比較我們算法正確與否.用Mathematica 5求解方程的根,得到四個(gè)根,取的根例2.1 方程在中的根 二分法： （2-1）不動(dòng)點(diǎn)迭代法： （2-2）牛頓迭代法：（2-3）弦截法： （2-4）2.1.2 計(jì)算迭代公式下面用二分法的程序來(lái)（程序詳見(jiàn)附錄B的二分法程序）計(jì)算（2-1）式的在的根,誤差度在,初始值計(jì)算把結(jié)果寫在表 2-1表 2-1 二分法的

14、計(jì)算結(jié)果備注11.0000001.5000001.5000000.5000005.0625001.2.3.初始值21.0000001.2500001.2500000.2500001.31640631.0000001.1250001.1250000.1250000.00805741.0625001.1250001.0625000.062500-0.53025851.0937501.1250001.0937500.031250-0.27006461.1093751.1250001.1093750.015625-0.13329571.1093751.1250001.1171880.007813-0.

15、06319881.1210941.1250001.1210940.003906-0.02771691.1230471.1250001.1230470.001953-0.009866101.1240231.1250001.1240230.000977-0.000914111.1240231.1245121.1245120.0004880.003569121.1240231.1245121.1242680.0002440.001327131.1240231.1241461.1241460.0001220.000206141.1240841.1241461.1240840.000061-0.0003

16、54最后的結(jié)果 ：=1.124115,由表 2-1二分法的最后結(jié)果與比較,我們可以看出與Mathematica 5求得結(jié)果在誤差范圍之內(nèi)幾乎一致,所以此算法是正確的,是可以應(yīng)用到下一小節(jié),進(jìn)行算法比較.下面用不動(dòng)點(diǎn)迭代法的C語(yǔ)言的程序來(lái)（程序詳見(jiàn)附錄B不動(dòng)點(diǎn)迭代法C語(yǔ)言程序）計(jì)算（2-2）式的在的根,誤差度在,初始迭代值為,計(jì)算把結(jié)果寫在表 2-2.計(jì)算完成后與進(jìn)行比較,來(lái)得出算法的正確與否.表 2-2不動(dòng)點(diǎn)迭代的計(jì)算結(jié)果備注11.2039480.7960521.2.3. 初始值21.1319080.07203931.1248870.00702141.1241980.00068951.1241

17、300.000068最后結(jié)果:=1.124130, k=5由表 2-2不動(dòng)點(diǎn)迭代法的最后結(jié)果與比較,我們可以看出與Mathematica 5求得結(jié)果在誤差范圍之內(nèi)幾乎一致,所以此算法是正確的,是可以應(yīng)用到下一小節(jié),進(jìn)行算法比較.下面用牛頓迭代法的C語(yǔ)言的程序來(lái)（程序詳見(jiàn)附錄B牛頓迭代法C語(yǔ)言程序）計(jì)算（2-3）式的在的根,誤差度在,初始迭代值為,計(jì)算把結(jié)果寫在表 2-3.計(jì)算完成后與進(jìn)行比較,來(lái)得出算法德正確與否.表 2-3牛頓迭代的計(jì)算結(jié)果備注11.51282119.00000039.0000000.4871791.2.3. 初始值21.2322855.30224018.9004030.28

18、053631.1349771.11068611.4141620.09730841.1242440.1007579.3880930.01073251.1241230.0011159.1808240.00012161.1241230.0000009.1784960.000000最后結(jié)果:=1.124123 , k=6由表 2-3牛頓迭代法的最后結(jié)果與比較,我們可以看出與Mathematica 5求得結(jié)果在誤差范圍之內(nèi)幾乎一致,所以此算法是正確的,是可以應(yīng)用到下一小節(jié),進(jìn)行算法比較.下面用弦截法的C語(yǔ)言的程序來(lái)（程序詳見(jiàn)附錄B弦截法C語(yǔ)言程序）計(jì)算（2-4）式的在的根,誤差度在,初始迭代值為,計(jì)算把

19、結(jié)果寫在表 2-4.計(jì)算完成后與進(jìn)行比較,來(lái)得出算法的正確與否.表 2-4弦截法的計(jì)算結(jié)果備注11.0500000.9500001.2.3.初始值,21.0804650.03046531.1277450.04728041.1239540.00379151.1241220.000168最后結(jié)果:=1.124122, k=5由表 2-4弦截法迭代法的最后結(jié)果與比較,我們可以看出與Mathematica 5求得結(jié)果在誤差范圍之內(nèi)幾乎一致,所以此算法是正確的,是可以應(yīng)用到下一小節(jié),進(jìn)行算法比較.2.2 C語(yǔ)言算法比較分析通過(guò)上一小節(jié)的計(jì)算,本節(jié)來(lái)分析分析幾種算法的優(yōu)缺點(diǎn),以便以后更好的應(yīng)用到學(xué)習(xí)和工作

20、中,做到學(xué)以致用,也是這次課題的主旨,活學(xué)活用.觀察表2-5的計(jì)算結(jié)果,可以直觀的看出來(lái),牛頓法,弦截法,不動(dòng)點(diǎn)迭代法的收斂速率差不多,但二分法明顯落后前三種收斂速率,所以得到一下結(jié)論.1.二分法是電子計(jì)算機(jī)上一種常用的算法,它的具有簡(jiǎn)單和易操作的優(yōu)點(diǎn),缺點(diǎn)是收斂較慢,且不能求重根.2.牛頓迭代法牛頓法優(yōu)點(diǎn)：牛頓迭代法具有至少平方收斂的速度,所以在迭代過(guò)程中只要迭代幾次就會(huì)得到很精確的解.這是牛頓迭代法比簡(jiǎn)單迭代法優(yōu)越的地方.特別是當(dāng)?shù)c(diǎn)充分靠近精確解時(shí).牛頓法的缺點(diǎn)：選定的初值要接近方程的解,否則有可能得不到收斂的結(jié)果.再者,牛頓迭代法計(jì)算量比較大.每次迭代要計(jì)算一次導(dǎo)數(shù)值,當(dāng)表達(dá)式復(fù)雜或

21、無(wú)明顯表達(dá)式時(shí)求解困難.對(duì)重根收斂速度較慢（線性收斂）.牛頓法是現(xiàn)在最常用的迭代方法.3.弦截法的收斂階雖然低于Newton法,但是迭代一次只要計(jì)算一次,不需要計(jì)算導(dǎo)數(shù)值,所以效率高,實(shí)際問(wèn)題中經(jīng)常使用. 弦截法比牛頓迭代法收斂速度稍慢,但它的計(jì)算量比牛頓迭代法小,特別當(dāng)都函數(shù)的導(dǎo)數(shù)的計(jì)算比較復(fù)雜時(shí),弦截法更顯示了它的優(yōu)越性.表 2-5 迭代結(jié)果迭代次數(shù)二分法不動(dòng)點(diǎn)迭代法牛頓法弦截法k1.5000001.2039481.5128211.05000011.2500001.1319081.2322851.08046521.1250001.1248871.1349771.12774531.06250

22、01.1241981.1242441.12395441.0937501.1241301.1241231.12412251.1093751.12412361.11718871.12109481.12304791.124023101.124512111.124268121.124146131.124146141.124115二分法是逐步將含根區(qū)間分半,主要用來(lái)求實(shí)根;迭代法是一種逐次逼近的方法,起著把根的精確值一步一步算出來(lái)的作用;牛頓法具有較快的收斂速度,但對(duì)初值選取要求較高.弦截法避開(kāi)了導(dǎo)數(shù)的計(jì)算,具有超線性的收斂速度,每計(jì)算一步,要用到前面兩步的信息.參考文獻(xiàn)1林成森.數(shù)值計(jì)算方法.北京:科

23、學(xué)出版社.2005年2金聰.熊盛武.數(shù)值分析.武漢:武漢理工大學(xué)出版社.2003年3顏暉 .C語(yǔ)言程序設(shè)計(jì).北京:高等教育出版社.2008年4張立科.MATLAB 7.0 應(yīng)用.北京：人民郵電出版社.2006年5賈得彬.數(shù)值計(jì)算方法.北京：水利水電出版社.2007年6李慶揚(yáng),王能超,易大義.數(shù)值分析基礎(chǔ).北京：清華大學(xué)出版,2008年.7徐士良.數(shù)值方法與計(jì)算機(jī)實(shí)現(xiàn).北京：清華大學(xué)出版社.2006年.附錄A本附錄包含不動(dòng)點(diǎn)迭代的流程圖.開(kāi) 始輸 入x0,N1kk+1kx1 x0y|x1- x0|?ynkN?n輸出近似根x1輸出迭代失敗標(biāo)志結(jié) 束附錄 B本附錄含二分法,不動(dòng)點(diǎn)迭代,牛頓法,弦截法

24、的的C語(yǔ)言計(jì)算程序.二分法C語(yǔ)言程序#include #define eps 0.0001 /* 容許誤差 */double jisuan(double x) return pow(x,4)+2*x*x-x-3 ;main() double a,b,y,x,h,j;int k=0;printf(a=);scanf(%lf,&a);printf(b=);scanf(%lf,&b);if(jisuan(a)*jisuan(b)=0) /* 判斷是否符合二分法使用的條件 */ printf(Not bisect of bisect); return; do x=(a+b)/2;k+;j=jisuan

25、(x);/* f(x)的結(jié)果 */if(jisuan(a)*jisuan(x)0) /* 如果f(a)*f(x)eps);/*判斷是否達(dá)到精度要求,若沒(méi)有達(dá)到,繼續(xù)循環(huán)*/x=(a+b)/2; /* 取最后的小區(qū)間中點(diǎn)作為根的近似值 */printf(n The zui hou root is x=%lf, k=%dn,x,k);不動(dòng)點(diǎn)迭代法C語(yǔ)言程序#include #define eps 0.0001 /* 容許誤差 */double jisuan(double x) double h ;h=sqrt(sqrt(x+4)-1);return h ;main() double x0,x1,h

26、; int k=0; printf(input 迭代初值 x1: ); scanf(%lf,&x1);do x0=x1; x1=jisuan(x0); k+; h=fabs(x1-x0); printf(n k=%2d , x1=%lf ,h=%lf ,k ,x1,h);while(fabs(x1-x0)eps);/*判斷是否達(dá)到精度要求,若沒(méi)有達(dá)到,繼續(xù)循環(huán)*/printf(n最后結(jié)果The root is n); printf(x=%lf, k=%dn,x1,k);牛頓迭代法C語(yǔ)言程序#include#includedouble js1(double x) double j;j=pow(x,4)+2*pow(x,2)-x-3;return j; double js2(double c) double j; j=4*pow(c,3)+4*c-1;