牛顿-拉夫森迭代法

1、3.4牛顿迭代法牛顿迭代法也称为牛顿-拉夫森(Newton-Raphson)迭代法，它是数值分析中最重要的方法 之一，它不仅适用于方程或方程组的求解，还常用于微分方程和积分方程求解。3.4.1牛顿迭代法用迭代法解非线性方程时，如何构造迭代函数是非常重要的，那么怎样构造的迭代函数才 能保证迭代法收敛呢？牛顿迭代法就是常用的方法之一，其迭代格式的来源大概有以下几种方式：1设f(x)G C2ab，对f(x)在点x或b作泰勒展开：f(x) = f(x ) + f(x )(x- x ) + 广(&)(x x)22!略去二次项，得到f (x)的线性近似式：f (x)注f (x)+ f (x)(x-x)。x

2、 = x 八、x = x 八、0），_ f （x ）气+】、f、（X）k由此得到方程f( 由此得到方程f( = 0的近似根(假定f(X ) *f(x )即可构造出迭代格式(假定广(即可构造出迭代格式(假定广(号* 0)： 这就是牛顿迭代公式，若得到的序列Xk收敛于以，则a就是非线性方程的根。（嚣a/Sq）.）9 引2牛顿迭代法也称为牛顿切线法，这是由于f (x)的线 性化近似函数(x) = f (x)+f (x)(x-x)是曲线 = X f (x)过点o f o的切线而得名的，求f (x)的零点代之 以求1 (x)的零点，即切线1 (x)与1轴交点的横坐标，如右图 所示，这就是牛顿切线法的几何

3、解释。实际上，牛顿迭代法 也可以从几何意义上推出。利用牛顿迭代公式，由xk得到xk+1（嚣a/Sq）.）9 引所以有(xkf (号)作函数f的切线1k，切线1k与x轴的交点就是xk+1， f (x )=色上所以有kT xk+1，整理后也能得出牛顿迭代公式：_f (x )气+广T f( x)k o3要保证迭代法收敛，不管非线性方程f (x) = 0的形式如何，总可以构造：x =中(x) = x 一 k (x) f (x)(k (x) * 0)作为方程求解的迭代函数。因为：中(x) = 1 -k(x)f (x) 一k(x)广(x) 而且 (x)在根a附近越小，其局部收敛速度越快，故可令：0(a)=

4、 0若广(a)*0(即根a不是f(*)= 0的重根)，则由甲(a)= 0得：()广(a)，k (*)=二气广外因此可令(*)，则也可以得出迭代公式：+1 f (*k)。4迭代法的基本思想是将方程f(*)= 0改写成等价的迭代形式* =中(*)，但随之而来的 问题却是迭代公式不一定收敛，或者收敛的速度较慢。运用前述加速技巧，对于简单迭代过程 *n+1 = *n + f (叩，其加速公式具有形式:(*n + 1 *n* =(*n + 1 *n* =9 (* )，其中 n+1nf (*) n L记L = T,上面两式可以合并写成：i1 *n+1 =1_0 = 记L = T,上面两式可以合并写成：i1

5、 *9 (*) = * - 业这种迭代公式称作简单的牛顿公式，其相应的迭代函数是：L 。需要注意的是，由于L是9(*)的估计值，若取9 (*) = * + f(*)，则9 (*)实际上便是 广(*)的估计值。假设广(*)* 0，则可以用广(*)代替上式中的L，就可得到牛顿法的迭代 HYPERLINK l bookmark24 o Current Document xf (* * n公式：n+1 n f (*)。牛顿迭代法实质上是一种线性化方法，其基本思想是将非线性方程逐步归结为某种线性方 程来求解。3.4.2牛顿迭代法的收敛性f ( *)9 (*) * ;牛顿迭代公式可以看成是由f (*)而获

6、得的不动点迭代格式。这样就可以应用不动点迭代的收敛原则，只须证明在根a附近的迭代函数是一个压缩映象。由于：,(*) = 1 一 f (*)2 - f (*) f(*) = f (*) f(*)9_ f (*)2 f (*)20(a)= f(以)广(以)=0这里的根a是单根，即f (以)=0且0)。0，于是：广(以)2。那么由0(x)的连续性可知，存在一个邻域(a-5，a+8)，对这个邻域内的一切*，有：(*)| q，其中o q 1，因此中(*)为区间(a8 ,a+S)上的一个压缩映象，于是有以下 结论：定理3.4. 1设f (x)G C 2a,仞，* *是(x) = 0的精确解，且f，( *)

7、 * 0，则存在* * 的8邻域(X * 8 , * * +8 )，对于任何迭代初值*0 G (* * 5，* +8 )，迭代序列*n收敛于 * *。牛顿迭代法具有较高的收敛速度，它的收敛阶数为P =2；而牛顿迭代法的局部收敛性较强，只有初值充分地接近X*，才能确保迭代序列的收敛性。为了放宽对局部收敛性的限制， 必须再增加条件建立以下收敛的充分条件。定理3.4. 2设f(X)G C2a,，且满足：在区间心用上 f (a) f (b) 0则牛顿迭代序列七，单调地收敛于方程f(x)=。的唯一解x *。由条件至条件可归结为四种情形：f (a) 0，f(X) 0，f (X) 0.；f (a) 0，f(

8、X) 0，f (X) 0，f (b) 0，f (X) 0.；f (a) 0，f (b) 0，f(x) 0，f(X) 0时，广(x) = 2x 0，f (x) = 2 0，故由收敛定理可知，对于任意满足条 件X0邮的初始近似值，由选代公式所产生的序列必定收敛于平方根 履。公式(3.4.2)是 计算平方根的准确而有效的计算方法。3.4.3牛顿迭代法的变形用牛顿法解方程，虽然在单根附近具有较快的收敛速度，但它有个明显的缺点，就是每次 都要计算导数广(x)，当f (x)比较复杂时，计算广(x)可能很困难。下面介绍两种克服这种 困难的方法，另外还介绍一种扩大牛顿迭代法初值选择范围的方法，它们统称为变形的

9、牛顿迭 代法。1简化牛顿法为避免频繁地计算导数值广(x)，可将它取为固定值，比如在牛顿迭代公式中用f(xo)代 替f(Xn)，即在迭代过程中始终保持分母不变，则有简化牛顿迭代公式(或固定斜率切线xf (X )X X n法)：n+1n f (Xo)公式(3.4.3)其几何意义如下图所示，这时除第一次迭代仍为曲线的切线外，其余皆为该切线的平行 线。简化牛顿法避免了每次计算导数值。i1七 L ，称为推广的简化切线法。这时L值应 满足下式：可见当L与广3)同号且满足上述不等式时，推广的简化0 v 空 v 2 满足上式的L为： L可见当L与广3)同号且满足上述不等式时，推广的简化2由牛顿法的收敛性定理知

10、，牛顿法对初始值的选取要求是很高的。一般地说，牛顿法只 有局部收敛性。当初始值取得离根太远时，迭代将不收敛，而一旦初始值进入收敛域内，牛顿法就有平方收敛的速度，为了扬长避短，扩大初始值选取的范围，下面介绍牛顿法的一种改进 牛顿下山法。.f (x.f (x )人nf(x )nf (Xnf (Xn)成立，当将牛顿法的迭代公式修改为：n+1其中，人是一个参数，入的选取应使 82，就停止迭代，且取渺Xn+1， 为根的误差限；否则再减人，继续迭代。按上述迭代过程计算，实际上得到了一个以零为下界 的严格单调下降的函数值序列，这个方法就称为牛顿下山法。入称为下山因子，要求满足0其中81，公式(3.4.3)f

11、 W A匕或82为事先给定的精度，81称为残量精确度，%工1，匕称为下山因子下界，为了方便，一般开始时可简单地取入=L然后逐步分半11减小，即可选取X =1，2，22，*2%，且使 ( n+)l I( n 成立。牛顿下山法计算步骤可归纳如下：选取初始近似值X0 ；取下山因子* = 1 ；x = x-f)计算 Xn + 1，E nf(Xn)计算f (Xn+1)，并比较 (Xn+1) 与 If C的大小，分以下两种情况：aja zfch f (X )| |f (x )| 和 X X 8 时和勘日口 X* R X二修vF毛口、吃右n+1 n ，则当n+1n 2时，则就取n+1，计算过程结束；当X X

12、eY Yn+1n8 2时，则把Xn + 1作为新的值，并重复回到。若f n+1) J(Xn)L则当拦8* 且 If (Xn+1) 8*，且f(Xn+1) 281时，则将下山因子缩小一半，并 转向重复计算。牛顿下山法不但放宽了初值的选取，且有时对某一初值，虽然用牛顿法不收敛，但用牛顿 下山法却有可能收敛。一般来说，牛顿下山法不再有平方收敛速度，它的优点在于可能将原来 收敛域以外的初始值，经过几次迭代后拉入收敛域内。例如，已知方程f (X)= X3X 1 = 0的一个根为X* R 1.32472，若取初值X0 =0.6，用牛 顿法计算得到的第一次近似值X1 = 17.9反而比X0更偏离根。若改用牛

13、顿下山法，当取下山因25时，可得X25时，可得X1=1.14063，修正后的迭代序列收敛。(沈建华P138)(史万明P48)子 3.4.4弦截法1单点弦截法为避免牛顿迭代法中导数的计算，可用平均变化率:来近似代替广（七），于是得到如下迭代公式:x = x _f (xnx = x _f (xn)n+ln f (x ) _f (x )n0_ x ) = x0f (xn)(x0)0f (叩-f (x)公式(3.4.4)n2双点弦截法称为单点弦截法。单点弦截法具有明显的几何意义，它 是用联结点A（x0，y0 ）与点B（ xn，yn ）的直线，代替x曲线求取与横轴交点作为近似值 （*0， * ）与（n

14、+ 1，七+1 ）两点 交点作为xn + 2,等等。其中（x0n+1的方法，以后再过作直线求取与横轴的* ）是一个固定点，称为不动点，另一点则不断更换，故名单点弦截法。可 以证明，单点弦截法具有收敛的阶r=1，即具有线性收 敛速度。若把单点弦截法中的不动点芒0，0 ）改为变动点（_1，n_1 ），则得到下面的双点弦截 法的迭代公式：x = x _fM2 （x _ x ） ） xn 1f （xn） fj （xnE n f ） 一 f 3n 一1） nn _1f ） 一 f n 一公式（3.4.5）用弦截法求根的近似值，在几何上相当于过点（气一1，f （气_1），和点（七，f （气）作 弦，然后用弦与x轴的交点的横坐标七+1作为x*的新的近似值。由于在双点弦截法中，构造 的迭代公式在计算新的近似值气+1时，不仅用到点七上 的函数值f （号，而且还用到点xk _1及其函数值，这就 有可能提高迭代法的收敛速度。与牛顿法一样，如果函数 = f （x）在其根