\documentclass[11pt,a4paper]{article}
\usepackage[utf8x]{inputenc}
\usepackage{ucs}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage[francais]{babel} 
\usepackage[margin=1cm, includefoot]{geometry} 
%\def\pgfsysdriver{pgfsys-dvipdfm.def} %si utilisation de dvipdfmx
\usepackage{pgf,tikz}
\usetikzlibrary{arrows}
\usetikzlibrary{patterns}
\usepackage{wrapfig}
\usepackage{moreverb} %Pour avoir un cadre autour d'un environnement verbatim

%\pagestyle{empty} %Pas de pagination
%\usepackage{fouriernc} %Police century scoolbook


\title{Approximations de \(\pi\)}
\date{}
\parindent=0em
\parskip=5pt

\begin{document}
\maketitle
\section{Méthode d'Archimède}
\subsection{Le principe}
{La méthode d'Archimède de calcul de \( \pi \) (historiquement la première que nous connaissions) est basée sur la remarque suivante : considérons un polygone régulier à \( n \) sommets inscrit dans un cercle \( \mathcal{C} \). Plus \( n \) augmente, plus la forme du polygone se rapproche de celle du cercle  \( \mathcal{C} \).

Si on appelle \( P_n \) le périmètre du polygone régulier à \( n \) côtés, on peut supposer (par observation) que \( (P_n) \) est croissante et bornée. Si on démontre ces deux propriétés, alors on sait que \( (P_n) \) est convergente ; on dira alors par définition que sa limite est la longueur du cercle \( \mathcal{C} \).

En fait, Archimède n'a pas considéré la suite des polygones à \( n \) côtés, mais la suite obtenue en multipliant le nombre de côtés par deux à chaque étape, autrement dit, la suite des polygones à \( 2^n \) côtés.

\begin{wrapfigure}{r}{0pt}
\begin{tikzpicture}[scale=0.7, transform shape]
\fill (0,0) circle (2pt) node[left] {$O$};
\fill (-30:4)circle (2pt) node[right] {$A$};
\fill (30:4) circle (2pt) node[right] {$B$};
\fill (3.464,0)circle (2pt)  node [right]{$C$};
\draw (-30:4) arc (-30:30:4);
\draw (0,0) -- (-30:4);
\draw (0,0) -- (30:4);
\draw (0,0)-- (3.464,0);
\draw (-30:4) -- (30:4);
\draw (0:1) arc (0:30:1) node[above] {$\dfrac{\alpha}{2}$};
\end{tikzpicture}
\end{wrapfigure}
Supposons que le cercle est de rayon 1. Le dessin ci-contre suggère que la longueur de l'arc \( \overset{\frown}{AB} \) est proche de la longueur du segment \( [AB] \) lorsque l'angle \( \widehat{AOB} \) est petit. Notons \( \alpha \) la longueur de \( \overset{\frown}{AB} \) ; comme \( \mathcal{C} \) est de rayon 1, \( \alpha \) est aussi une mesure  en radians de \( \widehat{AOB} \). Ainsi, \( \overset{\frown}{AB}\simeq AB \) se traduit par : \( 2 \sin \left( \dfrac{\alpha}{2}\right)\simeq \alpha \) ou \(  \sin \left( \dfrac{\alpha}{2}\right)\simeq \dfrac{\alpha}{2} \).

On peut traduire cette approximation en termes de limite : \[ \lim_{x\rightarrow 0} \dfrac{\sin \left( x \right)}{x} =1. \]

C'est une propriété fondamentale, admise au lycée.

Supposons qu'on a partagé le demi-cercle en \( 2^n \) parties. On obtient en posant \( x=\dfrac{\pi}{2^n} \):
\begin{equation} \lim_{n \rightarrow +\infty} {2^n \sin \left(\dfrac{\pi}{2^n} \right)} =\pi. \label{equ_1} \end{equation}

\subsection{Recherche d'une relation de récurrence}
Bien. Mais il faut aussi pouvoir passer de \( \sin \left(\dfrac{\pi}{2^n}\right) \) à \( \sin \left(\dfrac{\pi}{2^{n+1}}\right) \). Pour cela, on utilise une des formules de duplication vues en première : \( \sin(2 \alpha)=2 \sin \alpha \cos\alpha=2 \sin\alpha\sqrt{1-\sin^2\alpha} \).

On en déduit : \( \sin^2(2 \alpha)=4 \sin^2\alpha (1-\sin^2\alpha) \). 

Si on pose \( t=\sin^2\alpha\), on obtient une équation du second degré en $t$ : \( t^2-t+\frac{1}{4}\sin^2(2\alpha)=0 \).

On résout cette équation, on trouve : \( t=\dfrac{1-\sqrt{1-\sin^2(2\alpha)}}{2} \) ou \( t=\dfrac{1+\sqrt{1-\sin^2(2\alpha)}}{2} \).

Si on suppose \( \alpha \in [0 ; \frac{\pi}{4}]\) alors \(0\leq\sin\alpha\leq \dfrac{1}{\sqrt{2}} \) donc \(\sin^2\alpha\leq \dfrac{1}{2} \). Comme une racine carrée est un nombre positif, cela correspond à la première solution : \( \sin^2(\alpha)= \dfrac{1-\sqrt{1-\sin^2(2\alpha)}}{2}\).

Posant \( \alpha = \dfrac{\pi}{2^{n+1}}\), on obtient :
 \begin{equation}
\sin^2\left( \dfrac{\pi}{2^{n+1}}\right)= \dfrac{1-\sqrt{\ 1- \sin^2\left( \dfrac{\pi}{2^{n}}\right)}}{2}. \label{eqn_2}
\end{equation}
Et donc : \( \sin\left( \dfrac{\pi}{2^{n+1}}\right)= \sqrt{\dfrac{1-\sqrt{\ 1- \sin^2\left( \dfrac{\pi}{2^{n}}\right)}}{2}} \).

On peut donc introduire deux suites : \( (u_n) \) telle que \( u_n = \sin^2\left( \dfrac{\pi}{2^{n}}\right) \) et \( (p_n) \) telle que \( p_n=2^n \sqrt{u_n} \).\\ D'après l'équation (\ref{equ_1}) page \pageref{equ_1}, on a : 
\[ \lim_{n \rightarrow +\infty} {p_n} =\pi. \]

D'autre part, la relation de récurrence (\ref{eqn_2}) s'écrit : \[ u_{n+1}= \dfrac{1-\sqrt{\ 1- u_n}}{2} .\] Pour pouvoir utiliser cette formule, on a vu que \( u_{n+1} \) doit être dans l'intervalle \( [0 ; \frac{\pi}{4}]\). 

On pose donc : \( u_1=\sin \left ( \frac{\pi}{2} \right )=1 \).

\subsection{Calcul}
On dispose donc de deux suites \( (u_n) \) et \( p_n \) définies ainsi :
\[ \left\lbrace \begin{array}{l}
u_1=1 \\
u_{n+1}=\dfrac{1-\sqrt{\ 1- u_n}}{2} 
\end{array} \right. \quad \text{et} \quad p_n=2^n \sqrt{u_n}. \]

Remarque : \( u_n \) tend vers 0. Quand un ordinateur ou une calculatrice calcule \( 1-u_n \), le résultat va être rapidement arrondi à 1. Ainsi le numérateur \( 1-\sqrt{\ 1- u_n} \) va être arrondi à 0. Avec les calculatrices, ça se produit dès que \( u_n \) est inférieur à \( 10^{-10} \) ou \( 10^{-11} \). C'est ennuyeux, car il faudrait pouvoir poursuivre le calcul.

Pour pallier ce défaut, on peut transformer l'écriture de \( u_{n+1} \) ainsi :
\[\begin{split} u_{n+1} & =\dfrac{1-\sqrt{\ 1- u_n}}{2}
=\dfrac{\left( 1-\sqrt{\ 1- u_n} \right)\left( 1+\sqrt{\ 1- u_n} \right) }{2 \left( 1+\sqrt{\ 1- u_n} \right)}
=\dfrac{1^2-\sqrt{1- u_n} ^2}{2 \left( 1+\sqrt{ 1- u_n} \right)}
=\dfrac{1- (1-u_n)}{2 \left( 1+\sqrt{ 1- u_n} \right)}\\
u_{n+1}&=\dfrac{u_n}{2 \left( 1+\sqrt{ 1- u_n} \right)}. \end{split}\]

On obtient donc un algorithme ressemblant à ceci :

\begin{boxedverbatim}
u, p : nombre
u <- 1
Pour i de 2 à 10
      u <- u/(2*(1+sqrt(1-u)))
Fin pour
p <- 2^10*sqrt(u)
Afficher p
\end{boxedverbatim}

Remarque : On ne fait qu'une fois, à la fin, le calcul de \( p_n \) à partir de \( u_n \). Ce n'est pas obligatoire, on pourrait le faire à chaque itération. L'avantage, c'est que c'est plus rapide.

\begin{wrapfigure}{r}{0pt}
\begin{tikzpicture}[scale=0.7, transform shape]
\fill (0,0) circle (2pt) node[left] {$O$};
\fill (-30:4)circle (2pt) node[below] {$A$};
\fill (30:4) circle (2pt) node[above] {$B$};
\fill (3.464,0)circle (2pt)  node [above left]{$C$};
\fill (-30:4.6188)circle (2pt) node[right] {$A'$};
\fill (30:4.6188) circle (2pt) node[right] {$B'$};
\draw (-30:4) arc (-30:30:4);
\draw (0,0) -- (-30:4.6188);
\draw (0,0) -- (30:4.6188);
\draw (0,0)-- (4,0);
\draw (-30:4) -- (30:4);
\draw (-30:4.6188) -- (30:4.6188);
\draw (0:1) arc (0:30:1) node[above] {$\dfrac{\alpha}{2}$};
\end{tikzpicture}
\end{wrapfigure}

L'inconvénient, c'est qu'on ne voit pas les décimales se stabiliser, donc on ne sait pas si on est loin de la valeur exacte de \( \pi \).

\textbf{Travail à faire :}
\begin{enumerate}
\item Programmer cet algorithme.
\item Montrer que l'on a : \( 2^n\sqrt{u_n} \leq \pi \leq 2^n \sqrt{\dfrac{u_n}{1-u_n}} \), ce qui fournit un encadrement de \( \pi \).

Indication : on peut considérer la figure ci-contre et montrer que \( A'B'=\dfrac{AB}{\cos(\alpha/2)} \).
\item Modifier l'algorithme pour qu'il donne l'encadrement précédent.
\end{enumerate} 

\vline

\section{Aire d'un quart de disque par la méthode des rectangles}
\subsection{Le principe}
On considère le disque de centre \( O \) et de rayon 1 (c'est à dire le disque délimité par le cercle trigonométrique). On cherche à approcher l'aire du quart de disque délimité par les points  \( O(0\,;0) \), \( I(1\,;0) \) et \( J(0\,;1) \).

Pour cela, on subdivise le segment \( [OI] \) en \textit{n} segment égaux. On obtient donc \textit{n} points : \( B_0=O \), \( B_1 \), \( B_2 \),... \( B_n=I \) régulièrement espacés. On appelle d'autre part \( A_i \) le point du cercle \( \mathcal{C} \) de même abscisse que \( B_i \). 

Le cas \textit{n} = 4 est représenté ci-dessous.

\begin{center}
\begin{tikzpicture}[scale = 5]
\draw(0,0) -- (0,1);
\draw(0,0) -- (1,0) coordinate (A4) node[below]{$B_4$} node[above right]{$A_4$};
\draw(1,0) arc (0:90:1);

\foreach \k in {0,...,3}
    {
    \path ({(\k+1)/4},{sqrt(1-((\k+1)/4)^2)}) coordinate (C\k);
    \path ({(\k+1)/4},0) coordinate (D\k);
    \path ({(\k/4},{sqrt(1-(\k/4)^2)}) coordinate (A\k) node[above right]{$A_\k$};
    \path ({(\k/4},0) coordinate (B\k) node[below]{$B_\k$};
    \draw [pattern=crosshatch dots] (B\k) rectangle (C\k);
    \draw (A\k) rectangle (D\k);
     }
\end{tikzpicture}
\hspace{1cm}
\begin{tikzpicture}[scale = 5]
\draw(0,0) -- (0,1);
\draw(0,0) -- (1,0) coordinate (A4) node[below]{$x_4$} node[above right]{$f(x_4)$};
\draw(1,0) arc (0:90:1);
\foreach \k in {0,...,3}
    {
    \path ({(\k+1)/4},{sqrt(1-((\k+1)/4)^2)}) coordinate (C\k);
    \path ({(\k/4},{sqrt(1-(\k/4)^2)}) coordinate (A\k) node[above right]{$f(x_\k)$};
    \path ({(\k/4},0) coordinate (B\k) node[below]{$x_\k$};
    \draw (B\k) -- (A\k);
    \draw (B\k) rectangle (C\k);
    \draw (A\k) rectangle (D\k);
     }
\end{tikzpicture}
\end{center}

Considérons les rectangles de diagonale \( [B_0A_1] \), \( [B_1A_2] \), etc. Leur réunion forme une sorte de figure en escalier (grisée sur le dessin) contenue dans le quart de disque \( OIJ \) ; son aire \( \mathcal{A}_i \) est donc inférieure à l'aire du quart de disque. Considérons ensuite les rectangles de diagonale \( [B_1A_0] \), \( [B_2A_1] \), etc. Leur réunion forme une autre figure en escalier qui contient le quart de disque \( OIJ \) ; son aire \( \mathcal{A}_s \) est donc supérieure à l'aire du quart de disque.

Ainsi, l'aire \( \mathcal{A} \) du quart de disque est encadrée par \( \mathcal{A}_i \) et \( \mathcal{A}_s \). Or, \( \mathcal{A} \) vaut \( \dfrac{\pi\times R^2}{4}=\dfrac{\pi}{4} \), puisque le rayon du cercle est 1. Le calcul approché de \( \mathcal{A}_i \) et \( \mathcal{A}_s \) fournit donc un encadrement de \( \dfrac{\pi}{4} \), et on peut conjecturer que cet encadrement sera de plus en plus précis à mesure que \textit{n} augmente.
\subsection{Le calcul}
On note \( x_i \) l'abscisse de \( B_i \). Alors : \( x_0=0 \), \( x_1=\dfrac{1}{n} \), \( x_2=\dfrac{2}{n} \), ..., \( x_n=\dfrac{n}{n}=1 \). D'autre part, si on note \( f(x_i) \) l'ordonnée de \( A_i \), on a d'après le théorème de Pythagore : \( f(x_i)=\sqrt{1-x_i^2} \).

L'aire du rectangle de diagonale \( [B_0A_1] \) est égale à : \( B_0B_1\times B_1A_1 = \dfrac{1}{n}\times f(x_1) \), et ainsi de suite pour les autres rectangles.

La somme des aires des rectangles "inférieurs" est donc :
 \[ \mathcal{A}_i=\dfrac{1}{n}\times f(x_1)+\dfrac{1}{n}\times f(x_2)+...+\dfrac{1}{n}\times f(x_n) \]
Comme \( f(x_n)=0 \), on obtient :
 \[\mathcal{A}_i=\dfrac{1}{n}\left(f(x_1)+f(x_2)+...+f(x_{n-1})+f(x_{n-1})\right) \]
 
L'aire du rectangle de diagonale \( [B_1A_0] \) est égale à : \( B_0B_1\times B_0A_0 = \dfrac{1}{n}\times f(x_0) \), et ainsi de suite pour les autres rectangles.

La somme des aires des rectangles "supérieurs" est donc :
 \[ \mathcal{A}_s=\dfrac{1}{n}\times f(x_0)+\dfrac{1}{n}\times f(x_1)+...+\dfrac{1}{n}\times f(x_{n-1}) \]
Comme \( f(x_0)=1 \), on obtient :
 \[\mathcal{A}_s=\dfrac{1}{n}+\dfrac{1}{n}\left(f(x_1)+...+f(x_{n-1}) \right)\]
 
Remarquons que \( \mathcal{A}_s=\mathcal{A}_i+\dfrac{1}{n} \). Admettons que la suite \( \mathcal{A}_i\) a une limite lorsque \textit{n} tend vers \( +\infty \), alors la suite \( \mathcal{A}_s\) a la même limite. D'après le théorème des gendarmes, cette limite est aussi celle de \( \mathcal{A}\). D'autre part, on peut ainsi obtenir un encadrement de \( \dfrac{\pi}{4} \) avec une précision aussi grande qu'on veut : il suffit de choisir \textit{n} pour que \( \dfrac{1}{n} \) soit assez petit. Par exemple, pour avoir une valeur approchée au 1/1000\up{e}, il suffit de prendre \textit{n}=1000.

Il reste donc à programmer le calcul de  \( \mathcal{A}_i\).
\subsection{Mise en oeuvre de l'algorithme}
On a vu que : \( f(x_i)=\sqrt{1-x_i^2} \). 

On calcule \( S= f(x_1)+...+f(x_{n-1})\) à l'aide d'une boucle, puis on divise \textit{S} par \textit{n} pour obtenir \( \mathcal{A}_i\). On obtient donc un algorithme du type suivant :

\begin{boxedverbatim}
Variables :
A_i, A_s, n, S, x_i : nombres
S  <-  0
Pour k de 1 à n-1 :
      x_i  <-  k/n
      S  <-  S+sqrt(1-x_i^2)
Fin pour
A_i  <-  S/n
A_s  <-  A_i+1/n
Afficher A_i et A_s
\end{boxedverbatim}

\textbf{Travail à faire :}
Programmer et tester cet algorithme.
\pagebreak

\section{Méthode de Monte-Carlo}
\subsection{Une probabilité définie de manière géométrique}

Le principe est le suivant : On génère de façon \emph{équiprobable} deux nombres aléatoires \textit{x} et \textit{y} compris entre 0 et 1. Ces deux nombres forment alors les coordonnées d'un point \( A \) du carré unité \( OJKI \).

\begin{center}
\begin{tikzpicture}[scale = 4]
\draw (0,0)node[below left]{$O$} rectangle (1,1)node[above right]{$K$};
\draw(1,0) node[below right]{$I$} arc (0:90:1) node[above left]{$J$};
\draw[dotted, thick] (0.7,0) -- (0.7,0.3) node[above]{$A(x,y)$} -- (0,0.3);
\node at (0.7,0.3){$\bullet$};
\end{tikzpicture}
\end{center}

Quelle est la probabilité que \( A \) appartienne au quart de disque \(\mathcal{D} \) de centre \( O \) limité par l'arc \( \overset{\frown}{IJ}\) ? Intuitivement, parmi les points du carré \( OJKI \), la proportion de points appartenant au quart de disque \( \mathcal{D} \) est égale au quotient de l'aire de \( \mathcal{D} \) par l'aire du carré unité. Ainsi : 
\[p(A \in \mathcal{D})= \dfrac{\text{Aire de }\mathcal{D}}{\text{Aire de }OJKI} \]
Or, l'aire du carré \( OJKI \) est de 1, et l'aire de \( \mathcal{D} \) est \( \dfrac{\pi}{4} \). Ainsi : \( p(A \in \mathcal{D})=\dfrac{\pi}{4} \).
\subsection{Évaluation de la probabilité}
Pour évaluer la probabilité \( p(A \in \mathcal{D}) \), on va procéder de façon classique : on simule un nombre de fois \textit{n} le tirage de \textit{x} et \textit{y} (autrement dit, on constitue un échantillon de taille \textit{n}), et on détermine la fréquence observée de l'événement \( (A \in \mathcal{D}) \). Lorsque \textit{n} devient très grand, la fréquence observée tend en général vers \( p(A \in \mathcal{D}) \).
Comment tester si A appartient à \( \mathcal{D} \) ? Facile : La distance OA est alors inférieure ou égale à 1.

On obtient donc un algorithme du type suivant (\verb+n+ : le nombre d'itération, \verb+n_D+ : l'effectif de \( (A \in \mathcal{D}) \), \verb+f+ : la fréquence de \( (A \in \mathcal{D}) \), \verb+val_pi+ : la valeur approchée de \( \pi \) obtenue) :

\begin{boxedverbatim}
Variables :
val_pi, n, x, y, n_D, f : nombres
Initialisation :
n_D <- 0
Lire n
Pour k de 1 à n :
    x  <-  nombre aléatoire pris dans [0;1]
    y  <-  nombre aléatoire pris dans [0;1]
    Si (x^2 + y^2 <= 1) alors :
        n_D  <-  n_D+1
    Fin si    
f  <-  n_D/n
val_pi  <-  f*4
Afficher val_pi
\end{boxedverbatim}

\textbf{Travail à faire :}
Programmer et tester cet algorithme.

Avec algobox, on peut aussi, à chaque itération, faire afficher le point de coordonnées \( (x ; y) \) (instruction \verb+TRACER_POINT+). On visualise ainsi la progression du calcul.
\pagebreak
\end{document}
