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