牛顿法

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

起源

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

方法说明

 

蓝线表示方程${\displaystyle f}$ 而红线表示切线。可以看出${\displaystyle x_{n+1}}$ 比${\displaystyle x_{n}}$ 更靠近${\displaystyle f}$ 所要求的根${\displaystyle x}$ 。

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

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

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

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

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

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

其它例子

第一个例子

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

${\displaystyle {\begin{matrix}x_{1}&=&x_{0}-{\frac {f(x_{0})}{f'(x_{0})}}&=&0.5-{\frac {\cos(0.5)-0.5^{3}}{-\sin(0.5)-3\times 0.5^{2}}}&=&1.112141637097\\x_{2}&=&x_{1}-{\frac {f(x_{1})}{f'(x_{1})}}&=&\vdots &=&{\underline {0.}}909672693736\\x_{3}&=&\vdots &=&\vdots &=&{\underline {0.86}}7263818209\\x_{4}&=&\vdots &=&\vdots &=&{\underline {0.86547}}7135298\\x_{5}&=&\vdots &=&\vdots &=&{\underline {0.8654740331}}11\\x_{6}&=&\vdots &=&\vdots &=&{\underline {0.865474033102}}\end{matrix}}}$ 

第二个例子

牛顿法亦可发挥与泰勒展开式，对于函式展开的功能。

求${\displaystyle a}$ 的${\displaystyle m}$ 次方根。

${\displaystyle x^{m}-a=0}$ 

设${\displaystyle f(x)=x^{m}-a}$ ，${\displaystyle f'(x)=mx^{m-1}}$ 

而a的m次方根，亦是x的解，

以牛顿法来迭代：

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

${\displaystyle x_{n+1}=x_{n}-{\frac {x_{n}^{m}-a}{mx_{n}^{m-1}}}}$ 

${\displaystyle x_{n+1}=x_{n}-{\frac {x_{n}}{m}}(1-ax_{n}^{-m})}$ 

（或 ${\displaystyle x_{n+1}=x_{n}-{\frac {1}{m}}\left(x_{n}-a{\frac {x_{n}}{x_{n}^{m}}}\right)}$ ）

應用

求解最值問題

主条目：應用於最優化的牛頓法

牛頓法也被用於求函數的極值。由於函數取極值的點處的導數值為零，故可用牛頓法求導函數的零點，其疊代式為

${\displaystyle x_{n+1}=x_{n}-{\frac {f^{\prime }(x_{n})}{f^{\prime \prime }(x_{n})}}.}$ 

求拐点的公式以此类推

註解

1. 存档副本 (PDF). [2018-06-26]. （原始内容 (PDF)于2021-04-24）. 
2. 张宏伟，金光日，施吉林，董波 (编). 计算机科学计算 2013年第2版. 北京: 高等教育出版社. 2005: 138. ISBN 9787040365955. 

外部連結

•  数学主题

• JAVA：牛頓勘根法 （页面存档备份，存于互联网档案馆） （繁體中文）