牛顿迭代法及其应用

1、精选优质文档-倾情为你奉上 编号 毕 业 设 计（论文）题目 Newton Raphson 算法及其应用 二级学院 数学与统计学院 专 业 信息与计算科学 班 级 学生姓名 侯杰 学号 指导教师 职称 时 间 目 录摘 要 3Abstract31、 绪论4 1.1 选题的背景和意义4 1.2 牛顿迭代法的优点及缺点4二、Newton Raphson 算法的基本原理5 2.1 Newton Raphsn算法5 2.2 一种修正的Newton Raphsn算法7 2.3 另外一种Newton Raphsn算法的修正11三、Newton Raphson 算法在计算方程中的应用18四、利用牛顿迭代法计

2、算附息国债的实时收益率214.1附息国债实时收益率的理论计算公式224.2附息国债实时收益率的实际计算方法22 4.3利用牛顿迭代法计算23五、结论26致谢27参考文献28摘 要牛顿在17世纪提出的一种近似求解方程的方法，即牛顿拉夫森迭代法.迭代法是一种不断的用变量的旧值递推新值的过程.跟迭代法相对应的是直接法或被称为一次解法，即一次性解决的问题.迭代法又分为精确迭代以及近似迭代.“”就属于近似迭代法，本文主要讨论的就是牛顿迭代法，方法本身的发现到演变到修正的过程，避免二阶导数计算的Newton迭代法的一个改进，以及用牛顿迭代法解方程，利用牛顿迭代法计算国债的实时收益率。 关键词：Newton

3、 Raphson迭代算法；近似解；收益率；AbstractIn the 17th century， Newton raised by an approximate method of solving equations， 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

4、-time problem solving. Iteration is divided into exact iterative and approximate iterative. "Newton Iterative Method" are approximate iterative method. This article mainly focuses on the Newton Iteration. The main contents of this article include the discovery， evolution and amendment proc

5、ess of this methods; an improve of avoiding calculating Newton Iteration with second-order derivative; Newton Raphson iterative method of solving equations and Calculating the real-time yield of government bonds.Keywords: Newton Iterative Algorithm; approximate solution; Yield； 一、 绪论1.1 选题的背景和意义牛顿拉夫

6、森迭代法是牛顿在17世纪提出的一种在实数域和复数域上近似求解方程的方法。多数方程不存在求根公式，因此求精确根非常困难，甚至不可能，从而寻找方程的近似根就显得特别重要。方法使用函数的泰勒级数的前面几项来寻找方程的根。牛顿迭代法是求方程根的重要方法之一，其最大优点是在方程的单根附近具有平方收敛，而且该法还可以用来求方程的重根、复根,此时线性收敛，但是可通过一些方法变成超线性收敛。 利用牛顿迭代法来解决问题需要做好的工作：（1）确定迭代变量。在可以用迭代算法解决的问题中，至少存在一个直接或间接地不断由旧值递推出新值的变量，这个变量就是迭代变量。 （2）建立迭代关系式。所谓迭代关系式，指如何从变量的前

7、一个值推出其下一个值的公式（或关系）。迭代关系式的建立是解决迭代问题的关键，通常可以使用递推或倒推的方法来完成。 （3）对迭代过程进行控制。在什么时候结束迭代过程？这是编写迭代程序必须考虑的问题。不能让迭代过程无休止地重复执行下去。迭代过程的控制通常可分为两种情况：一种是所需的迭代次数是个确定的值，可以计算出来；另一种是所需的迭代次数无法确定。对于前一种情况，可以构建一个固定次数的循环来实现对迭代过程的控制；对于后一种情况，需要进一步分析出用来结束迭代过程的条件。1.2 牛顿迭代法的优点及缺点 迭代法是求方程近似根的一个重要方法，也是计算方法中的一种基本方法，它的算法简单，是用于求方程或方程组

8、近似根的一种常用的算法设计方法。牛顿迭代法是求方程根的重要方法之一，其最大优点是在方程的单根附近具有平方收敛，而且该法还可以用来求方程的重根、复根。牛顿法是方程求根的一个有力方法，常常能快速求出其他方法求不出或者难以求出的解。假定有一个函数，方程在处有一个根，对于此根，先估计一个初始值 （可以是猜测的）。得到一个更好的估计值。为此处作该曲线切线，并将其延长与轴相交。切线与轴的交点通常很接近，我们用它作为下一个估计值，求出后，用代替。重复上述过程，在处作曲线的另一条切线，并将其延长至与轴相交，用切线的轴截距作为下一个近似值这样继续下去，所得出的这个轴截距的序列通常迅速接近根。 缺点：选定的初值要

