Calcolo di radici con Newton

Applicare Newton all’estrazione di radice porta a una formula antichissima, e mostra quanto sia rapida la sua convergenza.

Esempio — Calcolo di $\sqrt{2}$ con Newton

Sia $f(x)=x^2-2$, $f'(x)=2x$. L’iterazione diventa $x_{n+1} = x_n - \frac{x_n^2-2}{2x_n} = \frac{1}{2}\left(x_n+\frac{2}{x_n}\right).$ Partendo da $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}$ |

A ogni passo raddoppiano le cifre decimali corrette: la convergenza è quadratica, nel senso che $|x_{n+1}-\alpha|\le C\,|x_n-\alpha|^2$ in un intorno della radice $\alpha$ (Esty, 2014). È il celebre algoritmo babilonese-eroniano per il calcolo della radice, attribuito a Erone d’Alessandria ($\approx 60$ d.C.; Boyer, 2011).

La formula $x_{n+1} = \tfrac{1}{2}\left(x_n+\tfrac{2}{x_n}\right)$ ha una lettura intuitiva: se $x_n$ è una stima per eccesso di $\sqrt{2}$, allora $2/x_n$ lo è per difetto, e la loro media è una stima migliore. Questa idea di “media tra eccesso e difetto” è proprio il metodo antico, e la convergenza quadratica spiega perché bastino pochissimi passi per ottenere moltissime cifre.

Collegamenti

Argomenti: Continuita
Concetti: Convergenza quadratica · Metodo di newton raphson
Metodi: Newton raphson
Competenze: Calcolare · Usare formule
Persone: Erone