Newton牛顿法（一）

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

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

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

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

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

解：方程可改写为 x = e − x x=e^{-x} x=e−x，即 f ( x ) = x − e − x = 0 f(x)=x-e^{-x}=0 f(x)=x−e−x=0，此方程的Newton迭代格式为： x k + 1 = x k − x k − e − x k 1 + e − x k = x k − x k − e − x k 1 + x k 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 x_0=0.5 x0​=0.5，逐次迭代结果为 x 1 = 0.57102 , x 2 = 0.56716 ; x 3 = 0.56714 ; x 4 = 0.56714 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 ∣ ≤ 0.000005 |x_4-x_3|\leq 0.000005 ∣x4​−x3​∣≤0.000005的要求，收敛速度是很快的。

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

解：该问题等价于求 f ( x ) = x 3 − a f(x)=x^3-a f(x)=x3−a的零点，即解方程： f ( x ) = x 3 − a = 0 f(x)=x^3-a=0 f(x)=x3−a=0 运用Newton迭代公式，有： x k + 1 = x k − f ( x k ) f ′ ( x k ) = x k − x k 3 − a 3 x k 2 = 2 3 x k − a 3 x k 2 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,x_0=5 a=155,x0​=5，迭代计算结果为：

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

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

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