Acceuil




Ecrivez-moi :
raphael dot pasquier at free dot fr

Mise à jour le 2 octobre 2006













VERSION pdf :: ps :: tex

Algorithmes à convergence très rapide vers $ \pi$ utilisant les suites moyennes arithmético-géométriques



Cette page provient du site http://www.pi314.net/ .
En fait l'auteur propose aux internautes de refaire des démonstrations ce que je fis et je propose sur cette page mon travail.
Ainsi j'invite l'internaute à suivre les démonstrations et à les refaire :)


Introduction

Le mathématicien Gauss introduisit et étudia les suites moyennes arithmético-géométriques ainsi définies par récurrence :

$\displaystyle \left \lbrace \begin{array}{ll} a_0 = a & \mbox{donné}\\ b_0 = b... ...1} = \frac{ a_n + b_n }{2} & \\ b_{n+1} = \sqrt{a_n b_n} & \end{array}\right. $

Elles jouissent de nombreuses propriétés et en particulier si $ a$ et $ b$ sont positifs, elles convergent toutes les deux vers un même nombre noté $ M(a;b)$ à un vitesse vertigineuse.
Cette convergence est précisément quadratique.
Autrement dit le nombre de chiffres exactes à la limite double à chaque itérations.
Voici un exemple avec $ a=2$ et $ b=1$.

$\displaystyle a_1 = \frac{a_0 + b_0}{2}$ $\displaystyle =$ $\displaystyle {\bf 1},5$  
$\displaystyle b_1 = \sqrt{a_0 b_0}$ $\displaystyle =$ $\displaystyle {\bf 1},4142135623730950488016887242096980785696718753769480731766797379907\ldots$  
$\displaystyle a_2 = \frac{a_1 + b_1}{2}$ $\displaystyle =$ $\displaystyle {\bf 1,45}71067811865475244008443621048490392848359376884740365883398689953\ldots$  
$\displaystyle b_2 = \sqrt{a_1 b_1}$ $\displaystyle =$ $\displaystyle {\bf 1,45}64753151219702608511618824732524371397695735347456310918876492935\ldots$  
$\displaystyle a_3 = \frac{a_2 + b_2}{2}$ $\displaystyle =$ $\displaystyle {\bf 1,4567910}481542588926260031222890507382123027556116098338401137591444\ldots$  
$\displaystyle b_3 = \sqrt{a_2 b_2}$ $\displaystyle =$ $\displaystyle {\bf 1,4567910}139395549461941753969817717747744628562486345380802226293456\ldots$  
$\displaystyle a_4 = \frac{a_3 + b_3}{2}$ $\displaystyle =$ $\displaystyle {\bf 1,456791031046906}9194100892596354112564933828059301221859601681942450\ldots$  
$\displaystyle b_4 = \sqrt{a_3 b_3}$ $\displaystyle =$ $\displaystyle {\bf 1,456791031046906}8189627755068947535591981807707536213657982053831606\ldots$  
$\displaystyle a_5 = \frac{a_4 + b_4}{2}$ $\displaystyle =$ $\displaystyle {\bf 1,45679103104690686918643238326508}24078457817883418717758791867887028\ldots$  
$\displaystyle b_5 = \sqrt{a_4 b_4}$ $\displaystyle =$ $\displaystyle {\bf 1,45679103104690686918643238326508}15421019460981007394057091579778330\ldots$  
$\displaystyle a_6 = \frac{a_5 + b_5}{2}$ $\displaystyle =$ $\displaystyle {\bf 1,456791031046906869186432383265081974973863943221305590794172383267}9\ldots$  
$\displaystyle b_6 = \sqrt{a_5 b_5}$ $\displaystyle =$ $\displaystyle {\bf 1,456791031046906869186432383265081974973863943221305590794172383267}8\ldots$  

Mais Quel lien y a-t-il avec le nombre $ \pi$ ?

