牛顿迭代法..docx

《牛顿迭代法..docx》由会员分享，可在线阅读，更多相关《牛顿迭代法..docx（19页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

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

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

4、.迭代过程的控制通常可分为 两种情况：一种是所需的迭代次数是个确定的值，可以计算出来;另一种是所需的 迭代次数无法确定.对于前一种情况，可以构建一个固定次数的循环来实现对迭代 过程的控制;对于后一种情况，需要进一步分析出用来结束迭代过程的条件.1牛顿迭代法:,小 J 2(“/凡(1a丹加作切线 pc.12 7图中平行于PC.即用而,因此，我们取数在点1./(X/ 1J (%)力点尸的导数(1-)誉代替点A的导数, 1f xo)J。的坐标/ D xIM 0 .1小十第J主要对(3)式的分子/)用f E)与f xk ( V而仍用点A的迭代格式得到点(3)/,、的和代替，这 (、一 C样就得到新的迭

5、代公式:xk+ - xk1 口ww/ 、fM+f xk ( *) c1 小-。-喘(4)小一常1如果令(同=% (1厂)七 J(XXk+从而可知(4)式中迭代函数为: 引理15对于迭代公式产、；+i=g)=4W；贝上JJ u)_ fXM= x v L./、/ /(卬3)5小)-孔济二(七)，如果在所求的根*的邻近连续并且:卜*)=6卜*)=攵=屯(叫卜*) = 0,()(x*)wO,则该公式在的邻近是阶收敛的.定理1设方程/(%)的根为*,函数/(%)在*的的邻域内有至少四阶连续导数, 且/ (x) w0 ,则迭代公式在的X*邻近至少是三阶收敛的.证明 迭代公式的迭代函数为：o(x) = vv

6、(x)-/(卬(力)收,由于方程司的根为*所以/卜*) = 0,从而可知w(x*) = x*， f u)w x =0；x* =f (xvt (x)L I对(x)求导数得:f (卬(x) w (x) f (u(X) - /(卬(X)(X)n底)=0；同理可得：”(同=(x*) = w (尤*) 一卬 (%*) = 0.由引理知迭代公式(4)在/邻近至少是三阶收敛的.弓I理2 (4)假设函数/(x)在区间,可上存在二阶导数，且满足下列条件/(%)在a,句上不等于零;(1) / (九)在,可上不变号; /()/(/7)0；则由Newton迭代法七用=%-/(%)/国)得到的序列七收敛于) = 0的惟

7、一根 定理2假设函数在区间q,可上存在二阶导数，且满足下列条件(1)。(尤)在a,以上不等于零;(2) f (x)在,可上不变号；(4)设入式,/?,且满足条件元)/(x)0.则由多点迭代公式(4)得到的序列玉收敛于= 0的惟一根%*.证明 函数X)在可上连续，由连续函数根的存在定理，从知道 力在,可上根存在，又由条件/(尤)工0及/(%)的保号性知道,/(X)在心可 上不变号，故/(X)在,可上是单调函数，因此/(X)在,，可上的根X*存在且惟一.由定理条件，曲线y = /(x)可有如下四种不同情况:(a) f(6/) 0, f (x) 0,则/(%)单调上升，f (Z?)/()0；/()0

8、, f (x)f (Z?)0；(b) /(a)0,/(Z?)0,则/(%)单调上升，fa)f(Z?)0,/(Z?)0,/1(x)/ (2)0.通过对自变量的变号或对函数的变号可以将四种情况归结为一种情况，所以 我们只需对其中一种情况证明迭代过程(4)是收敛的就可以了.下面仅就情况(a)证明定理2,其余情况的证明类似.对情况(a)来说此时司=0在 ,可上的根存在且惟一，且“X)在肉上单调递增,首先证明，对任何初始近似由迭代公式(4)求出的逐次近似4都属于仁力)，并且单调递减.事实上，由引理2的证明我们可知，只要) = /-(1-)半%*问，就有(/)/，再由(3)式得八1 0知因而由(4)式产生

9、的序列玉单调递减并有下界，故！的天存在.设limx=x, (4)式两边当攵f go时求极限得: 87777“X)在,可上单调递增,且/卜*) = 0所以：f=0 a=0；因止匕得：x x.本方法代方法比Newton和文4的迭代法的收敛速度明显要快，而且对于在f尤* =。之前迭代格式会产生负值.所以,格式(4)的收敛速度和的选取有关.对于定理2中的四个条件，在MATLAB中通过简单的程序即可验证.4中国古代算法盈不足术与牛顿迭代算法的比较：首先介绍盈不足术九章算术中的第七章是盈不足术，这是求解方程的一种最古老的方法.为了说明该方法的基本思想，我们考虑该章的第一个例子：今有共买物，人出8,盈3；人

