Newton迭代法浅析.doc

目 录第一章：绪论2第二章 Newton迭代原理32.1 一般迭代思想的设计32.2 Newton迭代法的原理32.3小结：5第三章 Newton迭代法的收敛性63.1 Newton迭代法中不收敛的情况63.2 定理证明73.3 Newton迭代法的收敛性分析103.4小结：12第四章 两种改进的Newton迭代法134.1 改进初值的Newton下山法11134.2 一种新的Newton迭代法加速设计13144.3小结：15第五章 Newton迭代法的应用165.1 Newton迭代法的Matlab实现165.2 数值举例165.3小结：19第六章：总 论20参考文献21致 谢22第一章： 绪 论 在自然科学和工程技术中很多问题的解决常常归结为解非线性方程（组）或者线性方程（组)代数方程组，例如电学中的网络问题，船体数学放样中建立三次样条函数问题，用最小而乘求是实验数据的曲线拟合问题，用差分或者有限元方法解常微分方程等。关于非线性方程（组）的求解，一般有两类解法：直接法和迭代法。我们知道，只有一次、二次和三次方程有规范的求根公式，而高于三次的方程是不存在求根公式的。因此求根变得一异常的困难。而科学计算却很好解决了这一问题，其中最基本的算迭代法了，它对于解决非线性方程（组）的根变得异常方面。就迭代法而言，Newton迭代法可算是其经典之作。 Newton迭代法又称为Newton-Raphson迭代法，它是Newton在17世纪提出的一种在实数域和复数域上近似求解方程的方法。牛顿迭代法是求非线性方程（组）根的重要方法之一，其迭代格式简单，且在单根附近具有平方收敛，而且该法还可以用来求方程的重根、复根。 关于Newton迭代法，许多学者为之做了相当多的研究，并且留下了很多经典的文献(2-6)。Newton迭代法在解决Banach空间中非线性方程或方程组的应用更为重要，如梯形Newton迭代法。其中，Ksntorovich7关于Newton迭代法收敛的工作是解决方程算法现代研究的起点，并给出的Ksntorovich条件。 Newton迭代法是一个重要的计算方法和思想。牛顿迭代法的主要功能：计算方程时可以比较快速方便的计算出来结果但并不影响计算出来结果的精确度，运用于多种工业设计和数学设计方面，其重要性可见一般。 在我们开设的由李庆扬等编数值分析（第五版）中，其第七章7.4节就专门对Newton迭代法进行了一定的讲解。但是，其书上所讲内容甚微。这对于一个初学者来说，算是一个障碍。因此，本人想对Newton迭代法做一个系统的总结。本文主要从Newton迭代法的基本思想、收敛性、及几种Newton迭代法的变形作一个全方面的介绍。主要是想在总结前人的经典研究之上，系统的对Newton迭代法作一下总结，以便更加快速的学习和掌握Newton迭代法。第二章 Newton迭代原理2.1 一般迭代思想的设计迭代法作为最常用的近似方法，对于求非线性方程（1.1.1）的近似根，我们考虑将方程（1.1.1）转化为等价方程 （2.1.1）其中，称为迭代函数。显然，若是方程（2.1.1）的根，那么必为方程（1.1.1）的；反之已然。由方程（2.1.1）我们就可以建立迭代算法了。 我们去起根的一个近似值为初始猜测值，然后由 （2.1.2） 产生一个序列，称之为迭代序列。我们假定 在连续，且 ，若 收敛与，则必满足方程（1.1.1），即为方程（1.1.1）的根。我们也称方程（2.1.1）的根为函数的的不动点，因此迭代算是（2.1.2）也称不动点迭代9。2.2 Newton迭代法的原理 我们从三个角度看Newton迭代法： 2.2.1（1）设是方程的根, 取*将 在做一阶Taylor展开:其中在之间，于是解得，用Newton迭代法 （2.2.1）只要，每一步迭代都有的根。迭代函数（2.2.1）即为Newton迭代格式。 2.2.2（2） 从几何上看，方程（1.1.1）的根是曲线与轴的交点。设为根的一个近似值，用过处的切线与轴的交点来近似（如图 1） 图2. 1因为过点处的切线方程为 它与轴的交点坐标即为，2.2.3 （3） 对不动点方程（2.1.3）,它导出的迭代过程有可能发散,也可能收敛得非常缓慢.这时,我们有没有办法改进不动点方程,让迭代过程收敛得快一些呢?我们考虑到和都是不动点方程,他们的加权平均 （2.3.1）从而有，整理有 （2.3.2）也是不动点方程,而且与有完全相同的不动点.适当选取的值,可以使发散的迭代过程变得收敛,使收敛慢的迭代过程变得收敛迅速. 由于在不动点附近的导数值在很大程度上决定了迭代过程的收敛性.的绝对值越小,收敛性越好.因此,选择使得.由（2.3.2）式可得到理想的值为将上式代入（2.3.1）得 （2.3.3）在的情况下，为求解方程（1.1.1）,可以使用不动点方程,相应的迭代函数为.对进行迭代（2.3.4）即为牛顿迭代格式。 从而，我们用Newton迭代很好的解决了有关方程（1.1.1）的求根问题。2.3小结： 不动点迭代是迭代法中的重点，它的基本思路与数列收敛差不多。而Newton迭代法则是从导数的角度来建立迭代格式，思路新异独到，关键在于起设计思路上。第三章 Newton迭代法的收敛性3.1 Newton迭代法中不收敛的情况在Newton迭代法中，不是所有情况Newton迭代法都收敛的，若不具有连续的有界的，那么Newton迭代法有可能不收敛9，如图2所示.图中，为转向点，即在点处其导数为零。并过点的切线交点，而过的切线交点与点刚好重合，从而这个迭代就变成了一个死循环。 0 图 23.1 另外有一中情况是，其迭代初值的选取不恰当，从而导致迭代发散12。如图33.1 0 图33.2因而，在应用Newton迭代法的时候，对其迭代条件的判断和迭代初值的选取十分重要，这关系到整个迭代成功与否。3.2 定理证明定义 11 设有不动点，如果存在的某个领域，迭代法（2.1.2）产生的序列，且收敛到，则称迭代法（2.1.2）局部收敛；定义 2 9 设序列如果存在常数，使得 （3.2.1）成立，则称序列，或者说序列称迭代法（2.1.2）是阶收敛的，如果相应的迭代序列特别地，当时称为线性收敛，称为超线性收敛，时称为平方收敛或二次收敛。定理 19 设迭代函数在其不动点附近有连续的二阶导数，且 当时，不动点迭代（1.2.1）是平方收敛的。证明 由于，由连续性，存在闭领域,使得故按照（2.2.1）产生的迭代序列均收敛于方程（1.1.1）的根。又由Lagrange中值定理， 而，当时，有，故有即.故定理中的迭代序列是局部收敛的当时，由Taylor展开即 （3.2.2）所以 （3.2.3）而又因为，不动点迭代（2.2.1）是平方收敛的。推论 设迭代函数在其不动点附近有连续的阶导数，且 当时，不动点迭代（2.2.1）是阶收敛的。证明： 将在附近Taylor展开 (3.2.4)由（2.1.2）知，则 (3.2.5)因为，所以 （3.2.6）而且为常数的，而 (3.2.7)由收敛阶的定义可知，给收敛是收敛的。定理 210设上连续可微的凸函数，满足条件（1）（2） 上不变号；则有（1） 存在唯一的，使得（2） 对任意满足，记 （3.2.8）则是单调有界序列；（3）对上述的序列，当时有；证明：首先证明（1）因为且不变号，所以是上的单调函数，由函数的连续性可知，满足方程的根是唯一存在的。（2） 由（3.2.8）式有 （3.2.9）不妨设，有因为即有，故对所有的均有 (3.2.10) 在由（3.2.9）式可知所有的有 (3.2.11)又因为假定了，故有对任意的，均有， （3.2.12)故是单调有界序列；（3） 由（2）可知收敛，设其收敛到，由Cuachy收敛准则有 (3.2.13)在联系(3.2.8)式有由（1）可知，若，则必有 （3.2.14）故对于序列有3.3 Newton迭代法的收敛性分析 3.2.1 （1） 单根情形设方程（1.1.1）的函数在零点 的某领域内具有二阶连续导数，且 由Newton迭代函数 （3.3.1）则 （3.3.2）因此 ，有以上定理可知Newton迭代法是至少二阶收敛。 3.2.2（2） 重根情形9 以上两种情况，均为Newton迭代法在方程（1.1.1）在处有单根的情形，要是方程（1.1.1）在处有重根呢？那是不一样的，这里我们考虑方程（1.1.1）在处具有重根的情况。 由于方程（1.1.1）在处具有重根，方程（1.1.1）的函数可表示成，且，在此，我们设函数具有连续导数，则有，从而在附近（除外)j均不为零，Newton迭代法仍然有效，但起收敛速度明显下降4。 在这种情况下，我们可以考虑方程（1.1.1）在附近的阶Taylor展式： （3.3.3） （3.3.4）因为展开右端的前项都为零，而将其带入Newton迭代格式有 (3.3.5)其中都介于之间。与是 (3.3.6)当时，的，所以，Newton迭代产生的迭代序列是线性收敛与的。 显然，在重根的时候，Newton迭代的速度大大降低了，此时我们就考虑对其进行修正9，提高其收敛速度。 （1）由以上可知，为函数的重根。我们令，从而是方程的单根，故有。对继续实施Newton迭代即(2.3.7)从而得到迭代公式： (3.3.8) 根据Newton迭代可知，迭代函数（3.2.3）是二阶收敛的，从而修正后的重根时的Newton迭代法是二阶收敛。3.4小结： Newton迭代法不是什么情况下都收敛的，更不是什么情况下的收敛速度都相同。本节着重就这两方面做了详细的分析，并知道改变Newton迭代的格式还可以提高它的收敛速度。第四章 两种改进的Newton迭代法4.1 改进初值的Newton下山法11我们知道，Newton迭代法对迭代初值的选取是有很高要求的，若初值的选取不好，很可能迭代就发散，为了改善这一苛刻的条件，我们设计了Newton下山法。Newton下山法是在事先没有给出较好的初值情况下, 求方程（1.1.1）的根的一种修正的Newton迭代法。为了防止迭代发散, 对迭代过程须再附加一项要求, 即要求 单调减, 也就是 （4.1.1）满足这项要求的算法称为下山法.将Newton迭代法与下山法结合起来使用的方法, 称为Newton下山法, 即将Newton迭代法的计算结果 （4.1.2）与前一步的近似值适当加权平均作为新的改进值 （4.1.3） 其中称为下山因子, 下山因子的选取应保证单调减, 即 （4.1.3）式即为 （4.1.4）称为Newton下山法。 下山因子的选择一般采用试算法。即由迭代即由迭代得后，取不同的值试算。通常取，用（4.1.3）式进行试算，在计算。每一次的试算，都要判断一次（4.1.1）式。 注：在进行算法设计时，若在整个的迭代过程中，存在一次试算不能满足（4.1.1），则迭代失败，在这种情况下，若对的取值不家限制，则整个算法进入死循环，为了防止算法的死循环，我们因对的选取作一个停机准则，对此我们可另选取初值进行迭代。4.2 一种新的Newton迭代法加速设计13 对于非线性方程（1.1.1），若 是该方程的单根，在区间满足二阶连续可导，由算术平均Newton迭代法格式8 （4.2.1）可知，我们对（4.2.1）中的第一式进行Newton迭代法，则可的得到如下的迭代格式： （4.2.2）迭代格式要求初始点要充分接近零点， 在区间上具有二阶连续导数，且满足，则改迭代（4.2.2）三阶收敛。证明：Newton迭代格式为相应的迭代函数为 （4.2.3）由于Newton迭代法在单根时至少是二阶收敛。则有迭代格式（4.2.2）的迭代函数： （4.2.4）故有。对（4.2.4）两边求导得： （3.2.5）由于，可知对（4.2.5）再求导有：有因为 ，故有 （4.2.6）由于是方程（1.1.1）的单根，则Newton迭代法至少二阶收敛。由此，迭代格式（4.2.2）是三阶收敛4.3小结： 在这里我们对Newton迭代法作了一下推广和一种加速迭代的设计，同时也给出了一种在单根时有三阶收敛速度的Newton迭代。第五章 Newton迭代法的应用5.1 Newton迭代法的Matlab实现下面我们给出Newton迭代的算法设计步骤1：步骤1 给定与的相允许误差、，给定最多迭代次数N，给定初值。计算，。步骤2 按Newton迭代格式（1.1.3）计算，再计算 步骤3 若满足或者，则终止迭代，以作为根输出。否则转到步骤4。这里有步骤4 若迭代次数达到N，仍为求的满足允许误差的根，或者，则停止程序：否则以代替转到步骤2。5.2 数值举例 首先看Newton迭代法应用的一个经典例子，开方计算。即：给定任何正数，有 （5.2.1）用Newton迭代法求方程（5.2.1）近似根（计算机实现），其计算公式为： (5.2.2)证明对给定的任意初值均二次收敛。分析：由公式（5.2.2），设有迭代函数为 （5.2.3）从而 则有 从而对任意的初值，由定理1可知，该迭代法均二阶收敛。例1用Newton迭代法解方程 分析：我们知道，该方程在区间上有一实根(证明见附录(1)。下面我们分别选取初值为0、1、2三种情况看看Newton迭代法的效果 newton(x.3-x-3,3*x.2-1,0,5e-16,5e-16,1)函数 x.3-x-3 的Newton迭代法 k f(x) dfdx x(k+1) 1 -3 -1 -3.00000000000000 2 -27 26 -1.96153846153846 3 -8.59 10.5 -1.14717596140355 4 -3.36 2.95 -0.00657937148071 5 -2.99 -1 -3.00038907407123 6 -27 26 -1.96181817566632 7 -8.59 10.5 -1.14743022848160 8 -3.36 2.95 -0.00725624755242 9 -2.99 -1 -3.00047318877322 10 -27 26 -1.96187864636024 11 -8.59 10.5 -1.14748519321677 12 -3.36 2.95 -0.00740250133287 13 -2.99 -1 -3.00049244291695 14 -27 26 -1.96189248824631 15 -8.59 10.5 -1.14749777454454 16 -3.36 2.95 -0.00743597525670 17 -2.99 -1 -3.00049690365354 18 -27 26 -1.96189569508551 19 -8.59 10.5 -1.14750068932977 20 -3.36 2.95 -0.00744373016891Warning: 在达到指定的次数20 后仍未找到满足指定允许误差的根 newton(x.3-x-3,3*x.2-1,1,5e-16,5e-16,1)函数 x.3-x-3 的Newton迭代法 k f(x) dfdx x(k+1) 1 -3 2 2.50000000000000 2 10.1 17.8 1.92957746478873 3 2.25 10.2 1.70786640021144 4 0.274 7.75 1.67255847335313 5 0.00634 7.39 1.67170038194364 6 3.69e-006 7.38 1.67169988165733 7 1.26e-012 7.38 1.67169988165716 8 -8.88e-016 7.38 1.67169988165716ans =1.6717 newton(x.3-x-3,3*x.2-1,2,5e-16,5e-16,1)函数 x.3-x-3 的Newton迭代法 k f(x) dfdx x(k+1) 1 3 11 1.72727272727273 2 0.426 7.95 1.67369117369117 3 0.0147 7.4 1.67170256974750 4 1.98e-005 7.38 1.67169988166207 5 3.62e-011 7.38 1.67169988165716 6 -8.88e-016 7.38 1.67169988165716ans =1.6717 由以上计算可知，当初值改变是，很可能会影响到Newton迭代法的结果和迭代过程。对于初值去0的情况，我们可以从一下图示（图4）可以体会其发散的理由：图45.1并且我们可以看到，在区间上函数是连续单调递增的，故其Newton迭代法有很好的收敛效果。一般地，如果是二次连续可导且在根附近局部收敛，那么应用Newton迭代法解决方程的根效果提别的好，其中它有两大优点：一时单调收敛；二是具有二价收敛；但是，我们从科学计算的角度出发，Newton迭代法的算法并不简单。因为，它的每一次迭代导函数和导函数的值，这对于科学计算来说是意见难事，就当今科学计算而言，还没有很好的解决计算机求导问题。这使得Newton迭代法在其算法的复杂性外，还存在这自身的不足。但就其整体而言，它的缺点与不足没别要看的太严重。不论是在科学计算上，还是在求非线性方程的理论上，它都有很重要的地位（2-6）。应用Newton迭代法，我们必须注意它的收敛性和迭代初值的选取。就如定理1与定理2所属条件。其初值选取的重要性可有例1可看出。在Newton迭代法收敛的情况下，其迭代初值直接影响到迭代的优越与否。而非线性方程（1.1.1）我们有专们的方法实现确定它的有根区间9，这也使得我们的Newton迭代法在使用上变得很方便。5.3小结： 本章针对牛顿迭代存在的不足提出改进后的实际应用，选取适当的例题做一个实际应用上的检验。对改进后的牛顿迭代在精确度上作实际的验证。第六章：总 论结 Newton迭代法是一个重要的计算方法和思想。牛顿迭代法的主要功能：计算方程时可以比较快速方便的计算出来结果但并不影响计算出来结果的精确度，运用于多种工业设计和数学设计方面，其重要性可见一般。 作为迭代法，其收敛性和收敛速度时期关键，收敛性保证了起迭代法的适用性，而收敛速度则是提高计算效率的根本，而适用和效率是我们解决问题的关键。本文就主要在这两方面，在对前人所作贡献的基础上，集中的给出了Newton迭代法的收敛性和收敛速度，为我们的初学者提供了一个很好的参考平台。在文中，我们给出了Newton迭代法的不足与优越性，总的来说，Newton迭代法是很重要的迭代法，很多的迭代法都是由它演变或启发而来，对它的全面掌握对我们学习迭代法是有很好的启发作用的。参考文献1李庆扬，王熊超，易大义.数值分析M.北京：清华大学出版社，20092 吴新元，对牛顿迭代法的一个重要修改，应用数学和力学M，1999，20（8）：863-8663J.M.Gutierrez and ,M.A.Hernandez , Newtons method under weak Kantorovich conditions.IMA J.Numer.Anal.,20(2002)521-5324王兴华，弱条件下Euler族迭代的收敛性M，中国科学（