Algorithmes de calcul d’intégrales

Accueil » Approfondissement et Grand Oral » Algorithmes de calcul d’intégrales

La manière la plus simple de déterminer l’intégrale d’une fonction continue \(f\) entre deux réels \(a\) et \(b\) est sans doute de déterminer une primitive de cette fonction. Seulement, une telle primitive n’est pas toujours aisée à obtenir (et pour certaines fonctions, il est même sans espoir d’espérer exprimer leurs primitives en utilisant simplement les fonctions de base, comme par exemple la fonction \(x\mapsto e^{-x^2}\)).

En revanche, il est possible d’utiliser différentes méthodes pour approcher cette intégrale. Dans les exemples qui suivent, nous considérerons une fonction \(f\) continue sur un intervalle \([a;b]\)

Méthodes déterministes

Méthode des rectangles

La méthode historique, celle qui donne sa notation \(\displaystyle\displaystyle\int_a^bf(x)dx\) est la méthode des rectangles. On divise ainsi l’intervalle \([a,b]\) en \(n\) intervalles de taille \(dx\).

On forme alors des rectangles dont l’aire cumulée approchera celle de la courbe. Il y a trois possibilités pour construire un rectangle entre les abscisses \(x\) et \(x + dx\) :

  • On le construit d’une hauteur \(f(x)\) : les sommets en haut à gauche de chaque rectangle correspondent à des points de la courbe.
  • On le construit d’une hauteur \(f(x+dx)\) : les sommets en haut à droite de chaque rectangle correspondent à des points de la courbe.
  • On le construit d’une hauteur \(f\left(x+\dfrac{dx}{2}\right)\) : les milieu des côtés hauts de chaque rectangle correspondent à des points de la courbe.

Il s’avère que le rectangle milieu est plus efficace que les deux autres, mais le raisonnement derrière cette affirmation dépasse le cadre des mathématiques de Terminale.

Rendered by QuickLaTeX.com

Rendered by QuickLaTeX.com

Rendered by QuickLaTeX.com

Prenons le premiers cas, l’algorithme de calcul de la valeur approchée de \(\displaystyle\displaystyle\int_a^bf(x)dx\) est donc le suivant :

  • Entrées : une fonction \(f\), deux réels \(a\) et \(b\) désignant les bornes d’intégration et un entier naturel non nul \(n\) désignant le nombre de subdivisions de l’intervalle \([a;b]\) à considérer. On suppose que \(a < b\).
  • Initialisation :
    • On assigne à une variable x la valeur de \(a\).
    • On assigne à une variable \(I\) la valeur 0.
    • On assigne à \(dx\) la valeur de \(\dfrac{b-a}{n}\)
  • On répète \(n\) fois ce qui suit
    • On ajoute à I la valeur de \(f(x)*dx\)
    • On ajoute à \(x\) la valeur de \(dx\)
  • On renvoie la valeur de \(I\).

Une implémentation en Python pourrait être la suivante.

Méthode des trapèzes

La méthode des trapèzes ressembles à celle des rectangles, sauf qu’elle utilise… des trapèzes !

On divise toujours l’intervalle \([a,b]\) en \(n\) intervalles de taille \(dx\). Pour chacun de ces intervalles, on forme alors un trapèze dont le côté haut correspond au segment joignant les deux valeurs de la fonction aux bornes de l’intervalle considéré.

Rendered by QuickLaTeX.com

En ajoutant les aires des trapèzes ainsi construits, on obtient alors une estimation de l’intégrale de notre fonction \(f\) entre \(a\) et \(b\). Rappelons que l’aire d’un trapèze de hauteur \(h\), de petite base \(b\) et de grande base \(N\) vaut \(\frac{B+b}{2} \times h\). L’algorithme utilisée est donc le suivant.

  • Entrées : une fonction \(f\), deux réels \(a\) et \(b\) désignant les bornes d’intégration et un entier naturel non nul \(n\) désignant le nombre de subdivisions de l’intervalle \([a;b]\) à considérer. On suppose que \(a < b\).
  • Initialisation :
    • On assigne à une variable x la valeur de \(a\).
    • On assigne à une variable \(I\) la valeur 0.
    • On assigne à \(dx\) la valeur de \(\dfrac{b-a}{n}\)
  • On répète \(n\) fois ce qui suit
    • On ajoute à I la valeur de \(\dfrac{f(x)+f(x+dx)}{2}*dx\)
    • On ajoute à \(x\) la valeur de \(dx\)
  • On renvoie la valeur de \(I\).

Une implémentation en Python pourrait être la suivante. On peut d’emblée voir que la méthode des trapèzes semble plus efficace que celle des rectangles gauches ou droits : on obtient en 20 subdivisions un résultat déjà plus convaincant qu’en 1000 subdivisions avec la précédente.

