最后更新: 2025-03-16 10:28 查看: 185 次纠错评论(0) 课件开VIP

牛顿求根法 Newton 求根法

## 13.2.2 Newton 求根法
从计算数学的实用角度来看，如何提高数列收敛的速度非常重要，而一般的迭代数列，包括由压缩映射生成的在内，收敛速度不一定很快。Newton 求根法就是利用微分学成果的一个高效率算法，且有多方面的发展和应用。例如，Newton 求根法可以推广到高维空间而成为一大类算法的基础。

设 $f$ 在 $[a, b]$ 上可微，$f(a) f(b)<0, f^{\prime}$ 没有零点（从而 $f$ 严格单调），于是 $f$ 在 $(a, b)$ 内有惟一实根，记为 $\xi$ ．设已经有根的一个近似值 $x_n$ ，如何求下一个更好的近似值？这里就出现了迭代思想，即从 $x_n$ 求出 $x_{n+1}{ }^{(1)}$ 。

Newton 方法也称为切线法，图13．2可以解释为什么有这样的名称。但我们还是先不利用它的几何意义而作如下分析推导。

利用无穷小增量公式（见第六章 $\S 6.4$或（7．5）式），写出

$$
f(\xi)=f\left(x_n\right)+f^{\prime}\left(x_n\right)\left(\xi-x_n\right)+o\left(\xi-x_n\right)
$$

弃去余项，又利用 $f(\xi)=0$ ，就有

$$
\xi-x_n \approx-\frac{f\left(x_n\right)}{f^{\prime}\left(x_n\right)}
$$

![图片](/uploads/2025-02/4a1bcf.jpg)

右边就是修正量．于是取下次的近似值为
$$
x_{n+1}=x_n-\frac{f\left(x_n\right)}{f^{\prime}\left(x_n\right)}
$$

这就是 Newton 求根法的迭代公式．
从几何上看，在图13．2中过曲线上的点 $\left(x_n, f\left(x_n\right)\right)$ 作切线

$$
Y-f\left(x_n\right)=f^{\prime}\left(x_n\right)\left(X-x_n\right),
$$

它与 $x$ 轴的交点的横坐标就是公式（13．6）的右边表达式．在上面的推导中不用几何方法的好处是它可以几乎原封不动地推广为高维空间中的 Newton 求根法。
（1）在古代中国数学中已经出现了一系列用迭代计算的方法，其中包括求解线性方程组的消去法，计算圆周率的迭代方法和解一次不定方程的大衍求一术等［18］．

从图13．2可以看出，如果从 $x_{n+1}$ 计算出 $f\left(x_{n+1}\right)$ ，过点 $\left(x_{n+1}, f\left(x_{n+1}\right)\right)$ 再作切线与 $x$ 轴相交，则就可能与根 $\xi$ 相当接近了．这提示我们，Newton 求根法可能会有较好的收敛速度。

需要指出，Newton 求根法也需要一定的条件才能成功。如图13．3所示，数列 $\left\{x_n\right\}$ 不收玫，或者某一步之后迭代公式给出的 $x_{n+1}$ 越出函数的定义域，这些都有可能发生．关于这方面的分析可参考［8］等．
 ![图片](/uploads/2025-02/2103a2.jpg)
 
 关于 Newton 求根法的收玫速度可如下推导．先利用带 Lagrange 型余项的 Taylor 公式：

$$
0=f(\xi)=f\left(x_n\right)+f^{\prime}\left(x_n\right)\left(\xi-x_n\right)+\frac{f^{\prime \prime}\left(\theta_n\right)}{2}\left(\xi-x_n\right)^2
$$

其中 $\theta_n \in\left(\xi, x_n\right)$ ．这时利用迭代公式（13．6）就得到

$$
\begin{aligned}
x_{n+1}-\xi & =x_n-\frac{f\left(x_n\right)}{f^{\prime}\left(x_n\right)}-\xi=\frac{-f\left(x_n\right)-f^{\prime}\left(x_n\right)\left(\xi-x_n\right)}{f^{\prime}\left(x_n\right)} \\
& =\frac{f^{\prime \prime}\left(\theta_n\right)\left(\xi-x_n\right)^2}{2 f^{\prime}\left(x_n\right)}
\end{aligned}
$$

