Petit article sans grande prétention sur le plan scientifique, mais intéressant sur le plan des concepts qu'il évoque.
Il m'est arrivé de me demander comment est-ce que l'on estimait le nombre pi, et dans un hasard complet je suis tombé sur un applet java appliquant la méthode de Monte-Carlo pour estimer des surfaces appliquée à la découvert d'une estimation du nombre π.
Méthode de Monte-Carlo : estimation de surface
Tout d'abord i
maginons une surface carré d'environ 1 km de côté, au milieu de cette surface un plan d'eau de forme irrégulière. Notre carré a donc une surface de 1 km². Avec une pièce d'artillerie on tire dans cette surface, on sait que ce canon tire de manière totalement aléatoire sur une surface si réduite.
On compte le nombre de boulets tirés dans notre carré ainsi que le nombre de boulets tirés dans l'eau (un boulet qui arrive dans l'eau est compté comme arrivant dans notre carré).
Au bout de 200 tirs dans le carré, on a compté 140 boulets dans le plan d'eau... Ainsi on évalue la surface du plan d'eau à sept dixième de celle du carré (200/140 = 0,7), donc 0,7 km².
Application à l'estimation du nombre π (pi)
On sait comment estimer la taille d'une surface, il ne reste donc plus qu'à introduire une surface dont le cal
cul necessite π (pi). Ainsi on définit notre problème avec une surface carré de côté 2xr et un disque, qui y est inscrit, de rayon r.
La surface du carré est (2r)²=4r², celle du cercle est πr². Ainsi le rapport entre les tirs totaux et les tirs dans le cercle est théoriquement de πr²/(4r²)=π/4, donc si on appel ce taux de chute dans le cercle τ, on aura 4τ=pi.
Ensuite plutôt que d'utiliser un canon mal réglé, on tentera plutôt de faire un programme de simulation avec un générateur aléatoire de points sur notre surface, et on approxime π (pi) en fonction des résultats statistiques.
On comprend pour une telle méthode l'importance du générateur de nombre aléatoire : si la distribution n'est pas parfaitement aléatoire le modèle est parfaitement biaisé.
La qualité de l'estimation n'est pas formidable, mais on arrive très rapidement à 3,1, et donc une précision d'un dixième. Cela nous permet donc de majorer l'erreur par 0,1, ce qui rapporter à l'ordre de grandeur de π (pi) donne : 0,1/3,1 = 3,2%.
lundi 23 février 2009
Calcul de π (pi) à l'aide d'une méthode de Monte-Carlo
Inscription à :
Publier les commentaires (Atom)
Sympa, mais faut déjà trouver une dizaine de tireurs au canon...je n'imaginais pas ainsi les travaux de géomètre !
RépondreSupprimerJe ne sais pas si cette méthode a déjà été utilisée de manière concrète et si oui combien de tirs ont été effectués.
RépondreSupprimertrès sympa, le coup de canon! Je connaissais la version avec le jeu
RépondreSupprimerde fléchettes, moins destructrice et moins bruyante ;)
Il ne faut pas oublier que toute estimation
Par la méthode Monte Carlo reste une variable
aleatoire. Si on fait deux séries de 200 tirs
on n'aura pas le même résultat!
Il y aussi une autre application intéressante
du principe de calcul de surfaces : le calcul
d'intégrales . Une intégrale est la surface sous
Le graphe de la fontion.
Alors quand on a une intégrale un peu tordue
on sort l'artillerie lourde!
Ca se passe comment autour de l'intégrale ? On échantillone f(x) de manière aléatoire pour avoir une idée de l'allure de la fonction ?
RépondreSupprimerEn fait il y a deux approches de calcul d'une intégrale par simulation Monte Carlo. Elles correspondent à deux interprétations différentes d'une intégrale.
RépondreSupprimerD'un coté, une intégrale représente l'aire comprise entre la courbe d'une fonction et l'axe des abscices. Alors il suffit de tirer d'un canon dans un rectangle entre le min et le max de la fonction et calculer la proportion des boulets tombés sous le graphe.
D'un autre coté l'intégrale est la généralisation de la somme ( d'où d'ailleurs le symbole d'intégrale, c'est un S ancien). Qui dit somme, dit moyenne. Alors pour calculer l'intégrale on peut aussi échantillonner la fonction de façon aléatoire et prendre la moyenne.
Joli, non?
Oui, reste juste à avoir une idée de l'efficacité. Je pense qu'avec une fonction plutôt homogène les résultats doivent être bon, mais avec certaines autres ça ne doit pas être la joie non ?
RépondreSupprimer