L'algorithme de Gauss-Salamin

I. Introduction
- Les intégrales elliptiques
- La moyenne arithmético-géométrique
- Combinaison des deux
- Conclusion
II. Etude d'une intégrale auxiliaire
- Propriétés basiques
III. Utilisation des fonctions d'Euler
- Rappels
- Expression numérique du produit
IV. Conclusion
- Mise en commun des résultats
- Application calculatoire
- Mise en oeuvre


I. Introduction

Pour commencer, nous précisons ce qui vous devriez savoir.

- Les intégrales elliptiques

Les intégrales elliptiques sont apparues avec des problèmes simples, comme le calcul de la longueur d'une sinusoïde ou le périmètre d'une ellipse. Il est conseillé de les avoir déjà un peu étudiées pour continuer.

Nous rappelons ici un résultat utile sur les intégrales elliptiques du premier ordre. Il nous servira dans cet article.

En opérant le changement de variable t = b.tan() sur

, on obtient :

Citons aussi le cas trivial,

Ouvrir l'article sur les intégrales elliptique.

- La moyenne arithmético-géométrique

Nous devons à Gauss cette moyenne. Pour calculer la moyenne arithmético-géométrique M(a,b) des deux nombres a et b , on définit deux suites an et bn par

a0 = a b0 = b et



vérifie . La rapidité exponentielle de convergence nous permettra de trouver des méthode extrèmement efficientes pour calculer entre autre les intégrales elliptiques.

Pour avoir les démonstrations des résultats cités, allez voir :

Article sur la moyenne de Gauss

- Combinaison des deux

L'article sur les intégrales elliptique nous démontre que :


Ce résultat est fondamental pour la suite.

- Conclusion

De ce préambule à la démonstration de la formule de Gauss-Salamin, nous devons nous rappeler de ce double changement de variable : t=b.tan et , utilisé dans l'article sur les intégrales elliptiques.

II. Etude d'une intégrale auxiliaire

- Propriétés basiques

Nous allons étudier la fonction

Le changement de variable nous montre que

On obtient donc la relation L(a,b)+L(b,a)=I(a,b), qui est la raison d'être de cette fonction L.

Nous allons opérer sur L deux changements de variables, inspirés de l'article sur les intégrales elliptique.

Le premier t=b.tan , est celui qui a mis l'intégrale elliptique de premier ordre sous une autre forme.


Le second changement de variable est celui trouvé dans la partie "Combinaison avec la moyenne aritmético-géométrique", à savoir t=1/2. (x-ab/x)

Pour l'appliquer, on utilise les mêmes formules que dans cette partie, a laquelle je vous conseille de vous reporter, car on va aller un peu plus vite...


On réarrange le résultat précédent , sachant que :

, pour obtenir :

(E0)

on a de même :

(En-1)

En sommant les égalités 2n-1. En-1, les sommes partielles se télescopent, et on obtient :

Nous avons rappelé dans l'introduction que , on peut donc définir

De plus on a

et donc

. On peut maintenant écrire :


Ce résultat sert d'ailleurs dans l'article sur les intégrales elliptiques.

Ourvrir l'article sur les intégrales elliptiques

En se rappelant que L(b,a)=I(a,b) - L(a,b), on obtient


Cas particulier : en utilisant les valeurs initiales , on obtient


III. Utilisation des fonctions d'Euler

- Rappels

On utilise les fonctions bêta et gamma , qui vérifient les propriétés : et

est l'intégrale de Gauss-Poisson.

- Expression des intégrales elliptiques en fonction de la fonction Bêta

On étudie deux cas particuliers : et .

Le double changement de variable, x=cos(), t = x4 nous montre que :

Le changement de variable t = x4 nous donne, quand à lui :


- Expression numérique du produit

On utilise ces deux résultats pour montrer successivement que :

et donc, que


IV. Conclusion

- Mise en commun des résultats

On considère le cas particulier de la série arithmético-géométrique ou a est la racine carrée de deux, et b vaut l'unité. On a alors c0=1, et donc :




Une des grandes idées de cette formule est que l'on peut calculer M et S en même temps.

Pour des raisons techniques (calculatoire...) on préfère prendre

On a alors

ce qui induit à :

, où

- Application calculatoire

Il s'agit, bien évidemment, de calculer

qui a l'avantage de se calculer facilement par l'algorithme suivant (dit " algorithme de Gauss-Salamin ")

On utilise 5 variables : A et B représentent an et bn , C représente , X représente les puissances successives de deux, et Y.

On les initialise respectivement a 1, , 1/4 et 1.

On itère la boucle suivante :

Begin

Y=A

A = (A+B)/2

B=

C = C - X.(A-Y)2

X = 2.X

End ;

Y est ici une variable locale auxiliaire qui ne sert qu'a mémoriser A pour le calcul

de B et C.

Les lignes 2 et 3 représentent le calcul de la moyenne de Gauss, la ligne 4 représente le calcul de S', et la ligne 5 fait doubler X a chaque itération.

Après la dernière ligne, on peut afficher , qui représente

La rapidité de convergence vers Pi est hallucinante ; elle est due à la rapidité de convergence de la moyenne de Gauss. 20 itérations suffisent pour calculer un million de décimales de Pi.

- Mise en oeuvre

Celle-ci se base principalement sur les implémentations du calcul des grands nombres, qui doit faire l'objet d'un article dans folium.

Le plus dur à part ça étant d'obtenir l'inverse de la racine de deux avec une précision suffisante.



Première version : 13/11/96
Auteur : Thomas Capricelli (Page Web, e-mail : folium@carrosse.frmug.org)
Source : The mathematical Gazette "The Gauss-Salamin algorithm" by Nick Lord
Relecure : Aucune pour l'instant