Newton迭代法求解非线性方程.pdf
Newton 迭代法求解非线性方程 一、Newton 迭代法概述 构造迭代函数的一条重要途径是用近似方程来代替原方程去求根。因此，如果能将非线性方程f(x)=0用线性方程去代替，那么，求近似根问题就很容易解决，而且十分方便。牛顿(Newton)法就是一种将非线性方程线化的一种方法。设kx是方程f(x)=0的一个近似根，把如果)(xf在kx处作一阶 Taylor 展开，即：)xx)(x(f)x(f)x(fkkk (1-1)于是我们得到如下近似方程：0)xx)(x(f)x(fkkk (1-2)设0)(kxf，则方程的解为：x =xk+f(xk)f(xk)(1-3)取x作为原方程的新近似根1kx，即令：)x(f)x(fxxkkk1k,k=0,1,2,(1-4)上式称为牛顿迭代格式。用牛顿迭代格式求方程的根的方法就称为牛顿迭代法，简称牛顿法。牛顿法具有明显的几何意义。方程：)xx)(x(f)x(fykkk (1-5)是曲线)x(fy 上点)x(f,x(kk处的切线方程。迭代格式(1-4)就是用切线式(1-5)的零点来代替曲线的零点。正因为如此，牛顿法也称为切线法。牛顿迭代法对单根至少是二阶局部收敛的，而对于重根是一阶局部收敛的。一般来说，牛顿法对初值0 x的要求较高，初值足够靠近*x时才能保证收敛。若要保证初值在较大范围内收敛，则需对)x(f加一些条件。如果所加的条件不满足，而导致牛顿法不收敛时，则需对牛顿法作一些改时，即可以采用下面的迭代格式：)x(f)x(fxxkkk1k,2,1,0k (1-6)上式中，10，称为下山因子。因此，用这种方法求方程的根，也称为牛顿下山法。牛顿法对单根收敛速度快，但每迭代一次，除需计算)x(fk之外，还要计算)x(fk的值。如果)x(f比较复杂，计算)x(fk的工作量就可能比较大。为了避免计算导数值，我们可用差商来代替导数。通常用如下几种方法：1.割线法 如果用 1kk1kkxx)x(f)x(f代替)x(fk，则得到割线法的迭代格式为：)x(f)x(f)x(fxxxxk1kk1kkk1k (1-7)2.拟牛顿法 如果用)x(f)x(fx(f)x(fk1kkk代替)x(fk，则得到拟牛顿法的迭代格式为：)x(fx(f)x(f)x(fxx1kkkk2k1k (1-8)3.Steffenson法 如果用)x(f)x(f)x(fx(fkkkk代替)x(fk，则得到拟牛顿法的迭代格式为：)x(f)x(fx(f)x(fxxkkkk2k1k (1-9)二、算法分析 1.割线法 割线法的迭代公式为：)x(f)x(f)x(fxxxxk1kk1kkk1k,k=0,1,2,割线法是超线性收敛，其程序流程图为：2.拟牛顿法 牛顿拟迭代法迭代公式为：)x(fx(f)x(f)x(fxx1kkkk2k1k(1)对单根条件下，牛顿拟迭代法平方收敛，牛顿拟迭代法程序框图如下所示：(2)对重根条件下，此时迭代公式修改为：)x(fx(f)x(f)x(fmxx1kkkk2k1k,m 为根的重数 此时，牛顿迭代法至少平方收敛。3.Steffenson法 Steffenson迭代法程序流程图与牛顿拟迭代法类似。三、牛顿法的程序 给定初值0p，用牛顿法格式)p(f)p(fpp1k1k1kk，,2,1k，求解非线性方程0)x(f。*function p1,err,k,y=newton(f1041,df1041,p0,delta,max1)%f1041是非线性函数。%df1041是 f1041的微商。%p0是初始值。%delta是给定允许误差。%max1是迭代的最大次数。%p1是牛顿法求得的方程的近似解。%err是 p0 的误差估计。%k 是迭代次数。%y=f(p1)p0,feval(f1041,p0)for k=1:max1 p1=p0-feval(f1041,p0)/feval(df1041,p0);err=abs(p1-p0);p0=p1;p1,err,k,y=feval(f1041,p1)if (err prog1041 计算结果如下：p0=ans=p1=err=k=1 y=p1=err=k=1 y=p1=err=k=2 y=p1=err=k=2 y=p1=err=k=3 y=p1=err=k=3 y=p1=err=k=4 y=p1=err=k=4 y=p1=err=k=5 y=p1=err=k=5 y=p1=err=k=6 y=p1=err=k=6 y=p1=err=k=7 y=p1=err=k=7 y=p1=err=k=8 y=p1=err=k=8 y=p1=err=k=9 y=p1=err=k=9 y=p1=err=k=10 y=p1=err=k=10 y=p1=err=k=11 y=p1=err=k=11 y=p1=err=k=12 y=p1=err=k=12 y=p1=err=k=13 y=p1=err=k=13 y=p1=err=k=14 y=p1=err=k=14 y=p1=err=k=15 y=p1=err=k=15 y=p1=err=k=16 y=p1=err=k=16 y=p1=err=k=17 y=p1=err=k=17 y=p1=err=k=18 y=ans=这说明，经过 18 次迭代得到满足精度要求的值。以下是程序运行截图：