10、出7,不足4,问人数、物价各几何？其求解过程为(见图1)：Hl(8)TT(7)川图1中国古代盈不足术的图解法(1)把出率(8)和(7)放在第一行;(2)把盈数和不足数放置在出率下面；(3)计算维积(交差积)得(32)和(21),得和为(53)；(4)盈减去不足数为4-3 = 1；(5)从而得物价为5% = 53；用现代数学的观点，盈不足术可表示为：设为和为两个近似物价，用和6分 别表示为盈或不足数，则物价为：X =*2 ;人数为尸名士旦;正如白尚恕7指出的那样，在隋唐(581618年AD)盈不足术在中东被广泛流传，最早的阿 拉伯算术书是由al-Khowarizmi在公元825年写的，英文中的算

11、术一词(algorithm) 来自他的名字，他应该对九章算术和其他古代中国巨著很了解，并把盈不足术称 为中国方法.Khitai指China,类似的写法有Khatai, Chatayn, Chataain等等.普遍 认为中国算法是通过古代著名的意大利数学家Leonardo Fibonacci 1170? 1250?年) 传给西方的，据记载Fibonacci随他父亲周游了埃及、西西里、希腊和叙利亚，这 次周游使他接触了东方和阿拉伯的计算方法.在1202年，即他回家后不久他就出 版了著名的算经Liber Abaci.该书也介绍了盈不足术，并把这种方法称为中国 规则，这个名字来自中东，在那里中国算法称

12、为Hisabl-Chatin,里Chation指China 该书中的一些例子和算法和中国古代数学巨著完全一样.如在4世纪的孙子算经： 今有物不知其数，三三数之胜二，五五数之胜三，七七数之胜二，问物几何？该 问题的解题方法就是数论中的中国余数定理：在Fibonacci的算经中阿拉伯语 DeRegulisel-Chatavn 被译成拉丁文 DuarumFalsdrumPosicionumRegula 所以在西方 这种方法被称作双假定方法，这实际上是九章算术中的盈不足术，即中国算法， 它起源于中国是毫无疑问的，这正如钱宝琮8指出的那样可惜的是很多西方人认 为这种方法起源于印度，并被阿拉伯人所掌握所以

13、本作者强烈建议把双假设法改 称为中国算法或中国方法.中国算法与牛顿迭代算法考虑方程/(司=0设西，为方程的两个近似解，于是 我们得残量/(%)和/(%)应用中国算法，我们可得(5)(5)二2一(否)一一一(%2)F /(玉)-/(%2)在九章算术中给出了在下列情况下的一些不等式: 双盈，即/(%)0和/(x2)0(2)双亏，即 %)0和/(尤2)；(3) 一盈一亏，即上述算法可以根据不等式的性质确定更合适的两个数(%,%)或(九2，天)，再进行计算定更精确的近似解，为了与牛顿迭代算法比较，我们把(5)写成如下形式：%/(%)-/(%)(% -马),/(与)-/(%)/(5)-/(%)如果引入导

14、数/&),它定义为/(%)=旦止凡J那么我们马上可得:_小1)x = % fM这就是著名的牛顿迭代法，当两个近似值为和马位于真解的两侧时、即 /（可）/（%）。，中国算法比牛顿迭代算法具有很大的优势，牛顿迭代算法可以 更进一步的优化发展，可参考文献10, 11.中国算法的改进：中国算法可以看成是通过两个近似解的线性近似方法，见图2为了提高中国算 法的精度，我们用三点（匹,2，毛），而不用两点a,%2），用抛物线拟合该曲线，我 们得近似解为：x Xf2f312工力|*3于2于一 (/-)(/力)(/)/力) X)( j)；式中/=/（%）;综合概述：迭代算法是一种用途非常广泛的方法，本文不仅介绍

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

16、和力学，2002, 23(12)： 12561259.6王晓峰.一种修正的牛顿迭代法代,2010, 33 (1)长春理工大学学报,178 179.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 Simulation 200

17、0, 1(3):239240.1 lHeJi-huan.Newton-like iteration menthod for solving algebraice quationsJ. Communication NumSimulation, 1998, 3:106109Newton iterationLI Bao YangMathematical Sciences Information and Computing Science NO： 060424067Instructor :SU MenglongSummary： In the 17th century, Newton introduce

18、d 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 problem solving. It

