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