> Le Site du Zéro - Informatique

> Cours

> Tutoriels

> Programmation

> Algorithmique

> A la découverte de l'aléatoire et des probabilités

> La méthode de Monte Carlo

> Passez dans les dimensions supérieures

> Lecture du tutoriel

Passez dans les dimensions supérieures

Par

sebsheep

Mise à jour : 25/05/2010

Difficulté : Facile Facile

583 visites depuis 7 jours, dont 30 sur ce chapitre classé 194/786

Nous allons parler ici des fonctions à deux variables. Pourquoi s'arrêter à 2 ? Tout simplement car la difficulté se situe au niveau de passage de la première à la deuxième dimension. Après, une fois qu'on a bien compris comment ça marche, on a compris pour trois, quatre, voire n dimensions (après pour les dimensions infinies, c'est une autre histoire

Retour en haut

Sommaire du chapitre :

Les fonctions à deux variables, ou comment avoir de jolies courbes en 3D
Doublez les intégrales
Et avec Monte Carlo, c'est mieux ?

Retour en haut

Les fonctions à deux variables, ou comment avoir de jolies courbes en 3D

Si vous avez survécu jusqu'ici, vous connaissez parfaitement les fonctions à une variable : f(x) = 4x+5 , par exemple. Cette fonction associe à chaque valeur de $\mathbb{R}$ (l'ensemble de tous les nombres), une autre valeur dans $\mathbb{R}$ . On représente souvent ces fonctions à l'aide d'un graphe en 2 dimensions :

Je pense que je ne vous apprends pas grand chose. Maintenant, au lieu d'associer un point de $\mathbb{R}$ à un autre, nous allons prendre un point $\mathbb{R}\times\mathbb{R} = \mathbb{R}^2$ auquel nous associons un point de $\mathbb{R}$ .

Euh... $\mathbb{R}^2$ ?