又利用 $\lim _{n \rightarrow \infty} f^{\prime \prime}\left(\theta_n\right)=f^{\prime \prime}(\xi), \lim _{n \rightarrow \infty} f^{\prime}\left(x_n\right)=f^{\prime}(\xi) \neq 0$ ，可见存在 $M>0$ ，使得当 $n$充分大时成立

$$
\left|x_{n+1}-\xi\right| \leqslant M\left|x_n-\xi\right|^2
$$

这就是所谓的二阶收玫速度．粗略地说，即每迭代一次可以将有效位数增加一倍．
例如试用 Newton 求根法计算 $A>0$ 的平方根．这就是要求二次方程 $f(x)=$ $x^2-A=0$ 的正根．Newton 迭代公式为

$$
x_{n+1}=x_n-\frac{x_n^2-A}{2 x_n}=\frac{1}{2}\left(x_n+\frac{A}{x_n}\right)
$$

以 $A=2$ 为例，即

$$
x_{n+1}=\frac{1}{2}\left(x_n+\frac{2}{x_n}\right)=\frac{x_n}{2}+\frac{1}{x_n}
$$

设 $x_0=1$ ，则有

$$
x_1=1.5, x_2=0.75+0 . \dot{6}=1.41 \dot{6}, x_3=1.414215986 \cdots,
$$

$$
x_4=1.414213562 \cdots
$$

其中 $x_4$ 写出的全为有效数字．从中可见二阶收玫速度的特征是明显的．

注 这种求根方法已见于古代中东地区的美索不达米亚的泥板中．不清楚当时如何发明这样的算法．．但可以设想，对于 $\sqrt{A}$ 而言，若其近似值 $x<\sqrt{A}$ ，则 $\frac{A}{x}>\sqrt{A}$ ，反之，若 $x>\sqrt{A}$ ，则 $\frac{A}{x}<\sqrt{A}$ ．因此它们的算术平均值 $\frac{1}{2}\left(x+\frac{A}{x}\right)$有可能是更好的近似值［18］．

科数题库(单机版) 会议室预约系统(book)

今日还可看 0 篇未注册用户每天查看4篇，注册用户每天8篇，开通VIP会员无限制查看。

免费注册

《高等数学》难点解析

高数教程 泰勒公式切线与法线切平面与法平面驻点·拐点·极值点·零点间断点渐进线瑕积分欧拉方程伯努利方程 Abel 收敛定理偏导数的几何意义偏导数的几何意义梯度数量场与向量场多元函数极值拉格朗日算子通量与散度环流量与旋度格林公式高斯公式斯托克斯公式三大公式比较傅里叶级数极坐标微元点法式方程变上限定积分 X型计算面积 Y型计算面积微分的意义渐近线间断点 y''+py'+qy=f(x)方程高斯黎曼傅里叶变换(复数) 拉普拉斯变换(复数)

《线性代数》难点解析

线代教程 近世代数对数学的整体思考线性的意义矩阵乘法(列视角) 矩阵乘法(行视角) 矩阵左乘矩阵右乘逆矩阵求解方程组阶梯形矩阵的求法方程组解的判定四阶行列式的计算线性变换的意义线性空间向量组的等价线性空间的几何意义基础解系的求法施密特正交化特征值与特征向量的意义矩阵相似的几何意义矩阵可对角化的理解秩的意义(向量版) 秩的意义(方程版) 二次型的意义

《概率论与数理统计》难点解析

概率教程 置信区间与上a分位数概率中的“取”与“放” 贝叶斯公式全概率公式泊松分布指数分布伽玛分布二维密度图的意义卷积的意义相关系数的意义 k阶矩是与矩母函数卡方分布的作用单正态区间估计理解假设检验理解切比雪夫不等式中心极限定理

上一篇：压缩映射原理

下一篇：实数系理论简介

本文对您是否有用？有用 (0) 无用 (0)