非線性方程求根的數(shù)值方法04數(shù)本林一明1

1、非線性方程求根的數(shù)值方法林一明（廣西民族大學(xué)數(shù)計學(xué)院04數(shù)本1班, 南寧 530006）摘 要: 本文討論非線性方程的數(shù)值解，闡述了二分法、三分法、冒泡法、簡單迭代法和牛頓迭代法原理。并對非線性方程的數(shù)值例子進行了近似計算，并比較了它們的收斂速度。關(guān)鍵詞: 非線性方程；二分法；迭代法；收斂性Numerical Method of the Root for Solving Nonlinear EquationLin Yiming(College of Mathematics and Computer Science,Guangxi University for Nationalities, Na

2、nning 530006)Abstract: In this paper, we study numerical solution of the nonlinear equation, the procedures of dichotomy, rule of thirds, bubble method, the simple iterate method and the Newton iterate method are expounded, And has carried on the approximate calculation to the nonlinear equation, an

3、d compare their convergence rate.Keywords: nonlinear equation；dichotomy；iteration method；convergence0 引 言代數(shù)方程求根問題是個古老的數(shù)學(xué)問題，在19世紀，理論上就證明了n5次一般代數(shù)方程不能用代數(shù)公式求解，超越方程和工程及科學(xué)技術(shù)中的許多問題都難以求得精確解，這些方程都歸類為非線性方程。因此，需要研究用數(shù)值方法求得滿足一定代數(shù)精度的非線性方程的近似解。當(dāng)給定非線性方程范圍內(nèi)的某個根，而根的粗略位置已從問題的物理背景或應(yīng)用其它方法獲知，要求取非線性方程精度范圍內(nèi)的根。本文著重討論非線性方程的數(shù)

4、值解法，給出二分法、三分法、冒泡法、簡單迭代法和牛頓迭代法的基本原理，并對非線性方程的數(shù)值例子進行了近似計算。1 二分法每次把的零點所在小區(qū)間收縮一半，使區(qū)間的兩個端點逐步迫近函數(shù)的零點，以求得零點的近似值，這種方法叫做二分法3。設(shè)在上連續(xù)，假定，取中點，檢查的符號，若，則就是方程的一個根；若，記為，為，則得有根區(qū)間；若，記為，為，則得有根區(qū)間，它的長度為區(qū)間的一半。對區(qū)間，令，再用同樣的方法，可得新的有根區(qū)間，如此反復(fù)進行下去，其中每一個區(qū)間長度都是前一區(qū)間長度的一半，有這就是方程的根，而即為方程的近似根，且有估計誤差其方法的matlab程序(見附錄1)。二分法具有計算簡單，易于程序?qū)崿F(xiàn)的優(yōu)

5、點。2 三分法三分法是二分法的推廣，只是比二分法復(fù)雜一些，但求解速度比二分法快。設(shè)在上連續(xù)，假定，并且對有，取， ，檢查,的符號，若,就是方程的一個根，或者,就是方程的一個根。若，記為，為，則得到方程的有根區(qū)間；若,記為，為，則得到方程的有根區(qū)間；若，記為，為，則得到方程的有根區(qū)間；新區(qū)間的長度為區(qū)間的。如此反復(fù)進行下去，其中每一個區(qū)間是前一個區(qū)間長度的，且有而為方程一個實根的近似值，且它滿足關(guān)系式: ，這表明方程近似根的絕對誤差小于最初區(qū)間長度的分之一，三分法Matlab程序?qū)崿F(xiàn)過程見附錄2.3 冒泡法 三分法和二分法其求出方程的近似解的個數(shù)比較多后才能得到比較精確的解,冒泡法也是二分法的進

