algorithme de Brent et Salamin
L'algorithme de Brent et Salamin est un algorithme de calcul du nombre π, découvert indépendamment par Richard Brent et Eugene Salamin en 1976. Il présente la particularité d'avoir une convergence quadratique, c'est-à-dire que le nombre de décimales exactes de π double approximativement à chaque itération. Cet algorithme repose sur le calcul de la moyenne arithmético-géométrique et exploite des identités classiques de la théorie des fonctions elliptiques.
Sommaire
Ce que vous allez apprendre
- Identifier les quatre suites et leurs valeurs initiales.
- Exécuter les mises à jour dans le bon ordre.
- Vérifier la progression des décimales sur trois itérations.
- Repérer une fausse stabilité causée par un arrondi trop précoce.
En clair
On part de deux nombres positifs, puis on les rapproche de deux façons : par leur moyenne ordinaire et par leur moyenne géométrique. À chaque tour, ces deux nouvelles valeurs deviennent très vite presque égales.
L’algorithme de Brent et Salamin transforme ce rapprochement en une approximation de π. Son intérêt tient à son accélération : une itération apporte approximativement deux fois plus de décimales exactes que la précédente.
Définition
L’algorithme de Brent et Salamin, découvert indépendamment par Richard Brent et Eugene Salamin en 1976, calcule des approximations successives de π. Il est aussi fondé sur l’itération des moyennes arithmétique et géométrique, dont la limite commune est appelée moyenne arithmético-géométrique. Quatre suites interviennent : le terme arithmétique an, le terme géométrique bn, un correcteur tn et un poids pn. Elles commencent par .
À l’itération suivante, la nouvelle valeur an+1 est la moyenne arithmétique de an et bn, tandis que bn+1 est leur moyenne géométrique. Le correcteur retire l’écart au carré, pondéré par pn, et le poids double. Ces quatre mises à jour s’écrivent :
Après chaque mise à jour, l’approximation est . Sa convergence est quadratique : lorsque la précision de calcul est suffisante, le nombre de décimales exactes double approximativement à chaque itération. Le lien avec π vient d’identités classiques de la théorie des fonctions elliptiques.
Le principe
Initialiser les quatre suites par . À chaque tour, remplacer a par la moyenne arithmétique de a et b, remplacer b par leur moyenne géométrique, corriger t avec l’ancien poids p, puis doubler p.
La valeur courante de π est alors . On s’arrête lorsque la précision visée est atteinte ou lorsqu’une nouvelle itération ne modifie plus le résultat à la précision de calcul disponible.
Quand l'utiliser
La procédure s’applique au calcul numérique de π avec les valeurs initiales indiquées. Elle demande de conserver simultanément a, b, t et p, d’utiliser l’ancienne valeur de a dans la correction de t et d’évaluer les racines carrées avec une précision adaptée au nombre de décimales recherché.
Si les nombres sont arrondis trop tôt, a et b peuvent devenir artificiellement égaux : les tours suivants n’ajoutent alors aucune décimale fiable. Il faut augmenter la précision arithmétique avant de poursuivre. De même, d’autres valeurs initiales ne constituent pas automatiquement cet algorithme de calcul de π ; il faut revenir au quadruplet initial prescrit.
Un exemple, pas à pas
On calcule π avec a0 = 1, b0 ≈ 0,7071067812, t0 = 0,25 et p0 = 1. Les valeurs affichées sont arrondies ; les calculs intermédiaires gardent davantage de chiffres.
1. Avant toute mise à jour, la formule donne π0 ≈ 2,9142135624. Cette première valeur est encore éloignée de π.
2. Au premier tour, a1 ≈ 0,8535533906 et b1 ≈ 0,8408964153. La correction donne t1 ≈ 0,2285533906 et le poids devient p1 = 2. On obtient π1 ≈ 3,1405792505.
3. Au deuxième tour, a2 ≈ 0,8472249029, b2 ≈ 0,8472012667 et t2 ≈ 0,2284732911. La nouvelle approximation vaut π2 ≈ 3,1415926462.
4. Un troisième tour conduit à π3 ≈ 3,141592653589794. À l’arrondi affiché, ce résultat diffère de π seulement sur le dernier chiffre.
Le contrôle se fait en comparant les préfixes décimaux : 3,14 après un tour, 3,1415926 après deux, puis 3,14159265358979 après trois. La progression rend visible le quasi-doublement du nombre de décimales correctes.
En pratique
Pour obtenir beaucoup de décimales de π, on choisit d’abord une arithmétique capable de conserver la précision visée. On répète ensuite les mises à jour jusqu’à ce que l’approximation soit stable sur les chiffres demandés.
Pour étudier la convergence, on note après chaque tour le nombre de décimales communes avec une valeur de contrôle de π. Brent-Salamin est particulièrement parlant lorsque l’on veut observer une convergence quadratique sur très peu d’itérations.
Pour un calcul court à la main, une méthode élémentaire peut demander moins de suivi : Brent-Salamin impose quatre quantités et une racine carrée à chaque tour. Son avantage apparaît surtout quand la précision recherchée augmente.
À ne pas confondre
La moyenne arithmético-géométrique est le processus qui rapproche deux suites par deux moyennes. L’algorithme de Brent et Salamin ajoute un correcteur et un poids pour en tirer π : calculer seulement les deux moyennes ne suffit pas.
La convergence quadratique ne désigne pas ici une moyenne de carrés. Elle décrit la vitesse de l’erreur : le nombre de décimales exactes double approximativement par tour. Une « convergence en moyenne quadratique » est une autre notion.
Limites et pièges
Le doublement des décimales est approximatif, pas une promesse exacte à chaque tour. Dans l’exemple, on passe d’environ 2 décimales correctes après le premier tour à 7 après le deuxième ; il faut contrôler les chiffres obtenus plutôt que les compter mécaniquement.
Une stabilité apparente peut provenir de l’arrondi. Si a et b sont égaux seulement parce que la machine ne distingue plus leur écart, répéter l’itération ne valide pas de nouveaux chiffres : il faut recalculer avec davantage de précision.
L’ordre des mises à jour compte. Employer an+1 à la place de l’ancien an dans le mauvais terme, ou doubler p avant la correction de t, modifie la récurrence. Il faut conserver les anciennes valeurs jusqu’à la fin du tour.
Pour aller plus loin
La moyenne arithmético-géométrique détaille le rapprochement des deux suites qui forme le cœur de l’algorithme.
La fiche Pi (calcul par la méthode de Monte-Carlo) présente une autre manière d’approcher π et permet de comparer les mécanismes de convergence.
L’algorithme de Chudnovsky offre un autre point d’entrée vers le calcul de nombreuses décimales de π.
La fonction elliptique ouvre sur la théorie dont sont issues les identités reliant la moyenne arithmético-géométrique à π.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres