Aller au menu - Aller au contenu

2 541 Zéros connectés
298 519 Zéros inscrits
Inscription
Connexion
- Pseudo
- Mot de passe
- Mot de passe oublié ?
- Connexion auto.
- Connexion avec un compte :

Informatique
- Informatique
- Sciences
- Cours
- Forums
- Participez
- Études
- Emploi
- Boutique
+

> 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

> Savez-vous intégrer ?

> Lecture du tutoriel

Savez-vous intégrer ?

Par

sebsheep

Mise à jour : 25/05/2010

Difficulté : Facile Facile

Facile

Creative Commons BY

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

Nous l'avons vu dans le chapitre précédent, les méthodes de Monte Carlo peuvent servir à calculer des surfaces (il existe d'autres méthodes dites de "Monte Carlo" dont je ne parlerai pas ici). En réalité, nous avons calculé ce qu'on appelle une intégrale... Non, ne partez pas ! Bon tant pis, je continue tout seul. Mais qu'est-ce qu'une intégrale ?

Nous allons voir donc dans cette partie ce qu'est une intégrale, une méthode "classique" de calcul d'une intégrale, puis un calcul par Monte Carlo. Cela nous permettra de comparer les deux méthodes.

Pour aborder ce tutoriel tranquillement, vous devez parfaitement maitriser les notions de fonction et de représentation d'une fonction.

Ce chapitre renvoie à d'autres articles du Web (notamment un tutoriel du SdZ) ou techniques mathématiques. Cependant, le tutoriel a été pensé pour se suffire à lui-même. Admettez donc les choses en première lecture pour ne pas vous embrouiller ; mais plus tard, n'hésitez pas à suivre les liens ou faire des recherches sur les sujets vous intéressant.

Sommaire du chapitre :

Icône du chapitre

Définissons les choses
Une méthode de calcul classique
Le calcul par Monte Carlo

Chapitre précédent

Sommaire

Chapitre suivant

Définissons les choses

Intégrale de f de 1 à 4

De façon simple, l'intégrale d'une fonction positive f entre deux points a et b peut-être vue comme la surface sous la courbe représentant f entre x=a et x=b. On note cette surface : $\int_{[a,b]} f(x)dx$ (lire : "l'intégrale de f entre a et b" ; on dira aussi que l'on "intègre f sur l'intervalle [a,b]"). Sur l'image de droite, la partie rose saumon correspond à l'intégrale de 1 à 4 de la fonction f(x) = x³-5x²+20 représentée en bleu. Dans ce cas, on note alors : $\int_{[1,4]}(x^3-5x^2+20)dx$ .

En Terminale, on utilise plus la notation : $\int_a^b f(x)dx$ . Cela revient exactement au même, mais lorsque nous verrons les intégrales doubles un peu plus loin, cette notation ne sera pas très commode à utiliser.

Mais si la fonction est négative, ce n'est pas défini ?

Si, mais cela ne nous sera pas utile pour ce tutoriel. Si vous voulez en savoir plus, soit vous attendez patiemment la Terminale, soit vous vous renseignez sur Wikiversité. Sachez tout de même que tout ce je vais dire par la suite est vrai quel que soit le signe de f.

Revenons maintenant à la notation $\int_{[a,b]} f(x)dx$ . Elle va nous aider à mieux cerner le problème. Le dx représente une variation infinitésimale (=infiniment petite) de x. L'idée est de considérer que sur un intervalle [x,x+dx] la fonction est constante (vu que c'est un intervalle infiniment petit, ça se comprend). Dans ce cas-là, la "surface sous la courbe" entre x et x+dx est un rectangle de hauteur f(x) et de largeur dx dont l'aire est donnée par f(x)dx (comprendre f(x) fois dx).

Le symbole $\int$ est en réalité une sorte de S un peu stylisé, pour "Somme". Donc lorsqu'on le met devant l'expression f(x)dx, cela signifie que l'on va sommer (additionner) l'aire de tous les petits rectangles :

Intégrale découpée

Cette figure n'est qu'un schéma, elle ne reflète pas vraiment la réalité de l'intégrale. Il faudrait pour cela diminuer dx "à l'infini" ; le nombre de rectangles deviendrait lui, infini (vous comprendrez pourquoi je ne peux donc pas le représenter correctement sur un dessin

).

