牛頓的函數求根法

牛頓曾經發表了一個求解

的數值計算方法. 這是今天所謂牛頓求根法的濫觴. 奇怪的是, 牛頓始終沒有用一般的微分形式來表達他的計算法, 而是用了多項式的特殊微分公式. 以今天的符號來表現, 若是要求 f(x) = 0 的數值解 (而且 f(x) 是可微的), 則令 x₀ 是一個靠近真解的數, 做以下的疊代

在高中的時候我們聽說過, 如此造成的數列 x₀, x₁, x₂, ... 將會逼近, 或是收斂, 到 f(x)=0 的一個靠近 x₀ 的根. 其實, 也許沒這麼順利, 詳細的情形大概要等到數值分析這門課來說了. 牛頓法的想法如下圖.

圖十八

舉一個簡單的例子, 假如我們要求 f(x) = x² 的零根. 當然你知道答案是 0. 牛頓法的疊代方程式是

如果我們取 p₀ =1, 則所造成的 {p_n} 數列是

根據我們直觀的認識, x_n 的確在

的時候收斂到 0. 因為從 0 到 x_n 之間的距離, 也就是

隨著 n的變大而變小.

我們再看一個例子, 假如我們要求 f(x) = x²-2 的零根. 當然你知道答案是 sqrt(2)。拿出你的掌上型計算器, 可以得到答案. 寫成小數形態的前幾項是

對這個問題, 牛頓法的疊代方程式是

讓我們取 x₀=1, 則 {q_n} 數列的前幾項是

(其中最後一式乃是個有理數, 只因循環節太長而省略後面的小數.) 看起來, 我們應該會相信這個數列 {q_n} 將會越來越接近

你可以更進一步觀察. 若將 q₁, ..., q₄ 與 (1) 中的數字比較, q₁ 有一位正確的數字, 也就是說, 誤差大約是 10^-1; q₂ 有三位正確的數字, 誤差大約是 10^-3; q₃ 有六位正確的數字, 誤差大約是 10^-6; q₄ 有十二位正確的數字, 誤差大約是 10^-12. 其實我們可以證明, 如果所逼近的根是一個單根, 則當牛頓法數列 x_n 有 k 位正確數字時, x_n+1 將會有 2k 位正確的數字.