Newton牛顿法（一）| 基本思想+迭代公式

基本思想与迭代公式

通常对已知方程$f(x)=0$f(x)=0进行变形而构造的迭代函数$\varphi(x)$φ(x)不是惟一的。在实际作用中，如果希望迭代函数$\varphi(x)$φ(x)有一种固定格式的构造方法，就可以采用Newton迭代法。

Newton迭代法的基本思想是：设法将一个非线性方程$f(x)=0$f(x)=0转化为某种线性方程求解，其解决问题的基础是Taylor（泰勒）多项式。具体描述如下：

设$f(x)=0$f(x)=0的近似根为$x_k$xk​，则函数$f(x)$f(x)在点$x_k$xk​附近可用一阶Taylor多项式$p_1(x)$p1​(x)来近似，即：
$p_(x)=f(x_k)+f'(x_k)(x-x_k) \cong f(x)$p(​x)=f(xk​)+f′(xk​)(x−xk​)≅f(x)
从而得到线性方程：
$f(x_k)+f'(x_k)(x-x_k)=0$f(xk​)+f′(xk​)(x−xk​)=0
解之，得该线性方程的根$x$x，但它是$f(x)=0$f(x)=0的一个新近似根，记做$x_{k+1}$xk+1​，即：
$x_{k+1}=x_k-\frac{f(x_k)}{f'(x_k)}$xk+1​=xk​−f′(xk​)f(xk​)​
上式实质上就是一种迭代格式，称为Newton迭代格式。相应地，Newton迭代函数为：
$\varphi(x)=x-\frac{f(x)}{f'(x)} \tag{1}$φ(x)=x−f′(x)f(x)​(1)
于是，按（1）式构造迭代函数解方程$f(x)=0$f(x)=0的方法，就是Newton迭代法。

Newton迭代法的几何解释如下图所示。方程$f(x)=0$f(x)=0的根$x^*$x∗为$y=f(x)$y=f(x)和$y=0$y=0（即x轴）的交点。设$x_k$xk​为$x^*$x∗的某个初始近似值，过$p_k$pk​点$(x_k,f(x_k))$(xk​,f(xk​))作$y=f(x)$y=f(x)的切线交x轴于$x_{k+1}$xk+1​，即为所求得的近似值。继续过$p_{k+1}$pk+1​点$(x_{k+1},f(x_{k+1}))$(xk+1​,f(xk+1​))，$p_{k+2}$pk+2​点$(x_{k+2},f(x_{k+2})),\cdots$(xk+2​,f(xk+2​)),⋯，作$y=f(x)$y=f(x)的切线，即可逐步逼近精确的根$x^*$x∗。因此，Newton法也叫切线法，因为它是沿着曲线$y=f()x$y=f()x上某一点作切线逐步外推逼近的。从$p_k$pk​点作切线与x轴的交点$x_{k+1}$xk+1​，由于$y=f(x)$y=f(x)不是直线，所以$f(x_{k+1})$f(xk+1​)就不可能为零。因此必须以$x_{k+1}$xk+1​作为新的起点，从与之对应的$p_{k+1}$pk+1​点继续作切线，重复上述步骤，直至$f(x_{k+1})$f(xk+1​)充分小，逼近零时为止。

例1：用Newton迭代法求方程$xe^x-1=0$xex−1=0的根。

解：方程可改写为$x=e^{-x}$x=e−x，即$f(x)=x-e^{-x}=0$f(x)=x−e−x=0，此方程的Newton迭代格式为：
$x_{k+1}=x_k-\frac{x_k-e^{-x_k}}{1+e^{-x_k}}=x_k-\frac{x_k-e^{-x_k}}{1+x_k}$xk+1​=xk​−1+e−xk​xk​−e−xk​​=xk​−1+xk​xk​−e−xk​​
取迭代初值为$x_0=0.5$x0​=0.5，逐次迭代结果为$x_1=0.57102,x_2=0.56716;x_3=0.56714;x_4=0.56714$x1​=0.57102,x2​=0.56716;x3​=0.56714;x4​=0.56714。由此可见，迭代4次即达到了$|x_4-x_3|\leq 0.000005$∣x4​−x3​∣≤0.000005的要求，收敛速度是很快的。

例2：推导立方根的Newton迭代公式，并求$a=155$a=155的立方根。

解：该问题等价于求$f(x)=x^3-a$f(x)=x3−a的零点，即解方程：
$f(x)=x^3-a=0$f(x)=x3−a=0
运用Newton迭代公式，有：
$x_{k+1}=x_k-\frac{f(x_k)}{f'(x_k)}=x_k-\frac{x_k^3-a}{3x_k^2}=\frac{2}{3}x_k-\frac{a}{3x_k^2}$xk+1​=xk​−f′(xk​)f(xk​)​=xk​−3xk2​xk3​−a​=32​xk​−3xk2​a​
令$a=155,x_0=5$a=155,x0​=5，迭代计算结果为：

n	0	1	2	3
x	5	5.4	5.371834	5.371686

仅迭代3步就求得精确解。再使用较差一些的初值$x_0=10$x0​=10，则迭代计算结果为：

n	0	1	2	3	4	5
x	10	7.183334	5.790176	5.401203	5.371847	5.371686

迭代5步之后得到精确值。

使用Newton法求方程的根，在什么条件下、选取什么样的初始值$x_0$x0​，才能保证迭代过程总是收敛于方程的根的根$x^*$x∗呢？这是运用Newton法求方程根的重要问题。