Une méthode de calcul classique

Cependant, cette représentation va nous servir pour calculer ces intégrales. Nous allons calculer l'aire de chacun des rectangles, puis les additionner. Comme vous le voyez sur la figure ci-dessus, nous commettrons bien sûr une erreur car si f décroît entre x et x+dx, nous allons compter de la surface "en trop" ; à l'inverse, si elle croît, nous allons en oublier. Cette erreur peut facilement être réduite en prenant dx plus petit (il y aura donc plus de rectangles, donc le calcul prendra plus longtemps).

Seule petite contrainte "pratique", il faut qu'un nombre entier de rectangles recouvre l'intervalle. Donc au lieu de choisir arbitrairement dx et avoir toutes les chances que "ça ne tombe pas juste", nous allons choisir le nombre de rectangles et en déduire dx.

Tentons donc de calculer l'aire de la surface rose saumon dont je vous bassine depuis le début. La longueur de l'intervalle est de 3 (= 4-1). Donc si je le découpe en n parties, on aura dx=3/n.

À la main

Pour rendre le calcul simple, prenons n=4. Comme cela, on pourra écrire tous les détails du calcul. Nous avons donc : dx=3/4=0.75. On calcule l'aire du premier rectangle en x=1 : sa hauteur est f(1)=16, sa largeur 0.75, son aire est donc de 16*0.75=12. Et de même pour les trois autres rectangles.

Au final, on a donc :

$\int_1^4 (x^3-5x^2+20)dx \simeq f(1)\times 0.75 + f(1.75)\times 0.75 + f(2.5)\times 0.75 + f(3.25)\times 0.75 =23.95$

Remarquez bien qu'on n'évalue pas f(4), chaque multiplication correspond aux aires des rectangles situés respectivement : entre 1 et 1.75, 1.75 et 2.5, 2.5 et 3.25, 3.25 et 4. Tout l'intervalle est donc bien couvert, pas besoin d'aller plus loin !

Vous allez le voir un peu plus bas, notre calcul comporte une assez grosse imprécision, que nous voulons évidemment réduire. L'un des moyens est d'augmenter considérablement le nombre de rectangles ; mais vous vous doutez bien qu'on ne va pas s'amuser à calculer ces intégrales à la main lorsqu'on a 2000 rectangles (même votre prof de maths ne serait pas assez fou pour ça).

Grâce à notre ordinateur

Je vous laisse chercher comment coder ça. Pour faire simple, contentez-vous de demander à l'utilisateur le nombre de rectangles à utiliser pour le calcul. Ne tentez pas de faire saisir une fonction à l'utilisateur, cela vous demanderait trop de travail en C (par contre si vous utilisez un langage de script, avec la fonction eval, c'est un jeu d'enfant).
Secret (cliquez pour afficher)

Code : C

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

// La fonction a intégrer : f(x)=x^3 - 5x^2 +20
double f(double x){return x*x*x - 5*x*x + 20; }

int main(int argc, char *argv[])
{
  double surface = 0;
  double dx=0;
  double x=0;
  int n=0;
  
  printf("En combien de parties voulez-vous decouper l'intervalle [1,4]? ");
  scanf("%d",&n);
  
  // Détermination du dx
  dx = 3./n;
  // On intègre de 1 a 4 avec un pas de dx
  for( x=1 ; x<4 ; x+=dx )
  {
	// Calcul de l'aire de chaque petit rectangle que l'on ajoute à la surface totale
	surface += f(x)*dx;
  }
  
  printf("L'integrale de f entre 1 et 4 est approximee par %lf \n",surface);
  
  return 0;
}

Les lecteurs attentifs auront remarqué que j'ai utilisé le verbe "estimer" pour la méthode de Monte Carlo et "approximer" pour cette méthode. Même si ces deux mots semblent proches, il y a une différence fondamentale entre les deux : lorsqu'on "estime", on a en général aucune idée sur l'erreur que l'on commet ; lorsqu'on "approxime", oui. Ce calcul d'erreur est un aspect fondamental des méthodes que je vous présentent, mais demande une analyse mathématique trop poussée pour être développée ici.