Méthode de Simpson

La méthode des rectangles approchait chaque portion de courbe par une fonction constante, c’est-à-dire une fonction polynômiale de degré au plus 0. La méthode des trapèzes, quant à elle, approchait chaque portion de courbe par une fonction affine, éventuellement constante. En d’autres termes, on approchait la fonction à l’aide d’une fonction polynômiale de degré au plus 1. On peut alors naturellement se demander si ces méthodes peuvent s’étendre à des fonctions de degré supérieur… Et en effet, elles le peuvent !

La méthode de Simpson approche chaque portion de courbe par un arc de parabole ou un segment de droite, selon les cas (et donc la fonction par une fonction polynômiale de degré au plus 2).

On considère un intervalle \([s;t]\), et on note \(m=\dfrac{s+t}{2}\). On approche alors la fonction \(f\) sur l’intervalle \([s;t]\) par la fonction polynômiale \(P\) définie pour tout réel \(x\in[s;t]\) par

\[P(x)=f(s) \dfrac{(x-t)(x-m)}{(s-t)(s-m)} + f(t) \dfrac{(x-s)(x-m)}{(t-s)(t-m)} + f(m) \dfrac{(x-t)(x-s)}{(m-t)(m-s)} \]

De cette manière, on a \(P(s)=f(s)\), \(P(t)=f(t)\) et \(P(m)=f(m)\). La courbe de la fonction et l’arc de parabole se croisent donc à des abscisses qui correspondent aux bords gauches et droits de l’intervalle considéré, mais aussi au milieu de cet intervalle.

On approche alors l’intégrale de \(f\) sur \([s;t]\) par l’intégrale de \(P\).

\[\displaystyle\int_{s}^tP(x)dx = \dfrac{t-s}{6}\left(P(s)+4P(m)+P(t)\right) = \dfrac{t-s}{6}\left(f(s)+4f(m)+f(t)\right) \]

Détails du calcul

On a
\[\displaystyle\int _s^tP(x)dx= \displaystyle\int _s^t \left(f(s) \dfrac{(x-t)(x-m)}{(s-t)(s-m)} + f(t) \dfrac{(x-s)(x-m)}{(t-s)(t-m)} + f(m) \dfrac{(x-t)(x-s)}{(m-t)(m-s)} \right)dx\]

On utilise alors la linéarité de l’intégrale, puis on note \(r\) le rayon de l’intervalle \([s;t]\). On a donc \(t-s=2r\) et \(t-m=m-s=r\). Ainsi,

\[\displaystyle\int _s^tP(x)dx= \dfrac{f(s)}{2r^2} \displaystyle\int _s^t (x-t)(x-m)dx + \dfrac{f(t)}{2r^2} \displaystyle\int _s^t (x-s)(x-m)dx – \dfrac{f(m)}{r^2} \displaystyle\int _s^t (x-t)(x-s)dx\]

Il nous reste alors à calculer ces trois intégrales. Pour cela, nous utiliserons le fait que \(m\) est le milieu de l’intervalle \([s:t]\) et nous allons découper judicieusement les facteurs dans l’intégrale.

Ainsi,
\[\renewcommand{\arraystretch}{2.5}\begin{array}{lll}\displaystyle\int _s^t (x-t)(x-m)dx &=& \displaystyle\int _s^t (x-m+m-t)(x-m)dx \\&=& \displaystyle\int _s^t (x-m)^2dx + (m-t)\displaystyle\int _s^t (x-m)dx\end{array}\]

Il nous reste alors à intégrer ces deux expressions

\[\displaystyle\int _s^t (x-t)(x-m)dx = \left[\dfrac{(x-m)^3}{3}\right]_s^t + (m-t)\left[\dfrac{(x-m)^2}{2}\right]_s^tdx\]

On rappelle alors que \(t-m=r\) et que \(s-m=-r\). Ainsi,

\[\renewcommand{\arraystretch}{2.5}\begin{array}{lll}\displaystyle\int _s^t (x-t)(x-m)dx &= & \dfrac{(t-m)^3}{3} – \dfrac{(s-m)^3}{3} + (m-t)\left(\dfrac{(t-m)^2}{2} -\dfrac{(s-m)^2}{2}\right) \\& =& \dfrac{r^3}{3}-\left(\dfrac{-r^3}{3}\right)+(m-t)\left(\dfrac{r^2}{2}-\dfrac{r^2}{2}\right)\\&=&\dfrac{2r^3}{3}\end{array}\]

Ainsi,
\[ \dfrac{f(s)}{2r^2} \times \displaystyle\int _s^t (x-t)(x-m)dx = \dfrac{f(s)}{2r^2} \times \dfrac{2r^3}{3} = \dfrac{2r}{6}f(s) = \dfrac{t-s}{6}f(s)\]

En utilisant la même méthode, on trouve que

