Newton迭代法的改进 | Newton下山法 + 简化Newton法 + 弦截法

Newton迭代法的改进

1. Newton下山法

Newton法的收敛性与初值$x_0$x0​的选取由很大关系，如果$x_0$x0​偏离方程的根$x^*$x∗太远，则Newton法可能发散或迭代次数增加，因此，有必要对迭代法加以改进。

例1：用Newton法求$x^3-x-1=0$x3−x−1=0在$x_0=1.5$x0​=1.5附近的一个根。

解：原方程的Newton迭代格式为$x_{k+1}=x_k-\frac{x_k^2-x-1}{2x_k^2-1}$xk+1​=xk​−2xk2​−1xk2​−x−1​，迭代结果为$x_3=1.32472$x3​=1.32472。如果迭代初值取为$x_0=0.6$x0​=0.6，则迭代一次所得结果$x_1=17.9$x1​=17.9就大大远离了$x^*$x∗。因此，迭代过程可能是发散的或迭代次数增加。

为了避免迭代过程出现发散或迭代次数增加，可对迭代过程再附加如下一个条件：
$|f(x_{k+1})|<|f(x_k)| \tag{1}$∣f(xk+1​)∣<∣f(xk​)∣(1)
即保证函数值单调下降，则上例中的现象可以避免。

将条件（1）与Newton迭代法合并起来，即在保证函数值稳定下降的条件下，用Newton法来加快迭代，这就是Newton下山法。

Newton下山法具体操作：