19、eration is divided into exact iterative and approximate iterative. Newton Iterative Method*1 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 methods; an i

20、mprove 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 Nin

21、e Section ; Duffing Equation; Nonlinear equations; Convergence rate; Progressive牛顿迭代法(Newton method)又称为牛顿-拉夫逊方法(Newton-Rapfson method),它是牛顿在17世纪提出的一种在实数域和复数域上近似求解方程的方 法.多数方程不存在求根公式，因此求精确根非常困难甚至不可能，从而寻找方程 的近似根就显得特别重要.方法使用函数/(%)的泰勒级数的前面几项来寻找方程x) = 0的根牛顿迭代法是求方程根的重要方法之一，其最大优点是在方程 /(尤)=0的单根附近具有平方收敛性，而且该法

22、还可以用来求方程的重根、复根. 另外该方法广泛用于计算机编程中：解非线性方程X) = 0的牛顿(Newton)法是把非线性的方程线性化的一种近似方法,把“X)的飞点附近展开泰勒(Taylor)级/(x) = /(x0) + /(x )/(%0)+ (%一0)2 取其线性部分作为非线性方程/(司=。的近似方程，则有:/(/) + / (%)(%/)=；设/(%)工0,则其解为:再把/(%)在王附近展开泰勒(Taylor)级数,也取其现行部分作为/(x) = 0的近似方程.若/(xJwO,则得:2 1这样，得到牛顿(Newton)法的一个迭代序列：/fM，牛顿迭代有十分明显的几何意义，如图所示：当

23、选取初值X。以后，过（为（%）做“X）的切线，其切线方程为:卜/(%) = /(%)(x7o)；求此切线方程和X轴的交点，即得:牛顿法正因为有这一明显的几何意义，所以也叫切线法. 例：用牛顿法求下面方程的根f (x) = X3 + 2x2 +10% - 20 = 0 ；解：因/(x) = 3x2+4x+10,所以迭代公式为：x+i -xn 一(d +2f +10x-20y(3x2 +4x + 10,选取% =1计算结果列表:N牛顿法弦位法抛物线法011111.5000000000000001.50000000000000021.3693364705882351.3544303797468361

24、.25000000000000031.3688081886175321.3682702596546871.36853585772136741.3698081078213751.36880790682018051.3688081078213731.3688081074722171.36880810782168161.3688081078213731.3688081078213731.36880810782137371.3688081078213731.368808107821373从结果可以看出，牛顿法的收敛是很快的，/误差1。一於,但用牛顿法计算工作量比较大，因每次计算迭代除了计算函数值外还要

25、计算微商值.为此我们提出了简化牛顿法：其公式为/（七）/（公）；用上面的公式计算，不再需要每步重新计算微商值，所以计算量小一些，但收敛也要慢一些.为了避免计算导数还可以采 用差商代导数的方案：Xn+ Xn关于牛顿迭代的收敛有下面结果:如果“X）在零点附近存在连续的二阶微商,J是/（力的一重零点，且初始与充分接近于那么牛顿迭代是收敛的，且有 加一小|/（2/）卜氏g；这表明牛顿法是二阶收敛的（平方收敛的）.最后考虑“X)是多项式的特殊情况，此时f(x)，/(X)在某个X值，比如X = c 时的计算可用综合除法.设 /(x) = axn +axn+ Han_xx+an,除以 x-c ,得商 q(x

26、),余厂：/(x)=q(x)(x-c)+ ；( i)其中：=%炉T +b1Xn2 + + 么_2% + .-1 ；厂=2 =/(c)；比较式两边f的系数便知这些4可以按下表进行：axa2。一 iab、cb_2c瓦二。04 = q + bcb2 = a2 +bcbn=an+bn-lC这一过程其实就是秦九韶算法，计算多项式值的嵌套算法:c + an ；c + an ；/ (c)= (。0 + q )c + 4C)c+,+%.1每个括号的值就是这里的瓦bn.至于导数的计算，注意到式可得：/(X)= q + q (X _ C)； 于是：/ (c) = q(c)；因此再对为2进行上述过程，或者再用一次秦

27、九韶算法即可.2一种修正的牛顿迭代法：给出了牛顿迭代法的一种修正形式，并证明了当。1/2时修正的牛顿迭代法 是二阶收敛的，当参数/= 1/2时是三阶收敛的，数值实验表明，与经典牛顿迭代 法相比，该修正牛顿迭代法具有一定的优势,众所周知，数值求解非线性方程 ) = 0的根的方法很多.经典的牛顿迭代法是非线性方程组求根的一个基本方 法，它二次收敛到单根，线性收敛到重根.牛顿法因收敛速度快而得到广泛应用， 也倍受学者的重视，近年来很多文献中提出各种改进的牛顿方法.文献8中利 用Newton迭代法和微分中值定理“中值点”的渐进性，提出了一种多点迭代法.设/(x)满足下述条件：f(x)&c2a,b, /

28、()/(/?)0),如图所示，作交点的切线交x轴于BA0线段的斜率为:由微分中值定理知，存在/(A)-/ /一使得:/(%) x TU)5 J而。-常+3/(%)、fM,1 小。）、= /(%)； 7m,因此，我们取数re1-a ，在点 2 )P xo-(1-r)L/ /0-(1一r)I J作切线PC,图中AO平行于PC,即用点尸的导数/ %_（i厂）业2I J代替点A的导数，而仍用点A的迭代格式得到点。的坐标fx/(%)7。()小),0重复上述过程，得到多点迭代公式XM XkXM Xk/(%) ；(2)其中为 ,句,左二 1,2,3，.下面我们对上述事实，从理论上加以严格证明.定理 设/（X