Vous connaissez déjà cet espace sans le savoir. $\mathbb{R}$ peut se représenter comme une droite infinie. Eh bien $\mathbb{R}^2$ se représente comme un plan infini (une surface toute plate qui s'étend aussi loin que vous voulez). En général, un "point" de $\mathbb{R}^2$ est noté (x,y).

Une fonction à deux variables est donc quelque chose de la forme : f(x,y)=x*cos(x)+3y*cos(y)+15. Maintenant, si on veut un moyen assez efficace de la représenter, on ne peut plus utiliser un graphe en deux dimensions. On a alors plusieurs possibilités : associer une couleur à un nombre, tracer des lignes de niveaux, ou, si notre carte graphique ne date pas de la préhistoire, utiliser une représentation 3D. C'est ce que nous allons utiliser ici. Par exemple, la fonction que j'ai donnée ci-dessus est représentée par le graphe suivant (j'ai aussi utilisé les couleurs, pour une meilleure lisibilité) :

C'est joli, mais comment ça se lit ?

On peut voir ce graphe comme une carte de relief d'une région vallonnée. Par exemple, vous souhaitez savoir quelle est l'altitude en (2,4) : on se place grâce à la grille en bas (c'est cette grille qui représente $\mathbb{R}^2$ ) sur l'intersection de la ligne 2 et de la colonne 4 ; on "remonte" ensuite pour lire l'altitude ; grâce à la couleur, on voit que c'est autour de 5.

Il y avait bien sûr un moyen plus précis de connaître cette altitude : calculer directement f(2,4) = 2cos(2) + 3*4cos(4) + 15 = 6.32398.

J'anticipe déjà vos questions : "Mais comment tu fais pour faire des jolis graphes comme ça ?". Vous avez deux solutions : soit utiliser Gnuplot directement, soit utiliser un logiciel comme Maxima qui utilise lui-même Gnuplot. Maxima est plus qu'une solution d'affichage, c'est un logiciel complet de calcul formel qui peut résoudre des équations, calculer des intégrales et pleins d'autres choses. Je vous conseille d'utiliser l'interface wxMaxima qui est très conviviale et permet de créer rapidement des courbes sans connaître aucune commande (il existe une autre interface graphique, xMaxima, qui est beaucoup moins pratique à mon goût).

Maintenant que nous avons vu ce qu'était une fonction à deux variables, intéressons-nous à ce que signifie une intégrale de ces fonctions.

Retour en haut

Doublez les intégrales

Juste avant, je vous ai parlé d'intégrales d'une fonction à une variable sur un intervalle, ou autrement dit, un segment ; ce sont des intégrales simples, dans le sens qu'il n'y a qu'une seule variable (et non parce que c'est facile :-°

). Voyons ce que sont les intégrales doubles.

Accrochez-vous bien et prenez votre temps ; cette partie est la plus délicate du tutoriel. Si vous n'êtes pas parfaitement réveillé, faites une sieste et revenez après !

Une histoire de volume

Avec des fonctions à deux variables, on n'intègre plus sur un segment, mais sur une surface ; cette intégrale ne représente plus une aire, mais le volume contenu sous la courbe représentant la fonction. Pour l'instant (pour faire simple), nous intègrerons sur le carré [0,4]x[2,6], c'est à dire l'ensemble des points (x,y) tels que : $0\leq x \leq 4 \ \ et \ \ 2\leq y \leq 6$ . Regardez le schéma à droite pour bien comprendre ce qu'il se passe : en vert, j'ai dessiné le carré [0,4]x[2,6], et en rose transparent, j'ai représenté l'intégrale de la fonction sur ce carré (cette intégrale est donc un volume).

On note ça : $\iint_{ {[0,4]\times [2,6]}} f(x,y) dx\ dy$ .

Notez bien les différences avec la notation précédente :

pour indiquer que l'on intègre sur une surface, on met deux symboles $\int$ au lieu d'un seul ;
il y a deux variations infinitésimales : dx et dy, ces symboles indiquent par rapport à quelles variables on intègre.

Le retour des rectangles

Évidemment, ce qui nous intéresse ici est de calculer ces intégrales. Nous allons commencer par une méthode "classique", qui est l'analogue de la méthode des rectangles en une dimension (celle que nous avons vue juste avant). On va voir que le principe de la méthode est d'utiliser ce qu'on sait déjà faire, c'est à dire calculer des intégrales simples. C'est un procédé assez fréquent en maths : se ramener à des trucs plus simples qu'on sait déjà faire.

Dans la plupart des cas (du moment que vous ne vous frottez pas à l'infini, c'est bon), on a l'égalité suivante :

$\iint_{ {[0,4]\times [2,6]}} f(x,y) dx\ dy = \int_{[0,4]} \left( \int_{[2,6]}f(x,y) dy \right) dx = \int_{[2,6]} \left( \int_{[0,4]}f(x,y) dx \right) dy$

Oui, bien sûr... Et ça veut dire quoi ?

Concrètement, que l'on peut calculer cette intégrale soit en intégrant d'abord par rapport à x, puis, par rapport à y soit dans l'ordre inverse, cela ne change rien (ça paraît "évident", mais malheureusement, cela ne l'est pas). Bon, je sens que c'est un peu abstrait pour vous, voici comment on pourrait calculer cette intégrale avec la méthode des rectangles :

Prenons déjà dx=dy=1 (le calcul aura une grosse erreur, mais c'est juste pour bien comprendre sans s'encombrer de constantes sans intérêt). Je choisis d'intégrer d'abord par rapport à y, autrement dit, je vais calculer :

$I=\int_{[0,4]} \left( \int_{[2,6]}f(x,y) dy \right) dx$

C'est ici que l'astuce du russe intervient :magicien:

: on pose

$g(x) = \left( \int_{[2,6]}f(x,y) dy \right)$

Et ça, on sait très bien le calculer, il suffit d'appliquer la méthode des rectangles vue en première partie. Donc avec notre dy=1, on a :

$g(x) = f(x,2)*1 + f(x,3)*1 + f(x,4)*1 + f(x,5)*1$

(je vous laisse, coder ça en exercice, cela revient pratiquement au même que le code de la première partie).

Et maintenant, on n'a plus qu'à calculer :

$I=\int_{[0,4]}g(x)dx$

ce qui est exactement pareil que ce que l'on a fait avant (remplacez le g par le f

).

