非線性方程解法

1、第七章 非線性方程解法2. Newton-下山法.每次迭代在改變量前加一因子以保證收斂:x n+1=xn-n f(xn)/f(xn)這兒n在0,1間,可用各種方法搜索,例如用分半法取1,1/2,1/4,試探,使下山條件f(xn+1)<f(xn)成立為止。牛頓下山實(shí)驗(yàn)上機(jī)題目:牛頓下山法上機(jī)實(shí)驗(yàn)實(shí)驗(yàn)?zāi)康?編制求單變量非線性方程組的程序.實(shí)驗(yàn)要求: 上機(jī)前充分準(zhǔn)備，復(fù)習(xí)有關(guān)內(nèi)容，寫出計(jì)算步驟，查對程序；完成實(shí)驗(yàn)后寫出完整的實(shí)驗(yàn)報(bào)告，內(nèi)容應(yīng)該包括：所用的算法語言，算法步驟陳述，變量說明，程序清單，輸出計(jì)算結(jié)果，結(jié)果分析等等；用編好的程序在atlab環(huán)境中執(zhí)行。利用Newton下山法來解方程；計(jì)

2、算步驟：準(zhǔn)備 選定初始近似值x，計(jì)算f=f(x),。迭代 按公式 x迭代一次，得新的近似值x, 計(jì)算.最初=1，之后獎減半進(jìn)行試算直到下山條件 f(xn+1)<f(xn)成立?？刂?如果滿足f(xn+1)<f(xn)則終止迭代，；否則轉(zhuǎn)步驟4； 修改 如果迭代次數(shù)達(dá)到預(yù)先指定的次數(shù)N，或者=0，則方程失?。环駝t以（x，）代替（）轉(zhuǎn)步驟2繼續(xù)迭代。算法例題：用牛頓下山方法解方程 x-x-1=0，取迭代初值 x=1.5, d=10.Newton下山法的Matlab程序：function x=newton_xiashanfa(f,x0,d,max)y=diff(f); %取導(dǎo)數(shù)y=inl

