主題
Search

牛頓迭代法

DOWNLOAD Mathematica Notebook下載 Wolfram 筆記本

牛頓迭代法是一種用於計算數字 n 的 平方根 sqrt(n) 的演算法，透過 遞推方程

x_(k+1)=1/2(x_k+n/(x_k)),
(1)

其中 x_0=1。此遞推式二次收斂，當 lim_(k->infty)x_k。

牛頓迭代法僅僅是 牛頓法 在求解方程上的一個應用

x^2-n=0.
(2)

例如，當數值應用時，前幾個迭代值逼近 勾股定理常數 sqrt(2)=1.4142... 為 1, 1.5, 1.41667, 1.41422, 1.41421, ....

前幾個近似值 x_1, x_2, ... 逼近 sqrt(n) 由下式給出

1,1/2(1+n),(1+6n+n^2)/(4(n+1)),(1+28n+70n^2+28n^3+n^4)/(8(1+n)(1+6n+n^2)),....
(3)

這些可以由解析公式給出

x_k=sqrt(n)[1+2/(((1+sqrt(n))/(1-sqrt(n)))^(2^k)-1)]
(4)
=sqrt(n)coth(2^ktanh^(-1)(sqrt(n))).
(5)

這些可以透過注意到遞推式可以寫成

(x_k-sqrt(n))/(x_k+sqrt(n))=((x_(k-1)-sqrt(n))/(x_(k-1)+sqrt(n)))^2,
(6)

它具有巧妙的閉合形式解

(x_k-sqrt(n))/(x_k+sqrt(n))=((1-sqrt(n))/(1+sqrt(n)))^(2^k).
(7)

求解 x_k 然後得到上面推導的解。

下表總結了對於小正整數 n 的前幾個收斂值

nOEISx_1, x_2, ...
11, 1, 1, 1, 1, 1, 1, 1, ...
2A001601/A0510091, 3/2, 17/12, 577/408, 665857/470832, ...
3A002812/A0715791, 2, 7/4, 97/56, 18817/10864, 708158977/408855776, ...

另請參閱

牛頓法, 平方根, 平方根演算法, Wolfram 迭代

使用 探索

參考文獻

Sloane, N. J. A. Sequences A001601/M3042, A002812/M1817, A051009, A071579 in "The On-Line Encyclopedia of Integer Sequences。"Wolfram, S. 一種新科學。 Champaign, IL: Wolfram Media, p. 913, 2002。

在 中被引用

牛頓迭代法

請引用為

Weisstein, Eric W. “牛頓迭代法。” 來自 Web 資源。 https://mathworld.tw/NewtonsIteration.html

學科分類