Newton-Raphson Square Roots

The Newton-Raphson iteration

The Newton-Raphson method computes square roots. Given $a$, the iteration is:

$x_{\text{next}} = \frac{\frac{a}{x} + x}{2}$

In OCaml:

let next a x = (a /. x +. x) /. 2.0
(* val next : float -> float -> float = <fun> *)

Convergence on infinite sequences

iterates (next a) x₀ generates the infinite series of approximations. For $\sqrt{2}$ with $x_0 = 1.0$:

Iteration	Approximation
$x_0$	1.0
$x_1$	1.5
$x_2$	1.41667…
$x_3$	1.4142157…
$x_4$	1.414213562…

The last value is accurate to 10 significant digits. Convergence is quadratic: the number of correct digits roughly doubles each iteration.

within: stopping criterion

let rec within eps = function
  | Cons (x, xf) ->
      match xf () with
      | Cons (y, yf) ->
          if abs_float (x -. y) <= eps then y
          else within eps (Cons (y, yf))
(* val within : float -> float seq -> float = <fun> *)

within eps searches the lazy list for two consecutive approximations whose absolute difference is at most eps. When found, it returns the second (more accurate) value.

root: putting it together

let root a = within 1e-6 (iterates (next a) 1.0)
(* val root : float -> float = <fun> *)

root 2.0
(* : float = 1.41421356237309492 *)

This composes three small, interchangeable components:

1. next a - one iteration step
2. iterates (next a) 1.0 - infinite series of approximations
3. within 1e-6 - convergence test

The initial approximation of 1.0 is deliberately poor to demonstrate the method’s robustness.

Richardson extrapolation

This compositional approach to numerical computation has received attention in research literature. A recurring example is Richardson extrapolation, which improves the accuracy of numerical integration by combining results at different step sizes. The principle is the same: build numerical methods from small, combinable parts operating on sequences.