3、ine(y); %定義yf=inline(f); %定義fx(1)=x0;l=1;disp('k l x '); %以指定格式輸出'k','x'.for k=1:max x(k+1)=x(k)-l*f(x(k)/y(x(k); % 計(jì)算公式 if abs(f(x(k+1)<abs(f(x(k) %判斷是否小于d if abs(x(k+1)-x(k)<d break end else if abs(f(x(k+1)>abs(f(x(k) l=l/2; end w=k; end for k=1:wdisp(sprintf('

4、%d %f %10f ',k,l,x(k) %輸出算結(jié)果 endx=x(k+1);運(yùn)行結(jié)果：x=newton_xiashanfa('x3-x-1',1.5,10(-6),3)max =3k x f(x(K+1) f(x(k)3 1.325213 0.662708 0.463111x = 1.5000 1.3478 1.3252 1.3247Newton下山法的流程圖:：流程圖解釋：1） 輸入；2）把1 賦給;3）把賦給；4）判斷，若那么表明下山成功，停止；若，那么到步驟5）；5）判斷 ，若 ，重迭；否則把膩給 ，到步驟3）；3.   

5、60;   用差商代導(dǎo)數(shù):x n+1=xn-f(xn)(xn-x n-1)/(f(xn)- f(xn-1)它免除了計(jì)算導(dǎo)數(shù). Newton法解方程組試以二個未知數(shù)的非線性方程組為例介紹.與一維情況一樣,在初始近似(x0, y0)用Taylor展開線性化.取線性部分的零點(diǎn)為新的近似,即解方程組求出x,y,再計(jì)算x1= x0+x, y1=0+y求出1次近似后,再用同樣方法求2次近似,再求3次近似,4次近似,直到相鄰兩次近似之差(的范數(shù))在預(yù)定許可范圍內(nèi).下面看個例子；例         &

6、#160;    用Newton法解方程組, 解：取初始近似(1,1)T 計(jì)算結(jié)果如下表：nxyJ（系數(shù)矩陣）f1f01.00001.00002.0000 2.0000-2.0000 2.0000-3.0000-2.000011.25002.25002.5000 4.5000-0.7500 2.25001.62500.312521.00002.02782.0000 4.0556-0.9722 2.00000.11190.055631.00022.00012.0004 4.0002-0.9999 2.00020.0007664-0.000005441.00002.0

7、0002.0000 4.0000-1.0000 2.00000.4666×10-70.1835×10-7一般情況下n個未知數(shù)的非線性方程組k次近似x(k)=(x1(k),x2(k),xn(k)T用Taylor展開并線性化得線性方程組。令則線性方程組可寫成 J(k)x= -f(k)解出x后便可算出x(k+1)=x(k)+x；這樣得到算法如下：給出初始近似x(0)=(x1(0),x2(0),xn(0)T對k=0,1,計(jì)算J(k),f(k)解J(k)x= -f(k)求x計(jì)算新近似x(k+1)=x(k)+x直到x注：非線性方程組的Newton法與非線性方程的Newton法形式上可以

8、一致；x(k+1)=x(k)-(f (x( k)-1f(x( k) 這兒f (x( k) =J( k)Newton線截法:（給予參考）流程圖解釋：1） 輸入和最大循環(huán)次序N；2）把1 賦給k;3）判斷是否等于零，若=0，則輸出奇異標(biāo)志，停止；若，則到步驟 4； 4）把賦給；5）判斷，若那么輸出方程的近似解，即輸出 ，停止；否則到步驟6；6）判斷k 是否等于 N ，若k=N ，那么，輸出迭代法失敗標(biāo)志，停止；否則過步驟7； 7）把k+1 賦給 k,把賦給，到步驟3；總結(jié)分析:Newton法收斂速度快，可是每步迭代要計(jì)算f(x)及它的導(dǎo)數(shù)，計(jì)算量大，有時計(jì)算導(dǎo)數(shù)較困難，而初始近似x只在x附近才能保

9、證收斂，如果x給的不適合可能不收斂。使用簡化Newton和Newton下山法可將一階方法加速為二階.并可避免以上錯誤。 切線法     (x1,y1) x0 x2 x1 (x0,y0)方法這次我們用線性插值函數(shù)也就是用割線來構(gòu)造近似.由初始近似x0, x1作線性插值函數(shù),取其零點(diǎn)為x2:x2=x2-f(x2)(x2-x1)/(f(x2)- f(x1)一般x n+1=xn-f(xn)(xn-x n-1)/(f(xn)- f(xn-1)稱為割線法.它要求兩個初始值.下面來個例子。例2. 求f(x)=x3- x-1=0在區(qū)間1,1.5內(nèi)的一個實(shí)根；解：割線法取

10、x0=1,x1=1.5,計(jì)算結(jié)果見表：.nxn01.0000000000000011.5000000000000021.26666666666667341.3252141139641451.3247138858183161.3247179553629071.3247179572447581.32471795724475割線法不用算f(x)的導(dǎo)數(shù),又具有超線性收斂,是多點(diǎn)迭代法.常用的有效方法之一. 收斂性割線法在f(x)=0單根附近是p=(51/2+1)/2階收斂的,并且有x n+1-f()/(2f()p-1x n-p割線法較Newton法收斂慢,但每步不必計(jì)算導(dǎo)數(shù),總計(jì)算量也有可能低于New

11、ton法.因此,割線法頗具競爭力.          弦截法與拋物線法 弦截法用牛頓法求方程的根每步除計(jì)算f(x)外還要計(jì)算它的導(dǎo)數(shù)，當(dāng)函數(shù)比較復(fù)雜時計(jì)算導(dǎo)數(shù)往往較困難，為此可以利用已求函數(shù)值來回避導(dǎo)數(shù)值的計(jì)算，這類方法建立在插值原理基礎(chǔ)上的。設(shè)，是f(x)=0的近似根，利用f(),f()構(gòu)造一次插值多項(xiàng)式(x),并用(x)=0的根作為f(x)=0的新近似根。由于。因此有因之，按上式求得的x實(shí)際上是弦線與x軸交點(diǎn)的橫坐標(biāo)，這種算法因此而稱弦截法。（詳看書上例題10）。為了在Matlab環(huán)境中實(shí)現(xiàn)弦截法有

12、興趣著可以由以下程序編出它的算法：function x=xianjiefa(f,x0,x1,d,max)f=inline(f);x(1)=x0;x(2)=x1;for k=2:max x(k+1)=x(k)-f(x(k)*(x(k)-x(k-1)/(f(x(k)-f(x(k-1); if abs(x(k+1)-x(k)<d break end disp(sprintf('%d %f %f',k,x(k),x(k+1)end拋物線法設(shè)已知方程f(x)=0的三個近似根，以這三位節(jié)點(diǎn)構(gòu)造二次插值多項(xiàng)式(x)并適當(dāng)選取(x)的一個零點(diǎn)x，作為新的近似根，這樣確定的迭代法過程稱拋物

13、線法。其計(jì)算公式為：為了在Matlab環(huán)境中實(shí)現(xiàn)拋物線法有 興趣著可以由以下程序編出它的算法：function x=paowu(f,x0,x1,x2,d,max)f=inline(f);x(1)=x0; x(2)=x1; x(3)=x2; w1=(f(x(2)-f(x(3)/(x(2)-x(3); t1=(f(x(1)-f(x(3)/(x(1)-x(3); t2=(f(x(1)-f(x(2)/(x(1)-x(2); w2=1/(x(1)-x(2)*(t1-t2); w=w1+w2*(x(3)-x(2);for k=3:max x(k+1)=x(k)-2*f(x(k)/(w+sqrt(w2-4*f(x(k)*w2); if abs(x(k+1)-x(k)<d break end disp(sprintf('%d %f %f',k,x(k+1),f(x(k+1)end x=x(k+1)弦截法和拋物線法是是屬于插值方法，它們都不用算f(x)的導(dǎo)數(shù)，又具有超線性收斂，也是常用的有效的方法之一。這類方法是多