牛顿迭代法

牛顿迭代法李保洋数学科学学院信息与计算科学学号：060424067指导老师：苏孟龙摘要：牛顿在17世纪提出的一种在实数域和复数域上近似求解方程的方法，即牛顿迭代法.迭代法是一种不断用变量的旧值递推新值的过程.跟迭代法相对应的是直接法或者称为一次解法，即一次性解决问题.迭代法又分为精确迭代和近似迭代.“牛顿迭代法”属于近似迭代法，本文主要讨论的是牛顿迭代法，方法本身的发现和演变和修正过程，避免二阶导数计算的Newton迭代法的一个改进，并与中国古代的算法，即盈不足术，与牛顿迭代算法的比较.关键词：Newton迭代算法；近似求解；收敛阶；数值试验；中国古代数学；九章算术；Duffing方程；非线性方程；收敛速度；渐进性0引言：迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程，跟迭代法相对应的是直接法或者称为一次解法，即一次性解决问题.迭代法又分为精确迭代和近似迭代.“二分法”和“牛顿迭代法”属于近似迭代法.迭代算法是用计算机解决问题的一种基本方法.它利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令（或一定步骤）进行重复执行，在每次执行这组指令（或这些步骤）时，都从变量的原值推出它的一个新值.具体使用迭代法求根时应注意以下两种可能发生的情况：(1)如果方程无解，算法求出的近似根序列就不会收敛，迭代过程会变成死循环，因此在使用迭代算法前应先考察方程是否有解，并在程序中对迭代的次数给予限制.(2)方程虽然有解，但迭代公式选择不当，或迭代的初始近似根选择不合理，也会导致迭代失败.所以利用迭代算法解决问题，需要做好以下三个方面的工作：1、确定迭代变量.在可以用迭代算法解决的问题中，至少存在一个直接或间接地不断由旧值递推出新值的变量，这个变量就是迭代变量.2、建立迭代关系式.所谓迭代关系式，指如何从变量的前一个值推出其下一个值的公式(或关系).迭代关系式的建立是解决迭代问题的关键，通常可以使用递推或倒推的方法来完成.3、对迭代过程进行控制，在什么时候结束迭代过程？这是编写迭代程序必须考虑的问题.不能让迭代过程无休止地重复执行下去.迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来;另一种是所需的迭代次数无法确定.对于前一种情况，可以构建一个固定次数的循环来实现对迭代过程的控制;对于后一种情况，需要进一步分析出用来结束迭代过程的条件.1牛顿迭代法：洛阳师范学院本科毕业论文1yxOx*x1x0牛顿迭代法(Newtonmethod)又称为牛顿-拉夫逊方法(Newton-Rapfsonmethod)，它是牛顿在17世纪提出的一种在实数域和复数域上近似求解方程的方法.多数方程不存在求根公式，因此求精确根非常困难甚至不可能，从而寻找方程的近似根就显得特别重要.方法使用函数fx的泰勒级数的前面几项来寻找方程0fx的根.牛顿迭代法是求方程根的重要方法之一，其最大优点是在方程0fx的单根附近具有平方收敛性，而且该法还可以用来求方程的重根、复根.另外该方法广泛用于计算机编程中：解非线性方程0fx的牛顿(Newton)法是把非线性的方程线性化的一种近似方法.把fx的0x点附近展开泰勒(Taylor）级''20'00002!fxfxfxfxxfxxx；取其线性部分作为非线性方程0fx的近似方程，则有：'0000fxfxxx；设'00fx，则其解为：0'100fxxxfx；再把fx在1x附近展开泰勒(Taylor)级数，也取其现行部分作为0fx的近似方程.若'10fx，则得：1'211fxxxfx；这样，得到牛顿(Newton)法的一个迭代序列：'1nnnnfxxxfx；牛顿迭代有十分明显的几何意义，如图所示：洛阳师范学院本科毕业论文2当选取初值0x以后，过00,xfx做fx的切线，其切线方程为：'000yfxfxxx；求此切线方程和x轴的交点，即得：'1000xxfxfx；牛顿法正因为有这一明显的几何意义，所以也叫切线法.例：用牛顿法求下面方程的根32210200fxxxx；解：因'23410fxxx，所以迭代公式为：3221210203410nnxxxxxxx；选取01x计算结果列表：N牛顿法弦位法抛物线法011111.4117647058823531.5000000000000001.50000000000000021.3693364705882351.3544303797468361.25000000000000031.3688081886175321.3682702596546871.36853585772136741.3698081078213751.3688103503938871.36880790682018051.3688081078213731.3688081074722171.36880810782168161.3688081078213731.3688081078213731.36880810782137371.3688081078213731.368808107821373从结果可以看出，牛顿法的收敛是很快的，5x误差1510.但用牛顿法计算工作量比较大，因每次计算迭代除了计算函数值外还要计算微商值.为此我们提出了简化牛顿法：其公式为'10nnnxxfxfx；用上面的公式计算，不再需要每步重新计算微商值，所以计算量小一些，但收敛也要慢一些.为了避免计算导数还可以采用差商代导数的方案：111nnnnnnnfxxxxxfxfx；关于牛顿迭代的收敛有下面结果：如果fx在零点附近存在连续的二阶微商，是fx的一重零点，且初始0x充分接近于，那么牛顿迭代是收敛的，且有2'''1/2nnxffx；这表明牛顿法是二阶收敛的（平方收敛的）.洛阳师范学院本科毕业论文3最后考虑fx是多项式的特殊情况，此时fx，'fx在某个x值，比如xc时的计算可用综合除法.设111nnnnfxaxaxaxa，除以xc，得商qx，余r：fxqxxcr；（1）其中：120121nnnnqxbxbxbxb；nrbfc；比较(1)式两边kx的系数便知这些kb可以按下表进行：0a1a2a1nana0bc1bc2nbc1nbc00ba110babc221babc112nnnbabc1nnnbabc这一过程其实就是秦九韶算法，计算多项式值的嵌套算法：0121nnfcaacaccaca；每个括号的值就是这里的0nbb.至于导数的计算，注意到(1)式可得：''fxqxqxxc；于是：'fcqc；因此再对0nbb进行上述过程，或者再用一次秦九韶算法即可.2一种修正的牛顿迭代法：给出了牛顿迭代法的一种修正形式，并证明了当1/2r时修正的牛顿迭代法是二阶收敛的，当参数1/2r时是三阶收敛的，数值实验表明，与经典牛顿迭代法相比，该修正牛顿迭代法具有一定的优势.众所周知，数值求解非线性方程0fx的根的方法很多.经典的牛顿迭代法是非线性方程组求根的一个基本方法，它二次收敛到单根，线性收敛到重根.牛顿法因收敛速度快而得到广泛应用，也倍受学者的重视，近年来很多文献中提出各种改进的牛顿方法.文献［8］中利用Newton迭代法和微分中值定理“中值点”的渐进性，提出了一种多点迭代法.洛阳师范学院本科毕业论文4设()fx满足下述条件：2,fxcab，0fafb；'0fx，''fx在[,]ab上保号.(A)根据微分中值定理，存在(,)ab，使得：'fbfafba，而1lim2baaba.因此，当b与a的距离无限接近时有：12aba.也就是说，在区间(,)ab不甚大时，中值点一定在其渐近位置12aba附近，并随区间变小而趋于其渐近位置.图所示迭代法构造图本方案基于上述考虑，给出一种通过迭代点选取另一个点，利用两个点进行迭代求近似根的新方法.这种方法虽然在迭代中又只利用了一个其它点，但其计算精度却相当高，它的某一种特殊情形恰是通常的Newton迭代法.为了更加直观起见，我们通过几何直观图来构造这种迭代法.设fx满足条件(A)，当选定初值0x(仅要求00fxfx)，如图所示，作交点的切线交x轴于B00'0,0fxxfx，AQ线段的斜率为：000'0000'0fxfxfxfxfxxxfx.由微分中值定理知，存在000'0,fxxxfx使得：洛阳师范学院本科毕业论文5000'0'0000'0fxfxfxfxfxfxxxfx；而0000''0012fxfxxxfxfx，因此，我们取数1,12r，在点0000''001,1fxfxPxrfxrfxfx作切线PC，图中AD平行于PC.即用点P的导数0'0'01fxfxrfx代替点A的导数，而仍用点A的迭代格式得到点D的坐标00'00'0,01fxDxfxfxrfx；重复上述过程，得到多点迭代公式1''1kkkkkkfxxxfxfxrfx；(2)其中[,]kxab，1,2,3,k.下面我们对上述事实，从理论上加以严格证明.定理设fx满足条件(A)，则由多点迭代公式(1)产生的序列{nx}必收敛于[,]ab上的唯一a，这里,nxab，0fa.证明函数fx在上连续，由连续函数根的存在定理，从0fafb知道fx在,ab上根存在，又由条件'0fx及''fx保号知道，'fx在,ab上不变号，故fx在,ab上是单调函数，因此fx在,ab上根a存在且唯一.由定理条件曲线yfx可有如下四种不同情况：(1)0,0,0fafbfx，则'fx单调上升，''0fafb；(2)0,0,0fafbfx，则'fx单调下降，''0fafb；洛阳师范学院本科毕业论文6(3)0,0,0fafbfx，则'fx单调上升，''0fafb；(4)0,0,0fafbfx，则'fx单调下降，''0fafb.通过对自变量的变号或对函数的变号可将四种情况归结为一种情况，所以我们只需对情况(一)证明迭代过程(1)收敛就可以了.若初值0,,,nxabxa所以00fx，故有0100'00'01fxxxxfxfxrfx；''0001000'''000000'''000111fxfafxafxaxxxxfxfxfxfxrfxrfxrfxfxfx；一方面，0.ax，且'00fxfxa.下证0''0'01fxfxfxrfx.若0''0'01fxfxfxrfx，由'fx的单调性有，x，