二分法、牛頓法、割線法、Steffencen法求非線性方程MATLAB實現(xiàn)

1、數(shù)值分析實驗求非線性方程的零點10級數(shù)學(xué)與應(yīng)用數(shù)學(xué)1班20103869 郝少強(qiáng)摘要本報告主要介紹了基于求非線性方程零點問題的牛頓法、二分法，簡易牛頓 法、割線法、Steveson法等數(shù)值分析方法的算法原理及實現(xiàn)方法。通過對非線 性方程/(x) = ?-3.r-l = 0分別運(yùn)用以上五種不同的迭代法進(jìn)行數(shù)值實驗，對幾 種迭代法的運(yùn)算量，空間存儲使用，迭代步數(shù)進(jìn)行了初步分析評價，并對幾種迭 代法分別適用于求解何種類型的非線性方程進(jìn)行了簡要分析說明A.牛頓法一、算法介紹牛頓法是一種能在許多不同情況下應(yīng)用的通用過程。特別的，當(dāng)用它來求實 變量實值函數(shù)零點時，常常被成為牛頓一拉弗森迭代。由于其收斂是二次

2、的而不 是線形或超線性的，所以通常牛頓法對分法和割線法要快。一口二次收斂變紂有 效時，即牛頓法序列的值能充分地接近根時，其收斂很快以至于僅僅再需要兒個 數(shù)值即可。不完美的是，牛頓法不能保證總是收斂，所以實際計算中常常將其與 其他較慢的方法結(jié)合形成一種數(shù)值上整體收斂的混合方法。假設(shè)我們有一個函數(shù)/,其零點由數(shù)值計算得出。設(shè)廠是/的零點，而工是'.的一個近似。若存在并且連續(xù)，則由泰勒定理，得o = /(/) = /(.Y+ 力)=/(.r) + hfx) + O/r)其中力=尸-.丫，若力較小(即工在廠附近)，則有理由略去項，并且在余下的方程中求力，其結(jié)果是若禺的-個近似，則一為應(yīng)該是，的

