牛顿法

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

起源

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

方法说明

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

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

$0=(x-x_0)\cdot f^{\prime }(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^{\prime }(x_n)}$

已有证明牛顿迭代法的二次收敛必须满足以下条件：
$f^{\prime }(x)\ne 0$; 对于所有$x\in I$，其中$I$为区间Template:Math，且$x_0$在区间其中$I$内，即 $|\alpha -x_0|\le r$ 的;
对于所有$x\in I$，$f^{″}(x)$是连续的;
$x_0$足够接近根Template:Math。

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

其它例子

第一个例子

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

$\begin{array}{ccccccc}{x}_1& =& x_0-\frac{f(x_0)}{f^{\prime }(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^{\prime }(x_1)}& =& ⋮& =& \underset{\_}{0.}909672693736\\ x_3& =& ⋮& =& ⋮& =& \underset{\_}{0.86}7263818209\\ x_4& =& ⋮& =& ⋮& =& \underset{\_}{0.86547}7135298\\ x_5& =& ⋮& =& ⋮& =& \underset{\_}{0.8654740331}11\\ x_6& =& ⋮& =& ⋮& =& \underset{\_}{0.865474033102}\end{array}$

第二个例子

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

求$a$的$m$次方根。

$x^m-a=0$

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

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

以牛顿法来迭代：

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

$x_{n+1}=x_n-\frac{x_n^m-a}{m{x}_n^{m-1}}$

$x_{n+1}=x_n-\frac{x_n}{m}(1-a{x}_n^{-m})$

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

應用

求解極值問題

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

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

求拐点的公式以此类推

電腦程式

可以用程式寫出牛頓法:

例題:$f(x)=x^3-10x^2+x+1=0$ 求x

用Python:

from math import pow
def f(x):
    y = pow(x,3)-(10*x*x)+x+1
    return y
def dx(x):
    y = (3*x*x)-(20*x)+1
    return y
x = 1
for i in range(1000):
    x = x - (f(x)/dx(x))
print(x)

用C語言:

#include <stdio.h>
#include <math.h>
double x = 1.0;
double f(double x){
    double y = pow(x,3)-(10*x*x)+x+1;
    return y;}
double dx(double x){
    double y = (3*x*x)-(20*x)+1;
    return y;}
int main (){
    for(int i=0;i<1000;i++){
    x = x - (f(x)/dx(x));}
    printf(" %f",x);
    return 0;
}

只要修改f(x)和dx(x)函數就可以解其他方程式

外部連結

• JAVA：牛頓勘根法 Template:Wayback Template:Zh-tw