牛顿迭代法.doc

1、 洛阳师范学院本科毕业论文 牛顿迭代法李保洋数学科学学院 信息与计算科学 学号：060424067指导老师：苏孟龙摘要：牛顿在17世纪提出的一种在实数域和复数域上近似求解方程的方法，即牛顿迭代法.迭代法是一种不断用变量的旧值递推新值的过程.跟迭代法相对应的是直接法或者称为一次解法，即一次性解决问题.迭代法又分为精确迭代和近似迭代.“牛顿迭代法”属于近似迭代法，本文主要讨论的是牛顿迭代法，方法本身的发现和演变和修正过程，避免二阶导数计算的Newton迭代法的一个改进，并与中国古代的算法，即盈不足术，与牛顿迭代算法的比较.关键词：Newton迭代算法；近似求解；收敛阶；数值试验；中国古代数学；九章

2、算术；方程；非线性方程；收敛速度；渐进性0 引言：迭代法也称辗转法，是一种不断用变量的旧值递推新值的过程，跟迭代法相对应的是直接法或者称为一次解法，即一次性解决问题.迭代法又分为精确迭代和近似迭代.“二分法”和“牛顿迭代法”属于近似迭代法. 迭代算法是用计算机解决问题的一种基本方法.它利用计算机运算速度快、适合做重复性操作的特点，让计算机对一组指令（或一定步骤）进行重复执行，在每次执行这组指令（或这些步骤）时，都从变量的原值推出它的一个新值.具体使用迭代法求根时应注意以下两种可能发生的情况： (1) 如果方程无解，算法求出的近似根序列就不会收敛，迭代过程会变成死循环，因此在使用迭代算法前应先考

3、察方程是否有解，并在程序中对迭代的次数给予限制. (2) 方程虽然有解，但迭代公式选择不当，或迭代的初始近似根选择不合理，也会导致迭代失败. 所以利用迭代算法解决问题，需要做好以下三个方面的工作：1、确定迭代变量.在可以用迭代算法解决的问题中，至少存在一个直接或间接地不断由旧值递推出新值的变量，这个变量就是迭代变量.2、建立迭代关系式.所谓迭代关系式，指如何从变量的前一个值推出其下一个值的公式(或关系).迭代关系式的建立是解决迭代问题的关键，通常可以使用递推或倒推的方法来完成.3、对迭代过程进行控制，在什么时候结束迭代过程？这是编写迭代程序必须考虑的问题.不能让迭代过程无休止地重复执行下去.迭

4、代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来;另一种是所需的迭代次数无法确定.对于前一种情况，可以构建一个固定次数的循环来实现对迭代过程的控制;对于后一种情况，需要进一步分析出用来结束迭代过程的条件.1牛顿迭代法：牛顿迭代法(Newton method)又称为牛顿-拉夫逊方法(Newton-Rapfson method)，它是牛顿在17世纪提出的一种在实数域和复数域上近似求解方程的方法.多数方程不存在求根公式，因此求精确根非常困难甚至不可能，从而寻找方程的近似根就显得特别重要.方法使用函数的泰勒级数的前面几项来寻找方程的根.牛顿迭代法是求方程根的重要方法之一，

