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

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

略去二次项，得到的线性近似式：。
由此得到方程0的近似根(假定0)，
即可构造出迭代格式(假定0)： 公式(3.4.1)
这就是牛顿迭代公式，若得到的序列{}收敛于则就是非线性方程的根。
2 牛顿迭代法也称为牛顿切线法，这是由于的线性化近似函数＝是曲线＝过点的切线而得名的，求的零点代之以求的零点，即切线与轴交点的横坐标，如右图所示，这就是牛顿切线法的几何解释。实际上，牛顿迭代法也可以从几何意义上推出。利用牛顿迭代公式，由得到，从几何图形上看，就是过点作函数的切线，切线与轴的交点就是，所以有，整理后也能得出牛顿迭代公式：
。
3 要保证迭代法收敛，不管非线性方程0的形式如何，总可以构造：

作为方程求解的迭代函数。因为：
而且在根附近越小，其局部收敛速度越快，故可令：
若0(即根不是0的重根)，则由得：，
因此可令，则也可以得出迭代公式：。
4 迭代法的基本思想是将方程改写成等价的迭代形式，但随之而来的问题却是迭代公式不一定收敛，或者收敛的速度较慢。运用前述加速技巧，对于简单迭代过程，其加速公式具有形式：
，其中
记，上面两式可以合并写成：
这种迭代公式称作简单的牛顿公式，其相应的迭代函数是：。
需要注意的是，由于是的估计值，若取，则实际上便是的估计值。假设，则可以用代替上式中的，就可得到牛顿法的迭代公式：。
牛顿迭代法实质上是一种线性化方法，其基本思想是将非线性方程逐步归结为某种线性方程来求解。
3.4.2 牛顿迭代法的收敛性
牛顿迭代公式可以看成是由而获得的不动点迭代格式。这样就可以应用不动点迭代的收敛原则，只须证明在根附近的迭代函数是一个压缩映象。由于：，
这里的根是单根，即且，于是：。
那么由的连续性可知，存在一个邻域，对这个邻域内的一切，有：，其中O＜＜1，因此为区间上的一个压缩映象，于是有以下结论：
定理 3.4.1 设，是的精确解，且，则存在的邻域，对于任何迭代初值，迭代序列收敛于。
牛顿迭代法具有较高的收敛速度，它的收敛阶数为＝2；而牛顿迭代法的局部收敛性较强，只有初值充分地接近，才能确保迭代序列的收敛性。为了放宽对局部收敛性的限制，必须再增加条件建立以下收敛的充分条件。
定理 3.4.2 设，且满足：在区间上，
⑴ ；⑵ ；
⑶ 不变号；⑷ ，满足条件
则牛顿迭代序列，单调地收敛于方程的唯一解。
由条件⑴至条件⑷可归结为四种情形：
① ，，，；
② ，，，；
③ ，，，；
④ ，，，。
对定理的几何意义作如下说明：条件⑴保证了根的存在性；条件⑵表明函数单调变化，在区间内有惟一的根；条件⑶表示函数图形在区间上的凹向不变。条件⑶和条件⑷一起保证了每一次迭代值都界于区间内。

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

【例3.4.1】对于给定的正数，用牛顿法建立求平方根的收敛迭代公式。
解 令，(＞0)，则的正根就是。
用牛顿法求解的迭代公式是：， 公式3.4.2)
由于当＞0时，＞0，＞0，故由收敛定理可知，对于任意满足条件的初始近似值，由选代公式所产生的序列必定收敛于平方根。公式(3.4.2)是计算平方根的准确而有效的计算方法。
3.4.3 牛顿迭代法的变形
用牛顿法解方程，虽然在单根附近具有较快的收敛速度，但它有个明显的缺点，就是每次都要计算导数，当比较复杂时，计算可能很困难。下面介绍两种克服这种困难的方法，另外还介绍一种扩大牛顿迭代法初值选择范围的方法，它们统称为变形的牛顿迭代法。
1 简化牛顿法
为避免频繁地计算导数值，可将它取为固定值，比如在牛顿迭代公式中用代替，即在迭代过程中始终保持分母不变，则有简化牛顿迭代公式(或固定斜率切线法)： 公式(3.4.3)
其几何意义如下图所示，这时除第一次迭代仍为曲线的切线外，其余皆为该切线的平行线。简化牛顿法避免了每次计算导数值。
更一般地，若取,则迭代公式成为：，称为推广的简化切线法。这时值应满足下式：

