牛顿拉夫森(NewtonRaphson)迭代法

1、牛顿迭代法牛顿迭代法也称为牛顿拉夫森迭代法，它是数值分析中最重要的方法之一，它不仅适用于方程或方程组的求解，还常用于微分方程和积分方程求解。.牛1顿迭代法用迭代法解非线性方程时，如何构造迭代函数是非常重要的，那么怎样构造的迭代函数才能保证迭代法收敛呢？牛顿迭代法就是常用的方法之一，其迭代格式的来源大概有以下几种方式：设f(X)C2a,b，对f(X)在点Xoa，b作泰勒展开：f()(XX)2f(X)f(X)f(X)(Xx)0002!f(X)f(X)f(X)(XX)000。Xx丄0略去二次项，得到f(x)的线性近似式:由此得到方程f(x)0的近似根(假定八x0)f(x0)即可构造出迭代格式假定f(

2、xk)这就是牛顿迭代公式，若得到的序列k/f(x)f(X)kxk收敛于，则就是非线性方程的根。牛顿迭代法也称为牛顿切线法，这是由于f(x)的线xxk1k公式性化近似函数1(x)=f(X0)广(x0)(xX0)是曲线y=f(x)过点(X0,f(X0)的切线而得名的，求f(x)的零点代之以求1(x)的零点，即切线1(x)与x轴交点的横坐标，如右图所示，这就是牛顿切线法的几何解释。实际上，牛顿迭代法冃牛顿迭代公式，由Xk得到Xk，从几何图形上看，就是过点切线lk，切线lk与x轴的交点就是Xk，所以有xk一.，整理后也能得出牛顿迭代公式：xxf(Xk)kkf(x)k。要保证迭代法收敛，不管非线性方程f

3、(X)的形式如何，总可以构造:X(X)Xk(X)f(X)(k(X)0)作为方程求解的迭代函数。因为：叫)(X)f(X)(X)广(X)而且(X)在根附近越小，其局部收敛速度越快，故可令：()0()0k()1-f()即根不是f(X)的重根，则由()0得：广，k(x)-XXf(Xk)因此可令广(x)，则也可以得出迭代公式：kkf(xk)。迭代法的基本思想是将方程f(x)0改写成等价的迭代形式xx)，但随之而来的问题却是迭代公式不一定收敛，或者收敛的速度较慢。运用前述加速技巧，对于简单迭代过程xnxnf(I)，其加速公式具有形式：n!xnJI”匸”xn岛(3些)其中x(x)，其中n1nxxfM2记L1

4、，上面两式可以合并写成：nL(x)xf(x)这种迭代公式称作简单的牛顿公式，其相应的迭代函数是：L。需要注意的是，由于L是(x)的估计值，若取(x)xf(x)，则(x)实际上便是f(x)的估计值。假设广(x)，则可以用广(x)代替上式中的L,就可得到牛顿法的迭代Xx公式：n八X?。牛顿迭代法实质上是一种线性化方法，其基本思想是将非线性方程逐步归结为某种线性方程来求解。.牛2顿迭代法的收敛性(x)xlL牛顿迭代公式可以看成是由广(x)而获得的不动点迭代格式。这样就可以应用不动点迭代的收敛原则，只须证明在根附近的迭代函数是一个压缩映象。由于：(x)1.f(x)2f(x)f(x)f(x)f(x)f(

5、x)2f(x)2，().f()f()0这里的根是单根，即fC)网且广()0，于是：ME2。那么由(x)的连续性可知，存在一个邻域()，对这个邻域内的一切x，有：(x)q，其中vqvi因此(x)为区间()上的一个压缩映象，于是有以下结论：定理设f(x)C2a，b，x*是f(x)0的精确解，且广(x*)皿，则存在x*的邻域(x*x*B)，对于任何迭代初值x0(x*x*-B)，迭代序列叮收敛于x*。牛顿迭代法具有较高的收敛速度，它的收敛阶数为=2而牛顿迭代法的局部收敛性较强，只有初值充分地接近x*，才能确保迭代序列的收敛性。为了放宽对局部收敛性的限制必须再增加条件建立以下收敛的充分条件。上，定理设门

6、x)C2a，b，且满足：在区间a，bf(a)f(b)0,)f(x)0；八X)不变号；X0叫b，满足条件：f(%)八X0)则牛顿迭代序列Xn，单调地收敛于方程f(X)0的唯一解X*。由条件至条件可归结为四种情形：f(b)0f(b)0f(b)0f(b)0f(a)0f(a)0f(a)0f(a)0如对定理的几何意义作如下说明：条件保证了根的存在性；条件表明函数单调变化，在区间ab内有惟一的根；条件表示函数图形在区间ab上的凹向不变。条件和条件一【例丨解令f(对于给定的正数a，用牛顿法建立x，则f(x)07求平方根的收敛迭代0亦、丿hcx用牛顿法求解的迭代公式是：n由于当x时，广(x)2x02:.土)X

