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}\backslash 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{.}\backslash dfrac\{f(x)\}\{f\text{'}(x)\}\; =\; \backslash dfrac\{x^2\; -a\}\{2x\}\; =\; \backslash dfrac\{x\}\{2\}\; -\; \backslash dfrac\{a\}\{2x\}.$

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 \backslash sqrt\{163\}\; =\; 12,7671453348037\; \backslash ldots$

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,g(x)\; =\; \backslash dfrac\{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,g(x)\; =\; \backslash dfrac\{1\}\{x\}-b,$ e $g^{\mathrm{\prime }}(x)={\displaystyle \frac{-1}{x^2}},g\text{'}(x)\; =\; \backslash dfrac\{-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,\backslash dfrac\{g(x)\}\{g\text{'}(x)\}\; =\; \backslash dfrac\{\; \backslash dfrac\{1\}\{x\}-b\}\{\backslash dfrac\{-1\}\{x^2\}\}\; =\; -x^2\; \backslash left(\; \backslash cfrac\{1\}\{x\}\; -b\backslash right)\; =\; -x\; +bx^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{.}v\_\{n+1\}\; =\; v\_n-\; \backslash dfrac\{g\backslash left(u\_n\backslash right)\}\{g\text{'}\backslash left(u\_n\; \backslash right)\}\; =\; v\_n\; +v\_n\; -bv\_n^2\; =\; v\_n\; \backslash left(\; 2-bv\_n\; \backslash right).$

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}},\backslash dfrac\{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}\backslash left\; \backslash \{\; \backslash begin\{array\}\{l\}\; u\_\{n+1\}\; =\; u\_n\; +\; \backslash left(\; a-u\_n^2\backslash right)\; v\_n,\; \backslash [0,7mm]\; v\_\{n+1\}\; =\; v\_n\; (2-2u\_nv\_n)\; =\; v\_n\; +(1-2u\_nv\_n)v\_n,\; \backslash end\{array\}\; \backslash right.$ con $v_0={\displaystyle \frac{1}{2u_0}}\mathrm{.}v\_0=\; \backslash dfrac\{1\}\{2u\_0\}.$