3、-個更好的近似。牛頓從'的-個估計無開始，然后歸納定義二、算法描述用牛頓法求方程f (x)=x"3-3*x-1=0在x0=2附近的根，已知根的準(zhǔn)確值為 x*=l. 87938524-通過牛頓迭代計算方程的根。取初始迭代值為2,精度取10化 MATLAB程序代碼如下： f=inline(' x 3-3*xT');df二inline(' 3*x 2-3*);d2f二inline(' 6*x');a二 1;b=2;dlt=0. 5*1.0e-8;if f (a) *d2f (a) >0xO 二a;elsexO=b;endm二min(ab

4、s(df(a), abs(df (b);k=0;while abs(f(xO)>m*dltk=k+l;xl=xOf(xO) df (xO);xO=xl;fprintf (' k=%d x=%. 5fn', k, xO);end三、實驗結(jié)果kX11. 8888921. 8795431. 8793941. 8793951. 87939四，結(jié)果分析牛頓迭代法是二次收斂的，因此用牛頓迭代法求解非線性方程的解，迭代次 數(shù)較小，能以較小的計算量和較小的空間利用得到相對較精確的數(shù)值解。但其缺 點為需要所求非線性方程的導(dǎo)函數(shù)值，所以適用范圍相對較小，只能對一階可導(dǎo) 的方程進(jìn)行迭代。B-二

5、分法一、算法介纟若/是區(qū)間“,力的連續(xù)函數(shù)，且/(“)/(力)vO,則/在“,力內(nèi)必有一個零 點。因為/(")/(力)<0,所以函數(shù)/在區(qū)間億力上改變符號，因此它在這個區(qū)間 內(nèi)至少存在一個零點。這是中值定理的結(jié)論，因此利用區(qū)間減半的方法對這一數(shù) 值計算思想進(jìn)行實踐運(yùn)算。二、算法描述設(shè)函數(shù)/（才）在區(qū)間S，力上連續(xù)，而且/（“）/3）0,則/（丫）在區(qū)間S，力上至少有一個根。首先確定有限區(qū)間：依據(jù)零點定理。設(shè)/（"£ C"，力,且/（“）/（力）0, 則方程/（"）= °在區(qū)間（"，力）上至少有一個根。如果/CO在（&q

6、uot;"）上恒正或恒負(fù), 則此根唯一。令"1 = 0 =力，力矽+ 若/（©）/（力0,則ghalf為有 根區(qū)間，否則加久幻為有根區(qū)間。記新的有根區(qū)間為勺，方，則勺 且A- = I（A-1）.對勺,2重復(fù)上述做法得：MM2，力2并”，力"二且勺一“藥（力一"），設(shè)所求的根為./ e a.b=1，2則,即占(力- ) = 0 liin an = limL"TH"TOC 1取心力込尹+女）為"的近似解。MATLAB程丿孕代碼如下 f=inline（' x3-3*x-l ）;b=2;dlt=O. 5*1. 0e

7、8;k=l;while abs(b-a)>dlt c=(a+b)/2;if f(c)=Obreak;else辻 f(c)*f(b)<0else b=c;endfprintf (' k=%d, x=%. 5fn，, k, c);k=k+l;三、實驗結(jié)果Couand Tindovk=b k=1. 50000 k=2.x=l. 75000 k=3,x=l. 87500 k=4, x= 1.93750 k=5, x= 1.90625 k=6J x= 1.89063 k=7, x= 1.88281 k=8,x=l. 87891 k=9Jx=l. 88086 k=10, x=l.879

8、88 k=U,x=l. 87939 k=12, x=l. 87915 k=13, s=l.87927 k二14, x=l.87933 k=15,爐1.87936 k=16, x=L 87938 k=17,x=l. 87939 k=18,x=l. 87938 k=19, x=l.87938 k=20, k=1.87939 k=21,x=l.87939 k=22, x=l.87939 k=23, x=l. 87939 k=24,x=l. 87939 k=25,x=l. 87939 k=26,x=l. 87939 k=27,x=l. 87939 k二28,x=l. 87939 »l四、結(jié)果

9、分析由實驗結(jié)果可知，二分法經(jīng)過多次迭代后，也能達(dá)到較好的精度，但當(dāng)所求問題較為龐大，且對其跟的估計范圍較為寬泛時，此方法所需迭代的步數(shù)很大, 無論計算量和空間儲存上都會有很大的開銷耗費(fèi)。C簡易牛頓法一、算法介纟簡易牛頓法與牛頓法大致思想相同，都是運(yùn)用切線和坐標(biāo)軸相交進(jìn)行迭代運(yùn) 算，不同的是簡易牛頓法在進(jìn)行迭代運(yùn)算時只取用了初始值的導(dǎo)函數(shù)值，使得算 法整體運(yùn)算最相對較小。二、算法描述在牛頓法程仔代碼上進(jìn)行小修改就行，MATLAB代碼如下: f二inline (' x 3-3*x-T );df二inline(' 3*x"2-3');d2f二inline('

10、 6*x');a-1;b=2;dlt=O. 5*1. Oe-8;if f(a)*d2f(a)>0x0=a;elsex0=b;endm=min(abs(df(a), abs(df(b);k=0;h=df (xO);whUe abs (f (xO) >m*dltk=k+l;xl=xO-f(xO)/h;xO=xl;fprintf (' k=%d x=%. 5fn*, k, xO);end三、實驗結(jié)果k=l x=l. 88889 k=2 x=l.88081 k=3 x=l.87961 k=4 x= 1.87942 k=5 x=l.87939 k=6 x=l.87939 k=

11、7 x=l.87939 k=8 x=l.87939 k=9 x=l.87939 k=10 x=L 87939 k=ll x=l.87939 k=12 x=l. 87939 k=13 x=l. 87939 k=14 x=L 87939 k=15 x=L 87939 k=16 x=l.87939 k=17 x=L 87939 k=18 x=l.87939 k=19 x=l.87939四、結(jié)果分析相比于牛頓法，建議牛頓法擁有較小的計算量，算法只用到初始值的導(dǎo)數(shù)值 作為分母，但缺點是需要迭代更多步數(shù)。綜合比較兩種迭代算法的話，簡易牛頓法適合簡單且容易觀察出零點大致位置的非線性方程，而牛頓法在更為復(fù)雜的

12、問 題上仍能以較小的運(yùn)算最得出令人滿意的數(shù)值解。D.割線法一、算法介纟我們前面己經(jīng)知道牛頓迭代法擁有許多良好的性質(zhì)，比如二次收斂速度很 快，迭代次數(shù)較少，所用存儲空間少，程序編寫簡單等。但不可否認(rèn)的是，牛頓 法仍然存在缺點，如局部收斂，需要求函數(shù)零點導(dǎo)數(shù)等。因此為克服存在函數(shù)不 可導(dǎo)的這一缺點，人們提出了割線法，即心”-心)局刁話因為”知得計算要用到兀和才I，所以開始時需要指定兩個初始點O二、算法描述輸入的量：初始值心、施，要求的近似根丑的誤差限tol, X,的函數(shù)值/(丑) 的誤差限ftol,迭代次數(shù)的最大值gxmax及其函數(shù)fnq(x)輸出的量:迭代序列耳,迭代k次得到的迭代值耳，相鄰兩次

13、迭代的偏差 piancha=以及偏茅的相對誤壽再-/ “。MATLAB程序代碼如下：function k,piancha,xdpiancha, xk, yk=gexian(xOl, x02, tol, ftol, gxmax)x(l)=x01;x(2)=x02;for i-2: gxmaxu(i)= fnq(x(i)*(x(i)-x(i-l) ; v(i)= fnq(x(i)-fnq(x(i-l);x(i+l)=x(i)- u(i)/( v(i) ; piancha=abs (x(i+1)-x(i): xdpiancha= piancha/( abs(x(i+1)+eps) ; i二i+1;

14、xk= x(i): yk=fnq(x(i): (i-2) piancha xdpiancha xk yk if (abs(yk)<ftol)&( piancha <tol)| (xdpiancha< tol) k=i-2; xk=x(i);yk=fnq(x(i);(i-2) piancha xdpiancha xk yk；return;endendif i>gxmaxdispf請注意：迭代次數(shù)超過給定的最大值gxmax.')k=i2; xk二x(i);yk=fnq(x(i);return;end三、實驗結(jié)果kX11. 750021. 867831. 88

15、0641. 879451. 8794四、結(jié)果分析由實驗數(shù)據(jù)分析可知：割線法收斂速度不如牛頓迭代法收斂速度快，但比二 分法要快得多，可以達(dá)到相對較高的精度。且在其迭代過程中每步只需一次新的 函數(shù)賦值，乂因為此類迭代算法中函數(shù)賦值構(gòu)成了主要的計算量，所以綜合比較 割線法的運(yùn)算量要比牛頓法更小些。E. Steffensen 法一、算法介纟Steffensen算法是為了克服用牛頓迭代法時存在函數(shù)不可導(dǎo)的這一缺點而 提岀的另一種迭代法，同時也避免了進(jìn)行割線法迭代時因為兩個值之間相差很近 時造成的算法誤差。其迭代公式為；=耳-/(£)/&(才”)其中 g(“ = /3+ /)-/ /(-V)二、算法描述MATLAB程序代碼如下：function gen, time=Steff(fun, xO,tol)%如果缺省誤差參數(shù)，默認(rèn)為10的-5次方if (nargin=2)tol=l. 0e5;end%設(shè)置誤差初值time=0; %記迭代次數(shù)wucha二0. 1; %設(shè)置前后兩次迭代的誤差gen=x0;while(wucha>tol)xl=gen;y=subs(fun, xl)+