Newton's iteration is an algorithm for computing the square root
of a number
via the recurrence equation
This recurrence converges quadratically as .
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
are 1, 1.5, 1.41667, 1.41422, 1.41421, ....
The first few approximants , , ... to 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
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, ...|
See alsoNewton's Method
, Square Root
, Square Root Algorithms
Explore with Wolfram|Alpha
ReferencesSloane, 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,
Referenced on Wolfram|AlphaNewton's Iteration
Cite this as:
Weisstein, Eric W. "Newton's Iteration."
From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/NewtonsIteration.html