6、一步的推廣,求解非線性方程的一種相對簡單、容易編程，而且收斂速度比二分法和三分法要快的一種數(shù)值算法。冒泡法實現(xiàn)的具體過程如下。定理1 設(shè)函數(shù)在閉區(qū)間上存在二階連續(xù)導(dǎo)數(shù)且滿足條件：(1)在區(qū)間上保號,(2),(3),則冒泡法產(chǎn)生的的唯一解.證明 由條件（1），（2）知，函數(shù)f(x)在區(qū)間上為單調(diào)連續(xù)函數(shù)，因此在區(qū)間a,b上至多有一個根，再有條件（3）在內(nèi)至少存在一個根，因此，在區(qū)間內(nèi)存在唯一解.冒泡法的基本思想: 設(shè)函數(shù)在區(qū)間上符合定理1的條件，存在唯一的解x,把區(qū)間分成10等分，x分別取，, ，然后計算的值，用比較法找出絕對值最小的，并確定，若，則為方程的根，若，記，則得有根區(qū)間,方程根的區(qū)間

7、長度為原來的，即，再用同樣的方法，可得到新的根區(qū)間,如此進行下去，其中每一個區(qū)間是前一個區(qū)間的，有，(k 為常數(shù)屬于1至9這10個數(shù)字中的某一個數(shù))，作為方程的一個實根的近似值，且它滿足關(guān)系式 (k 為常數(shù)屬于1至9這10個數(shù)字中的某一個數(shù))上式表明方程近似值的絕對誤差小于最初區(qū)間長度的分之一。Matlab程序的maobao.m函數(shù)見附錄3。4 簡單迭代法迭代法也稱輾轉(zhuǎn)法，是一種不斷用變量的舊值遞推新值的過程,跟迭代法相對應(yīng)的是直接法（或者稱為一次解法），即一次性解決問題。迭代法又分為精確迭代和近似迭代?！岸址ā焙汀芭ｎD迭代法”屬于近似迭代法。簡單迭代法的基本思想: 設(shè)方

8、程有根，把方程化為等價方程因而有.選定s的初始近似值x0，用遞推公式 （k=0,1,2,） （4.1）產(chǎn)生序列，在一定條件下，序列收斂于. 在收斂的情況下，當(dāng)足夠大時就可取作為方程的近似根。迭代公式（1）被稱為求解方程f(x)=0的簡單迭代法，其中稱為迭代函數(shù)。因，故s是迭代函數(shù)的不動點。簡單迭代法（4.1）又稱為不動點迭代法.由迭代過程所產(chǎn)生的數(shù)列并不是都收斂于某一個數(shù),與其迭代方程的擷取有關(guān).定理2 設(shè)函數(shù)，在內(nèi)可導(dǎo)，且滿足兩個條件：（1） 當(dāng)時，（2） 當(dāng)時，其中L為一常數(shù)。則有如下兩個結(jié)論：1.當(dāng)方程在區(qū)間上有唯一的根s;2.對任取的,簡單的迭代法（4.1）產(chǎn)生的序列,且收斂于 s;證

9、明 (1)令,則，并由條件（1）可知若上面兩個不等式中有一個等號成立，則方程（4.1）有根或 ;若兩個都是嚴格不等式，則根據(jù)連續(xù)函數(shù)的介值定理，必存在,使,即方程（4.1）有根,今設(shè)有兩個不同的使，,則由微分中值定理以及條件（2），有其中在與之間，因而，上式出現(xiàn)的矛盾證實.(2) 因，由條件（1）可知，又由條件（2）得其中在與s之間，因而，因，故有.收斂性定義：設(shè)序列收斂于s，并且，如果存在常數(shù)和常數(shù),使得極限成立，或者使得當(dāng)（某個正整數(shù)）時，成立，則稱序列收斂于具有階收斂速度，簡稱是階收斂的。常數(shù)稱為漸近收斂常數(shù)，也稱為收斂因子。顯然，大小反映了序列收斂的快慢程度， 越大收斂越快, =1時，