Le résultat pour 100 rectangles est de 19.05, et pour 1000 rectangles, il est de 18.77. Cette fonction étant relativement simple, il existe des moyens de calculer exactement son intégrale (cf. cours de Terminale) ; ce calcul nous donne 18.75. On voit donc que notre approximation n'est pas trop mauvaise, mais avoir une telle erreur avec 1000 rectangles est une bien piètre performance, faites moi confiance. Il existe d'autres méthodes que celle-ci (qui est appelée tout simplement "méthode des rectangles"), comme la méthode des trapèzes, de Simpson (rien à voir avec Bart ou Homer

) ou de Newton-Cotes. Ces méthodes sont (beaucoup) plus efficaces mais reposent sur le même principe de base : découper l'intervalle en plusieurs parties sur lesquelles on approche f par quelque chose de plus simple.

Vous allez me dire : "C'est bien beau tout ça, mais c'est quoi le rapport avec Monte Carlo ?". Pour l'instant, aucun. Mais nous allons voir dans le chapitre qui vient comment Monte Carlo peut nous aider à calculer cette intégrale d'une manière complètement différente que celle que nous avons vue.

Le calcul par Monte Carlo

L'idée de l'algorithme

L'idée de l'algorithme de Monte Carlo est très simple : on tire un point x₁ au hasard dans l'intervalle [a,b] sur lequel on veut intégrer, et on considère que la fonction vaut f(x₁) sur tout l'intervalle. Son aire est donc : "longueur de l'intervalle"*f(x₁) = (b-a)*f(x₁). Notons cette aire A₀.

Évidement, si on s'arrête ici, le résultat a toutes les chances d'être très faux. On va donc recommencer avec d'autres nombres x₂, x₃, x₄, ..., x_n. Et de la même façon, on aura A₂=(b-a)*f(x₂), A₃=(b-a)*f(x₃), ..., A_n=(b-a)*f(x_n).

Mais ça revient au même ! Toutes ces aires sont aussi fausses que la première !

Très juste ! Mais maintenant, on en a beaucoup (n pour être précis

). Et lorsqu'on a un grand nombre de données aléatoires mesurant un paramètre, ce paramètre est - à peu près - égal à la moyenne de ces données.

Vous n'avez rien compris à cette phrase ? C'est pourtant un principe que vous appliquez tout le temps ; par exemple à l'école : une note à un contrôle ne veut pas dire grand chose (il se peut que vous ayez cramé votre carte mère, le drame affreux qui vous empêche de vous concentrer). Donc pour évaluer votre niveau, vos profs vont prendre plusieurs notes (qui, prises séparément n'ont pas de sens) et en faire cette fameuse moyenne (qui elle a un sens).

En théorie, cette moyenne reflète votre niveau et vous permettra (ou pas) d'accéder aux écoles de vos rêves (je dis bien en théorie car je ne suis pas convaincu qu'une note puisse refléter un quelconque niveau

).

Avec les aires que nous avons calculées, c'est la même chose. L'estimation de l'intégrale s'écrit donc :

$\int_1^4 f(x)dx \simeq \frac{A_1 + A_2 + ... + A_n}{n}$ Image utilisateur

Image utilisateur

Le calcul concret

Je ne vous ferai pas l'affront de faire le calcul pour un n petit, vous pouvez le faire par vous-mêmes ; d'autant que si le nombre de tirages n'est pas très important, de par la nature de la méthode, le résultat sera entaché d'une erreur. Passons donc directement à son implémentation.

Il nous manque une petite fonctionnalité pour écrire cet algo. : tirer un nombre au hasard compris entre deux autres. On peut faire ça en réutilisant la fonction rand_0_1 (je vous renvoie encore une fois au tutoriel de Natim sur le sujet) :

Code : C

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

Je ne donne que le "cœur" du programme, le reste changeant très peu ; il suffit donc de remplacer la boucle for du programme précédent par celle-ci (et le texte demandant le nombre de rectangles par un texte demandant le nombre de points à tirer) :

Code : C

