当前位置：文档之家 › 牛顿-拉夫森(Newton-Raphson)迭代法

牛顿-拉夫森(Newton-Raphson)迭代法

  • 格式：doc
  • 大小：233.00 KB
  • 文档页数：6

§3.4 牛顿迭代法牛顿迭代法也称为牛顿-拉夫森(Newton-Raphson)迭代法，它是数值分析中最重要的方法之一，它不仅适用于方程或方程组的求解，还常用于微分方程和积分方程求解。

3.4.1 牛顿迭代法用迭代法解非线性方程时，如何构造迭代函数是非常重要的，那么怎样构造的迭代函数才能保证迭代法收敛呢？牛顿迭代法就是常用的方法之一，其迭代格式的来源大概有以下几种方式：1设],[)(2b a C x f ∈，对)(x f 在点],[0b a x ∈作泰勒展开： !2))((''))((')()(20000x x f x x x f x f x f -+-+=ξ略去二次项，得到)(x f 的线性近似式：))((')()(000x x x f x f x f -+≈。

由此得到方程=)(x f 0的近似根(假定≠)('0x f 0)，)(')(000x f x f x x -=即可构造出迭代格式(假定≠)('k x f 0)：)(')(1k k k k x f x f x x -=+ 公式(3.4.1)这就是牛顿迭代公式，若得到的序列{k x }收敛于α，则α就是非线性方程的根。

2 牛顿迭代法也称为牛顿切线法，这是由于)(x f 的线性化近似函数)(x l ＝))((')(000x x x f x f -+是曲线y ＝)(x f 过点))(,(00x f x 的切线而得名的，求)(x f 的零点代之以求)(x l 的零点，即切线)(x l 与x 轴交点的横坐标，如右图所示，这就是牛顿切线法的几何解释。

实际上，牛顿迭代法也可以从几何意义上推出。

利用牛顿迭代公式，由k x 得到1+k x ，从几何图形上看，就是过点))(,(k k x f x 作函数)(x f 的切线k l ，切线k l 与x 轴的交点就是1+k x ，所以有1)()('+-=k k k k x x x f x f ，整理后也能得出牛顿迭代公式： )(')(1k k k k x f x f x x -=+。

3 要保证迭代法收敛，不管非线性方程=)(x f 0的形式如何，总可以构造：)()()(x f x k x x x -==ϕ )0)((≠x k作为方程求解的迭代函数。

因为：)(')()()('1)('x f x k x f x k x --=ϕ而且)('x ϕ在根α附近越小，其局部收敛速度越快，故可令：0)('=αϕ若≠)('αf 0(即根α不是=)(x f 0的重根)，则由0)('=αϕ得：)('1)(ααf k =，因此可令)('1)(x f x k =，则也可以得出迭代公式：)(')(1k k k k x f x f x x -=+。

4 迭代法的基本思想是将方程0)(=x f 改写成等价的迭代形式)(x x ϕ=，但随之而来的问题却是迭代公式不一定收敛，或者收敛的速度较慢。

运用前述加速技巧，对于简单迭代过程)(1n n n x f x x +=+，其加速公式具有形式：θθϕ--=+1)(1n n n x x x )(111n n n x x x --+=++θθ，其中)(1n n x x ϕ=+ 记1-=θL ，上面两式可以合并写成：L x f x x n n n )(1-=+这种迭代公式称作简单的牛顿公式，其相应的迭代函数是：L x f x x )()(-=ϕ。

需要注意的是，由于L 是)('x ϕ的估计值，若取)()(x f x x +=ϕ，则)('x ϕ实际上便是)('x f 的估计值。

假设0)('≠x f ，则可以用)('x f 代替上式中的L ，就可得到牛顿法的迭代公式：)(')(1n n n n x f x f x x -=+。

牛顿迭代法实质上是一种线性化方法，其基本思想是将非线性方程逐步归结为某种线性方程来求解。

3.4.2 牛顿迭代法的收敛性牛顿迭代公式可以看成是由)(')()(x f x f x x -=ϕ而获得的不动点迭代格式。

这样就可以应用不动点迭代的收敛原则，只须证明在根α附近的迭代函数是一个压缩映象。

由于：222)]('[)(")()]('[)(")()]('[1)('x f x f x f x f x f x f x f x =--=ϕ，这里的根α是单根，即0)(=αf 且0)('≠αf ，于是：0)]('[)(")()('2==ααααϕf f f 。

那么由)('x ϕ的连续性可知，存在一个邻域),(δαδα+-，对这个邻域内的一切x ，有：q x <)('ϕ，其中O ＜q ＜1，因此)(x ϕ为区间),(δαδα+-上的一个压缩映象，于是有以下结论：定理 3.4.1 设],[)(2b a C x f ∈，*x 是0)(=x f 的精确解，且0*)('≠x f ，则存在*x 的δ邻域)*,*(δδ+-x x ，对于任何迭代初值)*,*(0δδ+-∈x x x ，迭代序列}{n x 收敛于*x 。

牛顿迭代法具有较高的收敛速度，它的收敛阶数为p ＝2；而牛顿迭代法的局部收敛性较强，只有初值充分地接近*x，才能确保迭代序列的收敛性。

为了放宽对局部收敛性的限制，必须再增加条件建立以下收敛的充分条件。

定理 3.4.2设],[)(2baCxf∈，且满足：在区间],[ba上，⑴)()(<bfaf；⑵0)('≠xf；⑶)("xf不变号；⑷],[bax∈，满足条件：)(")(>xfxf则牛顿迭代序列}{nx，单调地收敛于方程)(=xf的唯一解*x。

由条件⑴至条件⑷可归结为四种情形：①)(<af，0)(>bf，0)('>xf，0)(">xf；②)(<af，0)(>bf，0)('>xf，0)("<xf；③)(>af，0)(<bf，0)('<xf，0)(">xf；④)(>af，0)(<bf，0)('<xf，0)("<xf。

对定理的几何意义作如下说明：条件⑴保证了根的存在性；条件⑵表明函数单调变化，在区间],[ba内有惟一的根；条件⑶表示函数图形在区间],[ba上的凹向不变。

条件⑶和条件⑷一起保证了每一次迭代值都界于区间],[ba内。

在不满足上述收敛充分条件时，有可能导致迭代值远离所求根的情况或死循环的情况(如下图所示)。

【例3.4.1】对于给定的正数a ，用牛顿法建立求平方根的收敛迭代公式。

解 令a x x f -=2)(，(x ＞0)，则0)(=x f 的正根就是a 。

用牛顿法求解的迭代公式是：)(21221n n n n n n x ax x a x x x +=--=+， 公式(3.4.2) 由于当x ＞0时，x x f 2)('=＞0，2)(''=x f ＞0，故由收敛定理可知，对于任意满足条件a x >0的初始近似值，由选代公式所产生的序列必定收敛于平方根a 。

公式(3.4.2)是计算平方根的准确而有效的计算方法。

3.4.3 牛顿迭代法的变形用牛顿法解方程，虽然在单根附近具有较快的收敛速度，但它有个明显的缺点，就是每次都要计算导数)('x f ，当)(x f 比较复杂时，计算)('x f 可能很困难。

下面介绍两种克服这种困难的方法，另外还介绍一种扩大牛顿迭代法初值选择范围的方法，它们统称为变形的牛顿迭代法。

1 简化牛顿法为避免频繁地计算导数值)('x f ，可将它取为固定值，比如在牛顿迭代公式中用)('0x f 代替)('n x f ，即在迭代过程中始终保持分母不变，则有简化牛顿迭代公式(或固定斜率切线法)：)(')(01x f x f x x n n n -=+ 公式(3.4.3)其几何意义如下图所示，这时除第一次迭代仍为曲线的切线外，其余皆为该切线的平行线。

简化牛顿法避免了每次计算导数值。

更一般地，若取L x f n =)(',则迭代公式成为：L x f x x n n n )(1-=+，称为推广的简化切线法。

这时L 值应满足下式：1)('1)('<-=L x f x ϕ满足上式的L 为：2)('0<<L x f ，可见当L 与)('x f 同号且满足上述不等式时，推广的简化切线法是收敛的。

该迭代形式在参数法里也曾得到过。

2 由牛顿法的收敛性定理知，牛顿法对初始值的选取要求是很高的。

一般地说，牛顿法只有局部收敛性。

当初始值取得离根太远时，迭代将不收敛，而一旦初始值进入收敛域内，牛顿法就有平方收敛的速度，为了扬长避短，扩大初始值选取的范围，下面介绍牛顿法的一种改进——牛顿下山法。

将牛顿法的迭代公式修改为：)(')(1n n n n x f x f x x λ-=+ 公式(3.4.3)其中，λ是一个参数，λ的选取应使)(1+n x f ＜)(n x f 成立，当)(1+n x f ＜1ε或nn x x -+1＜2ε，就停止迭代，且取1*+≈n x x ，其中1ε，2ε为事先给定的精度，1ε称为残量精确度，2ε为根的误差限；否则再减λ，继续迭代。

按上述迭代过程计算，实际上得到了一个以零为下界的严格单调下降的函数值序列，这个方法就称为牛顿下山法。

λ称为下山因子，要求满足0＜λε1≤≤λ，λε称为下山因子下界，为了方便，一般开始时可简单地取1=λ，然后逐步分半减小，即可选取1=λ，21，221，…，λελ≥，且使)(1+n x f ＜)(n x f 成立。

牛顿下山法计算步骤可归纳如下： ⑴ 选取初始近似值0x ；⑵ 取下山因子1=λ；⑶ 计算1+n x ，)(')(1n n n n x f x f x x λ-=+⑷ 计算)(1+n x f ，并比较)(1+n x f 与)(n x f 的大小，分以下两种情况：① 若)(1+n x f ＜)(n x f ，则当nn x x -+1＜2ε时，则就取1*+≈n x x ，计算过程结束；当nn x x -+1＞2ε时，则把1+n x 作为新的n x 值，并重复回到⑶。

②若)(1+n x f ≥)(n x f ，则当λελ≤且)(1+n x f ＜1ε，就取n x x ≈*，计算过程结束；否则，若λελ≤，而)(1+n x f ≥1ε时，则把1+n x 加上一个适当选定的小正数，即取δ++1n x 作为新的n x 值，并转向⑶重复计算；当λελ>，且)(1+n x f ≥1ε时，则将下山因子缩小一半，并转向⑶重复计算。

合集下载

牛顿迭代法论文

牛顿迭代法论文

南昌工程学院课程设计姓名：专业：年级：学号：年月日牛顿迭代算法摘要: 牛顿迭代法（Newton's method）又称为牛顿-拉夫逊方法（Newton-Raphsonmethod），它是牛顿在17世纪提出的一种在实数域和复数域上近似求解方程的方法。

多数方程不存在求根公式，因此求精确根非常困难，甚至不可能，从而寻找方程的近似根就显得特别重要。

牛顿迭代法是求方程根的重要方法之一，其最大优点是在方程f(x) = 0的单根附近具有平方收敛，而且该法还可以用来求方程的重根、复根,此时线性收敛，但是可通过一些方法变成超线性收敛。

另外该方法广泛用于计算机编程中。

牛顿迭代法是一个重要的计算方法和思想。

牛顿迭代法的主要功能：计算方程时可以比较快速方便的计算出来结果但并不影响计算出来结果的精确度，运用于多种工业设计和数学设计方面.关键字: 牛顿迭代方程根算法一 .牛顿迭代法简介1.1 牛顿迭代法的概述牛顿迭代法（Newton's method）又称为牛顿-拉夫逊方法（Newton-Raphson method），它是牛顿在17世纪提出的一种在实数域和复数域上近似求解方程的方法。

多数方程不存在求根公式，因此求精确根非常困难，甚至不可能，从而寻找方程的近似根就显得特别重要。

方法使用函数f(x)的泰勒级数的前面几项来寻找方程f(x) = 0的根。

设r是f(x) = 0的根，选取x0作为r初始近似值，过点（x0,f(x0)）做曲线y = f(x)的切线L，L的方程为y = f(x0) f'(x0)(x-x0)，求出L与x轴交点的横坐标 x1 = x0-f(x0)/f'(x0)，称x1为r的一次近似值。

过点（x1,f(x1)）做曲线y = f(x)的切线，并求该切线与x轴的横坐标 x2 = x1-f(x1)/f'(x1)，称x2为r的二次近似值。

重复以上过程，得r的近似值序列，其中x(n+1)=x(n)－f(x(n))/f'(x(n))，称为r的n+1次近似值，上式称为牛顿迭代公式。

牛顿迭代法(Newton‘s Method)

牛顿迭代法(Newton‘s Method)

牛顿迭代法（Newton’s Method）又称为牛顿-拉夫逊（拉弗森）方法（Newton-Raphson Method），它是牛顿在17世纪提出的一种在实数域和复数域上近似求解方程的方法。

与一阶方法相比，二阶方法使用二阶导数改进了优化，其中最广泛使用的二阶方法是牛顿法。

考虑无约束最优化问题：其中 \theta^{\ast} 为目标函数的极小点，假设 f\left( \theta \right) 具有二阶连续偏导数，若第 k 次迭代值为 \theta^{k} ，则可将f\left( \theta \right)在\theta^{k}近进行二阶泰勒展开：这里，g_{k}=x^{\left( \theta^{k} \right)}=∇f\left( \theta^{k} \right)是f\left( \theta \right) 的梯度向量在点 \theta^{k}的值， H\left( \theta^{k} \right) 是 f\left( \theta \right) 的Hessian矩阵：在点 \theta^{\left( k \right)}的值。

函数 f\left( \theta \right) 有极值的必要条件是在极值点处一阶导数为0，即梯度向量为0，特别是当H\left( \theta\right) 是正定矩阵时，函数 f\left( \theta \right) 的极值为极小值。

牛顿法利用极小点的必要条件：这就是牛顿迭代法。

迭代过程可参考下图：在深度学习中，目标函数的表面通常非凸（有很多特征），如鞍点。

因此使用牛顿法是有问题的。

如果Hessian矩阵的特征值并不都是正的，例如，靠近鞍点处，牛顿法实际上会导致更新朝错误的方向移动。

这种情况可以通过正则化Hessian矩阵来避免。

常用的正则化策略包括在Hessian矩阵对角线上增加常数α 。

正则化更新变为：这个正则化策略用于牛顿法的近似，例如Levenberg-Marquardt算，只要Hessian矩阵的负特征值仍然相对接近零，效果就会很好。

牛顿法

牛顿法

牛顿迭代法编辑同义词牛顿法一般指牛顿迭代法牛顿迭代法（Newton's method）又称为牛顿-拉夫逊（拉弗森）方法（Newton-Raphson method），它是牛顿在17世纪提出的一种在实数域和复数域上近似求解方程的方法。

中文名牛顿迭代法外文名Newton's method别名牛顿-拉夫逊（拉弗森）方法提出时间17世纪目录1 产生背景2 牛顿迭代公式3 其他迭代算法▪欧几里德算法▪斐波那契数列4 C语言代码5 C++代码6 matlab代码▪定义函数▪主程序7 Python代码8 Java代码9 JavaScript代码10 Fortran代码产生背景编辑多数方程不存在求根公式，因此求精确根非常困难，甚至不可解，从而寻找方程的近似根就显得特别重要。

方法使用函数的泰勒级数的前面几项来寻找方程的根。

牛顿迭代法是求方程根的重要方法之一，其最大优点是在方程的单根附近具有平方收敛，而且该法还可以用来求方程的重根、复根，此时线性收敛，但是可通过一些方法变成超线性收敛。

另外该方法广泛用于计算机编程中。

牛顿迭代公式编辑设是的根，选取作为的初始近似值，过点做曲线的切线，，则与轴交点的横坐标，称为的一次近似值。

过点做曲线的切线，并求该切线与x轴交点的横坐标，称为r的二次近似值。

重复以上过程，得的近似值序列，其中，称为的次近似值，上式称为牛顿迭代公式。

用牛顿迭代法解非线性方程，是把非线性方程线性化的一种近似方法。

把在点的某邻域内展开成泰勒级数，取其线性部分（即泰勒展开的前两项），并令其等于0，即，以此作为非线性方程的近似方程，若，则其解为，这样，得到牛顿迭代法的一个迭代关系式：。

已经证明，如果是连续的，并且待求的零点是孤立的，那么在零点周围存在一个区域，只要初始值位于这个邻近区域内，那么牛顿法必定收敛。

并且，如果不为0, 那么牛顿法将具有平方收敛的性能. 粗略的说，这意味着每迭代一次，牛顿法结果的有效数字将增加一倍。

Newton迭代法浅析

Newton迭代法浅析

目录第一章：绪论 (2)第二章 Newton迭代原理 (3)2.1 一般迭代思想的设计 (3)2.2 Newton迭代法的原理 (3)2.3小结： (5)第三章 Newton迭代法的收敛性 (6)3.1 Newton迭代法中不收敛的情况 (6)3.2 定理证明 (7)3.3 Newton迭代法的收敛性分析 (10)3.4小结： (12)第四章两种改进的Newton迭代法 (14)4.1 改进初值x的Newton下山法 (14)4.2 一种新的Newton迭代法加速设计 (15)4.3小结： (16)第五章 Newton迭代法的应用 (17)5.1 Newton迭代法的Matlab实现 (17)5.2 数值举例 (17)5.3小结： (20)总论 (21)参考文献 (22)致谢 (23)第一章绪论在自然科学和工程技术中很多问题的解决常常归结为解非线性方程（组）或者线性方程（组)代数方程组，例如电学中的网络问题，船体数学放样中建立三次样条函数问题，用最小而乘求是实验数据的曲线拟合问题，用差分或者有限元方法解常微分方程等。

关于非线性方程（组）的求解，一般有两类解法：直接法和迭代法。

我们知道，只有一次、二次和三次方程有规范的求根公式，而高于三次的方程0)xf是不存在求根公式的。

因此求根变得一异常的困难。

而科学计算却(很好解决了这一问题，其中最基本的算迭代法了，它对于解决非线性方程（组）的根变得异常方面。

就迭代法而言，Newton迭代法可算是其经典之作。

Newton迭代法又称为Newton-Raphson迭代法，它是Newton在17世纪提出的一种在实数域和复数域上近似求解方程的方法。

牛顿迭代法是求非线性方程（组）根的重要方法之一，其迭代格式简单，且在单根附近具有平方收敛，而且该法还可以用来求方程的重根、复根。

关于Newton迭代法，许多学者为之做了相当多的研究，并且留下了很多经典的文献([2-6])。

Newton迭代法在解决Banach空间中非线性方程或方程组的应用更为重要，如梯形Newton迭代法。