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

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.