牛顿法

牛顿法（英語：Newton's method）又称为牛顿-拉弗森方法（英語：Newton-Raphson method），它是一种在实数域和复数域上近似求解方程的方法。方法使用函数 $f(x)$ 的泰勒级数的前面几项来寻找方程 $f(x)=0$ 的根。

起源

牛顿法最初由艾萨克·牛頓在《流数法》（Method of Fluxions，1671年完成，在牛顿去世后於1736年公开发表）中提出。约瑟夫·鮑易也曾于1690年在Analysis Aequationum中提出此方法。

方法说明

首先，选择一个接近函数 $f(x)$ 零点的 $x_{0$ ，计算相应的 $f(x_{0})$ 和切线斜率 $f'(x_{0})$ （这里 $f'$ 表示函数 $f$ 的导数）。然后我们计算穿过点 $(x_{0},f(x_{0}))$ 并且斜率为 $f'(x_{0})$ 的直线和 $x$ 轴的交点的 $x$ 坐标，也就是求如下方程的解：

0=(x-x_{0})\cdot f'(x_{0})+f(x_{0})

我们将新求得的点的 $x$ 坐标命名为 $x_{1$ ，通常 $x_{1$ 会比 $x_{0$ 更接近方程 $f(x)=0$ 的解。因此我们现在可以利用 $x_{1$ 开始下一轮迭代。迭代公式可化简为如下所示：

x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})

已有证明牛顿迭代法的二次收敛^[1]必须满足以下条件：
$f'(x)\neq 0$ ; 对于所有 $x\in I$ ，其中 $I$ 为区间 $[α - r, α + r]$ ，且 $x_{0$ 在区间其中 $I$ 内，即 $r\geqslant \left|a-x_{0}\right|$ 的;
对于所有 $x\in I$ ， $f''(x)$ 是连续的;
$x_{0$ 足够接近根 $α$ 。

然而当 $f(x)=0$ 在 $x=a$ 处有m重根时，这时牛顿法会降为线性收敛，虽然使用牛顿法也可以继续算下去，但收敛速度会减慢。^[2]

其它例子

第一个例子

求方程 $\cos(x)-x^{3}=0$ 的根。令 $f(x)=\cos(x)-x^{3$ ，两边求导，得 $f'(x)=-\sin(x)-3x^{2$ 。由于 $-1\leq \cos(x)\leq 1(\forall x)$ ，则 $-1\leq x^{3}\leq 1$ ，即 $-1\leq x\leq 1$ ，可知方程的根位于 $0$ 和 $1$ 之间。我们从 $x_{0}=0.5$ 开始。