9、接近方程的解，否则有可能的不到收敛的结果。再者，牛顿迭代法计算量比较大。因每次迭代除计算函数值外还要计算微商值。2、 Newton Raphson 算法的基本原理2.1 Newton Raphsn算法牛顿(Newton method)又称为牛顿-拉夫森方法(Newton-Rapfson method)，它是在17世纪提出的一种近似求解方程的方法.多数方程不存在的求根公式，因此求精确根相当困难甚至不可能，从而寻找方程的近似根就会显得特别重要.方法在使用函数的泰勒级数的前面几项来寻找方程的根.牛顿迭代法是求方程的根的重要方法之一，其最大的优点是在方程的单根附近具有平方收敛性，而且该法还可以用来求方

10、程的重根、复根.牛顿迭代法方法简单，每次迭代都是简单的去重复运算，易于编制程序；与求解线性方程的精确法相比较，简单迭代法对于字长位数较少的计算机更加的适用，它可以用增加迭代的次数来弥补字长位数少的不足.初值可以任意的取，因而中间结果偶然的错误不影响最后结果的获得。 多数情况下是得不到一般的数学方法所需的函数表达式，或者难以找到原函数。线性方程组中的求解更是让人望而生畏，往往因为计算机的工作量太大而无法实施。对于这些问题，都可以利用数值的方法来求解，在计算机中实现的数值方法也被称之为数值算法。牛顿迭代法是数值分析中一个重要的计算方法和思想。迭代法的一个主要功能：计算方程时可以比较的快速。解非线性

