《牛顿迭代法资料》由会员分享，可在线阅读，更多相关《牛顿迭代法资料（25页珍藏版）》请在金锄头文库上搜索。
1、牛顿迭代法李保洋数学科学学院信息与计算科学学号：060424067指导老师：苏孟龙摘要：牛顿在17世纪提出的一种在实数域和复数域上近似求解方程的方法，即牛 顿迭代法.迭代法是一种不断用变量的旧值递推新值的过程跟迭代法相对应的是 直接法或者称为一次解法，即一次性解决问题迭代法又分为精确迭代和近似迭代.“牛顿迭代法”属于近似迭代法，本文主要讨论的是牛顿迭代法，方法本身的发 现和演变和修正过程，避免二阶导数计算的Newton迭代法的一个改进，并与中国 古代的算法，即盈不足术，与牛顿迭代算法的比较.关键词：Newton迭代算法；近似求解；收敛阶；数值试验；中国古代数学；九章算术；Duffing方程；非
2、线性方程；收敛速度；渐进性0引言：迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程，跟迭代法相 对应的是直接法或者称为一次解法，即一次性解决问题迭代法又分为精确迭代和 近似迭代“二分法”和“牛顿迭代法”属于近似迭代法.迭代算法是用计算机解决问题的一种基本方法它利用计算机运算速度快、适 合做重复性操作的特点，让计算机对一组指令（或一定步骤）进行重复执行，在 每次执行这组指令（或这些步骤）时，都从变量的原值推出它的一个新值.具体使 用迭代法求根时应注意以下两种可能发生的情况：（1）如果方程无解，算法求出的近似根序列就不会收敛，迭代过程会变成死循 环，因此在使用迭代算法前应先考察方程是否有解，
3、并在程序中对迭代的次数给 予限制.（2）方程虽然有解，但迭代公式选择不当，或迭代的初始近似根选择不合理， 也会导致迭代失败.所以利用迭代算法解决问题，需要做好以下三个方面的工作：1、确定迭代变量在可以用迭代算法解决的问题中，至少存在一个直接或间 接地不断由旧值递推出新值的变量，这个变量就是迭代变量.2、建立迭代关系式.所谓迭代关系式，指如何从变量的前一个值推出其下一 个值的公式（或关系）迭代关系式的建立是解决迭代问题的关键，通常可以使用递 推或倒推的方法来完成.3、对迭代过程进行控制，在什么时候结束迭代过程？这是编写迭代程序必须 考虑的问题不能让迭代过程无休止地重复执行下去迭代过程的控制通常可
4、分为 两种情况：一种是所需的迭代次数是个确定的值，可以计算出来;另一种是所需的 迭代次数无法确定对于前一种情况，可以构建一个固定次数的循环来实现对迭代 过程的控制;对于后一种情况，需要进一步分析出用来结束迭代过程的条件.1牛顿迭代法:牛顿迭代法(Newton method)又称为牛顿-拉夫逊方法(Newton-Rapfson method)，它是牛顿在17世纪提出的一种在实数域和复数域上近似求解方程的方 法多数方程不存在求根公式，因此求精确根非常困难甚至不可能，从而寻找方程 的近似根就显得特别重要.方法使用函数f (x)的泰勒级数的前面几项来寻找方程 f (x) = 0的根.牛顿迭代法是求方程
5、根的重要方法之一，其最大优点是在方程 f (x) = 0的单根附近具有平方收敛性，而且该法还可以用来求方程的重根、复根. 另外该方法广泛用于计算机编程中：解非线性方程f (x) = 0的牛顿(Newton)法是把非线性的方程线性化的一种近 似方法把f (x)的x点附近展开泰勒(Taylor)级0f (x )= f (x )+f (x - x ) f (x )+(x - x )2 凹 +；0 0 0 0 2!取其线性部分作为非线性方程f (x) = 0的近似方程，则有： f (x )+f(x )(x - x ) = 0 ；0 0 0设f(x )h0，则其解为：0f (x )/% (x)；z 0再
6、把f (x)在x附近展开泰勒(Taylor)级数,也取其现行部分作为f (x) = 0的近似方 程若f (x )乂 0，则得:1x = x2 1这样，得到牛顿(Newton)法的一个迭代序列:x = xn+1nf (Tf (x)；n牛顿迭代有十分明显的几何意义，如图所示:当选取初值x以后，过(% ,f (x )做f (x)的切线，其切线方程为:0 0 0y一f (x )= f (x )(x-x )；0 0 0 求此切线方程和x轴的交点，即得：牛顿法正因为有这一明显的几何意义，所以也叫切线法. 例：用牛顿法求下面方程的根f (x)= x3 + 2x2 +10x-20 = 0 ；+ 4 x +10
7、 )；=x Cx3 + 2 x2 +10 x 20n解：因f (x)= 3x2 + 4x +10，所以迭代公式为:xn+1顿法:其公式为xn+1用上面的公式计算，不再需要每步重新计算微商值，所以计算量小一些，但收敛也要慢一些为了避免计算导数还可以采 用差商代导数的方案：xn+1f (x )(-f (x )-/(x )(xnnn-1n-1关于牛顿迭代的收敛有下面结果:如果f (x )在零点附近存在连续的二阶微商,g是f (x)的一重零点，且初始x充分接近于g，那么牛顿迭代是收敛的，且有xn+1 -g-g I2 ；这表明牛顿法是二阶收敛的(平方收敛的).选取x = 1计算结果列表:0N牛顿法弦位法
8、抛物线法011111.4117647058823531.5000000000000001.50000000000000021.3693364705882351.3544303797468361.25000000000000031.3688081886175321.3682702596546871.36853585772136741.3698081078213751.3688103503938871.36880790682018051.3688081078213731.3688081074722171.36880810782168161.3688081078213731.368808107821
9、3731.36880810782137371.3688081078213731.368808107821373从结果可以看出，牛顿法的收敛是很快的，x误差10 -15 .但用牛顿法计算工作量比5较大，因每次计算迭代除了计算函数值外还要计算微商值为此我们提出了简化牛最后考虑f (x)是多项式的特殊情况，此时f (x), f(x)在某个x值，比如x = c 时的计算可用综合除法.f (c )=( (ao+ a )c + a c)c +1 2)c + an-1n设f (x)= axn + a xn+1 + a x + a，除以 x一c，得商q(x)，余r :1n-1nf ( x)= & X- ) c
10、+ ； r(1)其中：q (x ) = b xn-1 + bxn-2 + b x + b ；01n-2 n -1r = b = f (c )；n比较(1)式两边xk的系数便知这些b可以按下表进行:ka0a1a2an-1anb c0bc1b cn 一 2b cn-1b = ab = a + b cb =a + bcb = a + b cb = a + b c0 01 1 022 1n-1n-1n 一 2nnn-1这一过程其实就是秦九韶算法，计算多项式值的嵌套算法:每个括号的值就是这里的bb0n至于导数的计算，注意到式可得:f (x)= q(x)+ q (x)(x-c)；于是：f (c)=q(c)
11、；因此再对b0b进行上述过程，或者再用一次秦九韶算法即可.n2种修正的牛顿迭代法：给出了牛顿迭代法的一种修正形式，并证明了当r H 1/2时修正的牛顿迭代法 是二阶收敛的，当参数r = 1/2时是三阶收敛的，数值实验表明，与经典牛顿迭代 法相比，该修正牛顿迭代法具有一定的优势众所周知，数值求解非线性方程 f (x)= 0的根的方法很多经典的牛顿迭代法是非线性方程组求根的一个基本方 法，它二次收敛到单根，线性收敛到重根牛顿法因收敛速度快而得到广泛应用， 也倍受学者的重视，近年来很多文献中提出各种改进的牛顿方法文献8中利 用Newton迭代法和微分中值定理“中值点”的渐进性，提出了一种多点迭代法.
12、设f (x)满足下述条件：f (x ) e c 2 a,b, f (a) f (b) 0 )，如图所示，作交点的切线交x轴于B0f (x0) 广&)丿f (x0) fAQ线段的斜率为:f (x )E丿0 7由微分中值定理知，存在gf (x )FO0使得:1 + _2而g q x0P(x -(1 -rf4V 0f (x )0(x0VD的坐标点P的导数fxxxx0 Vf (x0)-f=f (x )；0，因此，我们取数r e(1 A上,1 J，在点),x0-(1 r )-(1 - r )作切线PC，图中AD平行于PC 即用代替点A的导数，而仍用点A的迭代格式得到点7重复上述过程，得到多点迭代公式x
13、= xk+1kf (x )(1x - (1- r )k其中 x e a,b， k = 1,2,3,k下面我们对上述事实，从理论上加以严格证明.定理 设f (x)满足条件(A)，则由多点迭代公式(1)产生的序列x 必收敛于na,b上的唯一a，这里x ea,b， f (a)= 0 n证明 函数f (x)在上连续，由连续函数根的存在定理，从f (a)f (b) 0知道f (x)在a, b上根存在，又由条件f(x)H 0及f(x)保号知道，f(x)在a, b上不变号，故f (x)在a,b上是单调函数，因此f (x)在a,b上根a存在且唯一由定理条件曲线y = f (x)可有如下四种不同情况:(1) f (a) 0, f(x) 0，则 f(x)单调上升，f(a)f(b) 0 ； f (a) 0, f”(x) 0，则 f(x)单调下降，f (a)f(b) 0 ； f(a)0,f(b)0，则f(x)单调上升，f(a)
