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

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

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,g(x)\; =\; \backslash dfrac\{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,g(x)\; =\; \backslash dfrac\{1\}\{x\}-b,$ y $g^{\mathrm{\prime }}(x)={\displaystyle \frac{-1}{x^2}},g\text{'}(x)\; =\; \backslash dfrac\{-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,\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,$

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{.}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).$

¡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}},\backslash dfrac\{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}\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\}.$