牛顿迭代法李保洋数学科学学院信息与计算科学学号：060424067指导老师：苏孟龙摘要：牛顿在17世纪提出的一种在实数域和复数域上近似求解方程的方法，即牛 顿迭代法•迭代法是一种不断用变量的旧值递推新值的过程.跟迭代法相对应的是 直接法或者称为一次解法，即一次性解决问题•迭代法又分为精确迭代和近似迭代.“牛顿迭代法”属于近似迭代法，本文主要讨论的是牛顿迭代法，方法本身的发 现和演变和修正过程，避免二阶导数计算的New ton迭代法的一个改进，并与中国 古代的算法，即盈不足术，与牛顿迭代算法的比较.关键词：New ton迭代算法；近似求解；收敛阶；数值试验；中国古代数学；九章算术；Duffing方程；非线性方程；收敛速度；渐进性0引言：迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程，跟迭代法相 对应的是直接法或者称为一次解法，即一次性解决问题•迭代法又分为精确迭代和 近似迭代•“二分法”和“牛顿迭代法”属于近似迭代法.迭代算法是用计算机解决问题的一种基本方法•它利用计算机运算速度快、适 合做重复性操作的特点，让计算机对一组指令（或一定步骤）进行重复执行，在 每次执行这组指令（或这些步骤）时，都从变量的原值推出它的一个新值.具体使 用迭代法求根时应注意以下两种可能发生的情况：（1） 如果方程无解，算法求出的近似根序列就不会收敛，迭代过程会变成死循 环，因此在使用迭代算法前应先考察方程是否有解，并在程序中对迭代的次数给 予限制.（2） 方程虽然有解，但迭代公式选择不当，或迭代的初始近似根选择不合理， 也会导致迭代失败.所以利用迭代算法解决问题，需要做好以下三个方面的工作：1、 确定迭代变量•在可以用迭代算法解决的问题中，至少存在一个直接或间 接地不断由旧值递推出新值的变量，这个变量就是迭代变量.2、 建立迭代关系式•所谓迭代关系式，指如何从变量的前一个值推出其下一 个值的公式（或关系）.迭代关系式的建立是解决迭代问题的关键，通常可以使用递 推或倒推的方法来完成.3、 对迭代过程进行控制，在什么时候结束迭代过程？这是编写迭代程序必须 考虑的问题•不能让迭代过程无休止地重复执行下去•迭代过程的控制通常可分为 两种情况：一种是所需的迭代次数是个确定的值，可以计算出来;另一种是所需的 迭代次数无法确定•对于前一种情况，可以构建一个固定次数的循环来实现对迭代 过程的控制；对于后一种情况，需要进一步分析出用来结束迭代过程的条件.1牛顿迭代法:牛顿迭代法(New ton met hod)又称为牛顿-拉夫逊方法(New ton-Rapfson met hod)，它是牛顿在17世纪提出的一种在实数域和复数域上近似求解方程的方 法•多数方程不存在求根公式，因此求精确根非常困难甚至不可能，从而寻找方程 的近似根就显得特别重要•方法使用函数f x的泰勒级数的前面几项来寻找方程f x 0的根•牛顿迭代法是求方程根的重要方法之一，其最大优点是在方程f x 0的单根附近具有平方收敛性，而且该法还可以用来求方程的重根、复根. 另外该方法广泛用于计算机编程中：解非线性方程f X 0的牛顿(Newton)法是把非线性的方程线性化的一种近似方法•把f x的X。
点附近展开泰勒仏⑴级f'' x f x f x fxxf'x x x 2 0o o o o 2!取其线性部分作为非线性方程f x0的近似方程，则有:f x f' x x x 0 ;0 0 0设f' X 0,则其解为:0再把f x在X附近展开泰勒(Taylor级数,也取其现行部分作为f x 0的近似方1程•若f' x 0,则得：1这样，得到牛顿(Newton)法的一个迭代序列:牛顿迭代有十分明显的几何意义，如图所示:xx0当选取初值X以后，过x ,f X 做f X的切线，其切线方程为:0 0 0y f x f' x0 0求此切线方程和x轴的交点，即得：x x1 0牛顿法正因为有这一明显的几何意义，所以也叫切线法.例：用牛顿法求下面方程的根f x X3 2x2 10x 20 0 ；解：因f' x 3x2 4x 10，所以迭代公式为：x3 2x2 10x 20 J 3x2 4x 10 ；选取x 1计算结果列表:0N牛顿法弦位法抛物线法011111.4117647058823531.5000000000000001.50000000000000021.3693364705882351.3544303797468361.25000000000000031.3688081886175321.3682702596546871.36853585772136741.3698081078213751.3688103503938871.36880790682018051.3688081078213731.3688081074722171.36880810782168161.3688081078213731.3688081078213731.36880810782137371.3688081078213731.368808107821373从结果可以看出，牛顿法的收敛是很快的，X误差10 15 •但用牛顿法计算工作量比5较大，因每次计算迭代除了计算函数值外还要计算微商值•为此我们提出了简化牛 顿法：其公式为X x f X / f' X ；用上面的公式计算，不再需要每步重新n 1 n n 0计算微商值，所以计算量小一些，但收敛也要慢一些.为了避免计算导数还可以采 用差商代导数的方案：f XX nn f X f Xn n 1关于牛顿迭代的收敛有下面结果:如果f x在零点附近存在连续的二阶微商,是f X的一重零点，且初始X充分接近于，0那么牛顿迭代是收敛的，且有f'' / 2f'这表明牛顿法是二阶收敛的（平方收敛的）.最后考虑f X是多项式的特殊情况，此时f X ,f' X在某个X值，比如x c时的计算可用综合除法.设 f X axn a Xn 1 a X a，除以 x c，得商 q x，余 r :1 n 1 n••f x q x xc；r(1)其中.q X b Xn 1 b Xn 20 1b x b ;n 2 n 1r b -c ；n比较（1式两边xk的系数便知这些b可以按下表进行:ka0a1a2an 1anb c0b c1b cn 2b cn 1b a0 0b a b c1 1 0b a b c2 2 1b a b cn 1 n 1 n 2b a b cn n n 1这一过程其实就是秦九韶算法，计算多项式值的嵌套算法：f c aacacc a c a ；0 1 2 n 1 n每个括号的值就是这里的b…b・ …0 n至于导数的计算，注意到⑴式可得：f' x q x q' x x c ；于是：f' c q c ；因此再对b b进行上述过程，或者再用一次秦九韶算法即可.0 n2—种修正的牛顿迭代法：给出了牛顿迭代法的一种修正形式，并证明了当r 1/2时修正的牛顿迭代法 是二阶收敛的，当参数r 1/2时是三阶收敛的，数值实验表明，与经典牛顿迭代 法相比，该修正牛顿迭代法具有一定的优势•众所周知，数值求解非线性方程f x 0的根的方法很多•经典的牛顿迭代法是非线性方程组求根的一个基本方 法，它二次收敛到单根，线性收敛到重根•牛顿法因收敛速度快而得到广泛应用， 也倍受学者的重视，近年来很多文献中提出各种改进的牛顿方法•文献［8］中利 用New ton迭代法和微分中值定理“中值点”的渐进性，提出了一种多点迭代法.设f（x）满足下述条件:f x C2a,b, f a f b 0 ;f' x 0， f'' x 在［a,b］上保号. （A）根据微分中值定理，存在 （a,b）,使得：工工 f'，而im a 1b a b a b a 2因此，当b与a的距离无限接近时有：a 2 b a附近，得随区间变小而趋于其渐近位置•图所示迭代法构造图本方乙案基于上述考虑，给出一种通过迭代点选取另一个点，利用两个点进行迭代求近 似根的新方法•这种方法虽然在迭代中又只利用了一个其它点，但其计算精度却相 当高，它的某一种特殊情形恰是通常的New ton迭代法•为了更加直观起见，我们 通过几何直观图来构造这种迭代法•设f x满足条件（A）,当选定初值x0f x（仅要求f X f" x 0）,如图所示，作交点的切线交x轴于B x h-,0 ,0 0 f' x0AQ线段的斜率为：f x f x f x 00 0 f' x0 f xx x —0 0 f' x0f x由微分中值定理知，存在 x 使得：0 f' x 00f xx 00 f' x0f xf x f x 匚0 0 f' x0— f' x ；f x 0x x —0 0 f' x01 f x 1-x -~—,因此，我们取数r -,1 ,在点2 0 f' x 2f xP x 1 r I f x0 f' x 00f x1 r 0 f' x0作切线PC ,图中AD平行于PC •即用0f x点P的导数f' x 1 r —代替点A的导数，而仍用点A的迭代格式得到点 0 f' x0D的坐标,0 ；f xD x 0—0 f xf' x 1 r 00 f' x0重复上述过程,得到多点迭代公式f x k f x f' x 1 r k k f' xk其中 x [a,b], k 1,2,3,・k下面我们对上述事实…从理论上加以严格证明.定理设f x满足条件(A),则由多点迭代公式(1)产生的序列｛x ｝必收敛于n[a,b]上的唯一a,这里 x a,b , f a 0 .n证明 函数f x在上连续，由连续函数根的存在定理，从f a f b 0知道 f X在a,b上根存在，又由条件f' X 0及f'' x保号知道，f' x在a,b上不 变号，故f x在a,b上是单调函数，因此f x在a,b上根a存在且唯一.由定理 条件曲线y f x可有如下四种不同情况：(1) f a 0, f b 0, f" x 0,则 f' x 单调上升，f' a f' b 0 ；(2) f a 0, f b 0, f" x 0,则 f' x 单调下降，f' a f' b 0 ;(3) f a 0,f b 0, f" x 0,则 f' x 单调上升，f' a f' b 0 ;(4) f a 0,f b 0, f" x 0,则 f' x 单调下降，f' a f' b 0 •通过对自变量的变号或对函数的变号可将四种情况归结为一种情况，所以我 们只需对情况（一）证明迭代过程（1）攵敛就可以了.若初值X a,b ,x0a，所以fx0 0,故有f'f X0f Xr 0_f' X0x0；x 0f' x0f X-0 f X。