7、nXn，式，故由收敛定理可知，对于任意满足条件X0a的初始近似值，由选代公式所产生的序列必定收敛于平方根Z。公式是计算平方根的准确而有效的计算方法。牛.顿3迭代法的变形用牛顿法解方程，虽然在单根附近具有较快的收敛速度，但它有个明显的缺点，就是每次都要计算导数广(X)，当f(X)比较复杂时，计算广(X)可能很困难。下面介绍两种克服这种困难的方法，另外还介绍一种扩大牛顿迭代法初值选择范围的方法，它们统称为变形的牛顿迭代法。1简化牛顿法为避免频繁地计算导数值广(x)，可将它取为固定值，比如在牛顿迭代公式中用广()代替f(xn)，即在迭代过程中始终保持分母不变，则有简化牛顿迭代公式(或固定斜率切线xx

8、.丿乞2法：nn广(x)公式其几何意义如下图所示，这时除第一次迭代仍为曲线的切线外，其余皆为该切线的平行线。简化牛顿法避免了每次计算导数值。I1更一般地，若取广FL则迭代公式成为：xx.02nnL，称为推广的简化切线法。这时L值应MW)有满足下式：(x)1f.1，可见当L与广(X)同号且满足上述不等式时，推广的简化多数法里也曾得到过。牛顿法对初始值的选取要求是很高的。一般地说，牛顿法只艮太远时，迭代将不收敛，而一旦初始值进入收敛域内，牛顿法就有平方收敛的速度，为了扬长避短，扩大初始值选取的范围，下面介绍牛顿法的一种改进牛顿下山法。xxf(Xn)将牛顿法的迭代公式修改为：f(J)公式其中，是一个

9、参数，的选取应使fXV成立，当f(Xn)V或XnXnVx*x，就停止迭代，且取XXn，其中,为事先给定的精度，称为残量精确度，为根的误差限；否则再减，继续迭代。按上述迭代过程计算，实际上得到了一个以零为下界的严格单调下降的函数值序列，这个方法就称为牛顿下山法。称为下山因子，要求满足V1，称为下山因子下界，为了方便，一般开始时可简单地取1，然后逐步分半11减小，即可选耳又，2，22，巳，且使?V丁怎)成立。牛顿下山法计算步骤可归纳如下：选取初始近似值Xo；取下山因子I；XXf(Xn)计算Xn-，”n八叮计算f(Xn)，并比较fWJ与fF的大小，分以下两种情况：若?V/叮，则当V时，则就耳艾XXn

10、，计算过程结束；当XnXn，时，则把I作为新的1值，并重复回到。若f(Xn)f(Xn)，则当且fW.)V，就取，计算过程结束；否则，若，而fJ)时，则把Xn加上一个适当选定的小正数，即取J作为新的Xn值，并转向重复计算；当.，且f(X时，则将下山因子缩小一半，并转向重复计算。牛顿下山法不但放宽了初值的选取，且有时对某一初值，虽然用牛顿法不收敛，但用牛顿下山法却有可能收敛。一般来说，牛顿下山法不再有平方收敛速度，它的优点在于可能将原来收敛域以外的初始值，经过几次迭代后拉入收敛域内。例如，已知方程f(X)X3X二的一个根为X*2若取初值X0二.用牛顿法计算得到的第一次近似值x117.9反而比x0更

11、偏离根。丄25时，可得x1.140631，修正后的迭代序列收敛。若改用牛顿下山法，当取下山因(沈建华)(史万明)f(X)f(X)n0XXn0.弦4截法1单点弦截法为避免牛顿迭代法中导数的计算，可用平均变化率0来近似代替f(xn)，于是得到如下迭代公式0 xxnnf(x)nf(x)f(x)n0 x、xf(x)xf(x)0f(x)f(x)n0公式0称为单点弦截法。单点弦截法具有明显的几何意义，它是用联结点(0,y0与点(,yn的直线，代替曲线求取与横轴交点作为近似值xn的方法，以后再过x0，人与xn1，yn两点，作直线求取与横轴的交点作为xn2，等等。其中x0，是一个固定点，称为不动点，另一点则不断更换，故名单点弦截法。可以证明，单点弦截法具有收敛的阶=,即具有线性收敛速度。，y0改为变动点xn，yn)则得到下面的双点弦截lx、xf(x)xf(x)nf(x)f(xj公式nnj上相当于过点x，fq.)和点“k，f*)作弦，然后用弦与x轴的交点的横坐标xk1作为x*的新的近似值。由于在双点弦截法中，构造的迭代公式在计算新的近似值xk!时，不仅用到点xk上的函数值f(X，而且还用到点xk及其函数值，这就有可能提高迭代法的收