Procédé archimédien

Un procédé archimédien (Archimedean process) est une méthode de calcul numérique itérative basée sur le calcul de moyennes (le plus couramment pythagoriciennes) de deux termes de deux suites.

Le nom vient du fait qu'il s'agit d'une généralisation de l'algorithme utilisé par Archimède pour donner les premières valeurs approchées de π, en utilisant les moyennes harmonique et géométrique.

Historique

Algorithme d'Archimède

Algorithme d'Archimède pour le calcul de π

Dans son ouvrage De la mesure du cercle du III^e siècle av. J.-C., Archimède décrit un algorithme de calcul de π qu'on peut définir comme suit :

• On part d'un demi-cercle de centre O et d'extrémités A et B
• Sur la demi-droite tangente au demi-cercle en A, on place un point A₀, et on construit B₀ sur le demi-cercle tel que ${\widehat {BAB_{0}}}={\widehat {AOA_{0}}}$
• On construit par récurrence les points A₁, A₂, ... et B₁, B₂, ... où pour tout n, A_n est l'intersection de AA₀ et de la bissectrice de l'angle ${\widehat {AOA_{n-1}}}$, et B_n sur le demi-cercle tel que ${\widehat {BAB_{n}}}={\widehat {AOA_{n}}}$

On a alors, par le théorème de la bissectrice intérieure :

$\forall n\in \mathbb {N} ,\ {\frac {OA_{n}}{OA}}={\frac {A_{n}A_{n+1}}{AA_{n+1}}}$

Donc

$\forall n\in \mathbb {N} ,\ {\frac {OA+OA_{n}}{OA}}=1+{\frac {OA_{n}}{OA}}=1+{\frac {A_{n}A_{n+1}}{AA_{n+1}}}={\frac {AA_{n+1}+A_{n}A_{n+1}}{AA_{n+1}}}={\frac {AA_{n}}{AA_{n+1}}}$

d'où :

${\frac {OA}{AA_{n}}}+{\frac {OA_{n}}{AA_{n}}}={\frac {OA}{AA_{n+1}}}$

De plus, le théorème de Pythagore donne :

$\forall n\in \mathbb {N} ,OA_{n}^{2}=OA^{2}+AA_{n}^{2}$

En posant $t_{n}=OA/AA_{n},s_{n}=OA_{n}/AA_{n}$, on déduit les relations de récurrence :

$\forall n\in \mathbb {N} ,t_{n+1}=t_{n}+s_{n},s_{n+1}={\sqrt {1+t_{n}^{2}}}.$

On pourra reconnaitre des identités trigonométriques en remarquant que, en posant $\theta ={\widehat {AOA_{0}}}$, on a

$t_{n}=\cot \left({\frac {\theta }{2^{n-1}}}\right),s_{n}=\csc \left({\frac {\theta }{2^{n-1}}}\right).$

Archimède a plus précisément étudié le cas où θ désigne la moitié d'un angle au centre d'un polygone régulier, soit $\theta ={\frac {\pi }{N}}$. Les suites p_n = 2ⁿN/s_n = 2ⁿN tan(π/2ⁿN) et P_n = 2ⁿN/t_n = 2ⁿN sin(π/2ⁿN) désignent alors respectivement les périmètres des polygones réguliers inscrits et circonscrits à 2ⁿN côtés. On a alors :

$\forall n\in \mathbb {N} ,P_{n+1}={\frac {2P_{n}p_{n}}{P_{n}+p_{n}}}=\mathrm {H} (p_{n},P_{n}),p_{n+1}={\sqrt {p_{n}P_{n+1}}}=\mathrm {G} (p_{n},P_{n}).$

où H désigne la moyenne harmonique et G, la moyenne géométrique.

Archimède a appliqué cet algorithme en partant de l'hexagone régulier (N = 6).

Algorithme de Descartes

Algorithme de Descartes pour le calcul de π

Dans un de ses travaux posthumes, Descartes a utilisé une approche différente pour le calcul de π.

On considère A₀B₀ un secteur circulaire de sommet O. On note M₀ le milieu de [A₀B₀]. On trace P₀ l'intersection de l'arc de cercle et de la bissectrice de l'angle ${\widehat {A_{0}OB_{0}}}$. On construit M₁ le milieu de M₀P₀ et on trace la parallèle de A₀B₀ passant par M₁, dont on note respectivement A₁ et B₁, les intersections avec (A₀P₀) et (B₀P₀).

Par construction, A₁B₁ vaut la moitié de A₀B₀. De plus, comme (OA₁) et (A₀P₀) sont perpendiculaires, on a :

$OM_{1}\times OP_{0}=OM_{1}\times (OM_{1}+M_{1}P_{0})=OM_{1}^{2}+OM_{1}\times M_{1}P_{0}=OM_{1}^{2}+M_{1}A_{1}^{2}=OA_{1}^{2}$.

