Computing roots with Newton

Applying Newton to the extraction of a root leads to a very ancient formula, and shows how fast its convergence is.

Example — Computing $\sqrt{2}$ with Newton

Let $f(x)=x^2-2$, $f'(x)=2x$. The iteration becomes $x_{n+1} = x_n - \frac{x_n^2-2}{2x_n} = \frac{1}{2}\left(x_n+\frac{2}{x_n}\right).$ Starting from $x_0=2$:

| $n$ | $x_n$ | $|x_n-\sqrt{2}|$ | |:---:|:---:|:---:| | $0$ | $2$ | $0{,}585\ldots$ | | $1$ | $1{,}5$ | $0{,}0858\ldots$ | | $2$ | $1{,}41\overline{6}$ | $0{,}0024\ldots$ | | $3$ | $1{,}41421568\ldots$ | $2{,}1\cdot 10^{-6}$ | | $4$ | $1{,}41421356\ldots$ | $\le 10^{-12}$ |

At each step the number of correct decimal digits doubles: the convergence is quadratic, in the sense that $|x_{n+1}-\alpha|\le C\,|x_n-\alpha|^2$ in a neighbourhood of the root $\alpha$ (Esty, 2014). It is the famous Babylonian-Heronian algorithm for computing the root, attributed to Hero of Alexandria ($\approx 60$ AD; Boyer, 2011).

The formula $x_{n+1} = \tfrac{1}{2}\left(x_n+\tfrac{2}{x_n}\right)$ has an intuitive reading: if $x_n$ is an overestimate of $\sqrt{2}$, then $2/x_n$ is an underestimate, and their average is a better estimate. This idea of the “average between overestimate and underestimate” is precisely the ancient method, and the quadratic convergence explains why very few steps are enough to obtain a great many digits.

Links

Topics: Continuita
Concepts: Convergenza quadratica · Metodo di newton raphson
Methods: Newton raphson
Skills: Calcolare · Usare formule
People: Erone