第七章非线性方程解法

新疆大学-1-数学与系统科学院第七章非线性方程解法2.Newton-下山法.每次迭代在改变量前加一因子以保证收敛:xn+1=xn-λnf(xn)/f′(xn)这儿λn在0,1间,可用各种方法搜索,例如用分半法取1,1/2,1/4,…试探,使下山条件∣f(xn+1)∣∣f(xn)∣成立为止。牛顿下山实验⑷上机题目:牛顿下山法上机实验实验目的:编制求单变量非线性方程组的程序.实验要求:①上机前充分准备，复习有关内容，写出计算步骤，查对程序；②完成实验后写出完整的实验报告，内容应该包括：所用的算法语言，算法步骤陈述，变量说明，程序清单，输出计算结果，结果分析等等；③用编好的程序在Ｍatlab环境中执行。利用Newton下山法来解方程；计算步骤：①准备选定初始近似值x0，计算f0=f(x0),f)(00xf。②迭代按公式x0001ffx迭代一次，得新的近似值x1,计算f)(),(1111xffxf.最初=1，之后奖减半进行试算直到下山条件∣f(xn+1)∣∣f(xn)∣成立。③控制如果满足∣f(xn+1)∣∣f(xn)∣则终止迭代，；否则转步骤4；④修改如果迭代次数达到预先指定的次数N，或者f=0，则方程失败；否则以（x1，11,ff）代替（000,,ffx）转步骤2继续迭代。算法例题：用牛顿下山方法解方程x3-x-1=0，取迭代初值x0=1.5,d=106.Newton下山法的Matlab程序：functionx=newton_xiashanfa(f,x0,d,max)y=diff(f);%取导数y=inline(y);%定义yf=inline(f);%定义fx(1)=x0;l=1;disp('klx');%以指定格式输出'k','x'.新疆大学-2-数学与系统科学院fork=1:maxx(k+1)=x(k)-l*f(x(k))/y(x(k));%计算公式ifabs(f(x(k+1)))abs(f(x(k)))%判断是否小于difabs(x(k+1)-x(k))dbreakendelseifabs(f(x(k+1)))abs(f(x(k)))l=l/2;endw=k;endfork=1:wdisp(sprintf('%d%f%10f',k,l,x(k)))%输出算结果endx=x(k+1);运行结果：x=newton_xiashanfa('x^3-x-1',1.5,10^(-6),3)max=3kxf(x(K+1))f(x(k))31.3252130.6627080.463111x=1.50001.34781.32521.3247Newton下山法的流程图:：流程图解释：1）输入,0x；2）把1赋给;3）把)()()0()0()0(xfxfx赋给1x；4）新疆大学-3-数学与系统科学院判断)()(01xfxf，若)()(01xfxf那么表明下山成功，停止；若)()(01xfxf，那么到步骤5）；5）判断，若，重迭0x；否则把2腻给，到步骤3）；3.用差商代导数:xn+1=xn-f(xn)(xn-xn-1)/(f(xn)-f(xn-1))它免除了计算导数.⒋Newton法解方程组试以二个未知数的非线性方程组为例介绍.0),(0),(21yxfyxf与一维情况一样,在初始近似(x0,y0)用Taylor展开线性化.取线性部分的零点为新的近似,即解方程组020202010101fyyfxxffyyfxxf求出Δx,Δy,再计算x1=x0+Δx,y1=ｙ0+Δy求出1次近似后,再用同样方法求2次近似,再求3次近似,4次近似,…直到相邻两次近似之差(的范数)在预定许可范围内.下面看个例子；例７用Newton法解方程组,0)13()1(),(05),(2221xyxyxfyxyxf解：取初始近似(1,1)T计算结果如下表：nxyJ（系数矩阵）f1f２01.00001.00002.00002.0000-2.00002.0000-3.0000-2.000011.25002.25002.50004.5000-0.75002.25001.62500.312521.00002.02782.00004.0556-0.97222.00000.11190.055631.00022.00012.00044.0002-0.99992.00020.0007664-0.000005441.00002.00002.00004.0000-1.00002.00000.4666×10-70.1835×10-7新疆大学-4-数学与系统科学院一般情况下n个未知数的非线性方程组0),,,(0),,,(0),,,(21212211nnnnxxxfxxxfxxxfk次近似x(k)=(x1(k),x2(k),…,xn(k))T用Taylor展开并线性化得线性方程组knnknnnnnnnfffxxxxfxfxfxfxfxfxfxfxf212112221212111。令knknknnnnnnnkffffxxxxxfxfxfxfxfxfxfxfxfJ21)(2112221212111)(,,则线性方程组可写成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(k),f(k)③解J(k)Δx=-f(k)求Δx④计算新近似x(k+1)=x(k)+Δx直到║Δx║≤ε注：非线性方程组的Newton法与非线性方程的Newton法形式上可以一致；x(k+1)=x(k)-(f′(x(k)))-1f(x(k))这儿f′(x(k))=J(k)Newton线截法:（给予参考）新疆大学-5-数学与系统科学院流程图解释：1）输入,)0(x和最大循环次序N；2）把1赋给k;3）判断'(0)()fx是否等于零，若'(0)()fx=0，则输出奇异标志，停止；若'(0)()0fx，则到步骤4；4）把(0)(0)'(0)()()fxxfx赋给1x；5）判断01xx，若01xx那么输出方程的近似解，即输出1x，停止；否则到步骤6；6）判断k是否等于N，若k=N，那么，输出迭代法失败标志，停止；否则过步骤7；7）把k+1赋给k,把1x赋给0x，到步骤3；总结分析:Newton法收敛速度快，可是每步迭代要计算f(xk)及它的导数，计算量大，有时计算导数较困难，而初始近似x0只在x附近才能保证收敛，如果x0给的不适合可能不收敛。使用简化Newton和Newton下山法可将一阶方法加速为二新疆大学-6-数学与系统科学院阶.并可避免以上错误。⒋切线法①方法这次我们用线性插值函数也就是用割线来构造近似.由初始近似x0,x1作线性插值函数,取其零点为x2:x2=x2-f(x2)(x2-x1)/(f(x2)-f(x1))一般xn+1=xn-f(xn)(xn-xn-1)/(f(xn)-f(xn-1))称为割线法.它要求两个初始值.下面来个例子。例2.求f(x)=x3-x-1=0在区间[1,1.5]内的一个实根；解：割线法取x0=1,x1=1.5,计算结果见表：.nxn01.0000000000000011.5000000000000021.2666666666666731.3159616732881541.3252141139641451.3247138858183161.3247179553629071.3247179572447581.32471795724475割线法不用算f(x)的导数,又具有超线性收敛,是多点迭代法.常用的有效方法之一.②收敛性∣xn+1-ξ∣≈∣f″(ξ)/(2f′(ξ))∣p-1∣xn-ξ∣p割线法较Newton法收敛慢,但每步不必计算导数,总计算量也有可能低于Newton法.因此,割线法颇具竞争力.⒌弦截法与抛物线法①弦截法用牛顿法求方程的根每步除计算f(xk)外还要计算它的导数，当函数比较复杂时计算导数往往较困难，为此可以利用已求函数值来回避导数值的计算，这类方法建立在插值原理基础上的。设kx，1kx是f(x)=0的近似根，利用f(kx),f(1kx)构造一次插值多项式1p(x),并用1p(x)=0的根作为f(x)=0的新近似根1kx。由于割线法在f(x)=0单根ξ附近是p=(51/2+1)/2阶收敛的,并且有(x1,y1)x0x2x1(x0,,y0)新疆大学-7-数学与系统科学院kk-11kkk-1f(x)-f(x)()()(x)xxkpxfxx。因此有)()()()(111kkkkkkkxxxfxfxfxx因之，按上式求得的x1k实际上是弦线1kkpp与x轴交点的横坐标，这种算法因此而称弦截法。（详看书上例题10）。为了在Matlab环境中实现弦截法有兴趣着可以由以下程序编出它的算法：functionx=xianjiefa(f,x0,x1,d,max)f=inline(f);x(1)=x0;x(2)=x1;fork=2:maxx(k+1)=x(k)-f(x(k))*(x(k)-x(k-1))/(f(x(k))-f(x(k-1)));ifabs(x(k+1)-x(k))dbreakenddisp(sprintf('%d%f%f',k,x(k),x(k+1)))end②抛物线法设已知方程f(x)=0的三个近似根kx，1kx，2kx，以这三位节点构造二次插值多项式2p(x)新疆大学-8-数学与系统科学院并适当选取2p(x)的一个零点x1k，作为新的近似根，这样确定的迭代法过程称抛物线法。其计算公式为：)](,,[],[,],,[)(4)(212112121kkkkkkkkkkkkkkxxxxxfxxfxxxfxfxfxx为了在Matlab环境中实现抛物线法有兴趣着可以由以下程序编出它的算法：functionx=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));fork=3:maxx(k+1)=x(k)-2*f(x(k))/(w+sqrt(w^2-4*f(x(k))*w2));ifabs(x(k+1)-x(k))dbreakenddisp(sprintf('%d%f%f',k,x(k+1),f(x(k+1))))endx=x(k+1)弦截法和抛物线法是是属于插值方法，它们都不用算f(x)的导数，又具有超线性收敛，也是常用的有效的方法之一。这类方法是多点迭代法，它不同于x1k=)(x单点迭代，计算时必须给出两个以上的初始近似。复习思考题1.什么叫二分法，它的优点是什么？如何估计误差？在什么情况下不能用二分法求根？2.什么是简单迭代法？它的收敛条件是什么？误差估计式（2-5）、（2-6）各有何特点？说明什么问题？3.迭代格式的收敛速度是如何定义的？如何判别一个迭代格式是几阶收敛的？4.牛顿迭代格式是什么？它是怎样导出的？有何几何意义？有什么优缺点？与割线法有何区别？