TOPICS
Search

Newton's Iteration


Newton's iteration is an algorithm for computing the square root sqrt(n) of a number n via the recurrence equation

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

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

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)

These can be derived by noting that the recurrence can be written as

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

which has the clever closed-form solution

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

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

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 Iteration

Cite this as:

Weisstein, Eric W. "Newton's Iteration." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/NewtonsIteration.html

Subject classifications