www.pi314.net


Histoire
Mathématiciens
Toutes les formules
Approx. numériques
Programmes
Algos perso/divers
Décimales
Poèmes
Articles/vidéos
Délires !
 Pi-Day
Images/Fonds
Musique
Liens sur Pi
Bibliographie



Boris Gourévitch
L'univers de Pi - V2.57
modif. 13/04/2013



Pi-Day dans
Pi Day Countdown
Google
Accueil Historique/Actu (Pi, site, moi) Edito Livre d'or Pages en .pdf Je me présente Quelques photos Remerciements Page des nets d'or Sites qui m'indexent Derniers changements Contact

Cette page en français This page in English


pict

Isaac Newton

Algorithme de Newton



1 La racine de tous les maux

Imaginez que l’on vous demande les premières décimales de  V~ -
  2  . Silence pendant quelques secondes... mmmmh... bon, c’est plus que 1, moins que 2 car  2
2 = 4  ... C’est moins que 1.5 car   2
1.5 = 2.25  etc... Rien de très simple... Alors comment les mathématiciens du 17e siècle pouvaient-ils approcher numériquement les solutions d’un polynôme du 4e degré ?

Toujours prolifique, Newton proposa vers 1669 (!) un processus itératif convergeant de manière quadratique vers de telles solutions, c’est-à-dire que le nombre de décimales exactes de la solution proposéee double à chaque itération. Du coup, cela ramèna la complexite algorithmique de la division et de l’extraction de racines carrées à celle de la multiplication. Une aubaine pour les calculateurs modernes, confrontés dans leur quête du record de décimales de p  à de douloureuses extractions de racines carrées dans les algorithmes de Salamin ou des frères Borwein. Cet algorithme a bien d’autres propriétés que je vous propose de découvrir ci-dessous.

2 Enoncé de l’algorithme de Newton

L’algorithme de Newton, vieux de plus de trois siècles, est à l’origine utilisé pour approcher numériquement une racine a  de l’équation f(x) = 0  . Il permet en fait de montrer l’équivalence de la multiplication, la division et l’extraction de racines carrées d’un point de vue complexité.

Newton avait proposé dès 1669 un processus itératif pour trouver les racines d’équations polynomiales et Raphson le mit sous forme plus algorithmique en 1690. Simpson, Mourraille, Cauchy et Kantorovich ajoutèrent des raffinements et proposèrent des généralisations pour arriver à l’énoncé moderne suivant

Theorem 2.1 Soit f  analytique dans un voisinage complexe de z  . Supposons que f (z) = 0  et f'(z) /= 0  . Alors l’itération

xk+1 = xk - f'(xk)
           f (xk)
(1)

converge uniformément et quadratiquement vers z  pour une valeur initiale x0   prise dans un voisinage de z  .

Cet algorithme s’accompagne d’une propriété étonnante d’auto-compensation des erreurs : si x
 k  est perturbé et ne compte plus que M  décimales justes par rapport à z  alors le terme x
 k+1  contiendra tout de même 2M  décimales exactes s’il a été calculé avec suffisamment de décimales, autrement dit la convergence quadratique sera préservée.

Une conséquence directe est que pour calculer z  avec n  décimales, il suffit d’initier l’algorithme avec quelques décimales au début et doubler la précision prise en compte à chaque itération jusqu’à atteindre une précision supérieure à n  . Ceci simplifie considérablement la complexité de l’opération et permet de montrer que la multiplication, la division et l’extraction de racines carrées sont équivalentes en complexité :

3 Applications

3.1 Inverse d’un nombre

Prenons l’exemple d’un nombre |y|< 1  dont on souhaite calculer l’inverse avec      d
n = 2  décimales exactes. En utilisant la fonction f(x) = 1/x - y  , l’itération associée est

             2
xk+1 = 2xk -x ky
(2)

qui utilise uniquement des multiplications et additions. L’expression

      1      (     1)2
xk+1- y-= - y xk - y-
(3)

illustre la convergence quadratique de l’algorithme. Initions maintenant l’itération avec une décimale exacte, soit

||    1||   1
||x0 - y||<  10.
(4)

Grâce à la propriété d’auto-correction de la méthode de Newton, à l’itération k  , on n’utilise que  k
2  décimales pour les calculs. Et d’après 2, pour obtenir xk,  on a uniquement besoin de 2  multiplications (xk-1 xk-1  et   2
x k- 1y  ) et 2  additions (xk-1 + xk-1  et         2
2xk-1- xk-1y  ). En raison de la convergence quadratique, il suffira d’environ log2(n) = d  itérations de 2 pour parvenir à n  décimales exactes de 1
y  . Si on note M (n)  la complexité d’une méthode de multiplication pour n  décimales, sachant que la complexité d’une addition sera n  , on obtient alors une complexité finale de

log sum 2(n)
     (2M (2k)+ 2.2k)< 4M (n)+ 4n < 8M (n)
 k=1
(5)

Il est en effet raisonnable d’envisager 2M  (p) < M (2p)  autrement dit que la complexité de 2  multiplications de nombres à p  décimales requiert un peu moins de complexité que la multiplication de deux nombres à 2p  décimales. Ceci induit    (  )     (    )
2M  2k  < M  2k+1 < ...< 2d-1k-1M (n)  dans 5. L’inversion n’est donc guère plus compliquée que la multiplication (c’est un O (M (n))  ) et comme a.b = a.1b  , la division est elle aussi un O (M (n))  .

3.2 Extraction de racines carrées

Les choses se passent aussi bien. On peut utiliser la fonction f(x) = x12 -y  qui conduit à l’approximation de  V~ 1y puis on fait  V~ -
 y = y.1 V~ y-  . L’itération associée est

                   2
xk+1 = xk + xk1--y.xk
                2
(6)

ce qui conduit en pratique à une complexité finale d’environ 4M (n)  .

Une alternative plus naturelle est d’utiliser directement la fonction f(x) = y - x2  , mais cela conduit à une itération comprenant une division disqualifiante

                2
xk+1 = xk + y--xk.
             2xk
(7)

Cependant, Schönhage, qui ne manquait pas d’idées (voir page FFT), a proposé en 1971 de remplacer 21xk-  par une approximation tirée d’une itération couplée et a obtenu

pict

Ce processus, où vk+1  estime 21 V~ y  , est appelé ”itération couplée de Newton” ([5], p257) et requiert en pratique une complexité d’environ 3M (n)  .

On trouvera de nombreux raffinements de la méthode de Newton dans [14] et l’équivalence de la complexité de la multiplication, la division et l’extraction de racines est abordée dans [23].

References

[1]   J. Arndt, C. Haenel, ”p  Unleashed”, Springer-Verlag, Berlin Heidelberg New York, 2001.

[2]   R. Brent, “Fast multiple-precision evaluation of elementary fonctions”, Journal of the Association of Computing Machinery, 1976, pp.242-251.

[3]   S. A. Cook, S. O. Aanderaa, “On the minimum computation of functions”, Trans. AMS, 1969, vol. 142, pp291-314.

[4]   M. D. Householder, “The Numerical Treatment of a Single Nonlinear Equation”, 1970, MacGraw-Hill, New-York.

[5]   A. Schönhage, V. Strassen, “Schennelle Multiplikation grosser Zahlen”, Computing, 1971, vol. 7, pp. 281-292.


Retour à la page d'accueil