El método de Newton

La calculadora utiliza sucesiones obtenidas mediante refinamientos del método de Newton (véanse Les Algorithmes, Bibliothèque Tangente 37, 2013, o Itération et Récurrence, Bibliothèque Tangente 76, 2021).

La función f utilizada se define por f (x) = x² ‒ a.

Buscamos la solución de f (x) = 0, pues la solución es precisamente $\sqrt{a}$ la cantidad que nos interesa. Apliquemos el algoritmo.

La derivada de f es f ' (x) = 2 x, y se tiene ${\displaystyle \frac{f(x)}{f^{\mathrm{\prime }}(x)}}={\displaystyle \frac{x^2-a}{2x}}={\displaystyle \frac{x}{2}}-{\displaystyle \frac{a}{2x}}\mathrm{.}$

De ello se deduce la sucesión de Herón:

Ilustremos ahora el método con a = 163. Para iniciar los cálculos, podemos partir de a o bien, dado que 163 está comprendido entre 144 = 12² y 169 = 13², de 12.

Tras solo tres iteraciones del algoritmo, el resultado es asombroso, pues $\sqrt{163}=12,7671453348037\dots$

En efecto, el número de cifras decimales correctas se duplica (como mínimo) en cada bucle (fenómeno de convergencia cuadrática).

En cada iteración hay una suma, una división y una división entre 2, fácil de programar en binario: solo tres operaciones que realizar.

El truco de Schönhage ---------------------

La principal desventaja de utilizar la sucesión de Herón (véase más arriba) es la presencia de una división: es una operación « penosa » y « lenta », incluso para un circuito electrónico. Pero es posible sustituir la división « a / *u_n » por una sucesión: se utiliza, una vez más, el método de Newton para calcular el inverso 1/b de un número real b > 0. Esta vez se utiliza la función g definida por $g(x)={\displaystyle \frac{1}{x}}-b,$ lo que conduce a la sucesión v definida por v_n*₊₁ = *v_n(2 ‒ bv_n*).

En efecto: $g(x)={\displaystyle \frac{1}{x}}-b,$ y $g^{\mathrm{\prime }}(x)={\displaystyle \frac{-1}{x^2}},$ de donde ${\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,$

es decir, $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{.}$

¡Aún se puede mejorar! El matemático alemán Arnold Schönhage (nacido en 1934) tuvo la idea de acoplar las dos sucesiones del método de Newton, y este acoplamiento resulta más eficaz que utilizar ambos métodos por separado. Para calcular un valor aproximado de la raíz cuadrada de a > 0, partimos de nuevo de la sucesión u, definida por

Para calcular ${\displaystyle \frac{1}{2u_n}},$ se utiliza el método de Newton aplicado al cálculo de inversos.

En este contexto se utilizan dos sucesiones, u y 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{.}$