Méthode de Monte-Carlo 100958 31684616 2008-07-18T16:03:08Z Sherbrooke 18624 Raccourcir. On appelle '''méthode de Monte-Carlo''' toute méthode visant à calculer une valeur numérique, et utilisant des procédés aléatoires, c'est-à-dire des techniques probabilistes. Le nom de ces méthodes fait allusion aux [[jeu de hasard|jeux de hasard]] pratiqués à [[Monte-Carlo]]. Les méthodes de Monte-Carlo sont particulièrement utilisées pour calculer des intégrales en dimensions plus grandes que 1 (en particulier, pour calculer des surfaces, des volumes, etc.) La méthode de simulation de Monte-Carlo permet aussi d'introduire une approche statistique du risque dans une décision financière. Elle consiste à isoler un certain nombre de variables-clés du projet telles que le chiffre d'affaires ou la marge... et à leur affecter une distribution de probabilités. Pour chacun de ces facteurs, on effectue un grand nombre de tirages aléatoires dans les distributions de probabilité déterminées précédemment, afin de déterminer la probabilité d'occurrence de chacun des résultats. Le véritable développement des méthodes de Monte-Carlo s'est effectué, sous l'impulsion de [[John von Neumann]] et [[Stanislaw Marcin Ulam|Stanislas Ulam]] notamment, lors de la [[Seconde Guerre mondiale]] et des recherches sur la fabrication de la [[Bombe A|bombe atomique]] . Notamment, ils ont utilisé ces méthodes probabilistes pour résoudre des équations aux dérivées partielles dans le cadre de la [[Monte-Carlo N-Particle transport]]. == Théorie == Nous disposons de la définition de l'[[espérance mathématique]] d'une [[fonction (mathématiques)|fonction]] <math>g</math> de variable aléatoire <math>X</math>, selon laquelle <math>E(g(X))=\int_{\Omega}g(x)f_X(x)dx</math> <math>f_X</math> est la fonction de densité. Ceci peut être étendu aux probabilités discrètes en sommant grâce à une mesure <math>\nu</math> discrète, de type [[Dirac]]. L'idée est de produire un échantillon <math>(x_1,x_2,...,x_N)</math> de la loi <math>X</math>, et de calculer un nouvel estimateur dit de Monte-Carlo, à partir de cet échantillon. Cet estimateur est construit à partir de la moyenne empirique, qui est un estimateur sans biais de l'espérance: <math>\tilde{g_N}(x) = \frac{1}{N} \sum_{i=1}^{N} g(x_i)</math> Ceci est l'estimateur de Monte-Carlo. Nous voyons bien qu'en remplaçant l'échantillon par un ensemble de valeurs prises dans le support d'une [[intégrale]], et de la fonction a intégrer, nous pouvons donc construire une approximation de sa valeur, construite statistiquement. == Exemples == === Résolution du Problème du voyageur de commerce === La résolution du [[problème du voyageur de commerce]] est difficile, du fait de la [[complexité]] du problème, l'emploi de méthodes d'[[optimisation]] probabilistes peut s'avérer efficace pour obtenir une approximation de la meilleure solution, en un temps plus court que pour des méthodes déterministes. === Détermination de la valeur de π (pi) === Cette méthode est proche de celle de [[Georges-Louis Leclerc, comte de Buffon|Buffon]]. Soit un point M de coordonnées (x, y), où 0<x<1 et 0<y<1. On tire aléatoirement les valeurs de x et y. Si <math>x^2+y^2<1</math> alors le point M appartient au disque de centre (0,0) de rayon 1. La probabilité que le point M appartienne au disque est π/4. En faisant le rapport du nombre de points dans le disque par rapport au nombre de tirages on obtient une approximation du nombre π/4 si le nombre de tirages est grand. === Détermination de la superficie d'un lac === Cet exemple est un classique en vulgarisation de la méthode de Monte-Carlo. Soit une zone rectangulaire ou carrée dont les côtés sont de longueur connue. Au sein de cette aire se trouve un lac dont la superficie est inconnue. Grâce aux mesures des côtés de la zone, on connaît l'aire du rectangle. Pour trouver l'aire du lac, on demande à une armée de tirer X coups de canon de manière aléatoire sur cette zone. On compte ensuite le nombre N de boulets qui sont restés sur le terrain ; on peut ainsi déterminer le nombre de boulets qui sont tombés dans le lac : X-N. Il suffit ensuite d'établir un rapport entre les valeurs : :<math>\frac{\mathrm{superficie}_{~\mathrm{terrain}}}{\mathrm{superficie}_{~\mathrm{lac}}} = \frac{X}{X-N}</math> :<math>\Longrightarrow \qquad \mathrm{superficie}_{~\mathrm{lac}} = \frac{(X-N)}{X} \ \times \ \mathrm{superficie}_{~\mathrm{terrain}}</math> Par exemple, si le terrain fait 1000 m{{2}}, que l'armée tire 500 boulets et que 100 projectiles sont tombés dans le lac, alors une estimation de la superficie du plan d'eau est de : 100*1000/500 = 200 m{{2}}. [[Image:Montecarlo.svg|center|400px|Estimation de la surface du lac grâce à des tirs d'artillerie aléatoires]] La qualité de l'estimation s'améliore en augmentant le nombre de tirs et en s'assurant que les artilleurs ne visent pas toujours le même endroit mais couvrent bien la zone. Cette dernière remarque est à mettre en parallèle avec la qualité du [[Générateur de nombres aléatoires|générateur aléatoire]] qui est primordiale pour avoir de bons résultats dans la méthode de Monte-Carlo. Un générateur biaisé est comme un canon qui tire toujours au même endroit : les informations qu'il apporte sont réduites. === Application au modèle d'Ising === {{Article détaillé|Modèle d'Ising}} {{...}} == Articles connexes == * [[Simulation informatique]], * Simuler des processus se produisant à des taux connus : [[Méthode de Monte-Carlo cinétique]]. * les techniques les plus efficaces de [[planification de mouvement]] utilisent des algorithmes probabilistes. * Méthodes de réduction de la variance de l'estimateur de Monte Carlo : [[Importance sampling]] * [[Physique statistique]] * [[Filtre particulaire (statistique)|Filtre particulaire]] * [[Algorithme de Las Vegas]] == Bibliographie == * {{en}} Michael Mascagni, ''Advanced Monte Carlo Methods I & II'', Cours du ETH de Zurich (2005/2006). {{pdf}} [http://www.cs.fsu.edu/~mascagni/Lecture_Notes.html Notes de cours]. On pourra également consulter la [http://www.cs.fsu.edu/~mascagni/Advanced_Monte_Carlo_Methods.html page de présentation du cours], qui contient de nombreuses références disponibles au format en pdf. *{{en}} Werner Krauth, [http://www.lpthe.jussieu.fr/DEA/krauth.html ''Introduction to Monte Carlo algorithms''], Notes de cours de l'école d'ete '96 a [[Beg Rohu]] (France) et Budapest. * Simon Léger, ''Monte Carlo pour les nuls'', 2006 {{pdf}} {{Lire en ligne|lien=http://homepages.nyu.edu/~sl1544/MonteCarloNuls.pdf}} *[http://www.datastructures.info/the-monte-carlo-algorithmmethod/ Exemple de calculer pi en utilisant la méthode de Monte Carlo, C++] *[http://www.ina.fr/archivespourtous/index.php?vue=notice&from=fulltext&full=physicien&num_notice=7&total_notices=21 Une explication de la méthode de Monte-Carlo par le physicien Pierre Auger] ==Liens externes== * {{en}} [http://www.vertex42.com/ExcelArticles/mc/MonteCarloSimulation.html Un exemple de simulation Monte-Carlo clair et didactique] L'exemple se base sur la fabrication d'une pièce mécanique à partir de ses composants. {{Portail|mathématiques|physique|finance}} [[Catégorie:Analyse numérique]] [[Catégorie:Algorithme numérique]] [[Catégorie:Probabilités]] [[Catégorie:Physique statistique]] [[cs:Metoda Monte Carlo]] [[da:Monte Carlo-metoder]] [[de:Monte-Carlo-Algorithmus]] [[en:Monte Carlo method]] [[es:Método de Monte Carlo]] [[fi:Monte Carlo -simulaatio]] [[he:שיטת מונטה קרלו]] [[hr:Monte Carlo simulacija]] [[id:Metode Monte Carlo]] [[it:Metodo Monte Carlo]] [[ja:モンテカルロ法]] [[ko:몬테카를로 방법]] [[nl:Monte-Carlosimulatie]] [[no:Monte Carlo-metoden]] [[pl:Metoda Monte Carlo]] [[pt:Método de Monte Carlo]] [[ru:Метод Монте-Карло]] [[simple:Monte Carlo algorithm]] [[su:Metoda Monte Carlo]] [[sv:Monte Carlometoden]] [[vi:Phương pháp Monte Carlo]] [[zh:蒙特·卡罗方法]]