§3.4  牛顿迭代法

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

3.4.1 牛顿迭代法

用迭代法解非线性方程时,如何构造迭代函数是非常重要的,那么怎样构造的迭代函数才能保证迭代法收敛呢?牛顿迭代法就是常用的方法之一,其迭代格式的来源大概有以下几种方式:

1,对在点作泰勒展开:

略去二次项,得到的线性近似式:

由此得到方程0的近似根(假定0)

即可构造出迭代格式(假定0)      公式(3.4.1)

这就是牛顿迭代公式,若得到的序列{}收敛于,则就是非线性方程的根。

2 牛顿迭代法也称为牛顿切线法,这是由于的线性化近似函数是曲线过点的切线而得名的,求的零点代之以求的零点,即切线轴交点的横坐标,如右图所示,这就是牛顿切线法的几何解释。实际上,牛顿迭代法也可以从几何意义上推出。利用牛顿迭代公式,由得到,从几何图形上看,就是过点作函数的切线,切线轴的交点就是,所以有,整理后也能得出牛顿迭代公式:

3 要保证迭代法收敛,不管非线性方程0的形式如何,总可以构造:

  

作为方程求解的迭代函数。因为:

而且在根附近越小,其局部收敛速度越快,故可令:

0(即根不是0的重根),则由得:

因此可令,则也可以得出迭代公式:

4  迭代法的基本思想是将方程改写成等价的迭代形式,但随之而来的问题却是迭代公式不一定收敛,或者收敛的速度较慢。运用前述加速技巧,对于简单迭代过程,其加速公式具有形式:

,其中

,上面两式可以合并写成:

这种迭代公式称作简单的牛顿公式,其相应的迭代函数是:

需要注意的是,由于的估计值,若取,则实际上便是的估计值。假设,则可以用代替上式中的,就可得到牛顿法的迭代公式:

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

3.4.2 牛顿迭代法的收敛性

牛顿迭代公式可以看成是由而获得的不动点迭代格式。这样就可以应用不动点迭代的收敛原则,只须证明在根附近的迭代函数是一个压缩映象。由于:

这里的根是单根,即,于是:

那么由的连续性可知,存在一个邻域,对这个邻域内的一切,有:,其中O1,因此为区间上的一个压缩映象,于是有以下结论:

    定理 3.4.1 的精确解,且,则存在邻域,对于任何迭代初值,迭代序列收敛于

牛顿迭代法具有较高的收敛速度,它的收敛阶数为2;而牛顿迭代法的局部收敛性较强,只有初值充分地接近,才能确保迭代序列的收敛性。为了放宽对局部收敛性的限制,必须再增加条件建立以下收敛的充分条件。

定理 3.4.2 ,且满足:在区间上,

;⑵

不变号;⑷ ,满足条件:

则牛顿迭代序列,单调地收敛于方程的唯一解

由条件⑴至条件⑷可归结为四种情形:

   

对定理的几何意义作如下说明:条件⑴保证了根的存在性;条件⑵表明函数单调变化,在区间内有惟一的根;条件⑶表示函数图形在区间上的凹向不变。条件⑶和条件⑷一起保证了每一次迭代值都界于区间内。

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

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

 解 令(0),则的正根就是

用牛顿法求解的迭代公式是:   公式(3.4.2)

由于当0时,00,故由收敛定理可知,对于任意满足条件的初始近似值,由选代公式所产生的序列必定收敛于平方根。公式(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()的直线,代替曲线求取与横轴交点作为近似值的方法,以后再过()()两点,作直线求取与横轴的交点作为,等等。其中()是一个固定点,称为不动点,另一点则不断更换,故名单点弦截法。可以证明,单点弦截法具有收敛的阶r1,即具有线性收敛速度。

2 双点弦截法

若把单点弦截法中的不动点()改为变动点(),则得到下面的双点弦截法的迭代公式:

 公式(3.4.5)

用弦截法求根的近似值,在几何上相当于过点(),和点()作弦,然后用弦与轴的交点的横坐标作为的新的近似值。由于在双点弦截法中,构造的迭代公式在计算新的近似值时,不仅用到点上的函数值,而且还用到点及其函数值,这就有可能提高迭代法的收敛速度。

与牛顿法一样,如果函数在其根附近具有直到二阶的连续导数,且,则弦截法具有局部收敛性,即当初始近似值充分接近于时,按双点弦截法迭代公式得到的迭代序列收敛于根。可以证明弦截法具有超线性收速度,且收敛阶数为P1.618。双点弦截法迭代公式与前面介绍的单点迭代法有明显的不同,就是在计算时要用到前两步的计算结果,所以在使用迭代公式前,必须先给出两个初始值,因此,这种迭代法也称两步法,而单点迭代法称为一步法。