Au final, on a :

$I = g(0)*1 + g(1)*1 + g(2)*1 + g(3)*1$
$= f(0,2) + f(0,3) + f(0,4) + f(0,5)$
$+ f(1,2) + f(1,3) + f(1,4) + f(1,5)$
$+f(2,2) + f(2,3) + f(2,4) + f(2,5)$
$+f(3,2) + f(3,3) + f(3,4) + f(3,5)$

Je vous invite très fortement à implémenter cet algo. Toutes les difficultés ont été aplanies, il suffit de manipuler un peu le code donné dans la partie précédente.

Bon, qu'est qu'on a fait en réalité ? Prenez un peu de recul, vous vous rendrez compte que l'on a simplement "quadrillé" notre petit carré ! Pour les intégrales simples, à une dimension, on découpait l'intervalle en petits segments ; ici, c'est le même principe sauf qu'on découpe le grand carré en carrés plus petits.

J'aurais très bien pu commencer à intégrer par rapport à x, on aurait eu :

$g(y)=\left(\int_{[2,6]} f(x,y)dx\right)$

Et en refaisant les mêmes calculs, on serait retombés sur la même chose à la fin.

Commentaires sur la méthode

On se rend compte assez aisément que pour calculer cette intégrale double, on a besoin de deux boucles imbriquées (même si l'imbrication de boucles est cachée par l'utilisation de fonctions intermédiaires). Si on avait une fonction à 3 variables, le calcul de son intégrale (qui n'est donc ni une surface, ni un volume mais un objet de dimension 4 :waw:

) demanderait trois boucles imbriquées.

Et ainsi de suite, pour une fonction à n variables, le calcul de son intégrale demanderait alors n boucles imbriquées. Je ne vous raconte pas la galère pour coder ça

(on peut le faire en utilisant une fonction récursive, mais ça reste assez lourd) !

On voit donc ici une certaine limite de la méthode.

Retour en haut

Et avec Monte Carlo, c'est mieux ?

On commence ici vraiment à toucher l'intérêt de cette méthode. Et cette fois, pas besoin de formules compliquées comme avec la méthode des rectangles, on utilise directement :

$\iint_{ {[0,4]\times [2,6]}} f(x,y) dx\ dy$

Comment ça marche ?

Comme en dimension 1, on va tirer un point (x₁,y₁) dans l'espace sur lequel on veut intégrer (dans notre cas, le carré [0,4]x[2,6]).

Puis on calcule le volume du parallélépipède de base carré [0,4]x[2,6] (les dimensions de ce carré sont :4x4, donc son aire est de 16) de hauteur f(x₁,y₁).

On nomme le volume ainsi calculé V₁.

Il faut bien voir qu'on multiplie f(x₁,y₁) par l'aire de la surface sur laquelle on intègre pour avoir ce volume. C'est important pour la suite d'avoir cette idée en tête.

On calcule de même V₂, V₃, ..., V_n ; puis on fait la moyenne de ce petit monde pour estimer l'intégrale, comme en une dimension.

À vous de jouer !

Je vous propose donc de coder un programme qui calcule l'intégrale de la fonction f(x,y)=x*cos(x)+3y*cos(y)+15 sur le carré [0,4]x[2,6] en utilisant la méthode de Monte Carlo. Vous aurez besoin de la fonction rand_a_b que l'on a définie au chapitre précédent, et de vous inspirer du programme faisant le calcul à une dimension.

Secret (cliquez pour afficher)

Code : C

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

// La fonction a integrer 
double f(double x, double y){return x*cos(x)+3*y*cos(y)+15; }

double rand_0_1(){   return rand()/(double)RAND_MAX; }
double rand_a_b(double a, double b){ return rand_0_1()*(b-a) +a; }

