\documentclass[11pt,a4paper]{article}


%***mise en page***
\setlength{\textwidth}{17cm} \setlength{\textheight}{25cm}
\setlength{\oddsidemargin}{-5.5mm}
\setlength{\evensidemargin}{0pt} \setlength{\marginparwidth}{1cm}
\setlength{\headheight}{13pt} \setlength{\topmargin}{-30pt}
\setlength{\footskip}{26pt} \setlength{\headsep}{13pt}

%***package***
\usepackage{amsmath,amscd,amssymb}
\pagestyle{empty}
\usepackage[T1]{fontenc}
\usepackage{graphics}
\usepackage{epic}

%*** Environnement ***
\newtheorem{myth}{Théorème}
\newtheorem{myprop}{Proposition}
\newtheorem{mylem}{Lemme}
\newtheorem{mycoro}{Corollaire}

%*** Macros ***
\newcommand{\ineg}{\leqslant}
\newcommand{\sueg}{\geqslant}
\newcommand{\cqfd}{\begin{flushright} $\blacksquare$ \end{flushright} }
\newcommand{\Rp}{ [ \, 0 \, ; \, +\infty \, [}
\newcommand{\Rpe}{ ] \, 0 \, ; \, +\infty \, [}
\newcommand{\R}{ \mathbb{R}  }

\begin{document}
\begin{center}
\huge Algorithmes à convergence très rapide vers $\pi$ utilisant les
	suites moyennes arithmético-géométriques
\end{center}

\section{Introduction}

	Le mathématicien Gauss introduisit et étudia les suites moyennes
	arithmético-géométriques ainsi définies par récurrence~:
$$
  \left \lbrace
  	\begin{array}{ll}
		a_0 = a & \mbox{donné}\\
		b_0 = b & \mbox{donné}\\
		a_{n+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 {\bf chiffres exactes} à la limite {\bf double} à {\bf chaque itérations}.\\
Voici un exemple avec $a=2$ et $b=1$.\\
{\small
\begin{eqnarray*}
 a_1 = \frac{a_0 + b_0}{2} & = & {\bf 1},5 \\
 b_1 = \sqrt{a_0 \, b_0}   & = & {\bf 1},4142135623730950488016887242096980785696718753769480731766797379907\ldots \\
 a_2 = \frac{a_1 + b_1}{2} & = & {\bf 1,45}71067811865475244008443621048490392848359376884740365883398689953\ldots\\
 b_2 = \sqrt{a_1 \, b_1}   & = & {\bf 1,45}64753151219702608511618824732524371397695735347456310918876492935\ldots\\
 a_3 = \frac{a_2 + b_2}{2} & = & {\bf 1,4567910}481542588926260031222890507382123027556116098338401137591444\ldots\\
 b_3 = \sqrt{a_2 \, b_2}   & = & {\bf 1,4567910}139395549461941753969817717747744628562486345380802226293456\ldots\\
 a_4 = \frac{a_3 + b_3}{2} & = & {\bf 1,456791031046906}9194100892596354112564933828059301221859601681942450\ldots\\
 b_4 = \sqrt{a_3 \, b_3}   & = & {\bf 1,456791031046906}8189627755068947535591981807707536213657982053831606\ldots\\
 a_5 = \frac{a_4 + b_4}{2} & = & {\bf 1,45679103104690686918643238326508}24078457817883418717758791867887028\ldots\\
 b_5 = \sqrt{a_4 \,b_4}    & = & {\bf 1,45679103104690686918643238326508}15421019460981007394057091579778330\ldots\\
 a_6 = \frac{a_5 + b_5}{2} & = & {\bf 1,456791031046906869186432383265081974973863943221305590794172383267}9\ldots\\
 b_6 = \sqrt{a_5 \,b_5}    & = & {\bf 1,456791031046906869186432383265081974973863943221305590794172383267}8\ldots
\end{eqnarray*}
}
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 :

$$
	\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.

\subsection{Algorithme de Salamin/Brent (1976) }

\begin{myth}
 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
 $$
  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
 $$
\end{myth}


\subsection{Algorithmes des frères Borwein (1984)}

\begin{myth}
Si $u_0 = \sqrt{2}$, $v_0 = 0$, $p_0 = 2 + \sqrt{2}$
$$
  u_{n+1} = \frac{\sqrt{u_n}}{2} + \frac{1}{2\sqrt{u_n}}
$$
$$
  v_{n+1} = \frac{ \sqrt{u_n} ( 1 + v_n ) }{u_n + v_n}
$$
alors
$$
  p_{n+1} = p_n u_n \frac{1+u_n}{1+v_n} \xrightarrow[n \to \infty]{} \pi
$$
\end{myth}

\subsection{Encore les frères Borwein (1987)}
\begin{myth}
 Si $y_0 = \sqrt{2} $, $z_1 = \sqrt[4]{2}$ et $f_0 = 2 + \sqrt{2} $
$$
  y_{n+1} = \frac{1+y_n}{2 \sqrt{y_n}}
$$
$$
  z_{n+1} = \frac{1+y_n z_n}{(1+z_n) \sqrt{y_n}}
$$
alors
$$
  f_{n+1} = f_n \frac{1+y_n}{1+z_n}   \xrightarrow[n \to \infty]{} \pi
$$
\end{myth}

\section{Les suites moyennes arithmético-géométriques}
\subsection{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 :
$$
  \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).

\subsection{Propriétés}

\begin{mylem}

\begin{enumerate}
	\item La suite $(a_n)_{n \in {\mathbb N}}$ est décroissante à partir du rang $1$.
	\item La suite $(b_n)_{n \in {\mathbb N}}$ est croissante à partir du rang $1$.
	\item $\forall n \sueg 1 $ on a : $b_n \ineg a_n$.
	\item $(a_n)$ et $(b_n)$ convergent vers un même réel qu'on notera $M(a;b)$.
\end{enumerate}
\end{mylem}
En un mot, les deux suites $(a_n)$ et $(b_n)$ sont adjacentes.\\
\underline{{\bf Remarque}} : si $0 \ineg b \ineg a $ alors les trois premiers points sont vrais au rang $0$.\\
\\
{\bf Preuve :}\\
Montrons le (3) :\\
Comme pour tout réel $A$ et $B$ on a $(A-B)^2 \sueg 0$ on déduit que $AB \ineg \frac{A^2+B^2}{2}$ (I).\\
Donc $\sqrt{ab} \ineg \frac{a+b}{2}$ puis $b_1 \ineg a_1$.
Et par une récurrence simple, on montre que $\forall n \sueg 1 $ on a : $b_n \ineg a_n$.
Montrons le (1) et (2) :\\
Du (3) on déduit que $\forall n \sueg 1 $ $a_{n+1} = \frac{a_n+b_n}{2}\ineg \frac{a_n+a_n}{2} = a_n$ :\\
c'est-à-dire $(a_n)$ est décroissante à partir du rang $1$.\\
et\\
$\forall n \sueg 1 $ , $b_{n+1} \sueg \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 \sueg 1 $ : $0 \ineg b_1 \ineg b_n \ineg a_n \ineg 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)$.
\cqfd

\begin{myprop}
 Les suites $(a_n)$ et $(b_n)$ converge de façon quadratique lorsque $a$ et $b$ sont positifs.
\end{myprop}

{\bf Preuve :}\\
Un calcul simple donne :
$$
  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 :
$$
 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 :
$$
 \frac{ e_{n+1}  }{ {e_n}^2  } \rightarrow \frac{1}{8M(a;b)}
$$
ie
$$
 \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}  $ \\
\begin{center}
{\bf Le nombre de chiffres exactes a environ doublé ! }
\end{center}
\cqfd

\subsection{Propriétés de la limite $M(a;b)$}

\begin{myprop}
\begin{enumerate}
	\item $M(a;a) = a$.
	\item $M(a;b) = M(b;a)$.
	\item Quel que soit $ n \sueg 0$ $M(a_n;b_n) = M(a;b)$ avec les mêmes notations.
	\item Quel que soit le réel $k \sueg 0$ $M(ka;kb) = k M(a;b)$.
	\item $M(a;b) = M \left( \frac{a+b}{2};\sqrt{ab} \right) $.
	\item Quel que soit $a \sueg b$ $M \left( a-b ; a+b \right) = M \left( a ; \sqrt{a^2-b^2} \right)$.
\end{enumerate}
\end{myprop}

{\bf Preuve :} laissée au lecteur.\\

\section{Etude de la fonction $x \mapsto M(1;x) $}
\subsection{Continuité de $x \mapsto M(1;x) $}

Considérons les suites de fonctions définies par récurrence pour $x \in \Rp$~:
$$
  	\begin{array}{rcl}
		a_0(x) & = & 1\\
		b_0(x) & = & x \\
		a_{n+1}(x) & = & \frac{ 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 $\Rp$ et à partir de $n \sueg 1$, $(a_n)$ est
une suite de fonctions décroissante $(b_n)$ est croissante et quel que soit $x \sueg 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
$$
 f(x) = M(1;x)
$$
On a :
$$
 b_n(x) \ineg f(x) \ineg a_n(x)
$$
J'énonce une propriété évidente :
\begin{myprop}
$a_n$ $b_n$ sont des fonctions continues sur $\Rp$ et ${\cal C}^{\infty}$ sur $\Rpe$.
\end{myprop}

Intéressons-nous plutôt à la propriété de cette section :
\begin{myprop}
$f$ est continue sur $\Rp$.
\end{myprop}

{\bf 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 \ineg a_n - f \ineg 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 $\Rp$ étant
donné que $r$ était arbitraire.
\cqfd

\subsection{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 $ {\Rpe}^2$ par :
$$
I(a;b) = \int_{0}^{+\infty}{\frac{dt}{ \sqrt{ (a^2+t^2)(b^2+t^2)} } }
$$

\begin{myprop}
	$$
	I(a;b) = I \left( \frac{a+b}{2} ; \sqrt{ab} \right)
	$$
\end{myprop}
Résultat dû à Gauss.\\
{\bf Preuve :}
Remarquons que :
$$
 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 :
$$
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 $\Rpe$ vers $\R$.\\
 Posons :
$$
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 :
$$
I \left( \frac{a+b}{2} ; \sqrt{ab} \right) = \int_{-\infty}^{+\infty}{\frac{ \frac{dt}{2}}
	{ \sqrt{ \left( { \left( \frac{a+b}{2} \right) }^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.
\cqfd

\begin{myprop}
 $(a,b) \mapsto I(a;b)$  est une fonction $ {\cal C}^1 $ sur ${\Rpe}^2$, à valeurs positives.
\end{myprop}

{\bf Preuve :}
en effet fixons $r >0$, alors pour $a \sueg r$ et $b \sueg r$ on a :
$$
q(t) \ineg \frac{1}{r^2 + t^2} \in L^1(\Rp)
$$
Donc par le théorème de convergence dominé $I$ est continue sur $[r;+\infty[$ donc sur $\Rpe$ aussi.\\
De même
$$
\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 \sueg r$ on trouve :
$$
 \mid \frac{\partial q}{ \partial a}(t) \mid \ineg \frac{R}{(a^2+t^2)^2} \in L^1(\Rp)
$$
donc
$ \frac{\partial q}{ \partial a}$ est ${\cal C}^1$ sur la bande (par le théorème de
convergence dominé) donc sur ${\Rpe}^2$. Il en est de même de $ \frac{\partial q}{ \partial b}$.
\cqfd

\begin{myprop}
\begin{enumerate}
	\item Pour tout réel $k >0$, $I(ka;kb) = \frac{1}{k} I(a;b)$.
	\item $I(b;a)=I(a;b)$.
	\item $I(1;1) = \frac{\pi}{2}$.
\end{enumerate}
\end{myprop}
{\bf 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.
\cqfd
Le nombre $\pi$ commence à apparaître !

\begin{myth}
 Pour tout réel positif $a$ et $b$ , on a :
 $$
 I(a;b)M(a;b)=\frac{\pi}{2}
 $$
\end{myth}

{\bf 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
$$
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 :
$$
	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.
\cqfd

Définissons la fonction $g$ sur $\Rpe$
$$
g(x) = I(1;x)
$$
et rappellons
$$
f(x) = M(1;x)
$$
Ainsi
$$
f(x) \, g(x) = \frac{\pi}{2}
$$
\begin{myth}
	$f$ est ${\cal C}^1$ sur $\Rpe$.
\end{myth}
{\bf Preuve :} Cela découle de la relation précédente entre $f$ et $g$ et de la
propriété 6.
\cqfd

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

\begin{myprop}
	Quel que soit $x >0$ :
\begin{enumerate}
	\item $g(\frac{1}{x})=g(x)x$.
	\item $f(\frac{1}{x})=\frac{1}{x}f(x)$.
	\item $g(x) \underset{0^+}{\sim} - \ln(x)$.
	\item $f(x) \underset{0^+}{\sim} \frac{-\pi}{2 \ln(x)} $
	\item $f(x) \underset{+\infty}{\sim} \frac{\pi x}{2 \ln(x)} $
\end{enumerate}
\end{myprop}
{\bf Preuve :} les deux premiers points découlent des propositions 2 et 7.\\
Passons au troisième et écrivons :
$$
g(x) = \int_{0}^{+\infty}{\frac{dt}{ \sqrt{ (x^2+t^2)(1+t^2)} } }
     = \underbrace{\int_{0}^{a}{}}_{g_1(x)} + \underbrace{\int_{a}^{+\infty}{}}_{g_1(x)}
$$
où $a>0$ est fixé.\\
Pour $0 \ineg t \ineg a$ on a:
$$
 \frac{1}{\sqrt{1+a^2}} \ineg \frac{1}{\sqrt{1+t^2}} \ineg 1
$$
puis
$$
 \frac{h(x)}{\sqrt{1+a^2}} \ineg g_1(x) \ineg h(x)
$$
où on a posé
$$
  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}} \ineg \Theta(a,x) \ineg 1 $.\\
De plus
$$
   0 < \int_{a}^{+\infty}{ \frac{dt}{ \sqrt{ (x^2+t^2)(1+t^2)} } } \ineg
       \int_{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
$$
  \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
$$
   \frac{1}{\sqrt{1+a^2}} \ineg \underset{x \rightarrow 0^+}{\liminf} \frac{g(x)}{-\ln(x)}
                          \ineg \underset{x \rightarrow 0^+}{\limsup} \frac{g(x)}{-\ln(x)}
			  \ineg 1
$$
Ceci étant vrai quel que soit $a>0$ donc en faisant tendre $a$ vers $0$, on trouve bien :
$$
  \underset{x \rightarrow 0^+}{\lim} \frac{g(x)}{-\ln(x)} = 1
$$
$$
  g(x) \underset{0^+}{\sim} - \ln(x).
$$
Passons au point suivant.\\
Pour $x$ grand \\
$$
 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.
$$
  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.
\cqfd

\subsection{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 \sueg 0}$ et ${(d_n)}_{n \sueg 0}$ par :
\begin{eqnarray*}
	c_n & = & \sqrt{a_n^2 - b_n^2}  \\
	d_n & = & \frac{1}{2^n}\ln \left( \frac{a_n}{c_ n} \right)
\end{eqnarray*}

\begin{myprop}
	Quel que soit $n \sueg 0$ :
\begin{enumerate}
	\item $M(a_n;c_n) = 2 \, M( a_{n+1} ; c_{n+1} )$ .
	\item $M(a_0;c_0) = 2^n \, M(a_n;c_n)$.
\end{enumerate}
\end{myprop}
{\bf Preuve : } On remarque que :
$$
  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,
$$
  M(a_n - b_n ; a_n + b_n ) = M( a_n ; \sqrt{a_n^2 - b_n^2} )
$$
soit
$$
  M(2c_{n+1} ; 2 a_{n+1} ) = M(a_n;c_n )
$$
d'où
$$
  2 M( c_{n+1} ; a_{n+1} ) = M(a_n;c_n )
$$
et par récurrence on trouve le second point.
\cqfd

\begin{myprop}
	Quel que soit $x \in ]0;1[$, on a
	$$d_n(x) \xrightarrow[n \rightarrow +\infty]{} \frac{\pi}{2}\frac{f(x)}{f(\sqrt{1-x^2})}
	 \mbox{ \hspace{1.5cm} (convergence simple)}
	$$
\end{myprop}
{\bf Preuve : } On écrit que
$$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) :
$$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.
\cqfd
Voici un résultat important sur la suite $(d_n)$ :
\begin{myprop}
$$
	\frac{d_{n+1}'}{d_n'} = \frac{a_n}{b_n} = \frac{{b_{n+1}}^2}{{b_n}^2}
$$
soit
$$
	\frac{d_{n+1}'}{{b_{n+1}}^2} = \frac{d_n'}{{b_n}^2}
$$
\end{myprop}
Ce qui entraîne
\begin{mycoro}
	\begin{eqnarray*}
	\frac{d_n'(x)}{{b_n}^2(x)} & = & \frac{d_0'(x)}{{b_0}^2(x)} = \frac{1}{x(1-x^2)} \\
	             d_n'(x) & = & \frac{{b_n(x)}^2}{x(1-x^2)} \mbox{ \hspace{1.3cm} sur} \; ]0;1[
	\end{eqnarray*}
\end{mycoro}
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)$.\\

{\bf Preuve de la propriété : } on calcule $d_n'$ :
\begin{eqnarray*}
	d_n' & = & \frac{1}{2^n} {\left( \frac{a_n}{c_n} \right)}^{-1} \frac{a_n' c_n - a_n c_n' }{{c_n}^2} \\
	     & = & \frac{1}{2^n} \left( \frac{a_n'}{a_n} - \frac{c_n'}{c_n}  \right) \\
	     & = & \frac{1}{2^n} \frac{a_n b_n b_n' - {b_n}^2 a_n' }{ a_n ( {a_n}^2 - {b_n}^2 ) }
\end{eqnarray*}
on calcule de même $d_{n+1}'$ en remarquant que :
$$
  c_{n+1} = \frac{a_n-b_n}{2}
$$
et donc
$$
  c_{n+1}' = \frac{a_n'-b_n'}{2}
$$
Ainsi
\begin{eqnarray*}
	d_{n+1}' & = & \frac{1}{2^{n+1}} \left( \frac{a_{n+1}'}{a_{n+1}} - \frac{c_{n+1}'}{c_{n+1}}  \right) \\
                 & = & \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) \\
		 & = & \frac{1}{2^n} \frac{a_n b_n' - b_n a_n' }{ {a_n}^2 - {b_n}^2 }
\end{eqnarray*}
Donc on déduit
$$
  \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}
$$
\cqfd

\begin{myprop}
 $d_n'$ converge uniformément sur tout compact de $]0;1[$ vers $x \mapsto \frac{f^2(x)}{x(1-x^2)}$
\end{myprop}
{\bf Preuve : } on se rappelle que $0 < b_n(x) \ineg f(x)$ et considérons un compact $K$ de
$]0;1[$. Pour tout $x$ de $K$, on a :
\begin{eqnarray*}
	\mid d_n'(x) - \frac{f^2(x)}{x(1-x^2)} \mid
	& = & \mid \frac{ {b_n(x)}^2 - f^2(x)}{x(1-x^2)} \mid \\
	& = & \mid b_n(x) - f(x) \mid \times \mid \frac{b_n(x) + f(x)}{ x(1-x^2)} \mid           \\
	& \ineg & \mid f(x) - b_n(x) \mid \times \sup_{y \in K} \left( \frac{2f(y)}{y(1-y^2)} \right)
\end{eqnarray*}
$f$ étant continue sur $\Rp$, $\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é.
\cqfd

Résumons :
\begin{itemize}
	\item $d_n$ converge simplment vers $x \overset{l}{\mapsto} \frac{\pi}{2}\frac{f(x)}{f(\sqrt{1-x^2})}$
	\item $d_n'$ converge uniformément vers $\overset{h}{\mapsto} \frac{f^2(x)}{x(1-x^2)}$ sur tout compact
	de $]0;1[$.
\end{itemize}
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[$ :
\vspace{1cm}
$$
\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})
$$
\\
\vspace{1cm}
En évaluant l'équation en $x= \frac{1}{\sqrt{2}}$, on obtient l'égalité reliant $f$ et $\pi$ :
$$
	\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é.



\section{Justification des algorithmes à convergence quadratique}
\subsection{Etude des suites $(a_n')$ et $(b_n')$ sur $]0;1[$}
Rappelons les définitions :
$$
	\left \lbrace
  	\begin{array}{rcl}
		a_0(x) & = & 1\\
		b_0(x) & = & x \\
		a_{n+1}(x) & = & \frac{ a_n(x) + b_n(x) }{2} \\
		b_{n+1}(x) & = & \sqrt{a_n(x) b_n(x)}
	\end{array}
	\right.
$$
et donc
$$
	\left \lbrace
  	\begin{array}{rcl}
		a_0'(x) & = & 0\\
		b_0'(x) & = & 1 \\
		a_{n+1}'(x) & = & \frac{ a_n'(x) + b_n'(x) }{2} \\
		b_{n+1}'(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 \sueg 0$, les deux suites de fonctions sur $]0;1[$:
$$
  	\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.

\begin{myprop}
	Pour tout entier $n \sueg 1$,
\begin{enumerate}
	\item $y_{n+1} = \frac{1+y_n}{2\sqrt{y_n}}$,
	\item $z_{n+1} = \frac{1+y_n z_n}{(1+z_n)\sqrt{y_n}}$,
	\item $y_n \sueg 1$,
	\item $z_n \sueg 1$,
	\item $z_n \sueg y_n$,
	\item $(z_n)$ est une suite décroissante.
	\item $(y_n)$ et $(z_n)$ convergent uniformément sur tout compact de $]0;1[$ vers $1$.
\end{enumerate}
\end{myprop}

{\bf 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 \sueg b_n > 0$ d'où $y_n \sueg 1$.\\
Remarquons ensuite que $z_1(x)=\frac{1}{\sqrt{x}}$ donc $z_1 \sueg 1$ sur $]0;1[$.\\
Définissons la fonction $\phi_y$ par
$$
\phi_y(x) = \frac{1+yx}{(1+x)\sqrt{y}}
$$
alors
$$
  \phi_y'(x) = \frac{1}{\sqrt{y}} \frac{y-1}{(1+x)^2}
$$
donc si $y \sueg 1$, alors $\phi_y' \sueg 0$ sur $\Rp$ et comme
$\phi_y(1) = \frac{1+y}{2\sqrt{y}} \sueg 1$, on déduit que si
$z_n \sueg 1$ alors $z_{n+1} = \phi_{y_n}(z_n) \sueg \phi_{y_n}(1) \sueg 1 $
c'est-à-dire
$$
	z_{n+1} \sueg y_{n+1} \sueg 1 .
$$
Or
$ z_1(x) = \frac{1}{\sqrt{x}} \sueg 1 $
et
$ y_1(x) = \frac{1}{x} \sueg 1$,
donc on a bien $z_{n} \sueg y_{n}$ à partir de $n=1$ (par récurrence).\\

La monotonie de $(z_n)$ se déduit facilement :
$$
z_{n+1} = \frac{1+y_n z_n}{(1+z_n)\sqrt{y_n}}
        \ineg \frac{z_n+y_n z_n}{(1+z_n)\sqrt{y_n}}
$$
donc
$$
 \frac{z_{n+1}}{z_n}	\ineg \frac{1+y_n }{(1+z_n)\sqrt{y_n}} \ineg \frac{1}{\sqrt{y_n}} \ineg 1
$$
Etudions la convergence des deux suites.\\
Nous avons
$$
  y_n - 1 = \frac{a_n - b_n}{b_n} \ineg \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[$ :
$$
	y_n(x) - 1 \ineg \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 $\Rp$, 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.
\cqfd

\begin{myprop}
	les suites $(a_n')$ et $(b_n')$ converge uniformément sur tout compact de $]0;1[$ vers $f'$
	de façon quadratique.
\end{myprop}
{\bf Preuve : }commençons par préciser quelques notations. On note :\\
${\| (x,y) \|}_{\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 z_n - 1 \vert}_{K,\infty},{\vert y_n - 1 \vert}_{K,\infty}) \|}_{\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
$$
  z_{n+1} = G(y_n,z_n)
$$
$$
  y_{n+1} = H(y_n)
$$
avec
$$
G(y,z) = \frac{1+yz}{(1+z)\sqrt{y}}.
$$
$$
H(y) = \frac{1+y}{2\sqrt{y}}
$$
Puis prenons le développement limité de $G$ et $H$ au voisinage de $(1;1)$ :
$$
  G(1+h,1+k) = 1 + \frac{h^2}{8}+\frac{hk}{4}+ o( {\| (h;k) \|}_\infty^2 )
$$
$$
  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 \ineg r$ et $\vert k\vert \ineg r$
entraîne
$$
  \vert G(1+h,1+k) - 1 \vert \ineg {\| (h,k) \|}_{\infty}^2
$$
$$
  \vert H(1+h) - 1 \vert \ineg h^2 \ineg {\| (h,k) \|}_{\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 \sueg N_{K,r}$, on ait
$ {\vert y_n - 1 \vert}_{\infty,K} \ineg r $ et $ {\vert z_n - 1 \vert}_{\infty,K} \ineg r $
donc pour tout $x$ de $K$ :
$$
  \vert z_{n+1}(x) - 1 \vert \ineg {\| (z_n(x) - 1,y_n(x) - 1) \|}_{\infty}^2 \ineg
   {   {\| ({\vert y_n - 1 \vert}_{\infty,K};{\vert z_n - 1 \vert}_{\infty,K}) \|  }_\infty }^2
$$
et ainsi
$$
   {\| z_{n+1} - 1 \|}_{\infty,K} \ineg
    {   {\| ({\| y_n - 1 \|}_{\infty,K};{\| z_n - 1 \|}_{\infty,K}) \|  }_\infty }^2
$$
et en procédent de même pour $y_n$, on a :
$$ {\vert y_{n+1} - 1 \vert}_{\infty,K} \ineg
    { \|  {({\vert y_n - 1 \vert}_{\infty,K};{\vert z_n - 1 \vert}_{\infty,K}) \| }_\infty }^2
$$
i.e. pour $n \sueg N_{K,r}$
$$
  u_{n+1} \ineg u_n^2
$$
d'où par récurrence
$$
   u_n \ineg c \,r^{2^{n}}
$$
avec $c = r^{2^{-N_{K,r}}}$

Comme
$$
  { \vert a_{n+1}' \vert }_{K,\infty} \ineg \frac{1+ { \vert z_n \vert }_{K,\infty}}{2} { \vert a_n' \vert }_{K,\infty}
$$
on a pour $n \sueg N_{K,r}$
$$
  { \vert a_{n+1}' \vert }_{K,\infty} \ineg (1 + c_2 r^{2^n}) { \vert a_{n}' \vert }_{K,\infty}
$$
et ainsi
$$
  { \vert a_n' \vert }_{K,\infty} \ineg { \vert a_{N_{K,r}}' \vert }_{K,\infty} \prod_{k=1}^{n-1} (1 + c_2 r^{2^k})
  \ineg { \vert a_{N_{K,r}}' \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 \sueg N_{K,r}$
$$
   {\vert a_{n+1}'-a_n' \vert}_{K,\infty} \ineg c_3 \,r^{2^{n}}
$$
 car $(a_n')$ est bornée.
En conséquence pour $m \sueg n \sueg N_{K,r}$
$$
   {\vert a_{m}'-a_n' \vert}_{K,\infty} \ineg \sum_{k=n}^{m-1}{\vert a_{k+1}'-a_k' \vert}_{K,\infty}
   \ineg c_3 \sum_{k=n}^{m-1} r^{2^{k}}
   \ineg 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$
$$
  {\vert a_{m}'-a_n' \vert}_{K,\infty} \ineg \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
$$
   {\vert a_{m}'-a_n' \vert}_{K,\infty} \ineg c_3 \sum_{k=n}^{\infty} r^{2^{k}}
$$
on tire par passage à la limite $ m \to +\infty$ :
$$
   {\vert f'-a_n' \vert}_{K,\infty} \ineg c_3 \sum_{k=n}^{\infty} r^{2^{k}}
   \ineg r^{2^{n}} \sum_{k=0}^{\infty} r^k
   \ineg \frac{r^{2^{n}}}{1-r}
$$
d'où la convergence quadratique de $a_n'$ vers $f'$ et à fortiori de $b_n'$.


\cqfd

\subsection{Retour sur le dernier algorithme des frères Borwein}
\subsubsection{Explication détaillée}

Rapellons les suites :\\
 Si $y_0 = \sqrt{2} $, $z_1 = \sqrt[4]{2}$ et $f_0 = 2 + \sqrt{2} $
$$
  y_{n+1} = \frac{1+y_n}{2 \sqrt{y_n}}
$$
$$
  z_{n+1} = \frac{1+y_n z_n}{(1+z_n) \sqrt{y_n}}
$$
alors
$$
  f_{n+1} = f_{n} \frac{1+y_n}{1+z_n}   \xrightarrow[n \to \infty]{} \pi
$$
{\bf 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)$ :
$$
  w_n = \frac{a_n b_n^2}{a_n'}
$$
Nous savons d'après l'étude précédente que

$$w_n(\frac{1}{\sqrt{2}}) \xrightarrow[n \to \infty]{} \frac{\pi}{2\sqrt{2}} $$
D'après la formule
$$
	\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
$$
  \frac{w_{n+1}}{w_n} = \frac{1+y_n}{1+z_n}
$$
et
$$
  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.
\cqfd

\subsubsection{Premier algorithme}



\subsection{Explication du premier algorithme des frères Borwein}
Rapellons les suites :\\
si $u_0 = \sqrt{2}$, $v_0 = 0$, $p_0 = 2 + \sqrt{2}$
$$
  u_{n+1} = \frac{\sqrt{u_n}}{2} + \frac{1}{2\sqrt{u_n}}
$$
$$
  v_{n+1} = \frac{ \sqrt{u_n} ( 1 + v_n ) }{u_n + v_n}
$$
alors
$$
  p_{n+1} = p_n u_n \frac{1+u_n}{1+v_n} \xrightarrow[n \to \infty]{} \pi
$$
{\bf 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}}$.
\cqfd


\subsection{Retour sur le dernier algorithme Brent et Salamin}
\subsubsection{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
 $$
  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
 $$
{\bf 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 :
$$
  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
$$
   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 :
$$
  \frac{b_{n+1}'}{b_{n+1}}= \frac{1}{2}\left( \frac{a_n'}{a_n} + \frac{b_n'}{b_n} \right)
$$
donc
$$
     \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
$$
  d_n'(x) = \frac{b_n^2(x)}{x(1-x^2)}
$$
ainsi que
$$
  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
$$
   \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
$$
    \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
$$
  \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
$$
  U_n = \frac{4a_n^2\left(\frac{1}{\sqrt{2}}\right)}{1-2 \sum\limits_{k=1}^{n}{2^k \left(a_k^2\left(\frac{1}{\sqrt{2}}\right) -
      b_k^2\left(\frac{1}{\sqrt{2}}\right) \right)}}
      = 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)}
      \xrightarrow[n \to \infty]{} \pi
$$
\cqfd

\subsubsection{Premier algorithme}

On écrit :
 $$
  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 :
\begin{eqnarray}
  A_n & = & a_n ^2    \nonumber \\
  B_n & = & b_n ^2  \nonumber \\
  S_n & = & \frac{1}{4} - \sum\limits_{k=1}^{n}{2^{k-1} (a_k^2 - b_k^2 )} \nonumber
\end{eqnarray}
On obtient :
$$
  A_0 = 1
$$
$$
  B_0 = \frac{1}{2}
$$
$$
  S_0 = \frac{1}{4}
$$
et les formules :
\begin{eqnarray}
  B_{n+1} & = & \sqrt{A_n B_n} \nonumber \\
  A_{n+1} & = & \frac{A_n+B_n}{4} + \frac{B_{n+1}}{2} \nonumber \\
  S_{n+1} & = & S_n - 2^n (A_{n+1} - B_{n+1} ) \nonumber
\end{eqnarray}
ce qui donne l'algorithme :

\begin{center}
\begin{tabular}{lr}
  $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$
\end{tabular}
\end{center}

\subsubsection{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
$$
   A_{n+1} = \frac{A_n+B_n}{4} + \frac{B_{n+1}}{2}
$$
on déduit que
$$
  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 :

\begin{center}
\begin{tabular}{lr}
  $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$
\end{tabular}
\end{center}
\end{document}

