对牛顿迭代法及改进的总结

科技信息牛顿迭代法（Newton'smethod）又称为牛顿-拉夫逊方法（Newton-Raphsonmethod），它是牛顿在17世纪提出的一种在实数域和复数域上近似求解方程的方法。大多非线性数方程不存在求根公式，因此求精确根非常困难，甚至不可能，从而寻找方程的近似根就显得特别重要。方法级数的前面使用函数f(x)的泰勒几项来寻找方程f(x)=0的根。牛顿迭代法是求方程根的重要方法之一，其最大优点是在方程f(x)=0的单根附近具有平方收敛，而且该法还可以用来求方程的重根、复根。在求非线性方程式时，它除了具有简单的迭代法的优点外，还具有二阶收敛速度（在单根邻近处）的特点。缺点是牛顿（Newton）法每迭代一步都要计算f(xk)及f'(xk)，且初始值选取比较苛刻（必须充分靠近方程的根），否则也可能不收敛。为了克服这些缺点很多数学工作者对牛顿法做出了一些改进，在本文中如文献[1]。为此，本文总结了几类经典的牛顿迭代法的改进，并且举例做了比较。数值结果是由QB程序得到。一、牛顿（Newton）法牛顿（Newton）法是求非线性方程f(x)=0的根的一种重要方法，其基本思想是将非线性方程转化为线性方程来求解。设f(x)连续可微，则将f(x)在x0处Taylor展开，f(x)=f(x0)+f'(x0)（x-x0）+f''(x0)2!(x-x0)2+……只要f'(x0)≠0，取其线性部分近似替代f(x)，便得f(x)=0的近似方程：f(x)≈f(x0)+f'(x0)（x-x0）=0即x=x0-f(x0)f′(x0)x,由迭代法的思想将上式左端x记为x1，便得到x1=x0-f(x0)f′(x0)一般地有xk+1=xk-f(xk)f′(xk)（1）并称其为Newton迭代公式（自然假定f'(xk)≠0）牛顿（Newton）迭代法的几何意义是：当取初始x0值后，过(x0,f(x0))作f(x)的切线，其切线方程为y-f(x)=f'(x0)（x-x0），此切线与轴交点就是x1=x0-f(x0)f′(x0)（2）如图1。图1牛顿迭代法的几何意义二、牛顿Newton迭代法的收敛性牛顿迭代公式作为不动点迭代，其迭代函数为ϕ(x)=x-f(x)f'(x)（3）从而有ϕ'(x)=1-[f'(x)2-f(x)⋅f''(x)][f'(x)]2=f(x)⋅f''(x)[f'(x)]2（4）如果在方程f(x)=0的根x*的某个邻域内f'(x)≠0，从而f'(x*)≠0，即x*是单根的情况，f''(x)存在并连续，从而有界。则只要x足够靠近x*，从而||f(x)足够靠近0，就有||ϕ(x)≤L1，又根据收敛性定理，可知，牛顿迭代公式收敛于x*，并由f(x*)=0导致ϕ(x*)=0又根据收敛阶判定定理，可知牛顿迭代公式在单根附近至少是2阶收敛的。三、牛顿Nowton迭代法的改进1.简化Nowton迭代法因为f′(x)的计算较为复杂,将f′(x)用f(x0)来代替,则有xk+1=xk－f(xk)f′(xk+1)（k=0,1,2……）改为xk+1=xk－f(xk)f′(x0)（k=0,1,2……）（5）迭代函数为ϕ(x)=xk－f(xk)f′(x0)（6）并称其为简化牛顿Nowton迭代公式。从几何上看，过曲线y=f（x）上的点（xk，f(xk)）且斜率为f'(x0)的切线方程是y－f(xk)=f′(x0)(x-xk),有时也称这种方法为平行切线法。简化牛顿迭代法收敛的证明过程如下证设c=1f′(x0)，此时迭代函数Φ(x)=x-cf(x),||Φ′(x)＝|1－|cf'(x)≤L＜1。即取0＜cf'(x)＜2与c同号，此时迭代法收敛。2.推广的简化牛顿迭代对于（5）来说，如果将f'(x0)用某个常数c取代，则一次导数值都不需要计算，其迭代格式为xk+1=xk-f(xk)c（7）证明：根据局部收敛定理中的局部收敛条件可以得到：|ϕ'(x)|≤L1，∀x∈[a-δ,a+δ]当常数c满足0f'(x)c2时迭代格式（7）收敛。3.Nowton下山法在讨论牛顿法的收敛条件时，都要假定初始值x0要充分的靠近x*时才能保证收敛并且牛顿（Newton）迭代对初值的要求很高。为了放宽初值的选取范围，我们采取如下迭代格式。xk+1=xk-λkf(xk)f′(xk)（8）其中0≤λk≤1称为下山因子。可通过适当选取下山因子λk，使得||f(xk+1)||f(xk)成立。上述迭代方法称为下山Newton法。通常,下山因子可用试选法确定。比如，依次取λk=1,12,122,⋯，直到满足||f(xk+1)||f(xk)例如：容易验算，x33-x=0方程有三个根-3，0，3，虽然初值x0=-0.99在前两个根-3，0之间，但下山Newton法最后收敛于第三个根3，若要求其它根，则要另选初值。通过试探性地改变初值，有可能得到方程各个不同的根。4.弦位法设方程f(x)=0的区间为[a,b]，如图2。连接曲线y=f(x)上的两点A=(a,f(b))和B(b,f(b))得到弦AB，令x0=a,x1=b,则弦AB的方程为y=f(x)－f(x1)-f(x0)x1-x0（x-x1）（9）对牛顿迭代法及改进的总结内蒙古化工职业学院李慧敏王晓燕［摘要］本文总结了牛顿迭代法及它的收敛性质,对几个经典的牛顿迭代法的改进做出了总结，并通过例题将它们做了比较。［关键词］牛顿迭代法收敛阶改进比较收敛速度——275科技信息令y=0得弦AB与x轴的交点的横坐标x2为x2=x0f(x1)-x1f(x0)f(x1)-f(x0)=x1-f(x1)f(x1)-f(x0)(x1-x0)（10）图2以x2为根x*的一个近似值，又过曲线y=f(x)上的两点(x1，f(x1))和(x2，f(x2))作弦，得它与x轴的交点的横坐标x3为x3=x1f(x2)-x2f(x1)f(x2)-f(x1)=x2-f(x2)f(x2)-f(x1)(x2-x1)（11）则又可以以x3作为根x*的一个近似值。继续这样作下去，则可以得到一般迭代公式为xn+1=xn-f(xn)f(xn)-f(xn-1)(xn-xn-1)（12）利用上式求方程f(x)=0的根的近似方法称为弦位法。弦位法的几何意义是，依次利用弦代替曲线，利用线性函数的零点作为函数f(x)零点的近似值。弦位法有收敛定理：若f(x)在根x*的某个领域S={x|x-x*|≤δ}内有二阶连续导数，且对任意x∈S,有f(x')≠0，则当S的领域充分小时，对S领域内任意的x0，x1，由弦位法迭代公式（11）得到的近似值序列{xn}收敛到方程f(x)=0的根x*，并且可以证明弦位法是按阶p=(1+5)2≈1.618收敛的。5.Nowton-like法对于非线性方程f(x)=0在[a.b]内的单重根x*，令g(x)=eαxf(x),α≠0,||α+∞（13）则x*也是方程g(x)=0在[a,b]内的单重根，反之亦然。为援引动力系统的结果，令v(x)=eαx||f(x)=eαxf(x),f(x)0（14）v(x)=eαx||f(x)=-eαxf(x),f(x)0（15）则当x∈[a,b]时v(x)≥0，并且等号⇔x=x*成立。假设[a,b]上有αf(x)+f′(x)≠0成立，则引入动力系统dxdt=-g(x)g′(x)=f(x)αf(x)+f′(x)x(0)=x0,x0∈[a,b]（16）显然方程f（x）=0在[a,b]内的根x*是动力系统（15）的一个平衡点，反之亦然。定理：设对∀x∈[a,b]有αf(x)+f′(x)≠0，f(a)f(b)0G(x)=-f(x)α(f(x)+f′(x))满足利普希茨（L）条件，则初值问题（15）在（0,+∞）上存在唯一满足limt→+∞x(t,x0)=x*x0∈[a,b]的饱和解运动x=x(t,x0)x0∈[a,b],t0,并且x*是方程f（x）=0在[a,b]内的唯一解。用Euler法解（15）得到xn+1=xn-hnf(xn)αf(xn)+f′(xn),n=(0,1,2,⋯⋯)（17）当hn≡1时，可以得到牛顿类法为xn+1=xn-f(xn)αf(xn)+f′(xn),n=(0,1,2,⋯⋯)（18）四、数值实验1.用迭代法求方程f(x)=x33-x附近的根（1）牛顿迭代法牛顿迭代公式xk+1=xk-f(xk)f′(xk)f(x)=x33-x,f′(x)=x2-1xk+1=xk-xk33-xkx2k-1,取初值x0=0.99,运行结果逼近如下表。表1牛顿迭代法k012345678910111213xk-0.9932.50582921.69108214.4915219.70723786.54090584.46496593.13383962.32607241.90230211.75247821.7324031.73205091.7320508f(xk)0.66656711416.363380.2156999.93518295.1986186.7399325.2061027.12525541.86908660.39235190.04158030.00070460.00000020.0000000（2）简化牛顿迭代法简化牛顿迭代公式xk+1=xk-f(xk)f′(x0),取初值x0=1.6表2简化牛顿迭代法k012345678910xk1.61.75042741.72649141.73358481.73161571.73217331.73201621.73206061.73204801.73205161.7320506f(xk)-0.23466670.0373402-0.01106530.030714-0.00086990.000245-0.00006920.0000196-0.00000560.000001600.00000000（3）下山Newton迭代法解：由于f(x)=x33-x,f′(x)=x2-1，下山Newton迭代格式为xk+1=xk-λkx33-xkx2k-1,取初值x0=-0.99,计算结果见表3。表3牛顿下山法k0123456λk10.50.250.1250.062510.50.251111xk-0.9932.5059815.757997.384003.197001.103504.114872.609161.856331.743521.732171.732051.73205f(xk)0.6665671146.51288.55126.8167.69495-0.6555919.108993.311620.275940.023160.000240.00000（4）弦位法（下转第277页）——276科技信息迭代公式xn+1=xn-f(xn)f(xn)-f(xn-1)(xn-xn-1),取初始值x0=1.75,x1=2。表4弦位法kxkf(xk)01.750.0364583120.666666721.73553720.006993931.73273330.001366041.73205890.000016251.73205080.00000002.用牛顿类法求f(x)=lnx的根迭代公式为xn+1=xn-f(xn)αf(xn)+f′(xn),取初值x0=2,结果参见文献[2]表5牛顿类法α00.30.50.7k=10.38630.02090.18120.2964k=20.08670.00210.00210.0240k=30.00390.00000.00000.0001k=40.00000.00000.00000.0000k=50.00000k=60取α=0时即为牛顿迭代法。从表上可以看出调整迭代公式中的α值,所产生的序列{xk}比牛顿迭代法的序列具有更高的收敛性。五、改进迭代法的比较由表1-表4可以看出弦位法的优点是不需要计算导数，但是收敛速度低于牛顿法，却又高于简单迭代法,只要初值取的合适,迭代的速度还是比较快的。而简单牛顿迭代法同弦位法一样,只要选好初值也可以收敛得很快。但弦位法要比简单牛顿法收敛的速度更快,这完全取决于所取初值。弦位法