Mathématiques

Méthode de Monte-Carlo : approximer Pi

Objectif :
Découvrir les méthodes de Monte Carlo, leurs différents domaines d’application et construire une exemple pratique. Cet exemple portera sur l’approximation de pi grâce à un script en Python. Des notions en programmation Python seraient utiles mais pas indispensables pour comprendre.

Code source sur mon Github

Naissance d’un outil de calcul très puissant

C’est en 1950 qu’une équipe de chercheurs menée par Nicholas Metropolis met au point une méthode dite de Monte Carlo. Le nom étant tiré du célèbre casino de Monte Carlo, où les jeux d’argent – domaine propice à l’exploitation des probabilités – sont légion.
Par la suite c’est toute une famille d’algorithmes qui portera ce nom, regroupant des procédures qui se chargent d’estimer un résultat numériques à la suite de répétitions d’expériences aléatoires.

Lors de la seconde guerre mondiale, les Etats-Unis investissent considérablement dans la recherche en physique et en mathématiques. Érudit déjà reconnu pour plusieurs travaux en maths, John Von Neumann est également un fervent anticommuniste. C’est sans scrupule qu’il participa à la recherche de la bombe H car pour lui, seul une puissance démocratique méritait d’obtenir un tel moyen de pression, la course contre la Russie était engagée. Les temps de calculs étant considérablement longs, Von Neumann et Stanislaw Marcin Ulam développèrent davantage les méthodes de Monte Carlo. En effet, simuler au hasard des événements et prendre la moyenne des résultats comme approximation se révéla bien plus rapide tout en étant très juste !

Des applications multiples

Il ne faut pas croire que ce divin outil de calcul n’est réservé qu’à la théorie des jeux, elle est utile absolument partout ! Souvent utilisé pour le calcul d’aires, on peut aisément intégrer des fonctions dont on ne sais pas déterminer aisément la primitive. En effet, pour les moins matheux d’entre vous je rappelle que l’intégrale d’une fonction sur un intervalle donné [a,b] n’est rien d’autre que l’aire sous la courbe à cette intervalle.

Pour cela on tire des points au hasard situés de part et d’autre de la courbe, puis on calcule le rapport entre les points situés au dessous de la courbe (donc compris dans l’intégrale) et le nombre total de points tirés… et voilà une valeur approchée de notre intégrale !

Cette approche de l’intégration permet de résoudre divers problèmes, notamment en finance, en météorologie, optimisation ou encore la télécommunication. Cela déborde même sur les sciences sociales où de nombreux problèmes exigent l’analyse des propriétés d’un nombre si grand d’objets que seuls des procédés de type Monte Carlo peuvent les traiter.

Un exemple à tester chez vous !

Et oui, parce que les maths c’est quand même le seul domaine scientifique où l’on a besoin de trois fois rien pour réaliser ses petites expériences ! Je vous propose de faire fonctionner vos méninges, en vous frottant à la question suivante :

Vous possédez un cercle de rayon r et un carré de côté 2r. Très soucieux de vos cours de collège, vous vous souvenez bien évidemment que l’aire d’un cercle équivaut à pi fois son rayon au carré, quant à l’aire d’un carré n’est autre que son côté élevé lui même au carré ! D’après l’explication plus haut du fonctionnement d’un algorithme type Monte Carlo dans le cas d’un calcul d’aire, à votre avis, comment estimer pi avec ce qu’on a sous la main ?

Ça y est, vous y avez réfléchi ? En êtes vous sûr(e) ? Je dévoile la solution plus bas.

Bien, bien soit ! Bravo à ceux qui on relevé le défi et pour les autres, on dira que c’est ma formulation qui n’était pas très claire. *clin d’oeil*

Alors si vous avez bien compris mon petit speech sur le calcul d’intégrale, vous aurez deviné que pour calculer une aire de façon probabiliste, il faut tirer aléatoirement des points se situant dedans et à l’extérieur de la figure, puis faire le rapport nombre de points dedans / nombre de points total.

Mais comment se servir de l’aire du cercle et du carré pour calculer notre si célèbre nombre irrationnel pi ? De petites lignes de calculs seront plus simple à comprendre que de longues phrase :

Aire du cerle : pi*r²
Aire du carré : (2r)² = 4r²

(pi*r²)/4r² = pi/4 , car les r² s’annulent

Remarquez que si on multiplie ce résultat par quatre on obtient naturellement pi.
d’où pi = 4 * (pi*r²)/4r²

La façon la plus rapide d’utiliser Monte Carlo et de prendre r = 1 et d’inscrire le cercle dans le carré. Ainsi nous tirerons aléatoirement des points dans le carré, l’aire du cercle sera environ égale au nombre de points à l’intérieur de lui divisé par le nombre de points total, qui n’est autre que l’approximation de l’aire du carré. Puis on multiplie ce rapport par quatre pour obtenir pi.

Evidemment, si l’on ne tire que trois ou quatre points au hasard, l’approximation de pi sera ridicule ! Il faut une quantité astronomique de tirages et c’est pour ça qu’on laisse ce genre de simulation à des ordinateurs… enfin, sauf si vous êtes un peu agité du bocal comme ces deux étudiants qui se sont amusés à reproduire cette expérience avec un fusil de chasse et du papier aluminium. Les délires de nos cousins québécois sont parfois incongrus.

Libre à vous d’essayer cela de manière totalement wtf, si vous en avez le temps pourquoi pas ? Sinon j’ai codé pour vous deux scripts en Python (voir source en haut de cet article) pour étudier tout cela. Le premier permet de générer un graphique représentant les points tirés au hasard dans le carré, avec ceux dans le cercle apparaissant en rouge, ainsi que de calculer pi  :

image
– Avec 10 000 tirs, on obtient une valeur de 3,1468 pour pi. l’approximation réelle étant 3,1415

Tandis que le second calcul de pi se fait en fonction du nombre de tirages puis on trace sa courbe. On constate clairement que plus le nombre de tirages est grand, plus l’on se rapproche de notre cher nombre mystérieux :

image
– L’estimation officelle de pi à 3,14159265 est en rouge. Avec un petit nombre de tir, on fluctue énormément avant d’arriver à une approximation plus précise.

Les scripts données nécessite un minimum de connaissance en python pour pouvoir faire apparaître les graphiques. Néanmoins le calcul de pi est très simple. Il consiste en l’algorithme suivant :


for i in range(nb_de_tirs):
x = random.uniform(-1,1)    # Prend un nombre aléatoire dans [-1,1[
y = random .uniform(-1,1)   # car ce sont les limites du carré
if not x**2+y**2 > 1:       # Si x et y vérifient l’équation d’un cercle de rayon 1,
tir_dedans += 1          #  le point est dans le cercle
pi = 4* shoot_inside / nb_de_tirs       # Calcul de pi
print (“Pi vaut: “, pi)                 # Affiche pi dans la console

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s