将用Newton法求得的结果$\overline{x_{k+1}}$xk+1​​与前一步迭代的近似值$x_k$xk​适当加权平均，作为新的改进值$x_{k+1}$xk+1​即：
$x_{k+1}=\lambda\overline{x_{k+1}}+(1-\lambda)x$xk+1​=λxk+1​​+(1−λ)x
或
$x_{k+1}=x_k-\lambda \frac{f(x_k)}{f'(x_k)}$xk+1​=xk​−λf′(xk​)f(xk​)​
其中，$\lambda(0\leq \lambda <1)$λ(0≤λ<1)称为下山因子。然后，适当选择$\lambda$λ的值，使之满足条件（1）。

下山因子$\lambda$λ的选择是一个逐步试探的过程，可以从$\lambda=1$λ=1开始，将$\lambda$λ逐步减半进行试算，一旦条件（1）满足，则称下山成功，否则下山失败，需另选初值$x_0$x0​再试。

现在用Newton下山来考察例1：仍取$x_0=0.6$x0​=0.6，将用Newton法求得的$\overline x_1=17.9$x1​=17.9与初值$x_0=0.6$x0​=0.6加权平均，并取$\lambda=\frac{1}{32}$λ=321​，则
$x_1=\frac{1}{32}\overline x_1+\frac{31}{32}x_0=1.140625$x1​=321​x1​+3231​x0​=1.140625
这个结果比$17.9$17.9要小许多。可见，上述严重偏离$x^*$x∗的现象已经不复存在。

2. 简化Newton法

应用Newton法求方程的根，要计算函数的导数。如果函数的导数太复杂，计算量大且繁琐，这时可以用常数值c来代替函数的导数值，则迭代公式就变成：
$x_{k+1}=x_k-\frac{f(x_k)}{c} \tag{2}$xk+1​=xk​−cf(xk​)​(2)
这就是简化Newton法。在（2）式中，常数值c的选取可以根据迭代函数及收敛条件来确定。记
$\varphi(x)=x-\frac{f(x)}{c}$φ(x)=x−cf(x)​
则
$\varphi'(x)=1-\frac{f'(x)}{c}$φ′(x)=1−cf′(x)​
由
$|\varphi'(x)|=|1-\frac{f'(x)}{c}|<1$∣φ′(x)∣=∣1−cf′(x)​∣<1
得
$0<\frac{f'(x)}{c}<2$0<cf′(x)​<2
这样，常数值c就容易确定了。

简化Newton法的几何意义是：过点$(x_k,f(x_k))$(xk​,f(xk​))，以c为斜率，作一直线与x轴的交点近似代替曲线与x轴的交点。如下图所示。

2.6.3 弦截法

弦截法是Newton法的简化与改进，它保留了Newton法收敛速度快的优点，克服了需要计算函数的导数$f'(x)$f′(x)的缺点。

如果用差商
$\frac{f(x_k)-f(x_{k-1})}{x_k-x_{k-1}}$xk​−xk−1​f(xk​)−f(xk−1​)​
代替Newton迭代法中的$f'(x_k)$f′(xk​)，则可得到下面的离散化形式：
$x_{k+1}=x_k-\frac{f(x_k)}{f(x_k)-f(x_{k-1})}(x_k-x_{k-1}) \tag{3}$xk+1​=xk​−f(xk​)−f(xk−1​)f(xk​)​(xk​−xk−1​)(3)
（3）式中的等号右边，即为下图所示曲线$y=f(x)$y=f(x)上$p_{k-1}$pk−1​点$(x_{k-1},f(x_{k-1}))$(xk−1​,f(xk−1​))与$p_k$pk​点$(x_k,f(x_k))$(xk​,f(xk​))相连的直线或弦线的方程式。按（3）式求得的$x_{k+1}$xk+1​，就是该弦线与x轴的交点的横坐标，故该方法被称为弦截法。另一方面，对照Newton法，（3）式实际上也可以看成是用经过曲线$y=f(x)$y=f(x)上$p_{k-1}$pk−1​点$(x_{k-1},f(x_{k-1}))$(xk−1​,f(xk−1​))和$p_k$pk​点$(x_k,f(x_k))$(xk​,f(xk​))的割线的斜率来代替函数在$p_k$pk​点$(x_k,f(x_k))$(xk​,f(xk​))的导数，故该方法又被称为割线法。

弦截法是一种两步迭代法，即在计算$x_{k+1}$xk+1​时，必须先给出$x_{k-1}$xk−1​和$x_k$xk​。因此，在使用公式（3）时，必须首先给出两个迭代初值$x_0$x0​和$x_1$x1​，否则无法启动迭代运算。

在（3）式中，$x_{k-1}$xk−1​点可以一直用一个固定点$x_0$x0​点来代替，此时弦截法演变成为了单点弦截法，其几何解释如下图所示。相应地之前的为双点弦截法。

弦截法的收敛性有下面两个定理：

定理3：设函数$f(x)$f(x)在区间$[a,b]$[a,b]上存在二阶导数，且满足条件：

（1）$f''(x)$f′′(x)在区间$[a,b]$[a,b]上不改变符号；

（2）$f'(x)$f′(x)在区间$[a,b]$[a,b]上不等于零；

（3）$f(a)f(b)<0$f(a)f(b)<0；

（4）$x_0\in[a,b]$x0​∈[a,b]且满足条件$f(x_0)f''(x_0)>0,x_1\in [a,b]$f(x0​)f′′(x0​)>0,x1​∈[a,b]

这时，由递推计算公式
$x_{n+1}=x_n-\frac{x_n-x_0}{f(x_n)-f(x_0)}f(x_n),\quad (n=1,2,\cdots)$xn+1​=xn​−f(xn​)−f(x0​)xn​−x0​​f(xn​),(n=1,2,⋯)
而得的序列$\{x_n\}${xn​}单调收敛于$f(x)$f(x)在$[a,b]$[a,b]上的惟一解$x^*$x∗。

该定理即为单点弦截法的收敛性定理。

定理4：设$x^*$x∗为$f(x)$f(x)的实根，$f'(x)$f′(x)和$f''(x)$f′′(x)在包含$x^*$x∗的某一区间是连续的，并且$f'(x^*)\neq 0$f′(x∗)​=0，则当$x_0$x0​和$x_1$x1​足够接近$x^*$x∗时，由递推计算公式
$x_{n+1}=x_n-\frac{x_n-x_{n-1}}{f(x_n)-f(x_{n-1})}f(x_n),\quad (n=1,2,\cdots)$xn+1​=xn​−f(xn​)−f(xn−1​)xn​−xn−1​​f(xn​),(n=1,2,⋯)
而得的序列${x_n}$xn​收敛于$x^*$x∗。

该定理即为双点弦截法的收敛性定理。