牛頓法

牛頓法（英語：Newton's method）又稱為牛頓-拉弗森方法（英語：Newton-Raphson method），它是一種在實數域和複數域上近似求解方程的方法。方法使用函數$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'(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})}}$

已有證明牛頓迭代法的二次收斂必須滿足以下條件：
$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重根時，這時牛頓法會降為線性收斂，雖然使用牛頓法也可以繼續算下去，但收斂速度會減慢。

其它例子

第一個例子

求方程$\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$開始。

${\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}}$

第二個例子

牛頓法亦可發揮與泰勒展開式，對於函式展開的功能。

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

$x^{m}-a=0$

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

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

以牛頓法來迭代：

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

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

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

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

應用

求解最值問題

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

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

$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：牛頓勘根法 （頁面存檔備份，存於網際網路檔案館） （繁體中文）