10、又序列是線性收斂的，此時必有0<c<=1; =2時,又稱序列是平方收斂的;對于的情況,序列統(tǒng)稱是超線性收斂的. 具體的matlab程序?qū)崿F(xiàn)過程見附錄4.5 Newton法牛頓法是牛頓在17世紀提出的一種求解方程，多數(shù)方程不存在求根公式，從而求精確根非常困難，甚至不可能，從而尋找方程的近似根就顯得特別重要。用簡單迭代法求方程(4.1)的根s，十分重要的問題構(gòu)造迭代函數(shù).為了使收斂速度的階高一些,就盡可能使在處有更多階導(dǎo)數(shù)等于零.現(xiàn)在令,為待定函數(shù)，但，則方程(4.1)與方程有共同的根s.現(xiàn)用條件確定. 由知，h(x)必須滿足. 顯然，取就具備這個條件，并且也滿足.于是，被確定為它滿足

11、. 由此得出下面的特殊的簡單迭代法 (5.1)上式所表示的迭代法稱為Newton(牛頓)法.定理34 設(shè)函數(shù)在閉區(qū)間上存在二階連續(xù)導(dǎo)數(shù)且滿足條件：(1) 在區(qū)間上保號,(2) , ,(3) ,(4) 設(shè)且,則牛頓迭代格式(5.1)產(chǎn)生的迭代序列收斂于方程的唯一解.下面對本定理的條件做些說明.(i)由條件（1）,（2）知，函數(shù)在區(qū)間上為單調(diào)連續(xù)函數(shù)，因此在區(qū)間上至多有一個根，再有條件（3）在內(nèi)至少存在一個根，因此，在區(qū)間內(nèi)存在唯一解.對于條件(1)和條件(3)僅可能產(chǎn)生下列四種情形:(1) ;(2)(3) ;(4) ;上述四種情形的幾何圖形如圖所示.(ii)對于第一種情形,由于在區(qū)間上單調(diào)增加,

12、且由條件(4)知,所以,當(dāng)時有，即滿足條件(4)的必要條件是.(iii)證明對任意初值，由迭代公式(5.1)求出的逐次近似值都屬于,且產(chǎn)生的序列單調(diào)增加。事實上，設(shè)表示曲線經(jīng)過點的切線，由于在區(qū)間內(nèi),所以曲線上凸,切線必在曲線的上方，因此，從而有另外，設(shè)，由于是經(jīng)過的切線，且單調(diào)增加，又有綜合上面兩種情形，可得連續(xù)函數(shù)滿足,因此,在區(qū)間內(nèi)存在一點使，即上式表明，由式(5.1)產(chǎn)生的序列單調(diào)增加且有上界，由極限存在的單調(diào)收斂準則知序列的極限存在，不妨設(shè)為，即.再對遞推公式(5.1)兩邊取極限，可得由于，從而得，因此，也是的根，再由第一步知，方程僅有唯一的根，因此.6 數(shù)值算例以下的例子是各種方法

13、對同一方程的數(shù)值求法解的列表.例1. (解的誤差數(shù)度為0.0001)(二分法,三分法,冒泡法取區(qū)間2,5,簡單迭代法和牛頓法的初值取) 方法迭代次數(shù)n二分法三分法冒泡法迭代法牛頓法1.2.3.4.5.6.7.8.9.10.11.12.3.52.753.1253.31253.21883.17193.14843.13673.14263.14553.1473.146243.66673.22223.18523.13583.1443.14683.14633.23.143.1523.14723.1462122.69312.99073.09553.133.1413.14453.14573.1463.1461

14、7.09393.44483.15183.15183.1462例 2. (解的誤差數(shù)度為0.0001)(二分法,三分法,冒泡法取區(qū)間0,1,簡單迭代法和牛頓法的初值取) 方法迭代次數(shù)n二分法三分法冒泡法迭代法牛頓法1.2.3.4.5.6.7.8.9.10.11.12.13.14.0.50.250.3750.31250.343750.359380.351560.347660.34570.346680.347170.347410.347290.347350.666670.555560.407410.358020.353910.348420.347970.347360.34730.30.340.348

