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


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


These can be given by the analytic formula


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

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, ...

See also

Newton's Method, Square Root, Square Root Algorithms, Wolfram's Iteration

Explore with Wolfram|Alpha


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 Iteration

Cite this as:

Weisstein, Eric W. "Newton's Iteration." From MathWorld--A Wolfram Web Resource.

Subject classifications