满足上式的为：，可见当与同号且满足上述不等式时，推广的简化切线法是收敛的。该迭代形式在参数法里也曾得到过。
2 由牛顿法的收敛性定理知，牛顿法对初始值的选取要求是很高的。一般地说，牛顿法只有局部收敛性。当初始值取得离根太远时，迭代将不收敛，而一旦初始值进入收敛域内，牛顿法就有平方收敛的速度，为了扬长避短，扩大初始值选取的范围下面介绍牛顿法的一种改进——牛顿下山法。
将牛顿法的迭代公式修改为： 公式(3.4.3)
其中，是一个参数，的选取应使＜成立，当＜或＜，就停止迭代，且取，其中，为事先给定的精度，称为残量精确度，为根的误差限；否则再减，继续迭代。按上述迭代过程计算，实际上得到了一个以零为下界的严格单调下降的函数值序列，这个方法就称为牛顿下山法。称为下山因子，要求满足0＜，称为下山因子下界，为了方便，一般开始时可简单地取，然后逐步分半减小，即可选取，，，…，，且使＜成立。
牛顿下山法计算步骤可归纳如下：
⑴ 选取初始近似值；⑵ 取下山因子；
⑶ 计算，
⑷ 计算，并比较与的大小，分以下两种情况：
① 若＜，则当＜时，则就取，计算过程结束；当＞时，则把作为新的值，并重复回到⑶。
②若，则当且＜，就取，计算过程结束；否则，若，而时，则把加上一个适当选定的小正数，即取作为新的值，并转向⑶重复计算；当，且时，则将下山因子缩小一半，并转向⑶重复计算。
牛顿下山法不但放宽了初值的选取，且有时对某一初值，虽然用牛顿法不收敛，但用牛顿下山法却有可能收敛。一般来说，牛顿下山法不再有平方收敛速度，它的优点在于可能将原来收敛域以外的初始值，经过几次迭代后拉入收敛域内。
例如，已知方程＝0的一个根为1.32472，若取初值＝0.6，用牛顿法计算得到的第一次近似值反而比更偏离根。若改用牛顿下山法，当取下山因子时，可得，修正后的迭代序列收敛。（沈建华P138）（史万明P48）
3.4.4 弦截法
1 单点弦截法
为避免牛顿迭代法中导数的计算，可用平均变化率：
来近似代替，于是得到如下迭代公式：
公式(3.4.4)
称为单点弦截法。单点弦截法具有明显的几何意义，它是用联结点A(，)与点B(，)的直线，代替曲线求取与横轴交点作为近似值的方法，以后再过(，)与(，)两点，作直线求取与横轴的交点作为，等等。其中(，)是一个固定点，称为不动点，另一点则不断更换，故名单点弦截法。可以证明，单点弦截法具有收敛的阶r＝1，即具有线性收敛速度。
2 双点弦截法
若把单点弦截法中的不动点(，)改为变动点(，)，则得到下面的双点弦截法的迭代公式：
公式(3.4.5)
用弦截法求根的近似值，在几何上相当于过点(，)，和点(，)作弦，然后用弦与轴的交点的横坐标作为的新的近似值。由于在双点弦截法中，构造的迭代公式在计算新的近似值时，不仅用到点上的函数值，而且还用到点及其函数值，这就有可能提高迭代法的收敛速度。
与牛顿法一样，如果函数在其根附近具有直到二阶的连续导数，且，则弦截法具有局部收敛性，即当初始近似值充分接近于时，按双点弦截法迭代公式得到的迭代序列收敛于根。可以证明弦截法具有超线性收速度，且收敛阶数为P＝1.618。双点弦截法迭代公式与前面介绍的单点迭代法有明显的不同，就是在计算时要用到前两步的计算结果、，所以在使用迭代公式前，必须先给出两个初始值、，因此，这种迭代法也称两步法，而单点迭代法称为一步法。