int i;
for( i = 0 ; i<n ; i++) 
{
    // On tire un point au hasard :
    x = rand_a_b(1,4);
    // Calcul de l'aire du rectangle que l'on ajoute à la surface totale 
    surface += f(x)*3; // (3=4-1 est la  longueur de l'intervalle [1,4])
}
// On divise par N pour avoir la moyenne
surface = surface / n;

Ici, nous n'avons aucun moyen de connaître l'erreur, donc nous n'avons pas approximé, mais estimé la valeur de l'intégrale.

J'ai fait tourner l'algo. et c'est complètement pourri ! Avec la méthode des rectangles, on avait beaucoup plus de précision et le code n'était pas plus compliqué. Monte Carlo ça sert à quoi finalement ?

Effectivement, sur cet exemple, l'intérêt de la méthode n'est pas encore évident. Je voudrais quand même vous faire remarquer que si on tire un nombre infini de points, cette méthode est équivalente à la méthode des rectangles. L'infini est un bien beau concept, mais malheureusement ce n'est qu'un concept, non approchable dans la pratique ; donc en pratique, la méthode des rectangles sera bien plus efficace que Monte Carlo pour calculer cette intégrale.

Pour commencer à voir où Monte Carlo sera efficace, il faut voir ce qu'il en est du calcul intégral d'une fonction... à deux variables ! Accrochez-vous bien, le chapitre suivant va un peu décoiffer, mais le résultat vaudra le coup.

Chapitre précédent

Sommaire

Chapitre suivant

Partager

Partager via Email

Partager via Twitter

Partager via Facebook

Imprimer

Lire aussi

	A la découverte de l'aléatoire et des probabilités
	Passez dans les dimensions supérieures
	Calculons pi !
	L'aléatoire en C et C++ : se servir de rand

12 commentaires pour "Savez-vous intégrer ?"

Note moyenne : 3.91 / 4 (32 votes)