\[ \dfrac{f(t)}{2r^2} \times \displaystyle\int _s^t (x-s)(x-m)dx = \dfrac{t-s}{6}f(t)\]

Il reste alors à déterminer la valeur de la dernière intégrale. Nous utiliserons le même procédé

\[\renewcommand{\arraystretch}{2.5}\begin{array}{lll}\displaystyle\int _s^t (x-t)(x-s)dx &= &\displaystyle\int _s^t (x-m+m-t)(x-m+m-s)dx \\ &=& \displaystyle\int _s^t (x-m-r)(x-m+r)dx \\&=& \displaystyle\int _s^t (x-m)^2dx – \displaystyle\int _s^t r^2dx \end{array}\]

On a vu précédemment que

\[\displaystyle\int _s^t (x-m)^2dx = \dfrac{2r^3}{3}\]

Par ailleurs,

\[\displaystyle\int _s^t r^2dx = r^2(t-s)=r^2 \times 2r = 2r^3\]

Ainsi,

\[\displaystyle\int _s^t (x-t)(x-s)dx = \dfrac{2r^3}{3}-2r^3=-\dfrac{4r^3}{3}\]

Il en vient que

\[- \dfrac{f(m)}{r^2} \times \displaystyle\int _s^t (x-t)(x-s)dx = – \dfrac{f(m)}{r^2} \times \left(-\dfrac{4r^3}{3}\right)= 4f(m) \times \dfrac{r}{3} = 4f(m) \times \dfrac{s-t}{6}\]

En réinjectant tout ceci dans la première expression et en factorisant par \(\dfrac{s-t}{6}\), on obtient l’expression voulue, à savoir,

\[\displaystyle\int_{s}^tP(x)dx = \dfrac{t-s}{6}\left(P(s)+4P(m)+P(t)\right) \]

Il suffit alors d’utiliser cette approximation sur chaque sous-intervalle sur lequel on souhaite intégrer notre fonction \(f\) pour obtenir une valeur approchée de son intégrale sur ce segment, ce qui conduit à l’algorithme suivant :

  • Entrées : une fonction \(f\), deux réels \(a\) et \(b\) désignant les bornes d’intégration et un entier naturel non nul \(n\) désignant le nombre de subdivisions de l’intervalle \([a;b]\) à considérer. On suppose que \(a < b\).
  • Initialisation :
    • On assigne à une variable x la valeur de \(a\).
    • On assigne à une variable \(I\) la valeur 0.
    • On assigne à \(dx\) la valeur de \(\dfrac{b-a}{n}\)
  • On répète \(n\) fois ce qui suit
    • On ajoute à I la valeur de \(\left(\dfrac{f(x)+f(x+dx)+4f\left(x+\frac{dx}{2}\right)}{6}\right)*dx\)
    • On ajoute à \(x\) la valeur de \(dx\)
  • On renvoie la valeur de \(I\).

Là encore, on peut l’implémenter en Python pour se rendre compte de la vitesse de convergence de cette méthode, qui surpasse les deux autres.

Méthode probabiliste : Monte-Carlo

Bien que cette méthode soit relativement peu efficace et anecdotique comparée aux précédentes, on peut la voir apparaître dans le programme de Terminale Générale, en tant qu’approfondissement proposé.

On suppose que l’on souhaite intégrer une fonction \(f\) continue et positive sur un intervalle \([a,b]\). On note \(M\) le maximums de notre fonction sur cet intervalle (celui-ci existe bel et bien, en vertu du théorème de Weierstrass que vous rencontrerez lors de vos études supérieures.). Si l’on ne parvient pas à le déterminer directement, on peut tout aussi bien se contenter d’un majorant.

On initialise un compteur \(C\) à 0, puis on recommence les étapes suivantes autant de fois que voulu :

  • On choisit alors un réel au hasard et de manière uniforme sur l’intervalle \([a;b]\) : on note \(x\) ce réel. Le programme ne parle pas de telles lois de probabilités sur des espaces continus, mais nous laisserons Python s’en charger pour nous.
  • On choisit un autre réel au hasard, de manière uniforme et indépendante du premier réel sur l’intervalle \([0;M]\).
  • Si \(y < f(x)\), on incrémente le compteur \(C\) de 1. Sinon, on ne fait rien.
  • On divise le compteur par le nombre de couples tirés pour obtenir une estimation de notre intégrale

L’idée est assez simple : on prend un point au hasard dans le plan et on regarde si celui-ci est au-dessus ou en-dessous de la courbe représentative de la fonction \(f\). On compte alors la proportion de points sous la courbe parmi ceux tirés au hasard et on utilise cette proportion comme estimation de l’intégrale de \(f\) entre \(a\) et \(b\).

Accueil » Approfondissement et Grand Oral » Algorithmes de calcul d’intégrales