3.43.4 牛顿迭代法牛顿迭代法牛顿迭代法也称为牛顿-拉夫森(Newton-Raphson)迭代法，它是数值分析中最重要的方法 之一，它不仅适用于方程或方程组的求解，还常用于微分方程和积分方程求解。3.4.13.4.1 牛顿迭代法牛顿迭代法用迭代法解非线性方程时，如何构造迭代函数是非常重要的，那么怎样构造的迭代函数才 能保证迭代法收敛呢？牛顿迭代法就是常用的方法之一，其迭代格式的来源大概有以下几种方 式：1 设,)(2baCxf，对)(xf在点,0bax 作泰勒展开：! 2)( )( )()(2 0 000xxfxxxfxfxf略去二次项，得到)(xf的线性近似式：)( )()(000xxxfxfxf。由此得到方程)(xf0 的近似根(假定)( 0xf0)，)( )(00 0xfxfxx即可构造出迭代格式(假定)( kxf0)：)( )( 1 kk kkxfxfxx公式公式(3.4.1)(3.4.1)这就是牛顿迭代公式，若得到的序列kx收敛于，则就是非线性方程的根。2 牛顿迭代法也称为牛顿切线法，这是由于)(xf的线性化近似函数)(xl)( )(000xxxfxf是曲线y )(xf过点)(,(00xfx的切线而得名的，求)(xf的零点代之 以求)(xl的零点，即切线)(xl与x轴交点的横坐标，如右图 所示，这就是牛顿切线法的几何解释。实际上，牛顿迭代法也可以从几何意义上推出。利用牛顿迭代公式，由kx得到1kx，从几何图形上看，就是过点)(,(kkxfx作函数)(xf的切线kl，切线kl与x轴的交点就是1kx，所以有1)()( kkk kxxxfxf ，整理后也能得出牛顿迭代公式：)( )( 1 kk kkxfxfxx 。 3 要保证迭代法收敛，不管非线性方程)(xf0 的形式如何，总可以构造： )()()(xfxkxxx)0)(xk作为方程求解的迭代函数。因为：)( )()()( 1)( xfxkxfxkx而且)( x在根附近越小，其局部收敛速度越快，故可令：0)( 若)( f0(即根不是)(xf0 的重根)，则由0)( 得：)( 1)(fk ，因此可令)( 1)(xfxk ，则也可以得出迭代公式：)( )( 1 kk kkxfxfxx 。4 迭代法的基本思想是将方程0)(xf改写成等价的迭代形式)(xx，但随之而来的 问题却是迭代公式不一定收敛，或者收敛的速度较慢。运用前述加速技巧，对于简单迭代过程 )(1nnnxfxx，其加速公式具有形式： 1)( 1nn nxxx)(111nnnxxx，其中)(1nnxx记1L，上面两式可以合并写成：Lxfxxn nn)( 1这种迭代公式称作简单的牛顿公式，其相应的迭代函数是：Lxfxx)()( 。需要注意的是，由于L是)( x的估计值，若取)()(xfxx，则)( x实际上便是 )( xf的估计值。假设0)( xf，则可以用)( xf代替上式中的L，就可得到牛顿法的迭代公式：)( )( 1 nn nnxfxfxx 。 牛顿迭代法实质上是一种线性化方法，其基本思想是将非线性方程逐步归结为某种线性方 程来求解。3.4.23.4.2 牛顿迭代法的收敛性牛顿迭代法的收敛性牛顿迭代公式可以看成是由)( )()(xfxfxx 而获得的不动点迭代格式。这样就可以应用 不动点迭代的收敛原则，只须证明在根附近的迭代函数是一个压缩映象。由于：222)( )( “)( )( )( “)()( 1)( xfxfxf xfxfxfxfx ，这里的根是单根，即0)(f且0)( f，于是：0)( )( “)()( 2fff。那么由)( x的连续性可知，存在一个邻域),(，对这个邻域内的一切x，有： qx )( ，其中 Oq1，因此)(x为区间),(上的一个压缩映象，于是有以下 结论：定理定理 3.4.13.4.1 设,)(2baCxf，*x是0)(xf的精确解，且0*)( xf，则存在 *x的邻域)*,*(xx，对于任何迭代初值)*,*(0xxx，迭代序列nx收敛 于*x。 牛顿迭代法具有较高的收敛速度，它的收敛阶数为p2；而牛顿迭代法的局部收敛性较强，只有初值充分地接近*x，才能确保迭代序列的收敛性。为了放宽对局部收敛性的限制， 必须再增加条件建立以下收敛的充分条件。定理定理 3.4.23.4.2 设,)(2baCxf，且满足：在区间,ba上， 0)()(bfaf； 0)( xf； )( “ xf不变号； ,0bax ，满足条件：0)( “)(00xfxf则牛顿迭代序列nx，单调地收敛于方程0)(xf的唯一解*x。 由条件至条件可归结为四种情形： 0)(af，0)(bf，0)( xf，0)( “xf； 0)(af，0)(bf，0)( xf，0)( “xf； 0)(af，0)(bf，0)( xf，0)( “xf； 0)(af，0)(bf，0)( xf，0)( “xf。 对定理的几何意义作如下说明：条件保证了根的存在性；条件表明函数单调变化，在区间,ba内有惟一的根；条件表示函数图形在区间,ba上的凹向不变。条件和条件一起保证了每一次迭代值都界于区间,ba内。在不满足上述收敛充分条件时，有可能导致迭代值远离所求根的情况或死循环的情况(如 下图所示)。【例 3.4.1】对于给定的正数a，用牛顿法建立求平方根的收敛迭代公式。解 令axxf2)(，(x0)，则0)(xf的正根就是a。用牛顿法求解的迭代公式是：)(21 221 nn nn nnxaxxaxxx ， 公式公式(3.4.2)(3.4.2)由于当x0 时，xxf2)( 0，2)( xf0，故由收敛定理可知，对于任意满足条件ax 0的初始近似值，由选代公式所产生的序列必定收敛于平方根a。公式(3.4.2)是 计算平方根的准确而有效的计算方法。3.4.33.4.3 牛顿迭代法的变形牛顿迭代法的变形用牛顿法解方程，虽然在单根附近具有较快的收敛速度，但它有个明显的缺点，就是每次都要计算导数)( xf，当)(xf比较复杂时，计算)( xf可能很困难。下面介绍两种克服这种 困难的方法，另外还介绍一种扩大牛顿迭代法初值选择范围的方法，它们统称为变形的牛顿迭 代法。 1 简化牛顿法为避免频繁地计算导数值)( xf，可将它取为固定值，比如在牛顿迭代公式中用)( 0xf代替)( nxf，即在迭代过程中始终保持分母不变，则有简化牛顿迭代公式(或固定斜率切线法)：)( )(01xfxfxxn nn公式公式(3.4.3)(3.4.3) 其几何意义如下图所示，这时除第一次迭代仍为曲线的切线外，其余皆为该切线的平行线。 简化牛顿法避免了每次计算导数值。更一般地，若取Lxfn)( ,则迭代公式成为：Lxfxxn nn)( 1，称为推广的简化切线法。这时L值应 满足下式：1)( 1)( Lxfx满足上式的L为：2)( 0Lxf，可见当L与)( xf同号且满足上述不等式时，推广的简化 切线法是收敛的。该迭代形式在参数法里也曾得到过。 2 由牛顿法的收敛性定理知，牛顿法对初始值的选取要求是很高的。一般地说，牛顿法只 有局部收敛性。当初始值取得离根太远时，迭代将不收敛，而一旦初始值进入收敛域内，牛顿 法就有平方收敛的速度，为了扬长避短，扩大初始值选取的范围，下面介绍牛顿法的一种改进 牛顿下山法。将牛顿法的迭代公式修改为：)( )( 1 nn nnxfxfxx公式公式(3.4.3)(3.4.3)其中，是一个参数，的选取应使)(1nxf)(nxf成立，当)(1nxf1或nnxx12，就停止迭代，且取1*nxx，其中1，2为事先给定的精度，1称为残量精确度，2为根的误差限；否则再减，继续迭代。按上述迭代过程计算，实际上得到了一个以零为 下界的严格单调下降的函数值序列，这个方法就称为牛顿下山法。称为下山因子，要求满足01，称为下山因子下界，为了方便，一般开始时可简单地取1，然后逐步分半减小，即可选取1，21，221，且使)(1nxf)(nxf成立。 牛顿下山法计算步骤可归纳如下： 选取初始近似值0x； 取下山因子1； 计算1nx，)( )( 1 nn nnxfxfxx 计算)(1nxf，并比较)(1nxf与)(nxf的大小，分以下两种情况： 若)(1nxf)(nxf，则当nnxx12时，则就取1*nxx，计算过程结束；当nnxx12时，则把1nx作为新的nx值，并重复回到。若)(1nxf)(nxf，则当且)(1nxf1，就取nxx *，计算过程结束；否则，若，而)(1nxf1时，则把1nx加上一个适当选定的小正数，即取1nx作为新的nx值，并转向重复计算；当，且)(1nxf1时，则将下山因子缩小一半，并 转向重复计算。 牛顿下山法不但放宽了初值的选取，且有时对某一初值，虽然用牛顿法不收敛，但用牛顿 下山法却有可能收敛。一般来说，牛顿下山法不再有平方收敛速度，它的优点在于可能将原来 收敛域以外的初始值，经过几次迭代后拉入收敛域内。例如，已知方程1)(3xxxf0 的一个根为*x1.32472，若取初值0x0.6，用牛顿法计算得到的第一次近似值9 .171x反而比0x更偏离根。若改用牛顿下山法，当取下山因子521 时，可得14063. 11x，修正后的迭代序列收敛。（沈建华 P138）（史万明 P48）3.4.43.4.4 弦截法弦截法1 单点弦截法为避免牛顿迭代法中导数的计算，可用平均变化率：00)()( xxxfxfnn 来近似代替)( nxf，于是得到如下迭代公式：)()()()()()()()(000 0 01xfxfxfxxfxxxxfxfxfxxnnn n nn nn公式公式(3.4.4)(3.4.4) 称为单点弦截法。单点弦截法具有明显的几何意义，它是用联结点 A(0x，0y)与点 B(nx，ny)的直线，代替曲线求取与横轴交点作为近似值1nx的方法，以后再过(0x，0y)与(1nx，1ny)两点，作直线求取与横轴的交点作为2nx，等等。其中(0x，0y)是一个固定点， 称为不动点，另一点则不断更换，故名单点弦截法。可 以证明，单点弦截法具有收敛的阶 r1，即具有线性收 敛速度。 2 双点弦截法若把单点弦截法中的不动点(0x，0y)改为变动点(1nx，1ny)，则得到下面的双点弦截 法的迭代公式：)()()()()()()()(111 1 11 nnnnnn nn nnn nnxfxfxfxxfxxxxfxfxfxx公式公式(3.4.5)(3.4.5)用弦截法求根的近似值，在几何上相当于过点(1kx，)(1kxf)，和点(kx，)(kxf)作弦，然后用弦与x轴的交点的横坐标1kx作为*x的新的近似值。由于在双点弦截法中，构造的迭代公式在计算新的近似值1kx时，不仅用到点kx上的函数值)(kxf，而且还用到点1kx及其 函数值，这就有可能提高迭代法的收敛速度。与牛顿法一样，如果函数)(xfy