15、0.34720.347360.34730.50.3750.350910.347740.347350.34730.333330.347220.3473從以上兩個圖表來看:三分法，冒泡法是二分法的推廣，這三種方法都比較直觀，都是計算方程的解x的誤差為0.0001，由上可知:冒泡法的計算的速度比較快。冒泡法、簡單迭代法、牛頓迭代法計算的速度相對于另外兩種方法來說都比較快，并且牛頓法是最快的。在例2中雖然在-2到0間有解，但當(dāng)其迭代函數(shù)為時用簡單迭代法求解中如果初值取0的時候，是得不到解的，其運行結(jié)果為: k x f(x)1 0 13 1.2392+0.6143i -2.2175+0.75519i4

16、1.4571+0.2933i -0.65373+0.96299i5 1.5105+0.12886i -0.16029+0.49332i6 1.5249+0.055442i -0.043026+0.22025i7 1.5294+0.023705i -0.013525+0.09521i8 1.531+0.010114i -0.004876+0.040776i9 1.5316+0.0043112i -0.0019155+0.017407i10 1.5319+0.0018371i -0.00078658+0.0074222i11 1.532+0.00078273i -0.00032975+0.0031

17、631i12 1.5321+0.00033348i -0.00013951+0.0013478i13 1.5321+0.00014207i -5.9258e-005+0.00057422i14 1.5321+6.0526e-005i -2.5213e-005+0.00024464i15 1.5321+2.5785e-005i -1.0736e-005+0.00010422i16 1.5321+1.0985e-005i -4.5725e-006+4.4401e-005i所以用簡單迭代法求方程的數(shù)值解時，注意迭代函數(shù)的選取是很重要的。參考文獻1 王沫然. MATLAB與科學(xué)計算(第2版)M. 北京

18、: 電子工業(yè)出版社,2004.2 萬福永,戴浩暉,潘建瑜. 數(shù)學(xué)實驗教程(Matlab版)M. 北京: 科學(xué)出版社, 2006.3 朱方生,李大美,李素貞. 計算方法M. 武漢: 武漢大學(xué)出版社, 2006.4 顏慶津. 數(shù)值分析(第三版) M. 北京: 航空航天大學(xué)出版社, 2006.注1: 以下的fun函數(shù)是例題函數(shù)注2: 簡單迭代法和牛頓迭法是以例1為例子編寫的程序，例2要修改程序里面的函數(shù),其它的方法只改fun函數(shù)就可以運行了.附錄1二分法的matlab程序:function erfen(a,b,esp)if feval('fun',a)*feval('fun&

19、#39;,b)<0; n=1; while abs(b-a)>esp; c=a+(b-a)/2; if feval('fun',a)*feval('fun',c)<0; b=c; disp(num2str(n),' ',num2str(c); elseif feval('fun',c)*feval('fun',b)<0; a=c; disp(num2str(n),' ',num2str(c); end if feval('fun',a)*feval('

20、fun',c)=0; disp(num2str(n),' ',num2str(c); break; end n=n+1; end end附錄2三分法的matlab程序:function sanfen(a,b,esp)if feval('fun',a)*feval('fun',b)<0; n=0; while abs(b-a)>esp; n=n+1; if feval('fun',a)*feval('fun',b)<0; s=a:(b-a)/3:b; if feval('fun

21、9;,s(2)*feval('fun',s(3)<0; a=s(2);b=s(3); x0=(s(3)+s(2)/2; elseif feval('fun',a)*feval('fun',s(2)<0; b=s(2); x0=(a+s(2)/2; elseif feval('fun',s(2)=0; x0=s(2); break elseif feval('fun',s(3)=0; x0=s(3); break else a=s(3);x0=(s(3)+b)/2; end disp(num2str(n)

22、,' ',num2str(s(3); else break; end endend附錄3冒泡法matlab 程序:function maobao(a,b,esp)if feval('fun',a)*feval('fun',b)<0; n=1; while abs(b-a)>esp; if feval('fun',a)*feval('fun',b)<0; s=a:(b-a)/10:b; a0=abs(feval('fun',s(2); k=2; for i=3:10; if abs(feval('fun',s(i)<a0; a0=abs(feval('fun',s(i); k=i; end end n=n+1; a=s(k-1); b=s(k+1); n s(k) elseif feval('fun',a)=0; disp(n,a) break elseif feval('fun',b)=0; d