11、方程的Newton-Rapfson算法是把非线性的方程线性化为一种近似方法.把的点附近展开泰勒(Taylor）级.取其线性部分用来作为非线性方程的近似方程，则有：.设，则其解为： .再把在附近展开泰勒(Taylor)级数，取其现行部分作为的近似方程.若，则得：. 这样，得到牛顿(Newton-Rapfson)算法的一个迭代的序列：.牛顿迭代法有十分明显的几何意义，如下图所示： 图1当选取初值以后，过（，）做的切线，其切线的方程为：. 求此切线方程和轴的交点，即得：. 牛顿迭代法正因为有这一明显的几何意义，所以也叫切线法.：2.2 一种修正的Newton Raphsn算法给出了牛顿(Newton

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

13、。 （A) 根据微分中值定理，即存在，使得：，而.因此，当与的距离无限接近时有：图2OADCPyx .也就是说，在区间不甚大的时候，中值点一定在其渐近的位置附近，并随区间变小而趋于其渐近的位置.图所示的迭代算法构造图本方案基于上述考虑，给出一种通过迭代点而选取另一个点，利用两个点进行迭代求近似根的新方法.这种方法虽然在迭代中又只利用了一个其它的点，但其计算精度却相当的高，它的某一种特殊情形恰是通常的Newton-Rapfson迭代算法.为了更加直观起见，我们通过几何直观图来构造这种迭代算法.设满足条件(A)，当选定初值(仅要求)，如图所示，作交点的切线交轴于B ， AQ线段的斜率为：. 由微分

14、中值定理得知，存在使得：. 而，因此，我们取数，在点作切线PC，图中AD平行于PC.即用点P的导数取代点A的导数，而继续用点的迭代格式得到的点D的坐标. 重复上述过程，得到多点迭代公式： . (1) 其中，.下面我们对上述事实，从理论上加以严格的证明.定理 设满足条件(A)，则由多点迭代公式(1)产生的序列必收敛于上的唯一，这里，.证明: 函数在上连续，由连续函数根的存在定理，从知道在上的根存在，又由条件以及保号知道，在上不变号，故在上是单调函数，因此在上的根存在且唯一.由定理条件曲线可有如下四种不同的情况：(1)，则单调上升，；(2)，则单调下降，；(3)，则单调上升，；(4)，则单调下降，

15、.通过对自变量的变号或者对函数的变号可将四种情况归结为一种情况，所以我们只需对其情况(一)证明迭代过程(1)收敛就可以了.若初值，所以，故有 .一方面，且.下证.若，由的单调性有：，又因，因此就有，与Newton迭代算法的收敛性矛盾.由(一)的假设及可得：. 一般地，若，同样可以证明由式(1)得到满足.依极限理论的必有极限.对式(1)两边取极限，由极限理论可求得.再由，可知函数方程在上的根是唯一的，因此有.当时，式(1)即为Newton-Rapfson迭代公式.本文给出的这种多点迭代方法不仅可以广泛应用于方程的近似求根，更重要的是它为人们提供了一种新的迭代算法思想，拓宽人们求方程近似求根方面的

16、思路.2.3 另外一种Newton Raphsn算法的修正Newton-Rapfson迭代算法是方程求根的一种简单而直观的近似方法，但在实际运用中，我们常常发现到，这种方法仅是利用了迭代点及该点的导数值，而没有充分利用其他点及其导数的值.是否存在可利用的点，这些点我们应怎样的去确定.文1给出了一种新的方法，但这种方法求根的关键在适当地去选取和或.选取不适当时，就会出现某次迭代的值不是迭代序列中的值.因此，我们会问这些值特别是能否不依靠人为选取，而通过迭代点来选取，本文将利用Newton-Rapfson迭代算法和微分中值定理“中值点”的渐近性，来寻找除迭代点以外的可以利用点，给出一种多点迭代方法

17、.设满足下列叙述条件：，；，在上保号. (A)根据微分中值定理，存在，使而.因此，当与a的距离无限接近时就有：.也就是说，在区间不甚大的时候，中值点一定在其渐近的位置附近，并随区间变小而趋于其渐近的位置.本方案基于上述考虑，给出一种通过其迭代点选取另一个点，利用两个点去迭代求近似根的新方法.设满足下列的条件(A)：(1) 在区间在区间上存在二阶导数；(2) 在上不等于零；(3) 在上不变号；(4) ；为了更为直观，我们通过几何直观图来构造多点迭代算法.设满足条件(A)，当选定初值（仅要求）后，如图所示：OyxDCAPBQ图3做A点的切线交X轴于B，AQ线段斜率为：；由微分中值定理可知，存在使得

18、：. 而，因此，我们可以取数，就在点作切线PC，图中的AD平行于PC.即用点P的导数代替点A的导数，而仍用点A的迭代格式去得到点D的坐标 (2)主要对(2)式的分子用与的和取代，这样就能得到新的迭代公式： . (3)如果令 .则： . 从而可知(3)式中迭代函数为：. 引理15 对于迭代公式，如果在所求根的邻近连续并且：，则该公式在的邻近是阶收敛的.定理1 设方程的根为，函数在的的邻域内有至少四阶连续的导数，且，则就迭代公式(3)在的邻近至少是三阶收敛的.证明 迭代公式(3)的迭代函数为：，在其中，由于方程的根为所以，从而可知，；对求导数得：；同理可得：. 由引理可知迭代公式(3)在邻近至少是

19、三阶收敛的.引理24假设函数在区间上存在二阶导数，且满足下列条件(1) 在上不等于零；(2) 在上不变号；(3) ；(4) 设，且满足条件；则由Newton-Rapfson迭代法得到序列收敛于的惟一根.定理2假设函数在区间上存在二阶导数，且满足下列条件(1) 在上不等于零；(2) 在上不变号；(3) ；(4) 设，且满足条件.则由多点迭代公式(3)得到的序列收敛于的惟一根.证明函数在上连续，由连续函数根的存在的定理，从知道在上的根存在，又由条件及的保号性可以知道，在上不变号，因此在上是单调函数，因此在上的根存在并且惟一.由定理条件，曲线可有如下四种不同的情况：(a) ，则单调上升，；(b) ，

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

21、 . ，在上单调递增，且所以：；因此得：.本方法代方法比Newton-Rapfson算法的收敛速度明显要快，而且对于，越大效果越差！当时，在之前迭代格式会产生负值.所以，格式(3)的收敛速度和的选取有关. 3、 Newton Raphson 算法在计算方程中的应用非线性方程求根最为常用的是迭代法。 迭代法是计算方法中的一种基本方法,主要有简单迭代法、牛顿迭代法和弦割法。本文主要通过借助非线性方程求解,介绍优化程序的方法,能够提高数值计算程序的质量。它对处理科学工程问题或企事业管理中的数值计算问题有一定的启发意义。首先，常用非线性方程解法的对比与分析对于收敛的迭代过程，只要迭代足够多次，就可以得

22、到满足制定精度要求的结果。但有时迭代过程收敛缓慢，计算效率很低。如何改进迭代法使之加快收敛速度，是实际应用中需要解决的问题。弦截法与牛顿迭代法都是线性化方法;但两者有本质的区别。牛顿迭代法与一般迭代法在计算时只用到前一步的值，故称之为单点迭代法；而弦截法在求时要用到前两步的结果和，使用这种方法必须给出两个初始近似根，这种方法称为多点迭代法。另外，弦截法比牛顿迭代法收敛速度较慢，但它的计算量比牛顿迭代法小。3.1 Newton Raphson 算法求解方程的根 例1：用牛顿法求下面方程的根 ； 解：因为，所以其迭代公式为：；选取计算结果列表如下：N牛顿法弦位法抛物线法0123456711.235

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

24、二阶微商，是的一重零点，并且初始充分接近于，那么牛顿迭代算法是收敛的，并且有； 这表明牛顿法是二阶收敛的（平方收敛的）.最后考虑是多项式的特殊的情况，而此时，在某个值，比如时的计算可以用综合除法.设 ，除以，得商，余： ； （4）其中：； ；比较(4)式两边的系数便知这些可以按下表来进行：这一过程就是秦九韶算法，计算多项式值的嵌套算法： ；每个括号的值就是这里的.至于导数的计算，我们注意到(4)式可得：；于是：；因此再对进行上述的过程，或者再用一次秦九韶算法即可.例2:计算在区间内的一个实根.我们已知有一个精确到十二位有效数字的实根.取，以Newton迭代法计算(记作)，取， 以式(4)计算(

25、记作)，其结果列表如表1.表1 计算结果：迭代次数N01234532.02.92.42.42.4从这个数值例子，我们能看出，式(4)比Newton迭代算法的收敛速度快得多，只进行三次迭代就可以得到满足精度要求的值了，而Newton迭代算法需迭代5次才可以得到满足精度要求的值.式(4)可以被广泛应用，特别是编成数学软件后，用计算机求解方程近似根时效果会更加显著.例3：计算的近似值。 解： 令问题转化为求的正根由牛顿迭代公式 迭代结果迭代次数迭代结果012345670.0.0.0.0.0.0.0.满足了精度要求 =0. 例4：用牛顿迭代法球方程=a（a>0）的近似正实根。由此我们建立一种求平

26、方根的计算方法。解：首先计算可知迭代公式为通过编写matlab程序计算得出， 比如5的平方根，初始值取做2，只需输入命令：it(5,2)，立即可得结果y=2.2361四、利用牛顿迭代法计算附息国债的实时收益率随着证券市场规模的扩大和机构投资者的增多，加上市场格局的变化，国债在证券市场中的地位和作用逐渐提高，许多投资者逐渐把目光转向国债市场。国债实时收益率是反映市场利率变化和衡量国债投资价值的重要指标，但是许多投资者对附息国债的实时收益率计算却无从下手。本文将介绍利用牛顿迭代法计算附息国债的实时收益率。4.1附息国债实时收益率的理论计算公式附息国债实时收益率也就是附息国债的内含收益率(或内部收益

27、率，IRR )，内含收益率以下面的公式为基础计:. (5)式中：附息国债实时收益率(内含收益率)；w：交易结算日至下一利息支付日的天数以上一利息支付日(LIPD)至下一利息支付日(NIPD)之间的天数，即：.c:每次支付的利息额；n：剩余的利息支付次数；：交易结算日的市场价格(全价，即：净价+累积利息)。4.2附息国债实时收益率的实际计算方法下面以696券(696券于1996年6月14日发行，10年期，票面年利率为11. 83%，附息国债)为例，介绍附息国债实时收益率的具体计算方法。设1997年6月14日之前的某一天购入696券的价格为，每百元每年的实时收益率为x，离第一次发放利息(1997年

28、6月14日)的时间为t(年数)，则： 发行一年后的除权价：发行二年后的除权价： 发行九年后的除权价：最后一年的到期本息为：上面一共10个方程可决定10个未知数：, , , ，将以上10个方程整理，消去, , , 得到.从以上例子可以看出，设距离兑付期为n年(取整数)的附息国债到期本金为M，每年票面利息为:，购入价格为的国债的到期收益率为x，那么：.此方程式中已知购入价格，每年票面利息为c，到期本金M，剩余年数取整为n(注:这里的n和(5)式中的n有区别),t为当前交易日至下一附息日的天数除以上一次利息支付日至下次利息支付日的天数，即t为当前日至下一个利息支付日的年数。 这是一个非线性代数方程，

29、一般不能直接求解，只能采用逐次通近的迭代方法求解，即当知道解的某一初始近似值后，从它开始逐步逼近所要求的解x，我们选用牛顿迭代法解以上方程。4.3利用牛顿迭代法计算牛顿迭代法是迭代法的一种，是求解函数方程的一种有效方法，其基本特征是计算格式简单且收敛较快。给定方程f(x) =0。以及根的初始近似值，并假设函数f (x)在的邻域内导数存在。设是方程f(x) =0。的根，即成立，将其在处按泰勒公式展开得：.略去含及以后各项得近似等式：因而得的近似表达式：以作为初始近似根的改正值得：重复应用以上做法可得：.此即为牛顿迭代公式。对于方程：，设y=1+x，整理得：.设：则：应用牛顿迭代公式：，选取误差，

30、y的初始近似值为，有：.若，则停止迭代，取，否则继续迭代.对于，如果则继续，否则停止迭代，得到方程的根，国债收益率。根据以上牛顿迭代公式编计算程序，可求得附息国债的实时收益率。程序编写如下(C语言)#include<math.h> #include<stdio.h> float gznewton (float,float,float,int,float,float,float);void main() float x; float a,b,d,e,f,g; int k;a=155.45;b=11.83;d=100.0;k=6;e=0.85;f=1.1;g=0.00001

31、; x=gznewton(a,b,d,k,e,f,g)-1; printf("SYL is %fn",x);float gznewton(float p0,float c,float m,int n,float t,float y0,float wc) int i,done=0; float y=y0,fy,fy1,Newton; /y=y0; do fy=p0*pow(y,n+t)-c-m; fy1=p0*(n+t)*pow(y,n+t-1); for(i=0;i<n;i+) fy=fy-c*pow(y,n-i); fy1=fy1-c*(n-i)*pow(y,n-i

32、-1); if (fy1!=0) Newton=y-fy/fy1; if (fabs(Newton-y)<wc | fabs(Newton-y0)>0.2) done=1; else y = Newton; else done=1; while(!done); return (Newton);运行结果如下显示：五、结论 牛顿迭代算法是一种用途非常广泛的方法，本文不仅介绍了这个方法很好的诠释这个方法， 而且做了牛顿迭代法的两种修正，也做了牛顿迭代法与弦位法以及抛物线法的比较得出牛顿迭代法的收敛速度是明显要快的。并且用牛顿迭代法计算附息国债的实时收益率，计算比较方便快捷。致谢本论文是在

33、我的导师魏正元老师的支持，鼓励和精心指导下完成的。在我本科生四年的学习过程中，魏老师渊博的专业知识，严谨的治学态度，以及敏锐的学术洞察力都让我受益匪浅。在我学习中所取得的任何进步都离不开魏老师对我的悉心指导和亲切关怀。在此特别表示我最深切的感谢。感谢我院各老师四年来对我孜孜不倦的教诲。老师们的深入浅出，细致入微的教学作风让我受益终身。感谢数学与统计学院2008级全体同学，和你们相处的四年中，我们在学业上共同进步，在生活上互相关心，度过了很多快乐的时光，特别感谢和我同一个导师的同学杜长敏，郭晓倩，李伟洪，和你们共同的学习和讨论帮助我在学习中克服很多困难。感谢我的班导师钟坚敏老师，感谢你四年来对我的帮助和关怀，你们是我学习和生活的良师。感谢我的亲人，我的爸爸，妈妈，感谢他们多年来对我的照顾，正是他们从未改变够的信念和不倦的鼓励，才使得我的论文得以顺利完成。 再次感谢所有帮助过我的老师，同学和