int main(int argc, char *argv[])
{
	double 	volume 	= 0; 
	int 	n       = 0; //le nombre de points a tirer
	int		i;   //le compteur de boucles
	double x,y;	     // (x,y) sera le point que l'on tire au hasard

	printf("Combien de points voulez-vous tirer pour calculer l'integrale ? ");
	scanf("%d",&n);
	
	for( i=0; i < n ; i++) 
	{
		// On tire un point au hasard dans le carre [0,4]x[2,6]
		x = rand_a_b(0,4);
		y = rand_a_b(2,6);
		volume += f(x,y) * 16; // 16 est l'aire du carre
	}
	volume = volume/n;
	
	printf("L'intégrale de la fonction sur le carre [0,4]x[2,6] est estimee a %lf",volume);
	
	return 0;
}

Vous pouvez maintenant tester cet algo. et comparer le résultat avec la valeur exacte : 195.85... Si vous faites le comparatif avec la méthode des rectangles, vous verrez que Monte Carlo ne s'en sort pas trop mal à partir de 1000 tirages.

En réalité, plus la dimension est importante, mieux Monte Carlo s'en sortira par rapport aux méthodes classiques. C'est un résultat qui découle directement du Théorème de la limite centrale. C'est un théorème assez dur que je peux difficilement vous expliquer (cela me prendrait un tutoriel entier), mais pour simplifier très grossièrement, voyez ça comme une application de la loi des grands nombres : si vous lancez 10 fois une pièce, il est très probable que 70% des lancers tombent sur face ; par contre, si vous faites 1000 lancers, il est quasi improbable d'avoir une telle proportion.

Retenez que lorsque la dimension augmente, il devient plus intéressant (moins couteux et plus précis) d'utiliser Monte Carlo. Donc premier avantage !

Les patatoïdes arrivent !

Et nous avons aussi un autre avantage clair en faveur de Monte Carlo : la simplicité du code. Souvenez vous, pour n variables, il fallait n boucles imbriquées. Ici, on voit bien que quel que soit le nombre de variables, on n'a besoin que de la boucle de répétition du tirage (plus éventuellement une boucle pour itérer sur les variables).

L'avantage est déjà flagrant lorsqu'on intègre sur des rectangles, parallélépipèdes ou objets équivalents en dimensions supérieures, mais cet avantage est encore plus marqué lorsqu'on intègre sur des formes un peu plus exotiques. En effet, en prenant un peu de recul, on constate que la méthode des rectangles consiste à quadriller l'espace sur lequel on veut intégrer ; Monte Carlo nous épargne ce travail de quadrillage !

Par exemple, admettons que nous ayons l'idée, humaine, certes, mais bizarre, d'intégrer sur un "patatoïde". Comment ferions nous ?

C'est quoi un patatozormachin ? Encore un mot pour nous embrouiller !