En définissant la fonction $ f$ par $ f(x)=M(1;x)$ on montre que cette fonction est continue sur $ [ 0 ; +\infty [$ et dérivable sur $ ] 0 ; +\infty [$ et surtout la relation :

$\displaystyle \pi = 2\sqrt{2} \; \frac{ {f \left( \frac{1}{\sqrt{2}} \right) }^3 } {f' \left( \frac{1}{\sqrt{2}} \right) } $

Elle permit aux mathématiciens Salamin et Brent puis aux frères Borwein de trouver des suites récurrentes convergeant vers $ \pi$ de manière quadratique dans les années 70 et 80, ce qui fut une grande étape dans le calcul de $ \pi$. Ce papier se propose de montrer le cheminement pour arriver à ces algorithmes.

Algorithme de Salamin/Brent (1976)

Théorème 1   Si $ a_0 = 1$, $ b_0 = \frac{1}{\sqrt{2}}$, $ a_{n+1} = \frac{a_n+b_n}{2}$, $ b_{n+1} = \sqrt{a_n b_n}$
alors

$\displaystyle U_n = \frac{4a_n^2}{1-2 \sum\limits_{k=1}^{n}{2^k (a_k^2 - b_k^2 )}} \xrightarrow[n \to \infty]{} \pi $

Algorithmes des frères Borwein (1984)

Théorème 2   Si $ u_0 = \sqrt{2}$, $ v_0 = 0$, $ p_0 = 2 + \sqrt{2}$

$\displaystyle u_{n+1} = \frac{\sqrt{u_n}}{2} + \frac{1}{2\sqrt{u_n}} $

$\displaystyle v_{n+1} = \frac{ \sqrt{u_n} ( 1 + v_n ) }{u_n + v_n} $

alors

$\displaystyle p_{n+1} = p_n u_n \frac{1+u_n}{1+v_n} \xrightarrow[n \to \infty]{} \pi $

Encore les frères Borwein (1987)

Théorème 3   Si $ y_0 = \sqrt{2} $, $ z_1 = \sqrt[4]{2}$ et $ f_0 = 2 + \sqrt{2} $

$\displaystyle y_{n+1} = \frac{1+y_n}{2 \sqrt{y_n}} $

$\displaystyle z_{n+1} = \frac{1+y_n z_n}{(1+z_n) \sqrt{y_n}} $

alors

$\displaystyle f_{n+1} = f_n \frac{1+y_n}{1+z_n} \xrightarrow[n \to \infty]{} \pi $

Les suites moyennes arithmético-géométriques

Définition

Soient deux réels positifs ou nuls $ a$ et $ b$. On définit par récurrence les deux suites $ (a_n)_{n \in {\mathbb{N}}}$ et $ (b_n)_{n \in {\mathbb{N}}}$ par :

$\displaystyle \left \lbrace \begin{array}{l} a_0 = a \\ b_0 = b \\ a_{n+1} = \frac{ a_n + b_n }{2} \\ b_{n+1} = \sqrt{a_n b_n} \end{array}\right. $

Ce sont les suites moyennes arithmético-géométriques ou AGM (pour arithmetic-geometric means).

Propriétés

Lemme 1  

  1. La suite $ (a_n)_{n \in {\mathbb{N}}}$ est décroissante à partir du rang $ 1$.
  2. La suite $ (b_n)_{n \in {\mathbb{N}}}$ est croissante à partir du rang $ 1$.
  3. $ \forall n \geqslant 1 $ on a : $ b_n \leqslant a_n$.
  4. $ (a_n)$ et $ (b_n)$ convergent vers un même réel qu'on notera $ M(a;b)$.

En un mot, les deux suites $ (a_n)$ et $ (b_n)$ sont adjacentes.
Remarque : si $ 0 \leqslant b \leqslant a $ alors les trois premiers points sont vrais au rang 0.

Preuve :
Montrons le (3) :
Comme pour tout réel $ A$ et $ B$ on a $ (A-B)^2 \geqslant 0$ on déduit que $ AB \leqslant \frac{A^2+B^2}{2}$ (I).
Donc $ \sqrt{ab} \leqslant \frac{a+b}{2}$ puis $ b_1 \leqslant a_1$. Et par une récurrence simple, on montre que $ \forall n \geqslant 1 $ on a : $ b_n \leqslant a_n$. Montrons le (1) et (2) :
Du (3) on déduit que $ \forall n \geqslant 1 $ $ a_{n+1} = \frac{a_n+b_n}{2}\leqslant \frac{a_n+a_n}{2} = a_n$ :
c'est-à-dire $ (a_n)$ est décroissante à partir du rang $ 1$.
et
$ \forall n \geqslant 1 $ , $ b_{n+1} \geqslant \sqrt{b_n^2} = b_n$ : c'est-à-dire $ (b_n)$ est croissante à partir du rang $ 1$.
Montrons le (4) :
On a ainsi $ \forall n \geqslant 1 $ : $ 0 \leqslant b_1 \leqslant b_n \leqslant a_n \leqslant a_1$. La suite $ (a_n)$ est décroissante et minorée par $ b_1$ donc d'après une propriété de $ \mathbb{R}$, elle est convergente vers un réel qu'on note $ \alpha$. De même $ (b_n)$ est croissante et majorée par $ a_1$ donc elle est aussi convergente vers un réel qu'on note $ \beta$.
En faisant tendre $ n$ vers l'infini dans l'expression $ a_{n+1} = \frac{a_n+b_n}{2}$, on trouve : $ \alpha = \frac{ \alpha + \beta }{2}$ soit $ \alpha = \beta$.
Donc $ (a_n)$ et $ (b_n)$ ont la même limite qu'on note $ M(a;b)$.
$ \blacksquare$

Proposition 1   Les suites $ (a_n)$ et $ (b_n)$ converge de façon quadratique lorsque $ a$ et $ b$ sont positifs.

Preuve :
Un calcul simple donne :

$\displaystyle a_{n+1}-b_{n+1} = \frac{(a_n-b_n)^2}{2(\sqrt{a_n}+\sqrt{b_n})^2} = \frac{(a_n-b_n)^2}{8a_{n+2}} $

Posons $ e_n = a_n-b_n$ l'erreur relative. On a ainsi :

$\displaystyle e_{n+1} = \frac{ {e_n}^2 }{ 8a_{n+2} } $

Nous savons que $ (e_n)$ tend vers 0 et $ (a_n)$ vers $ M(a;b)$ et donc si $ b$ et $ a$ sont positifs, $ M(a;b)$ le sera aussi et par conséquent :

$\displaystyle \frac{ e_{n+1} }{ {e_n}^2 } \rightarrow \frac{1}{8M(a;b)} $

ie

$\displaystyle \frac{ e_{n+1} }{ {e_n}^2 } = O(1) $

d'où la convergence quadratique.
Numériquement si $ e_n \approx 10^{-p}$ alors $ e_{n+1} \approx \frac{1}{8M(a;b)} 10^{-2p} \approx 10^{-2p} $
Le nombre de chiffres exactes a environ doublé !
$ \blacksquare$

Propriétés de la limite $ M(a;b)$

Proposition 2  
  1. $ M(a;a) = a$.
  2. $ M(a;b) = M(b;a)$.
  3. Quel que soit $ n \geqslant 0$ $ M(a_n;b_n) = M(a;b)$ avec les mêmes notations.
  4. Quel que soit le réel $ k \geqslant 0$ $ M(ka;kb) = k M(a;b)$.
  5. $ M(a;b) = M \left( \frac{a+b}{2};\sqrt{ab} \right) $.
  6. Quel que soit $ a \geqslant b$ $ M \left( a-b ; a+b \right) = M \left( a ; \sqrt{a^2-b^2} \right)$.

Preuve : laissée au lecteur.

Etude de la fonction $ x \mapsto M(1;x) $

Continuité de $ x \mapsto M(1;x) $

Considérons les suites de fonctions définies par récurrence pour $ x \in [ 0 ; +\infty [$ :

$\displaystyle \begin{array}{rcl} a_0(x) & = & 1\\ b_0(x) & = & x \\ a_{n+1}(x... ...rac{ a_n(x) + b_n(x) }{2} \\ b_{n+1}(x) & = & \sqrt{a_n(x) b_n(x)} \end{array}$

Un raisonnement par récurrence nous convint qu'elles sont bien définies sur $ [ 0 ; +\infty [$ et à partir de $ n \geqslant 1$, $ (a_n)$ est une suite de fonctions décroissante $ (b_n)$ est croissante et quel que soit $ x \geqslant 0$, $ a_n(x) \rightarrow M(1;x)$ et $ b_n(x) \rightarrow M(1;x)$ (convergence simple de suites de fonctions).
Notons pour la suite

$\displaystyle f(x) = M(1;x) $

On a :

$\displaystyle b_n(x) \leqslant f(x) \leqslant a_n(x) $

J'énonce une propriété évidente :

Proposition 3   $ a_n$ $ b_n$ sont des fonctions continues sur $ [ 0 ; +\infty [$ et $ {\cal C}^{\infty}$ sur $ ] 0 ; +\infty [$.

Intéressons-nous plutôt à la propriété de cette section :

Proposition 4   $ f$ est continue sur $ [ 0 ; +\infty [$.

Preuve : Travaillons sur l'intervalle compact $ [ 0 ; r ]$ où $ r >0$ est fixé.
Définissons la suite de fonctions $ (e_n)$ par $ e_n = a_n-b_n$. $ e_n$ est continue et la suite $ (e_n)$ est décroissante, convergeant simplement vers 0. D'après le théorème de Dini, on sait donc $ (e_n)$ converge uniformément vers 0 sur le compact $ [ 0 ; r ]$.
Et comme $ 0 \leqslant a_n - f \leqslant e_n$ on peut donc dire que $ (a_n)$ converge uniformément vers $ f$ sur $ [ 0 ; r ]$. $ a_n$ étant continue, $ f$ l'est aussi sur $ [ 0 ; r ]$, donc sur $ [ 0 ; +\infty [$ étant donné que $ r$ était arbitraire.

$ \blacksquare$

Dérivabilité de $ x \mapsto M(1;x) $

Pour étudier la dérivabilite de $ f$, on fait une petit détour par la théorie des fonctions elliptiques.
Définissons la fonction $ I$ sur $ { ] 0 ; +\infty [}^2$ par :

$\displaystyle I(a;b) = \int_{0}^{+\infty}{\frac{dt}{ \sqrt{ (a^2+t^2)(b^2+t^2)} } } $

Proposition 5  

$\displaystyle I(a;b) = I \left( \frac{a+b}{2} ; \sqrt{ab} \right) $

Résultat dû à Gauss.
Preuve : Remarquons que :

$\displaystyle 2 I(a;b) = \int_{-\infty}^{+\infty}{\frac{dt}{ \sqrt{ (a^2+t^2)(b^2+t^2) } } } $

qui découle de la parité de l'opérande.
Notons :

$\displaystyle q(t) = \frac{1}{ \sqrt{ (a^2+t^2)(b^2+t^2) } } $

puis cherchons un changement de variable de la forme $ t=\phi(s)=\alpha s - \frac{\beta}{s}$ avec $ \alpha$ et $ \beta$ positifs. $ \phi$ est bien dans ce cas une bijection de $ ] 0 ; +\infty [$ vers $ \mathbb{R}$.
Posons :

$\displaystyle Q(s) = \frac{ \frac{\alpha + \frac{\beta}{s^2}}{2} }{ \left( {\left( \frac{a+b}{2} \right)}^2 + {\phi(s)}^2 \right) \left(ab+{\phi(s)}^2 \right) } $

On a ainsi :

$\displaystyle I \left( \frac{a+b}{2} ; \sqrt{ab} \right) = \int_{-\infty}^{+\in... ...) }^2+t^2 \right) \left( ab +t^2 \right) } } } = \int_{0}^{+\infty}{ Q(s) ds } $

On aimerez avoir $ q(s)=Q(s)$.
Or $ Q(s) \underset{+\infty}{\sim} \frac{1}{2\alpha s^2} $ et $ q(s) \underset{+\infty}{\sim} \frac{1}{ s^2} $ ce qui conduit à prendre $ \alpha = \frac{1}{2}$.
De même $ Q(0)=\frac{1}{2\beta}$ et $ q(0)=\frac{1}{ab}$ donc nécessairement $ \beta=\frac{ab}{2}$.
Or si on fait le changement de variable $ t=\phi(s)= \frac{s}{2} - \frac{ab}{2s}$ on obtient après calcul ce que l'on recherchait $ q(s)=Q(s)$ de façon surprenante.
$ \blacksquare$

Proposition 6   $ (a,b) \mapsto I(a;b)$ est une fonction $ {\cal C}^1 $ sur $ { ] 0 ; +\infty [}^2$, à valeurs positives.

Preuve : en effet fixons $ r >0$, alors pour $ a \geqslant r$ et $ b \geqslant r$ on a :

$\displaystyle q(t) \leqslant \frac{1}{r^2 + t^2} \in L^1( [ 0 ; +\infty [) $

Donc par le théorème de convergence dominé $ I$ est continue sur $ [r;+\infty[$ donc sur $ ] 0 ; +\infty [$ aussi.
De même

$\displaystyle \frac{\partial q}{ \partial a}(t) = -q(t)\frac{a}{a^2+t^2} $

En se restreignant à la bande $ 0 < r < a < R$ et $ b \geqslant r$ on trouve :

$\displaystyle \mid \frac{\partial q}{ \partial a}(t) \mid \leqslant \frac{R}{(a^2+t^2)^2} \in L^1( [ 0 ; +\infty [) $

donc $ \frac{\partial q}{ \partial a}$ est $ {\cal C}^1 $ sur la bande (par le théorème de convergence dominé) donc sur $ { ] 0 ; +\infty [}^2$. Il en est de même de $ \frac{\partial q}{ \partial b}$.
$ \blacksquare$

Proposition 7  
  1. Pour tout réel $ k >0$, $ I(ka;kb) = \frac{1}{k} I(a;b)$.
  2. $ I(b;a)=I(a;b)$.
  3. $ I(1;1) = \frac{\pi}{2}$.

Preuve : on a : $ I(1;1) = \int_{0}^{+\infty}{\frac{dt}{ 1 + t^2 } } $. Or $ \frac{d}{dx}(\arctan)(x) = \frac{1}{1+x^2}$ et $ \lim_{+\infty}\arctan(x)=\frac{\pi}{2}$ d'où le troisième point.
$ \blacksquare$
Le nombre $ \pi$ commence à apparaître !

Théorème 4   Pour tout réel positif $ a$ et $ b$ , on a :

$\displaystyle I(a;b)M(a;b)=\frac{\pi}{2} $

Preuve : On a vu (proposition précédente) que $ \forall a > 0$ et $ \forall b > 0$ on avait $ I(a;b) = I(\frac{a+b}{2};\sqrt{ab})$
et donc

$\displaystyle I(a_0;b_0)=I(a_1;b_1)=I(a_2;b_2)= \ldots = I(a_n;b_n). $

Comme $ I$ est continue en $ (M(a;b),M(a;b))$, par passage à la limite, on trouve :

$\displaystyle I(a_0;b_0) = I(M(a;b);Ma(a;b)) = {M(a;b)}^{-1} I(1;1) = {M(a;b)}^{-1} \frac{\pi}{2} $

d'où le résultat.
$ \blacksquare$

Définissons la fonction $ g$ sur $ ] 0 ; +\infty [$

$\displaystyle g(x) = I(1;x) $

et rappellons

$\displaystyle f(x) = M(1;x) $

Ainsi

$\displaystyle f(x) g(x) = \frac{\pi}{2} $

Théorème 5   $ f$ est $ {\cal C}^1 $ sur $ ] 0 ; +\infty [$.

Preuve : Cela découle de la relation précédente entre $ f$ et $ g$ et de la propriété 6.
$ \blacksquare$

Etude de $ x \mapsto M(1;x) $ au voisinage de 0 et $ +\infty$

Proposition 8   Quel que soit $ x >0$ :
  1. $ g(\frac{1}{x})=g(x)x$.
  2. $ f(\frac{1}{x})=\frac{1}{x}f(x)$.
  3. $ g(x) \underset{0^+}{\sim} - \ln(x)$.
  4. $ f(x) \underset{0^+}{\sim} \frac{-\pi}{2 \ln(x)} $
  5. $ f(x) \underset{+\infty}{\sim} \frac{\pi x}{2 \ln(x)} $

Preuve : les deux premiers points découlent des propositions 2 et 7.
Passons au troisième et écrivons :

$\displaystyle g(x) = \int_{0}^{+\infty}{\frac{dt}{ \sqrt{ (x^2+t^2)(1+t^2)} } }... ...derbrace{\int_{0}^{a}{}}_{g_1(x)} + \underbrace{\int_{a}^{+\infty}{}}_{g_1(x)} $

où $ a>0$ est fixé.
Pour $ 0 \leqslant t \leqslant a$ on a:

$\displaystyle \frac{1}{\sqrt{1+a^2}} \leqslant \frac{1}{\sqrt{1+t^2}} \leqslant 1 $

puis

$\displaystyle \frac{h(x)}{\sqrt{1+a^2}} \leqslant g_1(x) \leqslant h(x) $

où on a posé

$\displaystyle h(x) = \int_{0}^{a}{\frac{dt}{ \sqrt{ x^2 + t^2 } } } = -\ln(x)+\ln(a+\sqrt{x^2+a^2}) $

On écrira $ g_1(x)= \Theta(a,x) h(x) $ avec $ \frac{1}{\sqrt{1+a^2}} \leqslant \Theta(a,x) \leqslant 1 $.
De plus

$\displaystyle 0 < \int_{a}^{+\infty}{ \frac{dt}{ \sqrt{ (x^2+t^2)(1+t^2)} } } \... ...nt_{a}^{+\infty}{ \frac{dt}{ t \sqrt{ (1+t^2)} } } = B_a \in {\mathbb{R}}_+ $

i.e. $ g_2(x)$ est bornée par une constante indépendante de $ x >0$
et ainsi

$\displaystyle \frac{g(x)}{-\ln(x)} = \Theta(a;x) + \frac{\Theta(a;x)\ln(a+\sqrt{x^2+a^2})+g_2(x)}{-\ln(x)} $

et par passage à la limite sup/limite inf le deuxième terme tend vers 0. On trouve donc

$\displaystyle \frac{1}{\sqrt{1+a^2}} \leqslant \underset{x \rightarrow 0^+}{\li... ...eqslant \underset{x \rightarrow 0^+}{\limsup} \frac{g(x)}{-\ln(x)} \leqslant 1 $

Ceci étant vrai quel que soit $ a>0$ donc en faisant tendre $ a$ vers 0, on trouve bien :

$\displaystyle \underset{x \rightarrow 0^+}{\lim} \frac{g(x)}{-\ln(x)} = 1 $

$\displaystyle g(x) \underset{0^+}{\sim} - \ln(x). $

Passons au point suivant.
Pour $ x$ grand

$\displaystyle g(x) = \frac{1}{x}g \left( \frac{1}{x} \right) \underset{+\infty}{\sim} \frac{1}{x} -\ln \left( \frac{1}{x} \right) = \frac{\ln(x)}{x} $

i.e.

$\displaystyle g(x) \underset{+\infty}{\sim} \frac{\ln(x)}{x} $

Ensuite sachant que $ f(x) g(x) = \frac{\pi}{2}$, on trouve les deux derniers points.

$ \blacksquare$

Une équation différentielle vérifiée par $ x \mapsto M(1;x) $ sur $ ] 0 ; 1 [$

Pour tout la suite de l'exposé, on se resteindra à l'intervalle $ ] 0 ; 1 [$.
Définissons les suites de fonctions $ {(c_n)}_{n \geqslant 0}$ et $ {(d_n)}_{n \geqslant 0}$ par :

$\displaystyle c_n$ $\displaystyle =$ $\displaystyle \sqrt{a_n^2 - b_n^2}$  
$\displaystyle d_n$ $\displaystyle =$ $\displaystyle \frac{1}{2^n}\ln \left( \frac{a_n}{c_ n} \right)$  

Proposition 9   Quel que soit $ n \geqslant 0$ :
  1. $ M(a_n;c_n) = 2 M( a_{n+1} ; c_{n+1} )$ .
  2. $ M(a_0;c_0) = 2^n M(a_n;c_n)$.

Preuve : On remarque que :

$\displaystyle c_{n+1} = \sqrt{a_{n+1}^2 - b_{n+1}^2} = \sqrt{ {\left( \frac{a_n+b_n}{2} \right)}^2 - a_n b_n } = \frac{a_n - b_n}{2} $

D'après la proposition 2,

$\displaystyle M(a_n - b_n ; a_n + b_n ) = M( a_n ; \sqrt{a_n^2 - b_n^2} ) $

soit

$\displaystyle M(2c_{n+1} ; 2 a_{n+1} ) = M(a_n;c_n ) $

d'où

$\displaystyle 2 M( c_{n+1} ; a_{n+1} ) = M(a_n;c_n ) $

et par récurrence on trouve le second point.
$ \blacksquare$

Proposition 10   Quel que soit $ x \in ]0;1[$, on a

$\displaystyle d_n(x) \xrightarrow[n \rightarrow +\infty]{} \frac{\pi}{2}\frac{f(x)}{f(\sqrt{1-x^2})}$    (convergence simple)$\displaystyle $

Preuve : On écrit que

$\displaystyle f(\sqrt{1-x^2}) = M(1;\sqrt{1-x^2})=M(a_0;c_0)=2^n M(a_n;c_n)= 2^n a_n M(1;\frac{c_n}{a_n}) = 2^n a_n f(\frac{c_n}{a_n}) $

$ a_n(x)$ tend vers $ f(x) >0$ ( $ x \in ]0;1[$) et $ \frac{c_n(x)}{a_n(x)}$ tend vers zéro
donc d'après le comportement de $ f$ au voisinage de zéro (proposition 8) :

$\displaystyle f \left( \frac{c_n(x)}{a_n(x)} \right) \underset{+\infty}{\sim} -\frac{\pi}{2 \ln \left( \frac{c_n(x)}{a_n(x)} \right)}$

Et on déduit le résultat.
$ \blacksquare$
Voici un résultat important sur la suite $ (d_n)$ :

Proposition 11  

$\displaystyle \frac{d_{n+1}'}{d_n'} = \frac{a_n}{b_n} = \frac{{b_{n+1}}^2}{{b_n}^2} $

soit

$\displaystyle \frac{d_{n+1}'}{{b_{n+1}}^2} = \frac{d_n'}{{b_n}^2} $

Ce qui entraîne

Corollaire 1  
$\displaystyle \frac{d_n'(x)}{{b_n}^2(x)}$ $\displaystyle =$ $\displaystyle \frac{d_0'(x)}{{b_0}^2(x)} = \frac{1}{x(1-x^2)}$  
$\displaystyle d_n'(x)$ $\displaystyle =$ $\displaystyle \frac{{b_n(x)}^2}{x(1-x^2)}$    sur$\displaystyle \; ]0;1[$  

Ainsi on peut exprimer explicitement $ \frac{d_n'(x)}{{b_n(x)}^2}$ e fonction de $ x$ et donc $ d_n'(x)$ en fonction de $ x$ et $ b_n(x)$.

Preuve de la propriété : on calcule $ d_n'$ :

$\displaystyle d_n'$ $\displaystyle =$ $\displaystyle \frac{1}{2^n} {\left( \frac{a_n}{c_n} \right)}^{-1} \frac{a_n' c_n - a_n c_n' }{{c_n}^2}$  
  $\displaystyle =$ $\displaystyle \frac{1}{2^n} \left( \frac{a_n'}{a_n} - \frac{c_n'}{c_n} \right)$  
  $\displaystyle =$ $\displaystyle \frac{1}{2^n} \frac{a_n b_n b_n' - {b_n}^2 a_n' }{ a_n ( {a_n}^2 - {b_n}^2 ) }$  

on calcule de même $ d_{n+1}'$ en remarquant que :

$\displaystyle c_{n+1} = \frac{a_n-b_n}{2} $

et donc

$\displaystyle c_{n+1}' = \frac{a_n'-b_n'}{2} $

Ainsi
$\displaystyle d_{n+1}'$ $\displaystyle =$ $\displaystyle \frac{1}{2^{n+1}} \left( \frac{a_{n+1}'}{a_{n+1}} - \frac{c_{n+1}'}{c_{n+1}} \right)$  
  $\displaystyle =$ $\displaystyle \frac{1}{2^{n+1}} \left( \frac{a_n'+b_n'}{a_n+b_n} - \frac{a_n'-b_n'}{a_n-b_n} \right)$  
  $\displaystyle =$ $\displaystyle \frac{1}{2^n} \frac{a_n b_n' - b_n a_n' }{ {a_n}^2 - {b_n}^2 }$  

Donc on déduit

$\displaystyle \frac{d_{n+1}'}{d_n'} = \frac{a_n}{b_n} = \frac{a_n b_n}{{b_n}^2} = \frac{{b_{n+1}}^2}{{b_n}^2} $

$ \blacksquare$

Proposition 12   $ d_n'$ converge uniformément sur tout compact de $ ]0;1[$ vers $ x \mapsto \frac{f^2(x)}{x(1-x^2)}$

Preuve : on se rappelle que $ 0 < b_n(x) \leqslant f(x)$ et considérons un compact $ K$ de $ ]0;1[$. Pour tout $ x$ de $ K$, on a :
$\displaystyle \mid d_n'(x) - \frac{f^2(x)}{x(1-x^2)} \mid$ $\displaystyle =$ $\displaystyle \mid \frac{ {b_n(x)}^2 - f^2(x)}{x(1-x^2)} \mid$  
  $\displaystyle =$ $\displaystyle \mid b_n(x) - f(x) \mid \times \mid \frac{b_n(x) + f(x)}{ x(1-x^2)} \mid$  
  $\displaystyle \leqslant$ $\displaystyle \mid f(x) - b_n(x) \mid \times \sup_{y \in K} \left( \frac{2f(y)}{y(1-y^2)} \right)$  

$ f$ étant continue sur $ [ 0 ; +\infty [$, $ \sup_{y \in K} \left( \frac{2f(y)}{y(1-y^2)} \right)$ est un nombre positif et puisque $ b_n$ converge uniformément sur tout compact de $ ]0;1[$ vers f, on déduit la propriété.
$ \blacksquare$

Résumons :

  • $ d_n$ converge simplment vers $ x \overset{l}{\mapsto} \frac{\pi}{2}\frac{f(x)}{f(\sqrt{1-x^2})}$
  • $ d_n'$ converge uniformément vers $ \overset{h}{\mapsto} \frac{f^2(x)}{x(1-x^2)}$ sur tout compact de $ ]0;1[$.
Donc d'après le théorème sur la limite de fonctions dérivables $ l$ est une fonction dérivable sur $ ]0;1[$ et $ l'=h$.
En dérivant $ l$ on trouve que $ f$ vérifie l'équation sur $ ]0;1[$ :


$\displaystyle \frac{\pi}{2} \left( x(1-x^2)f'(x) f(\sqrt{1-x^2})+x^2\sqrt{1-x^2}f(x)f(\sqrt{1-x^2}) \right) = f^2(x)f^2(\sqrt{1-x^2}) $





En évaluant l'équation en $ x= \frac{1}{\sqrt{2}}$, on obtient l'égalité reliant $ f$ et $ \pi$ :

$\displaystyle \pi = 2\sqrt{2} \; \frac{ {f \left( \frac{1}{\sqrt{2}} \right) }^3 } {f' \left( \frac{1}{\sqrt{2}} \right) } $

Au début de ce papier on a remarqué qu'on peut calculer avec grande précision et rapidement $ f \left( \frac{1}{\sqrt{2}} \right)$ et on sait calculer aussi rapidement $ \sqrt{2}$ (voir la méthode de Newton).
Maintenant le problème qui se pose est le suivant : peut-on approcher $ f' \left( \frac{1}{\sqrt{2}} \right)$ par une suite ayant une convergence quadratique comme les deux nombres précédents ?

Par chance, les suites dérivées $ a_n'$ et $ b_n'$ ont cette propriété.

Justification des algorithmes à convergence quadratique

Etude des suites $ (a_n')$ et $ (b_n')$ sur $ ]0;1[$

Rappelons les définitions :

$\displaystyle \left \lbrace \begin{array}{rcl} a_0(x) & = & 1\\ b_0(x) & = & x... ...(x) + b_n(x) }{2} \\ b_{n+1}(x) & = & \sqrt{a_n(x) b_n(x)} \end{array}\right. $

et donc

$\displaystyle \left \lbrace \begin{array}{rcl} a_0'(x) & = & 0\\ b_0'(x) & = &... ...& \frac{a_n'(x)b_n(x)+a_n(x)b_n'(x)}{2\sqrt{a_n(x) b_n(x)}} \end{array}\right. $

Définissons pour $ n \geqslant 0$, les deux suites de fonctions sur $ ]0;1[$:

$\displaystyle \begin{array}{rcl} y_n & = & \frac{a_n}{b_n} \\ z_n & = & \frac{b_n'}{a_n'} \end{array}$

qui nous servirons pour l'étude des fonctions $ a_n'$ et $ b_n'$ et pour exprimer les algorithmes.

Proposition 13   Pour tout entier $ n \geqslant 1$,
  1. $ y_{n+1} = \frac{1+y_n}{2\sqrt{y_n}}$,
  2. $ z_{n+1} = \frac{1+y_n z_n}{(1+z_n)\sqrt{y_n}}$,
  3. $ y_n \geqslant 1$,
  4. $ z_n \geqslant 1$,
  5. $ z_n \geqslant y_n$,
  6. $ (z_n)$ est une suite décroissante.
  7. $ (y_n)$ et $ (z_n)$ convergent uniformément sur tout compact de $ ]0;1[$ vers $ 1$.

Preuve : les deux premiers points résultent des relations de récurrence précédentes entre $ a_{n+1}'$, $ b_{n+1}'$ et $ a_n'$, $ b_n'$.

nous savons déjà que $ a_n \geqslant b_n > 0$ d'où $ y_n \geqslant 1$.
Remarquons ensuite que $ z_1(x)=\frac{1}{\sqrt{x}}$ donc $ z_1 \geqslant 1$ sur $ ]0;1[$.
Définissons la fonction $ \phi_y$ par

$\displaystyle \phi_y(x) = \frac{1+yx}{(1+x)\sqrt{y}} $

alors

$\displaystyle \phi_y'(x) = \frac{1}{\sqrt{y}} \frac{y-1}{(1+x)^2} $

donc si $ y \geqslant 1$, alors $ \phi_y' \geqslant 0$ sur $ [ 0 ; +\infty [$ et comme $ \phi_y(1) = \frac{1+y}{2\sqrt{y}} \geqslant 1$, on déduit que si $ z_n \geqslant 1$ alors $ z_{n+1} = \phi_{y_n}(z_n) \geqslant \phi_{y_n}(1) \geqslant 1 $ c'est-à-dire

$\displaystyle z_{n+1} \geqslant y_{n+1} \geqslant 1 . $

Or $ z_1(x) = \frac{1}{\sqrt{x}} \geqslant 1 $ et $ y_1(x) = \frac{1}{x} \geqslant 1$, donc on a bien $ z_{n} \geqslant y_{n}$ à partir de $ n=1$ (par récurrence).

La monotonie de $ (z_n)$ se déduit facilement :

$\displaystyle z_{n+1} = \frac{1+y_n z_n}{(1+z_n)\sqrt{y_n}} \leqslant \frac{z_n+y_n z_n}{(1+z_n)\sqrt{y_n}} $

donc

$\displaystyle \frac{z_{n+1}}{z_n} \leqslant \frac{1+y_n }{(1+z_n)\sqrt{y_n}} \leqslant \frac{1}{\sqrt{y_n}} \leqslant 1 $

Etudions la convergence des deux suites.
Nous avons

$\displaystyle y_n - 1 = \frac{a_n - b_n}{b_n} \leqslant \frac{a_n - b_n}{b_0} $

du fait de la croissance de la suite $ (b_n)$, d'où pour tout $ x$ d'un compact $ K$ de $ ]0;1[$ :

$\displaystyle y_n(x) - 1 \leqslant \sup_{y \in K}\left(\frac{1}{y}\right) (a_n(x)-b_n(x)) $

Et comme $ (a_n-b_n)$ converge uniformément vers 0 sur tout compact de $ [ 0 ; +\infty [$, on déduit que $ (y_n)$ tend vers $ 1$ uniformément sur tout compact de $ ]0;1[$.

Pour tout réel $ x$ de l'intervalle $ ]0;1[$, $ (z_n(x))$ est une suite décroissante minorée par $ 1$ donc elle converge et comme $ y_n(x) \xrightarrow[n \to \infty]{} 1$, on déduit de l'expression de récurrence $ z_{n+1} = \frac{1+y_n z_n}{(1+z_n)\sqrt{y_n}}$ que $ z_n(x)$ tend vers $ 1$.
Ensuite les fonctions $ z_n$ étant continues comme $ x \mapsto 1$ et la suite $ (z_n)$ étant décroissante, on conclut grâce au théorème de Dini que $ (z_n)$ converge en fait uniformément sur tout compact de $ ]0;1[$ vers 1.

$ \blacksquare$

Proposition 14   les suites $ (a_n')$ et $ (b_n')$ converge uniformément sur tout compact de $ ]0;1[$ vers $ f'$ de façon quadratique.

Preuve : commençons par préciser quelques notations. On note :
$ {\Vert (x,y) \Vert}_{\infty} = \max(\vert x \vert,\vert y\vert)$
et pour une fonction sur un compact $ K$ de $ ]0;1[$,
$ {\vert f \vert}_{K,\infty} = \sup_{y \in K} \vert f(y) \vert $.

Définissons $ u_n = {\Vert ({\vert z_n - 1 \vert}_{K,\infty},{\vert y_n - 1 \vert}_{K,\infty}) \Vert}_{\infty}$

Commençons par prouver que $ (a_n')$ est bornée pour la norme $ {\vert \;\;\;\; \vert}_{K,\infty}$.
Puisque $ a_{n+1}' = \frac{ a_n' + b_n' }{2}$, on a $ a_{n+1}' = \frac{1+z_n}{2} a_n'$.
Etudions la suite $ (z_n)$.
On peut écrire

$\displaystyle z_{n+1} = G(y_n,z_n) $

$\displaystyle y_{n+1} = H(y_n) $

avec

$\displaystyle G(y,z) = \frac{1+yz}{(1+z)\sqrt{y}}. $

$\displaystyle H(y) = \frac{1+y}{2\sqrt{y}} $

Puis prenons le développement limité de $ G$ et $ H$ au voisinage de $ (1;1)$ :

$\displaystyle G(1+h,1+k) = 1 + \frac{h^2}{8}+\frac{hk}{4}+ o( {\Vert (h;k) \Vert}_\infty^2 ) $

$\displaystyle H(1+h) = 1 + \frac{h^2}{8} + o( h^2 ) $

Donc on peut trouver un réel $ r$, $ 1>r>0$ tel que $ \vert h \vert \leqslant r$ et $ \vert k\vert \leqslant r$ entraîne

$\displaystyle \vert G(1+h,1+k) - 1 \vert \leqslant {\Vert (h,k) \Vert}_{\infty}^2 $

$\displaystyle \vert H(1+h) - 1 \vert \leqslant h^2 \leqslant {\Vert (h,k) \Vert}_{\infty}^2 $

Puisque $ (y_n)$ et $ (z_n)$ converge uniformément sur tout compact de $ ]0;1[$ vers $ 1$, pour tout $ K$ compact de $ ]0;1[$ il existe un entier $ N_{K,r}$ positif, tel que pour tout $ n \geqslant N_{K,r}$, on ait $ {\vert y_n - 1 \vert}_{\infty,K} \leqslant r $ et $ {\vert z_n - 1 \vert}_{\infty,K} \leqslant r $ donc pour tout $ x$ de $ K$ :

$\displaystyle \vert z_{n+1}(x) - 1 \vert \leqslant {\Vert (z_n(x) - 1,y_n(x) - ... ...y_n - 1 \vert}_{\infty,K};{\vert z_n - 1 \vert}_{\infty,K}) \Vert }_\infty }^2 $

et ainsi

$\displaystyle {\Vert z_{n+1} - 1 \Vert}_{\infty,K} \leqslant { {\Vert ({\Vert y_n - 1 \Vert}_{\infty,K};{\Vert z_n - 1 \Vert}_{\infty,K}) \Vert }_\infty }^2 $

et en procédent de même pour $ y_n$, on a :

$\displaystyle {\vert y_{n+1} - 1 \vert}_{\infty,K} \leqslant { \Vert {({\vert y_n - 1 \vert}_{\infty,K};{\vert z_n - 1 \vert}_{\infty,K}) \Vert }_\infty }^2 $

i.e. pour $ n \geqslant N_{K,r}$

$\displaystyle u_{n+1} \leqslant u_n^2 $

d'où par récurrence

$\displaystyle u_n \leqslant c r^{2^{n}} $

avec $ c = r^{2^{-N_{K,r}}}$

Comme

$\displaystyle { \vert a_{n+1}' \vert }_{K,\infty} \leqslant \frac{1+ { \vert z_n \vert }_{K,\infty}}{2} { \vert a_n' \vert }_{K,\infty} $

on a pour $ n \geqslant N_{K,r}$

$\displaystyle { \vert a_{n+1}' \vert }_{K,\infty} \leqslant (1 + c_2 r^{2^n}) { \vert a_{n}' \vert }_{K,\infty} $

et ainsi

$\displaystyle { \vert a_n' \vert }_{K,\infty} \leqslant { \vert a_{N_{K,r}}' \v... ...' \vert }_{K,\infty} \prod_{k=1}^{\infty} (1 + c_2 r^{2^k}) \in {\mathbb{R}}_+ $

La suite $ (a_n')$ est donc bien bornée et puis elle vérifie le critère de Cauchy uniforme sur $ K$ car $ a_{n+1}'-a_n' = \frac{b_n'-a_n'}{2} = \frac{z_n-1}{2} a_n' $ et donc si $ n \geqslant N_{K,r}$

$\displaystyle {\vert a_{n+1}'-a_n' \vert}_{K,\infty} \leqslant c_3 r^{2^{n}} $

car $ (a_n')$ est bornée. En conséquence pour $ m \geqslant n \geqslant N_{K,r}$

$\displaystyle {\vert a_{m}'-a_n' \vert}_{K,\infty} \leqslant \sum_{k=n}^{m-1}{\... ...{m-1} r^{2^{k}} \leqslant c_3 \sum_{k=n}^{\infty} r^{2^{k}} \in {\mathbb{R}}_+ $

et puisque la série $ \sum_{k=0}^{\infty} r^{2^{k}}$ converge, quel que soit $ \epsilon >0$

$\displaystyle {\vert a_{m}'-a_n' \vert}_{K,\infty} \leqslant \epsilon $

pour $ n$ assez grand. $ (a_n')$ est donc une suite qui converge uniformément sur $ K$ vers une fonction continue $ J$ et comme $ (a_n)$ converge simplement vers $ f$ sur $ K$, on peut donc affirmer que $ (a_n')$ converge en fait vers $ f'$ sur $ K$.
Et de la relation $ a_{n+1}' = \frac{ a_n' + b_n' }{2}$, on tire que $ (b_n')$ converge aussi uniformément sur $ K$ vers $ f'$.

Enfin puisque

$\displaystyle {\vert a_{m}'-a_n' \vert}_{K,\infty} \leqslant c_3 \sum_{k=n}^{\infty} r^{2^{k}} $

on tire par passage à la limite $ m \to +\infty$ :

$\displaystyle {\vert f'-a_n' \vert}_{K,\infty} \leqslant c_3 \sum_{k=n}^{\infty... ...}} \leqslant r^{2^{n}} \sum_{k=0}^{\infty} r^k \leqslant \frac{r^{2^{n}}}{1-r} $

d'où la convergence quadratique de $ a_n'$ vers $ f'$ et à fortiori de $ b_n'$.

$ \blacksquare$

Retour sur le dernier algorithme des frères Borwein

Explication détaillée

Rapellons les suites :
Si $ y_0 = \sqrt{2} $, $ z_1 = \sqrt[4]{2}$ et $ f_0 = 2 + \sqrt{2} $

$\displaystyle y_{n+1} = \frac{1+y_n}{2 \sqrt{y_n}} $

$\displaystyle z_{n+1} = \frac{1+y_n z_n}{(1+z_n) \sqrt{y_n}} $

alors

$\displaystyle f_{n+1} = f_{n} \frac{1+y_n}{1+z_n} \xrightarrow[n \to \infty]{} \pi $

Preuve : Les suites numériques $ (y_n)$ et $ (z_n)$ sont en fait les suites $ (y_n(\frac{1}{\sqrt{2}}))$ et $ (z_n(\frac{1}{\sqrt{2}}))$ de la section précédente. Définissons la suite de fonctions $ (w_n)$ :

$\displaystyle w_n = \frac{a_n b_n^2}{a_n'} $

Nous savons d'après l'étude précédente que

$\displaystyle w_n(\frac{1}{\sqrt{2}}) \xrightarrow[n \to \infty]{} \frac{\pi}{2\sqrt{2}} $

D'après la formule

$\displaystyle \pi = 2\sqrt{2} \; \frac{ {f \left( \frac{1}{\sqrt{2}} \right) }^3 } {f' \left( \frac{1}{\sqrt{2}} \right) } $

Or un calcul montre que

$\displaystyle \frac{w_{n+1}}{w_n} = \frac{1+y_n}{1+z_n} $

et

$\displaystyle w_1(\frac{1}{\sqrt{2}}) = \frac{1}{2}+ \frac{1}{\sqrt{2}} $

donc on peut calculer par récurrence la suite numérique $ w_n(\frac{1}{\sqrt{2}})$
et en définissant $ f_n= 2\sqrt{2} w_n$, on retrouve la suite du théorème.
$ \blacksquare$

Premier algorithme

Explication du premier algorithme des frères Borwein

Rapellons les suites :
si $ u_0 = \sqrt{2}$, $ v_0 = 0$, $ p_0 = 2 + \sqrt{2}$

$\displaystyle u_{n+1} = \frac{\sqrt{u_n}}{2} + \frac{1}{2\sqrt{u_n}} $

$\displaystyle v_{n+1} = \frac{ \sqrt{u_n} ( 1 + v_n ) }{u_n + v_n} $

alors

$\displaystyle p_{n+1} = p_n u_n \frac{1+u_n}{1+v_n} \xrightarrow[n \to \infty]{} \pi $

Preuve : C'est en fait l'algorithme précédent en posant $ v_n = \frac{1}{z_n}$ et $ u_n = y_n$ et on vérifie que si on peut pose $ v_0 = 0$, on retrouvera $ v_1 = \frac{1}{\sqrt[4]{2}}$.
$ \blacksquare$

Retour sur le dernier algorithme Brent et Salamin

Explication détaillée

Ils ont découvert cet algorithme en même temps et indépendamment.
Rapellons les suites :
si $ a_0 = 1$, $ b_0 = \frac{1}{\sqrt{2}}$, $ a_{n+1} = \frac{a_n+b_n}{2}$, $ b_{n+1} = \sqrt{a_n b_n}$
alors

$\displaystyle U_n = \frac{4a_n^2}{1-2 \sum\limits_{k=1}^{n}{2^k (a_k^2 - b_k^2 )}} \xrightarrow[n \to \infty]{} \pi $

Preuve :
comme vous l'avez remarqué, les suites numériques $ (a_n)$ et $ (b_n)$ sont en fait les suites $ (a_n(\frac{1}{\sqrt{2}}))$ et $ (b_n(\frac{1}{\sqrt{2}}))$ des sections précédentes. Il nous reste à voir que :

$\displaystyle U_n = 2\sqrt{2} \frac{ a_n^2 \left(\frac{1}{\sqrt{2}}\right) b_{n+1}\left(\frac{1}{\sqrt{2}}\right)} {b_{n+1}'\left(\frac{1}{\sqrt{2}}\right)} $

puis on en conclura

$\displaystyle U_n \xrightarrow[n \to \infty]{} \pi $

D'après les formules de récurrence de $ a_n$, $ b_n$, $ a_n'$ et $ b_n'$, on a :

$\displaystyle \frac{b_{n+1}'}{b_{n+1}}= \frac{1}{2}\left( \frac{a_n'}{a_n} + \frac{b_n'}{b_n} \right) $

donc

$\displaystyle \frac{b_n'}{b_n} - \frac{b_{n+1}'}{b_{n+1}} = \frac{1}{2}\left( \frac{b_n'}{b_n} - \frac{a_n'}{a_n} \right) $

Et nous avons vu (proposition 11) que

$\displaystyle d_n'(x) = \frac{b_n^2(x)}{x(1-x^2)} $

ainsi que

$\displaystyle d_n'(x) = \frac{1}{2^n} \frac{ b_n' - b_n \frac{a_n'}{a_n} }{ {a_n}^2 - {b_n}^2 } $

donc on tire

$\displaystyle \frac{b_n'}{b_n} - \frac{b_{n+1}'}{b_{n+1}} = \frac{2^n ({a_n}^2 - {b_n}^2)}{2x(1-x^2)} $

et par récurrence

$\displaystyle \frac{b_{n+1}'}{b_{n+1}} = \frac{1}{2x} - \frac{1}{2x(1-x^2)} \sum_{k=1}^n 2^k (a_k^2-b_k^2). $

Pour $ x= \frac{1}{\sqrt{2}}$ on trouve

$\displaystyle \sqrt{2} \frac{b_{n+1}'\left(\frac{1}{\sqrt{2}}\right)}{b_{n+1}\left(\frac{1}{\sqrt{2}}\right)} = 1 - 2 \sum_{k=1}^n 2^k (a_k^2-b_k^2) $

Par conséquent

$\displaystyle U_n = \frac{4a_n^2\left(\frac{1}{\sqrt{2}}\right)}{1-2 \sum\limit... ...t)} {b_{n+1}'\left(\frac{1}{\sqrt{2}}\right)} \xrightarrow[n \to \infty]{} \pi $

$ \blacksquare$

Premier algorithme

On écrit :

$\displaystyle U_n = \frac{4a_n^2}{1-2 \sum\limits_{k=1}^{n}{2^k (a_k^2 - b_k^2 )}} = \frac{a_n^2}{\frac{1}{4} - \sum\limits_{k=1}^{n}{2^{k-1} (a_k^2 - b_k^2 )}} $

puis on considère les variables :
$\displaystyle A_n$ $\displaystyle =$ $\displaystyle a_n ^2$  
$\displaystyle B_n$ $\displaystyle =$ $\displaystyle b_n ^2$  
$\displaystyle S_n$ $\displaystyle =$ $\displaystyle \frac{1}{4} - \sum\limits_{k=1}^{n}{2^{k-1} (a_k^2 - b_k^2 )}$  

On obtient :

$\displaystyle A_0 = 1 $

$\displaystyle B_0 = \frac{1}{2} $

$\displaystyle S_0 = \frac{1}{4} $

et les formules :
$\displaystyle B_{n+1}$ $\displaystyle =$ $\displaystyle \sqrt{A_n B_n}$  
$\displaystyle A_{n+1}$ $\displaystyle =$ $\displaystyle \frac{A_n+B_n}{4} + \frac{B_{n+1}}{2}$  
$\displaystyle S_{n+1}$ $\displaystyle =$ $\displaystyle S_n - 2^n (A_{n+1} - B_{n+1} )$  

ce qui donne l'algorithme :

$ A \gets 1$  
$ B \gets 1 \div 2$  
$ S \gets 1 \div 4$  
   
répéter pour $ n$ variant de 0 à $ N$  
$ t \gets AB$  
$ t \gets \sqrt{t}$  
$ A \gets A+B$  
$ A \gets \div 4$  
$ A \gets A+ t$  
$ t \gets A-B$  
$ t \gets 2^k t$  
$ S \gets S - t$  
fin de la boucle  
   
$ t \gets A \div S$  
afficher $ t \approx \pi$  

Deuxime algorithme

Cette amélioration est dûe à Arnold Schönhage en 1994.
Elle évite une multiplication (ce qui demande beaucoup de calcul) pour un carré (ce qui en demande moins). Puisque

$\displaystyle A_{n+1} = \frac{A_n+B_n}{4} + \frac{B_{n+1}}{2} $

on déduit que

$\displaystyle B_{n+1} = 2 A_{n+1} - \frac{A_n + B_n}{2} $

et on utilise les suites $ a_n$, $ A_n$, $ B_n$ et $ s_n=2S_n$.
Voici l'algorithme :

$ a \gets 1$  
$ A \gets 1$  
$ B \gets 1 \div 2$  
$ s \gets 1 \div 2$  
   
répéter pour $ n$ variant de 0 à $ N-1$  
$ t \gets A+B$  
$ t \gets t \div 4$  
$ B \gets \sqrt{B}$  
$ a \gets a+B$  
$ a \gets a \div 2$  
$ A \gets a^2$  
$ B \gets A-t$  
$ B \gets 2 \times B$  
$ t \gets A-B$  
$ t \gets 2^{k+1} t$  
$ s \gets s - t$  
fin de la boucle  
   
$ A \gets A+B$  
$ t \gets A \div s$  
afficher $ t \approx \pi$  

About this document ...

This document was generated using the LaTeX2HTML translator Version 2002-2-1 (1.70)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -split 1 pi_AGM.tex

The translation was initiated by raphi on 2004-05-30


raphi 2004-05-30