Newton's Iteration
Newton's iteration is an algorithm for computing the square root sqrt(n) of a number n via the recurrence equation
where x_0=1. This recurrence converges quadratically as lim_(k->infty)x_k.
Newton's iteration is simply an application of Newton's method for solving the equation
| x^2-n=0. |
(2)
|
For example, when applied numerically, the first few iterations to Pythagoras's constant sqrt(2)=1.4142... are 1, 1.5, 1.41667, 1.41422, 1.41421, ....
The first few approximants x_1, x_2, ... to sqrt(n) are given by
| 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)
|
These can be given by the analytic formula
![画像:sqrt(n)[1+2/(((1+sqrt(n))/(1-sqrt(n)))^(2^k)-1)]](/index.cgi/contrast/https://mathworld.wolfram.com/images/equations/NewtonsIteration/Inline11.svg){kind=link}
These can be derived by noting that the recurrence can be written as
which has the clever closed-form solution
Solving for x_k then gives the solution derived above.
The following table summarizes the first few convergents for small positive integer n
See also
Newton's Method, Square Root, Square Root Algorithms, Wolfram's IterationExplore with Wolfram|Alpha
More things to try:
References
Sloane, N. J. A. Sequences A001601/M3042, A002812/M1817, A051009, A071579 in "The On-Line Encyclopedia of Integer Sequences."Wolfram, S. A New Kind of Science. Champaign, IL: Wolfram Media, p. 913, 2002.Referenced on Wolfram|Alpha
Newton's IterationCite this as:
Weisstein, Eric W. "Newton's Iteration." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/NewtonsIteration.html