微積分/牛頓法

← 極值點和拐點	微積分	相關變化率 →
	牛頓法

牛頓法（也稱為牛頓-拉弗森方法）是一種遞迴演算法，用於逼近可微函式的根。我們知道用於尋找線性和二次方程的根的簡單公式，並且還有一些用於三次方程和四次方程的更復雜公式。曾經有人希望能夠找到用於五次方程和更高次方程的公式，但後來由尼爾斯·亨利克·阿貝爾證明，這樣的方程不存在。牛頓-拉弗森方法是一種用於逼近任意階數多項式方程的根的方法。事實上，該方法適用於任何方程，無論是否為多項式，只要函式在所需區間內可微。

牛頓法

令 $f(x)$ 是一個可微函式。選擇一個點 $x_{0}$ ，它基於對根的第一次近似，任意接近函式的根。然後使用以下公式遞迴計算以逼近根：

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

隨著遞迴計算， $x_{n+1}$ 通常會成為函式根的越來越好的近似值。

為了解釋牛頓法，假設 $x_{0}$ 已經非常接近 $f(x)$ 的一個零點。我們知道，如果我們只檢視非常接近 $x_{0}$ 的點，那麼 $f(x)$ 看起來像它的切線。如果 $x_{0}$ 已經接近 $f(x)$ 為 0 的位置，並且在 $x_{0}$ 附近我們知道 $f(x)$ 看起來像它的切線，那麼我們希望 $x_{0}$ 處切線的零點比 $x_{0}$ 本身是一個更好的近似值。

過點 $x_{0}$ 的函式 $f(x)$ 的切線的方程為：

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

現在我們令 $y=0$ 並解出 $x$ 。

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

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

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

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

我們認為這個 $x$ 值應該是 $f(x)=0$ 的一個更好的近似值。我們稱這個 $x$ 值為 $x_{1}$ ，經過簡單的代數運算，我們得到

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

如果我們的直覺是正確的，並且 $x_{1}$ 實際上是 $f(x)$ 的根的更好近似值，那麼我們的邏輯應該同樣適用於 $x_{1}$ 。我們可以看看在 $x_{1}$ 處的切線為零的地方。我們稱之為 $x_{2}$ ，根據上面的代數，我們得到了公式

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

我們可以一直這樣做，只要我們願意。在每一步中，如果你的當前近似值是 $x_{n}$ ，我們的新近似值將是 $x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}$ 。

示例

求函式 $f(x)=x^{2}$ 的根。

圖 1：牛頓法應用於 $y=x^{2}$ 的幾個迭代，從 $x_{0}=4$ 開始。藍色曲線是 $f(x)$ 。其他實線是各個迭代點的切線。

${\begin{aligned}x_{0}&=&4\\x_{1}&=&x_{0}-{\frac {f(x_{0})}{f'(x_{0})}}=4-{\frac {16}{8}}=2\\x_{2}&=&x_{1}-{\frac {f(x_{1})}{f'(x_{1})}}=2-{\frac {4}{4}}=1\\x_{3}&=&x_{2}-{\frac {f(x_{2})}{f'(x_{2})}}=1-{\frac {1}{2}}={\frac {1}{2}}\\x_{4}&=&x_{3}-{\frac {f(x_{3})}{f'(x_{3})}}={\frac {1}{2}}-{\frac {\frac {1}{4}}{1}}={\frac {1}{4}}\\x_{5}&=&x_{4}-{\frac {f(x_{4})}{f'(x_{4})}}={\frac {1}{4}}-{\frac {\frac {1}{16}}{\frac {1}{2}}}={\frac {1}{8}}\\x_{6}&=&x_{5}-{\frac {f(x_{5})}{f'(x_{5})}}={\frac {1}{8}}-{\frac {\frac {1}{64}}{\frac {1}{4}}}={\frac {1}{16}}\\x_{7}&=&x_{6}-{\frac {f(x_{6})}{f'(x_{6})}}={\frac {\frac {1}{256}}{\frac {1}{8}}}={\frac {1}{32}}\end{aligned}}$