5、其最大优点是在方程的单根附近具有平方收敛性，而且该法还可以用来求方程的重根、复根.另外该方法广泛用于计算机编程中：解非线性方程的牛顿(Newton)法是把非线性的方程线性化的一种近似方法.把的点附近展开泰勒(Taylor）级；取其线性部分作为非线性方程的近似方程，则有：； 设，则其解为： ； 再把在附近展开泰勒(Taylor)级数，也取其现行部分作为的近似方程.若，则得： ； y xO x* x1 x0这样，得到牛顿(Newton)法的一个迭代序列：；牛顿迭代有十分明显的几何意义，如图所示： 当选取初值以后，过做的切线，其切线方程为：； 求此切线方程和轴的交点，即得： ； 牛顿法正因为有这一明

6、显的几何意义，所以也叫切线法.例：用牛顿法求下面方程的根 ； 解：因，所以迭代公式为：；选取计算结果列表：N牛顿法弦位法抛物线法011111.4117647058823531.5000000000000001.50000000000000021.3693364705882351.3544303797468361.25000000000000031.3688081886175321.3682702596546871.36853585772136741.3698081078213751.3688103503938871.36880790682018051.3688081078213731.3688

7、081074722171.36880810782168161.3688081078213731.3688081078213731.36880810782137371.3688081078213731.368808107821373从结果可以看出，牛顿法的收敛是很快的，误差.但用牛顿法计算工作量比较大，因每次计算迭代除了计算函数值外还要计算微商值.为此我们提出了简化牛顿法：其公式为；用上面的公式计算，不再需要每步重新计算微商值，所以计算量小一些，但收敛也要慢一些.为了避免计算导数还可以采用差商代导数的方案：； 关于牛顿迭代的收敛有下面结果：如果在零点附近存在连续的二阶微商，是的一重零点，且初始充

8、分接近于，那么牛顿迭代是收敛的，且有； 这表明牛顿法是二阶收敛的（平方收敛的）.最后考虑是多项式的特殊情况，此时，在某个值，比如时的计算可用综合除法.设 ，除以，得商，余： ； （1）其中：； ；比较(1)式两边的系数便知这些可以按下表进行：这一过程其实就是秦九韶算法，计算多项式值的嵌套算法：；每个括号的值就是这里的.至于导数的计算，注意到(1)式可得：；于是：；因此再对进行上述过程，或者再用一次秦九韶算法即可.2一种修正的牛顿迭代法：给出了牛顿迭代法的一种修正形式，并证明了当时修正的牛顿迭代法是二阶收敛的，当参数时是三阶收敛的，数值实验表明，与经典牛顿迭代法相比，该修正牛顿迭代法具有一定的优

9、势.众所周知，数值求解非线性方程的根的方法很多.经典的牛顿迭代法是非线性方程组求根的一个基本方法，它二次收敛到单根，线性收敛到重根.牛顿法因收敛速度快而得到广泛应用，也倍受学者的重视，近年来很多文献中提出各种改进的牛顿方法.文献8中利用Newton迭代法和微分中值定理“中值点”的渐进性，提出了一种多点迭代法.设满足下述条件：，； ， 在上保号. (A)根据微分中值定理，存在，使得：，而.因此，当与的距离无限接近时有：.也就是说，在区间不甚大时，中值点一定在其渐近位置附近，并随区间变小而趋于其渐近位置.图所示迭代法构造图本方案基于上述考虑，给出一种通过迭代点选取另一个点，利用两个点进行迭代求近似

10、根的新方法.这种方法虽然在迭代中又只利用了一个其它点，但其计算精度却相当高，它的某一种特殊情形恰是通常的Newton迭代法.为了更加直观起见，我们通过几何直观图来构造这种迭代法.设满足条件(A)，当选定初值(仅要求)，如图所示，作交点的切线交轴于 ， 线段的斜率为： . 由微分中值定理知，存在使得：； 而，因此，我们取数，在点作切线，图中平行于.即用点的导数代替点的导数，而仍用点的迭代格式得到点的坐标； 重复上述过程，得到多点迭代公式 ； (2) 其中，.下面我们对上述事实，从理论上加以严格证明.定理 设满足条件(A)，则由多点迭代公式(1)产生的序列必收敛于上的唯一，这里，.证明 函数在上连

11、续，由连续函数根的存在定理，从知道在上根存在，又由条件及保号知道，在上不变号，故在上是单调函数，因此在上根存在且唯一.由定理条件曲线可有如下四种不同情况：(1) ，则单调上升，；(2) ，则单调下降，；(3) ，则单调上升， ；(4) ，则单调下降，.通过对自变量的变号或对函数的变号可将四种情况归结为一种情况，所以我们只需对情况(一)证明迭代过程(1)收敛就可以了.若初值所以，故有； ；一方面，且.下证.若，由的单调性有，又因为，因此有，与Newton迭代法的收敛性矛盾.由(一)的假设及可得：； 一般地，若，同样可以证明由式(2)得到的满足.所以由式(1)产生的迭代序列单调下降且有下界.依极限

12、理论必有极限.对式(2)两边取极限，由极限理论可以求得.再由，可知函数方程在上的根是唯一的，因此有.当时，式(2)即为Newton迭代公式.本文给出的这种多点迭代方法不仅可以被广泛应用于方程的近似求根，更重要的是它为人们提供了一种新的迭代思想，拓宽人们在方程近似求根方面的思路.例 计算在区间内的一个实根.我们已知有一个精确到十二位有效数字的实根.取，以Newton迭代法计算(记作)，取， 以式(1)计算(记作)，其结果列表如表1.表1 计算结果：迭代次数N01234532.362.0951360372.0945516742.9455148232.184684462.0947263042.094

13、551482从这个数值例子，我们可以看出，式(2)比Newton迭代法的收敛速度快得多，只进行三次迭代就已得满足精度要求的值了，而Newton迭代法需迭代5次才可得到满足精度要求的值.式(2)可以被广泛应用，特别是编成数学软件后，用计算机求解方程近似根效果会更加显著.3另外一种牛顿迭代法的修正：Newton迭代法是方程求根的一种简单而直观的近似方法，但在实际运用中，我们常常觉察到，这种方法仅仅是利用了迭代点及该点的导数值，而没有充分利用其他点及其导数值.是否存在可利用的点，这些点我们应怎样确定.文1给出了一种方法，但这种方法求根的关键在适当地选取和或.选取不适当，就会出现某次迭代的值不是迭代序

14、列中的值.因此，我们会问这些值特别是能否不依靠人为选取，而通过迭代点来选取，本文将利用Newton迭代法和微分中值定理“中值点”的渐近性，来寻找除迭代点以外的可利用点，给出一种多点迭代方法.设满足下述条件：；在上保号. (A)根据微分中值定理，存在，使得而.因此，当与的距离无限接近时有：.也就是说，在区间不甚大时，中值点一定在其渐近位置附近，并随区间变小而趋于其渐近位置.本方案基于上述考虑，给出一种通过迭代点选取另一个点，利用两个点进行迭代求近似根的新方法.设满足下列条件(A)：(1) 在区间在区间上存在二阶导数；(2) 在上不等于零；(3) 在上不变号；(4) ；为了更为直观，我们通过几何直

15、观图来构造多点迭代法.设满足条件(A)，当选定初值（仅要求），如图所示：做点的切线交轴于，线段的斜率为：；由微分中值定理知，存在使得：； 而，因此，我们取数，在点作切线，图中平行于.即用点的导数代替点的导数，而仍用点的迭代格式得到点的坐标 ； (3)主要对(3)式的分子用与的和代替，这样就得到新的迭代公式：； (4)如果令 ；则：； 从而可知(4)式中迭代函数为：； 引理15 对于迭代公式，如果在所求的根的邻近连续并且：，则该公式在的邻近是阶收敛的.定理1 设方程的根为，函数在的的邻域内有至少四阶连续导数，且，则迭代公式(4)在的邻近至少是三阶收敛的.证明 迭代公式(4)的迭代函数为：，其中，

16、由于方程的根为所以，从而可知，；对求导数得：；同理可得：. 由引理知迭代公式(4)在邻近至少是三阶收敛的.引理2（4）假设函数在区间上存在二阶导数，且满足下列条件(1) 在上不等于零；(2) 在上不变号；(3) ；(4) 设，且满足条件；则由Newton迭代法得到的序列收敛于的惟一根.定理2假设函数在区间上存在二阶导数，且满足下列条件(1) 在上不等于零；(2) 在上不变号；(3) ；(4) 设，且满足条件.则由多点迭代公式(4)得到的序列收敛于的惟一根.证明函数在上连续，由连续函数根的存在定理，从知道在上根存在，又由条件及的保号性知道，在上不变号，故在上是单调函数，因此在上的根存在且惟一.由

17、定理条件，曲线可有如下四种不同情况：(a) ，则单调上升，；(b) ，则单调下降，；(c) ，则单调上升，；(d) ，则单调下降，.通过对自变量的变号或对函数的变号可以将四种情况归结为一种情况，所以我们只需对其中一种情况证明迭代过程(4)是收敛的就可以了.下面仅就情况(a)证明定理2，其余情况的证明类似.对情况(a)来说此时在上的根存在且惟一，且在上单调递增.首先证明，对任何初始近似，由迭代公式(4)求出的逐次近似都属于，并且单调递减. 事实上，由引理2的证明我们可知，只要，就有，即，再由(3)式得，另一方面(3)式可化为：；其中.由单调递增且知，故因而由(4)式产生的序列单调递减并有下界，故

18、存在.设，(4)式两边当时求极限得：； ； 可知 ； ，在上单调递增，且所以：；因此得：.本方法代方法比Newton和文4的迭代法的收敛速度明显要快，而且对于，越大效果越差！对于例1，用MATLAB程序运算格式(4)，当时，在之前迭代格式会产生负值.所以，格式(4)的收敛速度和的选取有关. 对于定理2中的四个条件，在MATLAB中通过简单的程序即可验证.4 中国古代算法盈不足术与牛顿迭代算法的比较：首先介绍盈不足术 九章算术中的第七章是盈不足术，这是求解方程的一种最古老的方法.为了说明该方法的基本思想，我们考虑该章的第一个例子：今有共买物，人出8，盈3；人出7，不足4，问人数、物价各几何？其求

19、解过程为(见图1)：(1) 把出率(8)和(7)放在第一行；(2) 把盈数(3)和不足数(4)放置在出率下面；(3) 计算维积(交差积)得(32)和(21)，得和为(53)；(4) 盈减去不足数为；(5) 从而得物价为；用现代数学的观点，盈不足术可表示为：设和为两个近似物价，和分别表示为盈或不足数，则物价为：;人数为；正如白尚恕7指出的那样，在隋唐(581618年AD)盈不足术在中东被广泛流传，最早的阿拉伯算术书是由al-Khowarizmi在公元825年写的，英文中的算术一词(algorithm)来自他的名字，他应该对九章算术和其他古代中国巨著很了解，并把盈不足术称为中国方法.Khitai指

20、China，类似的写法有Khatai，Chatayn，Chataain等等.普遍认为中国算法是通过古代著名的意大利数学家Leonardo Fibonacci(1170?1250?年)传给西方的，据记载Fibonacci随他父亲周游了埃及、西西里、希腊和叙利亚，这次周游使他接触了东方和阿拉伯的计算方法.在1202年，即他回家后不久他就出版了著名的算经Liber Abaci.该书也介绍了盈不足术，并把这种方法称为中国规则，这个名字来自中东，在那里中国算法称为Hisabl-Chatin，里Chation指China该书中的一些例子和算法和中国古代数学巨著完全一样.如在4世纪的孙子算经：今有物不知其数

21、，三三数之胜二，五五数之胜三，七七数之胜二，问物几何？该问题的解题方法就是数论中的中国余数定理：在Fibonacci的算经中阿拉伯语DeRegulisel-Chatavn被译成拉丁文DuarumFalsdrumPosicionumRegula所以在西方这种方法被称作双假定方法，这实际上是九章算术中的盈不足术，即中国算法，它起源于中国是毫无疑问的，这正如钱宝琮8指出的那样可惜的是很多西方人认为这种方法起源于印度，并被阿拉伯人所掌握所以本作者强烈建议把双假设法改称为中国算法或中国方法.中国算法与牛顿迭代算法考虑方程设为方程的两个近似解，于是我们得残量和应用中国算法，我们可得； （5）在九章算术中给

22、出了在下列情况下的一些不等式：(1)双盈，即和(2)双亏，即和；(3)一盈一亏，即；上述算法可以根据不等式的性质确定更合适的两个数或，再进行计算定更精确的近似解，为了与牛顿迭代算法比较，我们把(5)写成如下形式： ； 如果引入导数，它定义为；那么我们马上可得：；这就是著名的牛顿迭代法，当两个近似值和位于真解的两侧时，即，中国算法比牛顿迭代算法具有很大的优势，牛顿迭代算法可以更进一步的优化发展，可参考文献10，11.中国算法的改进：中国算法可以看成是通过两个近似解的线性近似方法，见图2为了提高中国算法的精度，我们用三点，而不用两点，用抛物线拟合该曲线，我们得近似解为： ； 式中；综合概述：迭代算

23、法是一种用途非常广泛的方法，本文不仅介绍了这个方法很好的诠释这个方法， 而且做了牛顿迭代法的两种修正，更做了牛顿迭和与中国古代算法的比较，不仅试读者更好理解了这个方法，更开阔了读者的视野，使读者更能留下研究的空间.参考文献：1 徐萃薇，孙绳武.计算方法引论（第三版）M.北京：高等教育出版社，2007.2 龙爱芳.避免二阶导数计算的迭代法J.浙江工业大学学报，2005， 33(5): 602604.3 李庆扬，王能超.数值分析M.武汉：华中科技大学出版社，1986.4 张新东，王秋华.避免二阶导数计算的Newton迭代法的一个改进J.山东大学学报，2007，42（7）：7276.5 何吉欢.盈不

24、足术与牛顿迭代算法的比较J.应用数学和力学，2002，23（12）：12561259.6 王晓峰.一种修正的牛顿迭代法J，2010，33（1）长春理工大学学报，178179.7 白尚恕.九章算术注释M.北京：科学出版社，1983.8 钱宝琮.中国数学史M.北京：科学出版社，1992.9 陈新一.一种多点迭代方法J.甘肃教育学报（自然科学版），2001，15（1）：1316.10HeJi-huan.Improvement of Newton interation menthod J.International Journal of Nonlinear Science and Numerical

25、Simulation 2000，1(3):239240. 11HeJi-huan.Newton-like iteration menthod for solving algebraice quationsJ. Communication NumSimulation，1998，3(2):106109Newton iterationLI Bao YangMathematical Sciences Information and Computing Science NO：060424067 Instructor :SU MenglongSummary：In the 17th century， New

26、ton introduced a method of solve equations approximately in real number domain and complex domain， that is Newton Iteration， a process of recursion new value constantly with the old value of variable. Correspond with the Iterative Method is A Direct Method or as A Solution， that is a one-time proble

27、m solving. Iteration is divided into exact iterative and approximate iterative. Newton Iterative Method is belong to approximate iterative methods. This article mainly focuses on the Newton Iteration. The main contents of this article include the discovery， evolution and amendment process of this me

28、thods; an improve of avoiding calculating Newton Iteration with second-order derivative; the comparison of the Chinese ancient algorithm-Yingbuzu Method and Newton Iterative Algorithms.Keywords: Newton Iterative Algorithm; approximate solution; order of convergence; numerical experimentation; Arithmetic in Nine Section ; Duffing Equation; Nonlinear equations; Convergence rate; Progressive 17