Pseudo	Commentaire
sebsheep	# Posté le 23/06/2009 à 21:50:13
Avis : Très bon Études : Universite Paris Sud 11	oui ici: http://www.siteduzero.com/tutoriel-3-6 [...] nt-a-tex.html "Il y a deux choses infinies dans le monde : l'univers et la bêtise humaine ... mais pour l'univers j'ai un doute" Tuto sur l'aléatoire et les probabilités. Un aperçu de Monte Carlo
robocop	# Posté le 24/06/2009 à 14:50:48
Études : Lycée Condorcet - Paris 9ème	Bonjour. Je suis en première, donc, ce que je vais dire est potentiellement faux (je n'ai pas vu l'intégrale autrement qu'en survolant ce tutoriel) , mais, il semblerait que les deux méthodes présentées soient exactement les mêmes. La première parcourt la fonction sur l'intervalle [a;b] : $S = f(a_1)e+f(a_2)e+f(a_3)e+...+f(a_n)e$ et $en = ab$ (en distance) D'ou : $S = e(f(a_1)+f(a_2)+f(a_3)+...+f(a_n))$ La deuxième prend n valeurs au hasard dans [a;b]. Le meilleur résultat sera obtenu si les n valeurs sont a1,a2,a3,...,an (bien que ça ne soit pas toujours vrai, mais pour les fonctions classiques, ça doit être pas mal). S est alors calculé comme ça : $S = \frac{f(a_1)L + f(a_2)L + ... + f(a_n)L}{n}$ avec L = ab (toujours en distance). Donc : $S = \frac{L}{n}(f(a_1)+f(a_2)+...+f(a_n))$ Or, $en = ab$ et $L = ab$ donc $en = L$ . Donc $e = L/n$ . Donc : $\frac{L}{n}(f(a_1)+f(a_2)+...+f(a_n)) = e(f(a_1)+f(a_2)+f(a_3)+...+f(a_n))$ On se rend compte que les deux méthodes sont strictement identiques si le tirage est optimal. Or, le tirage n'est jamais optimal, donc la première méthode est toujours meilleure que la deuxième. Quand tu dérives une fonction à n variables, dans la première méthode, tu prends n*n valeurs, et dans la deuxième, si on veut rester cohérant, il faudrait prendre autant de valeurs (sinon, on a pas la même erreur). Tu auras toujours plus d'erreurs dans le deuxième cas, donc ta méthode, quelque soit le nombre de variables est moins bonne. Certe, elle est plus simple à programmer, mais bon, on s'en sort très bien avec deux fonctions respectivement récursives. Ensuite, reste encore le cas du patatoïde dans le chapitre d'après. Au fait, dans le premièr cas, on délimiterait un rectangle plus grand que le patatoïde, on le parcourait, et on regarde à chaque fois que la valeur appartient bien à la patate (naïvement du moins). Dans le second, on prend une valeure dans le rectangle au hasard; on vérifie qu'elle appartient au patatoïde. Bref ça revient au même, et encore une fois, les valeurs tirées aléatoirements dans la seconde méthode ne sont pas optimales, donc la première donnera une meilleure précision. Conclusion : La méthode avec Monte Carlos n'a absolument aucun avantage sur la première, malgrès ce que tu dis. C'est en fait la même méthode, en moins bien, car le hasard fait mal les choses. (Sauf si je me suis trompé, dans ce cas la, merci de m'expliquer). Dans tout les cas, je te souhaite une bonne continuation, car tu as tu te donner du mal pour sortir ce tutoriel. Cordialement, Robocop/ Construisez votre robot sur robotix \| Tutoriel : Calcul d'une expression mathématique
sebsheep	# Posté le 24/06/2009 à 21:42:11
Avis : Très bon Études : Universite Paris Sud 11	Malgré ton message un peu fouilli, tu poses les bonnes question ! Je prendrai le temps de répondre correctement à tes remarques avant la fin de la semaine (je n'ai pas envie de bacler l'explication) et effectivement, je me suis donné du mal pour sortir ce tuto "Il y a deux choses infinies dans le monde : l'univers et la bêtise humaine ... mais pour l'univers j'ai un doute" Tuto sur l'aléatoire et les probabilités. Un aperçu de Monte Carlo
robocop	# Posté le 31/07/2009 à 22:48:23
Études : Lycée Condorcet - Paris 9ème	Bien que ça date, je suis toujours interessé par tes explications. Construisez votre robot sur robotix \| Tutoriel : Calcul d'une expression mathématique
sebsheep	# Posté le 14/05/2010 à 19:54:55
Avis : Très bon Études : Universite Paris Sud 11	Je réponds un peu tard, mais mieux vaut tard que jamais. Alors oui, les 2 méthodes sont les mêmes si tu prends un tirage aléatoire "parfaitement distribué". Si tu as compris ça, c'est très bien. Le tirage aléatoire te permet en fait de te décharger du travail de quadrillage que t'impose la méthode des rectangles. Et oui, tu as raison, en dimensions 2, si on découpe notre surface en nn carrés, il faut faire nn tirages aléatoires pour avoir la même précision. Et tu as des méthodes (cf "Simuler une distribution géométrique de cartes") qui te permettent de tirer de façon uniforme très rapidement dans une surface donnée (qui peut être un peu tarabiscotée). Donc ça t'évite un quadrillage fastidieux et des rejets en pagailles. Tu dis aussi que "le hasard fait mal les choses" ... eh bien non ! Quand le nombre de dimension augmente, la convergence de Monte Carlo reste "lente" mais elle ne dépend pas du nombre de dimensions, contrairement aux méthodes déterministes. Autre argument : les méthodes "de rectangles" convergent très vite lorsque ta fonction est régulière ("lisse", continue). Ce n'est pas le cas pour des fonctions très irrégulières (continues nulle part par exemple). Tu peux même ne pas avoir convergence de ces méthodes pour des fonctions très "moche". Pour Monte Carlo, la convergence ne dépend pas de la régularité de la fonction, donc on peut dire, (en faisant un mauvais jeu de mot probabiliste) que dans presque tous les cas, cette méthode converge lentement mais surement. En résumé, Monte Carlo n'est pas LA méthode à utiliser lorsqu'on veut faire de l'intégration numérique. C'est UNE méthode qui répond à certaines contraintes. "Il y a deux choses infinies dans le monde : l'univers et la bêtise humaine ... mais pour l'univers j'ai un doute" Tuto sur l'aléatoire et les probabilités. Un aperçu de Monte Carlo

Voir tous les commentaires

Ce tutoriel a été corrigé par les zCorrecteurs.