Non ce n'est pas un nom scientifique, juste une vue de l'esprit ; un patatoïde, comme son nom l'indique, désigne tout objet se rapprochant de près ou de (très) loin à une patate (vous noterez la précision de la définition). En fait, je l'emploie pour désigner des formes un peu biscornues et irrégulières, comme ce que vous avez à droite (n'y voyez là aucune tentative de création artistique abstraite, juste un dessin fait avec Gnu Paint en 12 secondes).

Comment appliquer la méthode des rectangles à ce genre de formes ? C'est possible (tout est possible), mais c'est assez dur de faire ça efficacement. Avec Monte Carlo, c'est un jeu d'enfant... Comme lancer des fléchettes sur une cible (attention, Titi revient) !

Mais assez disserté pour ce chapitre ! Vous verez tout ça dans le chapitre qui vient, qui est un TP d'application concret de cette méthode.

Retour en haut

Bravo à vous ! Vous venez de terminer la partie vraiment dure du tuto ; maintenant que vous avez compris, ça va être de la rigolade et vous allez vraiment prendre du plaisir. Félicitations si vous avez tenu jusque là ; honnêtement de mon côté j'ai eu du mal

, j'espère avoir trouvé le juste milieu entre "dire trop de choses pas toutes utiles" et "ne pas donner assez d'explications" ! N'hésitez pas à commenter les parties de ce chapitre (et du précédent) qui vous laissent perplexes, je tenterai de corriger au mieux.

Je conclurais ce chapitre en revenant à ce que nous avons fait au premier chapitre. Pour calculer pi, nous avons en réalité appliqué la méthode de Monte Carlo à une fonction à 2 variables assez simple qui vaut 1 sur le quart de cercle, et 0 partout ailleurs !
Comme quoi, comme M. Jourdain, vous faisiez du Monte Carlo sans le savoir !

Allez, un petit café et on se retrouve au dernier chapitre pour un TP final (à venir prochainement).

Retour en haut

Retour en haut

Lire aussi

	A la découverte de l'aléatoire et des probabilités
	Savez-vous intégrer ?
	Bruits et nombres aléatoires cohérents
	[TP] Le mot mystère

Retour en haut

17 commentaires pour "Passez dans les dimensions supérieures"

Note moyenne : 3.91 / 4 (32 votes)

Pseudo	Commentaire
AstroB	# Posté le 22/07/2009 à 15:38:14
Hey dude! Études : ESTACA	Très intéressant! Je note néanmoins une toute petite erreur à mon avis: Dans la partie "Et avec Monte Carlo, c'est mieux ? " > "Comment sa marche", tu parle de dimension 1, je dirais plutot dimension 2... (dimension 1 = une "ligne" graduée) Mon CV, mes réalisations, mon oeuvre: Programmation, robotique, ferroviaire
nbilal	# Posté le 08/09/2009 à 06:47:16
	Merci pour le tutoriel ! Cependant je trouve qu'il y a un point fondamentale qui manque. Dans les exemples de calcul d'intégrale, par exemple celui d'intégrale simple, tu n'as pas montré pourquoi t'as choisi d'utiliser la surface d'un rectangle pour estimer la surface sous la courbe ( f(x)*x ) et non pas autre forme. Aussi le lien entre le premier et les 2 autres exemple n'est pas montré, à part le fait qu'on calcule la moyenne. Je crois que le lecteur a besoin de comprendre comment définir un essai pour ensuite faire la moyenne.
bluestorm	# Posté le 03/11/2009 à 16:13:29
dont ask to ask Groupe : Anciens Blog Twitter close	Je ne suis pas très convaincu par les arguments du type "simplicité du code" que tu avances. Citation On se rend compte assez aisément que pour calculer cette intégrale double, on a besoin de deux boucles imbriquées (même si l'imbrication de boucles est cachée par l'utilisation de fonctions intermédiaires). Si on avait une fonction à 3 variables, le calcul de son intégrale (qui n'est donc ni une surface, ni un volume mais un objet de dimension 4 ) demanderait trois boucles imbriquées. Et ainsi de suite, pour une fonction à n variables, le calcul de son intégrale demanderait alors n boucles imbriquées. Je ne vous raconte pas la galère pour coder ça (un de mes amis l'a fait en utilisant une fonction récursive, mais ça reste assez lourd) ! On voit donc ici une certaine limite de la méthode. C'est argument n'est pas crédible. Écrire une fonction récursive n'est pas spécialement lourd, et on s'attend à un programmeur qui fait du calcul numérique qu'il maîtrise quand même ce principe, qui est une des bases en informatique. Pour cette raison, je trouve même la formulation "un de mes amis.." un peu 'ridicule' : je ne dis pas ça pour vexer, mais ça fait un peu comme "C'est une rumeur mais il paraît qu'un jour un type a réussi a ...", alors qu'on parle de quelque chose de simple. Tu y reviens dans la deuxième partie : Citation Et nous avons aussi un autre avantage clair en faveur de Monte Carlo : la simplicité du code. Souvenez vous, pour n variables, il fallait n boucles imbriquées. Ici, on voit bien que quel que soit le nombre de variables, on n'a besoin que de la boucle de répétition du tirage (plus éventuellement une boucle pour itérer sur les variables). L'avantage est déjà flagrant lorsqu'on intègre sur des rectangles, parallélépipèdes ou objets équivalents en dimensions supérieures, mais cet avantage est encore plus marqué lorsqu'on intègre sur des formes un peu plus exotiques. En effet, en prenant un peu de recul, on constate que la méthode des rectangles consiste à quadriller l'espace sur lequel on veut intégrer ; Monte Carlo nous épargne ce travail de quadrillage ! D'une part, il suffit effectivement d'un parcours linéaire des points aléatoires, mais tu tires quand même des points aléatoires en dimension N, donc tu as quand même une boucle. Tu as juste rejeté la complexité liée à la dimension dans la fonction de génération du point aléatoire, ça ne rend pas l'ensemble plus simple (puisque l'utilisateur à priori code tout à la fois). D'autre part, je ne comprends pas (mais c'est peut-être moi qui n'ai pas vu quelque chose, je ne connais pas le domaine) en quoi Monte-Carlo est fondamentalement plus efficace sur les patatoïdes. En effet, pour un quadrillage, la méthode la plus simple est de quadriller un rectangle qui encadre le patatoïde, en ne comptant que les points du quadrillage qui sont vraiment à l'intérieur du patatoïde; d'accord, on quadrille plus de points que nécessaire, donc c'est "moins efficace" pour un petit volume dans un gros rectangle. Mais pour Monte-Carlo, comment faire ? La seule idée simple qui me vient à l'esprit est de tirer un point au hasard dans ce même rectangle extérieur, et de ne garder que les tirages qui sont bien tombés dans le pataoïde. J'ai l'impression que cette méthode souffre d'exactement la même source d'inefficacité de la première (indépendamment des considérations de dimension). (Sinon, je trouve évidemment que l'ensemble du tutoriel est bien, je viens du topic "Cours Scolaires" et j'ai été curieux de passer voir le tuto) big tuto algorithmique \| tuto récursivité [PHP] \| tuto typage \| textes divers Ours & Hippy — le blog
robinson des bois	# Posté le 04/01/2012 à 09:26:53
Le fond de l'air est frais Ville : Saint romain lachalm Pays : France métropolitaine	Citation : 11TLP J'aime pas avouer que l'aléatoire soit plus précis que le calcul. Bande de probabilistes, je vous hais. Et je suis même pas encore entré en prépa quoi, je m'attend presque à voir des probas partout. OO Mais non c'est trop bien les probas, c'est par hasard que l'espèce humaine a fait les plus belles découvertes. Très bon tuto pour des personnes post-bac (rien de mieux que 50 pages de rappels sur les intégrales pour bien te dégouter, donc deux c'était parfait ). Par contre je pense qu'il manque une partie sur les moteurs de rendu 3D qui utilisent monté carlo pour leurs calculs. Ça te donnerais un vrais exemple concret pour les personnes qui ne vois pas l’intérêt des intégrales. "Rien n'est plus proche du vrai que le faux." (Albert Einstein) Rien n’est établi "trop rien." (Faignant)
n1co421	# Posté le 19/03/2012 à 15:54:42
	Citation : robinson des bois Par contre je pense qu'il manque une partie sur les moteurs de rendu 3D qui utilisent monté carlo pour leurs calculs. Ça te donnerais un vrais exemple concret pour les personnes qui ne vois pas l’intérêt des intégrales. Genre de commentaire qui me motive à aller plus loin J'étais venu approfondir mes connaissances, et - super tuto je trouve, Bravo - ça m'a permit d'avoir une nouvelle approche grâce aux proba. Et maintenant, bah je vais approfondir avec les intégrales :). Merci pour le lien sur le wikisité, Si j'ai un commentaire constructif a faire, ça serait de dire que je trouve qu'il manque des liens/sources. Mais je vais pas en mourir, je peux bien essayer de le faire tout seul .