 TOPICS  # Newton's Iteration

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

where . This recurrence converges quadratically as .

Newton's iteration is simply an application of Newton's method for solving the equation (2)

For example, when applied numerically, the first few iterations to Pythagoras's constant are 1, 1.5, 1.41667, 1.41422, 1.41421, ....

The first few approximants , , ... to are given by (3)

These can be given by the analytic formula   (4)   (5)

These can be derived by noting that the recurrence can be written as (6)

which has the clever closed-form solution (7)

Solving for then gives the solution derived above.

The following table summarizes the first few convergents for small positive integer  OEIS , , ... 1 1, 1, 1, 1, 1, 1, 1, 1, ... 2 A001601/A051009 1, 3/2, 17/12, 577/408, 665857/470832, ... 3 A002812/A071579 1, 2, 7/4, 97/56, 18817/10864, 708158977/408855776, ...

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

## Explore 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 Iteration

## Cite this as:

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