Ainsi, dans le cas où A₀ et B₀ désignent deux sommets consécutifs d'un polygone régulier à n côtés, OA₀ est le rayon de son cercle circonscrit, OM₀ celui de son cercle inscrit, et par construction, OA₁ et OM₁ sont respectivement les rayons des cercles circonscrit et inscrit d'un polygone régulier à 2n côtés.

Améliorations

James Gregory adapte l'algorithme au calcul de secteurs elliptiques et hyperboliques dans son Vera Circuli et Hyperbolae Quadratura.

Dans une lettre, Gauss propose d'étudier l'algorithme dans le cas où la moyenne harmonique est remplacée par la moyenne arithmétique. Pfaff parvient à donner la solution générale de ce problème, redécouverte par Borchardt en 1881.

Principe

On considère deux moyennes M₁ et M₂, définies peux deux nombres réels positifs, et deux nombres réels positifs a et b. Le procédé archimédien est défini par deux suites :

$a_{0}:=a,\ b_{0}:=b,\ \forall n\in \mathbb {N} ,a_{n+1}=M_{1}(a_{n},b_{n}),b_{n+1}=M_{2}(a_{n},b_{n}).$

Si M₁ et M₂ sont deux moyennes strictes, continues et symétriques, alors les deux suites convergent vers une même limite.

Algorithme d'Archimède–Borchardt

Suggéré d'abord par Gauss, il porte le nom de Karl Wilhelm Borchardt. L'algorithme de Borchardt est une modification de l'algorithme d'Archimède :

$a_{0}:=a,\ b_{0}:=b,\ \forall n\in \mathbb {N} ,a_{n+1}=M_{1}(a_{n},b_{n}),b_{n+1}=M_{2}(a_{n+1},b_{n}).$

Ainsi, l'algorithme d'Archimède décrit supra correspond au cas où M₁ est la moyenne harmonique et M₂, la moyenne géométrique, $a=3{\sqrt {3}},b=3{\sqrt {3}}/2$ ; l'algorithme de Descartes correspond au cas où M₁ est la moyenne arithmétique et M₂, la moyenne géométrique.

La moyenne obtenue avec M₁ est la moyenne harmonique et M₂, la moyenne géométrique est appelée moyenne de Schwab-Brochardt et vaut:

$SB(a,b)={\begin{cases}{\frac {\sqrt {b^{2}-a^{2}}}{\arccos(a/b)}}&{\text{ si }}0\leqslant a<b,\\{\frac {\sqrt {a^{2}-b^{2}}}{\operatorname {arcosh} (a/b)}}&{\text{ si }}0\leqslant b<a.\end{cases}}$

Le lien entre moyenne de Schwab-Brochardt et intégrale elliptique est établi par Carlson par l'égalité:

${\frac {1}{SB(a,b)}}={\frac {1}{2}}\int _{0}^{+\infty }{\frac {\mathrm {d} t}{{\sqrt {t+a^{2}}}(t+b^{2})}}=R_{F}(a^{2},b^{2},b^{2})$

où le deuxième terme est la forme symétrique de Carlson (de) d'une intégrale elliptique symétrique du premier type.

Applications

Calculs de racines carrées

La méthode de Héron, pour le calcul de la racine carrée d'un nombre A, peut être vue comme un algorithme d'Archimède avec les moyennes arithmétique et harmonique, en initialisant a₀ à un nombre t quelconque et en posant $b_{n}=A/a_{n}$.

Calculs d'intégrales elliptiques

Gauss a utilisé l'algorithme d'Archimède avec les moyennes arithmético-géométriques pour le calcul d'intégrales elliptiques après transformation de Landen, repris et approfondi par Derrick Lehmer.

Calculs de logarithmes et de fonctions trigonométriques réciproques

Carlson utilise l'algorithme de Borchardt avec les moyennes arithmético-géométriques pour le calcul de logarithmes et de fonctions trigonométriques réciproques (circulaires et hyperboliques).

Références

• (en) D. M. E. Foster et G. M. Phillips, « The Arithmetic-Harmonic Mean », Mathematics of Computation, vol. 43, n^o 165,‎ janvier 1984, p. 183-191 (lire en ligne)
• (en) D. M. E. Foster et G. M. Phillips, « A generalization of the Archimedean double sequence », Journal of Mathematical Analysis and Applications, vol. 101, n^o 2,‎ juillet 1984, p. 575-581 (DOI 10.1016/0022-247X(84)90121-5)
• (en) George Miel, « Of Calculations Past and Present: The Archimedean Algorithm », The American Mathematical Monthly, vol. 90, n^o 1,‎ 1983, p. 17–35 (DOI 10.2307/2975687, lire en ligne)