Il metodo di Newton

La calcolatrice usa successioni basate su perfezionamenti del metodo di Newton (vedi Les Algorithmes, Bibliothèque Tangente 37, 2013, oppure Itération et Récurrence, Bibliothèque Tangente 76, 2021).

La funzione f utilizzata è definita da f (x) = x² ‒ a.

Cerchiamo la soluzione di f (x) = 0, poiché la soluzione è proprio $\sqrt{a}$ la quantità che ci interessa. Implementiamo l’algoritmo.

La derivata di f è f ' (x) = 2 x, e si ha ${\displaystyle \frac{f(x)}{f^{\mathrm{\prime }}(x)}}={\displaystyle \frac{x^2-a}{2x}}={\displaystyle \frac{x}{2}}-{\displaystyle \frac{a}{2x}}\mathrm{.}$

Si ottiene così la successione di Erone:

Illustriamo ora il metodo con a = 163. Per inizializzare i calcoli, si può partire da a, oppure, dato che 163 è compreso tra 144 = 12² e 169 = 13², da 12.

Dopo appena tre iterazioni dell’algoritmo, il risultato è sorprendente, poiché $\sqrt{163}=12,7671453348037\dots$

Infatti, il numero di cifre decimali esatte raddoppia (come minimo) a ogni ciclo: è il fenomeno della convergenza quadratica.

A ogni iterazione occorrono un’addizione, una divisione e una divisione per 2, facile da programmare in binario: in tutto, appena tre operazioni.

L’astuzia di Schönhage ---------------------

Il principale svantaggio dell’uso della successione di Erone (vedi sopra) è la presenza di una divisione: un’operazione «gravosa» e «lenta», persino per un circuito elettronico. Tuttavia, la divisione « a / *u_n » può essere sostituita da una successione: ancora una volta si usa il metodo di Newton per calcolare l’inverso 1/b di un numero reale b > 0. Questa volta si usa la funzione g definita da $g(x)={\displaystyle \frac{1}{x}}-b,$ che porta alla successione v definita da v_n*₊₁ = *v_n(2 ‒ bv_n*).

Infatti: $g(x)={\displaystyle \frac{1}{x}}-b,$ e $g^{\mathrm{\prime }}(x)={\displaystyle \frac{-1}{x^2}},$ da cui ${\displaystyle \frac{g(x)}{g^{\mathrm{\prime }}(x)}}={\displaystyle \frac{{\displaystyle \frac{1}{x}}-b}{{\displaystyle \frac{-1}{x^2}}}}=-x^2({\displaystyle \frac{1}{x}}-b)=-x+b{x}^2,$

ossia $v_{n+1}=v_n-{\displaystyle \frac{g\left(u_n\right)}{g^{\mathrm{\prime }}\left(u_n\right)}}=v_n+v_n-b{v}_n^2=v_n(2-b{v}_n)\mathrm{.}$

Si può fare ancora meglio! Il matematico tedesco Arnold Schönhage (nato nel 1934) ebbe l’idea di accoppiare le due successioni del metodo di Newton; questo accoppiamento si rivelò più efficiente dell’uso separato dei due metodi. Per calcolare un valore approssimato della radice quadrata di a > 0, ripartiamo dalla successione u, definita da

Per calcolare ${\displaystyle \frac{1}{2u_n}},$ si usa il metodo di Newton per calcolare gli inversi.

In questo contesto si usano due successioni, u e v:

$\{\begin{array}{l}{u}_{n+1}=u_n+(a-u_n^2)v_n,\text{[}0,7mm]v_{n+1}=v_n(2-2u_n{v}_n)=v_n+(1-2u_n{v}_n)v_n,\end{array}$ con $v_0={\displaystyle \frac{1}{2u_0}}\mathrm{.}$