29、）满足条件（A）,则由多点迭代公式产生的序列当必收敛于a,b上的唯一，这里玉可，/（6Z）= 0.证明函数/）在上连续，由连续函数根的存在定理，从/（a）/（b）v0知道在可上根存在，又由条件/（%）w0及/（%）保号知道,f在,句上不变号，故X）在,可上是单调函数，因此犬）在凡可上根4存在且唯一.由定理 条件曲线丁=/（九）可有如下四种不同情况:(1)/()0,/(X)0,则/(X)单调上升，/(fl)/(Z?)0； /()0,/ (x)0,则/(%)单调下降，/()/9)0; /(a)O,/(b)v。,/ (%)。, 则 / (x)单调上升，/ (a)/ (/?)o,/(Z?) 0, f

30、(x) a,所以/(x0)0,故有，(%-Q)，(%-Q)一方面,柒且/) = /(%o-a).下证/(%)/|x0-(l-r)4 ,由 / (%)的单调性有, J xo)j又因为o -(1-r) J。 /一常，因此有，/、，与 NewtonfM,迭代法的收敛性矛盾.由(一)的假设及f 小0 -(一)等4可得: x0 (x0 -a = a ；一般地，若当=，同样可以证明由式(2)得到的七用满足所以由 式产生的迭代序列xj单调下降且有下界.依极限理论必有极限.对式两边取 极限，由极限理论可以求得/(。) = 0.再由/(x)w0,怎可，可知函数方程/(%) = 0在,可上的根是唯一的,因此有=

31、当厂=1时，式(2)即为Newton迭代公式.本文给出的这种多点迭代方法不仅可以被广泛应用于方程的近似求根，更重 要的是它为人们提供了一种新的迭代思想，拓宽人们在方程近似求根方面的思路.例 计算X）= /_2%_5 = 0在（2,3）区间内的一个实根.我们已知= 0有一个精确到十二位有效数字的实根a = 2.09455148154.取o=3,以Newton迭代法计算（记作七”），取0 =3 ,以式计算（记作了2），其结果列表如表1.表1计算结果:迭代次数NE03312.362.1846844622.0951360372.09472630432.0945516742.09455148242.94

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

33、迭代序列中的值.因此，我们会问这些值特别是与能否不依靠 人为选取，而通过迭代点来选取，本文将利用Newton迭代法和微分中值定理“中 值点”的渐近性，来寻找除迭代点以外的可利用点，给出一种多点迭代方法.设/（X）满足下述条件：/ wOJ （%）在a,可上保号.（A）根据微分中值定理，存在自使得,（牛/=/而1而三 二L因b-a2d b_a 2此，当b与的距离无限接近时有：Q).也就是说，在区间(4力)不甚 大时，中值点&一定在其渐近位置伍-。)附近，并随区间变小而趋于其渐 近位置.本方案基于上述考虑，给出一种通过迭代点选取另一个点，利用两个点进 行迭代求近似根的新方法.设/(%)满足下列条件(A)：(1) /(%)在区间在区间上可上存在二阶导数；(2) /(%)在,可上不等于零；(3) / (%)在,可上不变号；(4) /()/()。)，如图所示：%。)一小一偿% _(x /(一)r-7u)做A点的切线交X轴于84-0 , A。线段的斜率为: I fM )；由微分中值定理知，存在自 %-44，%使得: (/ (%)/(%)、fM,/(%)、fM,= /(%)；