algorithme de Borwein

On part d'une approximation assez grossière de π : 2,914213562… Avec la variante quartique de l'algorithme de Borwein, un tour de calcul donne déjà 3,141592646…, puis un second donne 3,141592653589793238462643383279502884197…

Le gain vient d'une convergence d'ordre quatre : lorsque les calculs sont assez précis et l'approximation déjà proche, le nombre de chiffres exacts est approximativement quadruplé à chaque tour. Le nom recouvre plusieurs algorithmes apparentés, et non une recette unique.

Les algorithmes de Borwein sont une famille de procédés itératifs conçus par Jonathan et Peter Borwein pour approcher π avec une convergence d'ordre élevé. Ils prolongent les travaux de Brent et Salamin. Leur construction s'appuie sur des transformations issues des fonctions modulaires et sur des propriétés liées aux moyennes arithmético-géométriques.

Dans la variante quartique, deux suites réelles sont calculées simultanément. La suite auxiliaire, notée $y_{n}y\_n$, tend très vite vers zéro. La seconde, notée $a_{n}a\_n$, tend vers l'inverse de π. L'approximation cherchée au rang n est donc $p_n=1\mathrm{/}{a}_{n}p\_n=1/a\_n$. Chaque nouvelle paire est obtenue à partir de la précédente par des racines quatrièmes, des puissances et une correction pondérée.

L'ordre quatre décrit le comportement de l'erreur lorsque l'itération est déjà dans son régime de convergence ; il ne garantit pas exactement quatre fois plus de décimales à chaque étape ni avec une précision de calcul insuffisante. D'autres algorithmes des Borwein ont des récurrences et des ordres différents.

Pour la variante quartique, l'indice n est un entier naturel, $y_{n}y\_n$ est la variable auxiliaire et $a_{n}a\_n$ est l'inverse approché de π. On initialise les deux suites par :

À chaque rang, la quantité $r_{n}r\_n$ désigne la racine quatrième positive de $1-y_n^{4}1-y\_n^4$. Les mises à jour sont :

Après chaque mise à jour d'indice n, $p_{n+1}=1\mathrm{/}{a}_{n+1}p\_\{n+1\}=1/a\_\{n+1\}$ fournit l'approximation de π. L'arrêt dépend du nombre de décimales visé et de la précision arithmétique disponible.

Cette récurrence s'applique au calcul réel de π avec les valeurs initiales prescrites. À chaque étape, il faut prendre la racine quatrième positive de $1-y_n^{4}1-y\_n^4$. Le calcul doit conserver davantage de chiffres que le résultat demandé, car les arrondis intermédiaires limitent les décimales fiables.

Trois points sont vérifiables : les deux valeurs initiales sont respectées ; le coefficient de correction dépend bien du rang n ; la précision de travail augmente avec l'objectif. Une calculatrice limitée à une quinzaine de chiffres bloque rapidement le gain : une deuxième itération ne peut pas y produire quarante décimales fiables. Pour un calcul courant, une valeur de π fournie par une bibliothèque suffit ; pour étudier une convergence quadratique fondée sur la moyenne arithmético-géométrique, l'algorithme de Brent et Salamin est l'alternative naturelle.

On applique la variante quartique avec une précision supérieure à 50 décimales. Les données sont le rang initial n = 0, la racine carrée positive de 2, puis les deux valeurs initiales imposées.

1. Initialiser : $y_0=\sqrt{2}-1y\_0=\backslash sqrt\{2\}-1$ ≈ 0,414213562373095 et $a_0=6-4\sqrt{2}a\_0=6-4\backslash sqrt\{2\}$ ≈ 0,343145750507620. L'inverse du second terme donne $p_0=1\mathrm{/}{a}_{0}p\_0=1/a\_0$ ≈ 2,914213562373095.

2. Calculer la racine quatrième positive $r_0=\sqrt[4]{1-y_0^4}r\_0=\backslash sqrt[4]\{1-y\_0^4\}$, puis le nouveau terme auxiliaire. On obtient $y_1=(1-r_0)\mathrm{/}(1+r_0)y\_1=(1-r\_0)/(1+r\_0)$ ≈ 0,00373488546332513.

3. Appliquer la correction de rang 0. Le résultat est $a_{1}a\_1$ ≈ 0,3183098869311611510, donc $p_1=1\mathrm{/}{a}_{1}p\_1=1/a\_1$ ≈ 3,1415926462135422821.

4. Recommencer au rang 1. On trouve $y_{2}y\_2$ ≈ 2,43231134188186 × 10⁻¹¹, puis $p_2=1\mathrm{/}{a}_{2}p\_2=1/a\_2$ ≈ 3,141592653589793238462643383279502884197114678.

Le contrôle consiste à comparer avec π calculé à une précision supérieure : les 40 premières décimales coïncident après la deuxième itération. Une échelle logarithmique rend visible la chute de l'erreur absolue, d'environ 2,27 × 10⁻¹ à 7,38 × 10⁻⁹, puis 5,47 × 10⁻⁴¹.

Pour produire un grand nombre de décimales de π, la variante quartique réduit fortement le nombre d'itérations. Elle devient intéressante lorsque l'arithmétique multiprécision sait effectuer efficacement de grandes multiplications et des racines.

Pour quelques décimales, on utilise plutôt la constante π déjà fournie par le logiciel. Le surcoût des racines quatrièmes et de la gestion de précision n'apporte alors aucun avantage observable.

Pour comparer des méthodes numériques, on relève après chaque itération l'erreur absolue et le temps de calcul. Brent-Salamin offre un point de comparaison quadratique ; une variante quartique de Borwein se reconnaît à une erreur qui décroît bien plus brutalement lorsque la précision de travail ne la bride pas.

Deux rapprochements sont utiles, à condition de conserver un critère précis.

Brent-Salamin met directement à jour une moyenne arithmétique et une moyenne géométrique et possède une convergence quadratique. La variante de Borwein présentée ici emploie une racine quatrième et une correction propre pour atteindre l'ordre quatre. La récurrence écrite permet donc de trancher.

La moyenne arithmético-géométrique est une limite commune obtenue en itérant deux moyennes. Un algorithme de Borwein est une procédure complète qui transforme des propriétés de cette moyenne et des fonctions modulaires en approximations de π. Calculer seulement la moyenne ne revient donc pas à exécuter la récurrence quartique.

La rapidité théorique ne dispense pas de contrôler le calcul effectué.

Avec 16 chiffres de précision de travail, demander une quarantième décimale après deux tours n'a pas de sens : les arrondis ont déjà effacé l'information. Le symptôme est une suite qui stagne ou des dernières décimales instables. Il faut augmenter la précision avant de relancer l'itération.

L'ordre quatre est asymptotique. Il ne signifie ni quatre décimales gagnées, ni exactement quatre fois plus à chaque rang. Dans l'exemple, l'erreur passe d'environ 2,27 × 10⁻¹ à 7,38 × 10⁻⁹, puis à 5,47 × 10⁻⁴¹. Il faut mesurer l'erreur ou employer une borne adaptée.

L'expression « algorithme de Borwein » peut viser plusieurs récurrences. Le symptôme est une formule annoncée avec un autre ordre ou d'autres valeurs initiales. Il faut préciser la variante ; cette fiche développe la variante quartique.

La moyenne arithmético-géométrique éclaire le mécanisme commun qui rapproche très vite deux suites et nourrit les méthodes rapides de calcul de π.

L'algorithme de Brent et Salamin permet de comparer une convergence quadratique fondée sur cette moyenne avec la convergence quartique détaillée ici.