Revenir
Revenir

Algorithme et programmation

La manière la plus directe pour déterminer l’intégrale d’une fonction continue

Sommaire

Algorithme de calcul approché d'intégralesÉnoncé du problèmeActivité CAPYTALE : calcul approché d'intégrales
Méthodes déterministesMéthode des rectanglesMéthode des trapèzesMéthode de Simpson
Méthode probabiliste : algorithme de Monte-CarloMéthode de Monte-Carlo

Algorithme de calcul approché d'intégrales

Énoncé du problème

La manière la plus directe pour 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. 
Cependant, une telle primitive n’est pas toujours aisée à obtenir. Pour certaines fonctions, il est même sans espoir d’espérer exprimer leurs primitives en utilisant simplement les fonctions de base : c'est par exemple le cas de la fonction
x↦e−x2x\mapsto \mathrm{e}^{-x^2}x↦e−x2
.
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 
fff
continue et positive sur un intervalle 
[a;b][a;b][a;b]
.

Activité CAPYTALE : calcul approché d'intégrales


Méthodes déterministes

Méthode des rectangles

La méthode historique, celle qui explique la notation
∫abf(x)dx\displaystyle\int_a^bf(x)dx∫ab​f(x)dx
, est la méthode des rectangles. 
On divise ainsi l’intervalle
[a,b][a,b][a,b]
 en 
nnn
intervalles de taille
dxdxdx
. On forme alors des rectangles dont l’aire cumulée approchera l'aire sous la courbe. Il y a toutefois trois possibilités pour construire un rectangle entre les abscisses 
xxx
et
x+dxx+dxx+dx
:
    • on le construit d’une hauteur
f(x)f(x)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)f(x+dx)f(x+dx)
 : les sommets en haut à droite de chaque rectangle correspondent à des points de la courbe ;
    • on le construit d’une hauteur
f(x+dx2)f\left(x+\dfrac{dx}{2}\right)f(x+2dx​)
 : les milieux 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.
Pour le premier cas, l’algorithme de calcul de la valeur approchée de
∫abf(x)dx\displaystyle\int_a^bf(x)dx∫ab​f(x)dx
 est le suivant.
Entrées
Une fonction
fff
, deux réels 
aaa
et 
bbb
désignant les bornes d’intégration et un entier naturel non nul 
nnn
 désignant le nombre de subdivisions de l’intervalle 
[a;b][a;b][a;b]
à considérer. On suppose que
a<ba<ba<b
Initialisation
&nbsp;&nbsp;&nbsp;&nbsp;•&nbsp;On assigne à une variable 
xxx
la valeur de 
aaa
.
&nbsp;&nbsp;&nbsp;&nbsp;•&nbsp;On assigne à une variable 
III
la valeur 0.
&nbsp;&nbsp;&nbsp;&nbsp;•&nbsp;On assigne à une variable
dxdxdx
la valeur de 
b−an\dfrac{b-a}{n}nb−a​
.
Algorithme
On répète n fois ce qui suit.
&nbsp;&nbsp;&nbsp;&nbsp;•&nbsp;On ajoute à
III
 la valeur de 
f(x)×dxf(x) \times dxf(x)×dx
 ;
&nbsp;&nbsp;&nbsp;&nbsp;•&nbsp;On ajoute à 
xxx
la valeur de 
dxdxdx
.
&nbsp;&nbsp;&nbsp;&nbsp;•&nbsp;On renvoie la valeur de 
III
.
Exercice
1.En suivant l'algorithme donné précédemment, compléter la fonction Python suivante permettant d'approcher l'aire d'une fonction en utilisant la méthode des rectangles à gauche.
2.Compléter la fonction 
fff
pour qu'elle prenne en argument un réel 
xxx
et renvoie la valeur 
f(x)=x3+2x2−x+3f(x)=x^3+2x^2-x+3f(x)=x3+2x2−x+3
.
3.À l'aide de ces deux fonctions, donner une valeur approchée de
∫14f(x)dx\displaystyle\int_1^4 f(x)dx∫14​f(x)dx
. On prendra 
n=1000n=1000n=1000
.
4.Comparer avec la valeur réelle de cette intégrale, obtenue à l'aide d'une primitive.
def f(x) :
    return ...
def rectangle(f, a, b, n) :
    '''
    Approche l'intégrale de f entre a et b en subdivisant l'intervalle [a,b]
    en n sous-intervalles et en utilisant la méthode des rectangles gauches
    ----------
    Entrées :
    f : une fonction continue dont on souhaite calculer l'intégrale
    a : un réel, borne gauche de l'intervalle d'intégration
    b : un réel, borne droite de l'intervalle d'intégration
    n : un entier, nombre de subdivisions de l'intervalle [a,b]
    ----------
    Sorties :
    I : un réel, valeur approchée de l'intégrale de f
    '''
    x = ...
    I = ...
    dx = ...
    for i in range(...) :
        I = I + ...
        x = x + ...
    return I

Méthode des trapèzes

La méthode des trapèzes ressemble à celle des rectangles, sauf qu’elle utilise… des trapèzes !
On divise toujours l’intervalle
[a,b][a,b][a,b]
 en 
nnn
intervalles de taille
dxdxdx
. 
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é.
La somme des aires des trapèzes ainsi construits fournit une estimation de l’intégrale de notre fonction 
fff
entre 
aaa
et
bbb
. 
Rappelons que l’aire d’un trapèze de hauteur
hhh
, de petite base 
bbb
et de grande base 
BBB
vaut
B+b2×h\dfrac{B+b}{2} \times h2B+b​×h
.
L'algorithme est donc le même que celui des rectangles. La seule différence est que, au lieu d'ajouter à la variable 
III
l'aire du rectangle de largeur 
dxdxdx
et de longueur
f(x)f(x)f(x)
, on ajoute cette fois l'aire d'un trapèze dont les bases sont de longueurs
f(x)f(x)f(x)
 et
f(x+dx)f(x+dx)f(x+dx)
 et dont la hauteur vaut
dxdxdx
.
Exercice
1.Compléter l'algorithme suivant permettant d'implémenter la méthode des trapèzes.
2.Donner une valeur approchée de
∫14(x3+2x2−x+3)dx\displaystyle\int_1^4 (x^3+2x^2-x+3)dx∫14​(x3+2x2−x+3)dx
 en prenant
n=20n=20n=20
. 
3.Comparer ce résultat avec la méthode précédente. Quel algorithme semble plus efficace ?
def trapeze(f, a, b, n) :
    '''
    Approche l'intégrale de f entre a et b en subdivisant l'intervalle [a,b]
    en n sous-intervalles et en utilisant la méthode des trapèzes
    ----------
    Entrées :
    f : une fonction continue dont on souhaite calculer l'intégrale
    a : un réel, borne gauche de l'intervalle d'intégration
    b : un réel, borne droite de l'intervalle d'intégration
    n : un entier, nombre de subdivisions de l'intervalle [a,b]
    ----------
    Sorties :
    I : un réel, valeur approchée de l'intégrale de f
    '''
    x = ...
    I = ...
    dx = ...
    for i in range(n) :
        I = ...
        x = ...
    return I

Méthode de Simpson

La méthode des rectangles approche 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, approche chaque portion de courbe par une fonction affine, éventuellement constante. En d’autres termes, on approche la fonction à l’aide d’une fonction polynomiale 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. La fonction étudiée est donc approchée par une fonction polynômiale de degré au plus 2.
Exercice
On considère un intervalle 
[s;t][s;t][s;t]
et on note 
m=s+t2m=\dfrac{s+t}{2}m=2s+t​
.
On considère la fonction 
P:x↦f(s)(x−t)(x−m)(s−t)(s−m)+f(t)(x−s)(x−m)(t−s)(t−m)+f(m)(x−t)(x−s)(m−t)(m−s)P:x\mapsto 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)}P:x↦f(s)(s−t)(s−m)(x−t)(x−m)​+f(t)(t−s)(t−m)(x−s)(x−m)​+f(m)(m−t)(m−s)(x−t)(x−s)​
1.La fonction 
PPP
est-elle polynômiale ? Quel est son degré ?
2.Calculer 
P(t)P(t)P(t)
, 
P(s)P(s)P(s)
 et 
P(m)P(m)P(m)
.
On utilise alors la fonction 
PPP
définie ci-dessus pour approcher la fonction 
fff
sur l'intervalle
[s;t][s;t][s;t]
.
L'intégrale de
fff
 sur
[s;t][s;t][s;t]
 peut alors être approchée par l'intégrale de
P
sur ce même intervalle.
On peut par ailleurs montrer que
∫stP(x)dx=t−s6×(f(s)+4f(m)+f(t))\displaystyle\int_s^t P(x)dx = \dfrac{t-s}{6} \times (f(s) + 4f(m) + f(t))∫st​P(x)dx=6t−s​×(f(s)+4f(m)+f(t))
.
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 vitesses de convergence des deux méthodes précédentes. Dans le cas suivant, on utilise simplement 3 subdivisions de l'intervalle
[1;4][1;4][1;4]
.
from math import log, sqrt
def fonction(x) :
    return  2*x**2 *log(x) + x - 2*sqrt(x)
def simpson(f, a, b, n) :
    '''
    Approche l'intégrale de f entre a et b en subdivisant l'intervalle [a,b]
    en n sous-intervalles et en utilisant la méthode de Simpson
    ----------
    Entrées :
    f : une fonction continue dont on souhaite calculer l'intégrale
    a : un réel, borne gauche de l'intervalle d'intégration
    b : un réel, borne droite de l'intervalle d'intégration
    n : un entier, nombre de subdivisions de l'intervalle [a,b]
    ----------
    Sorties :
    I : un réel, valeur approchée de l'intégrale de f
    '''
    I = 0
    dx = (b-a) / n
    x = a
    for i in range(n) :
        I += (f(x) + f(x + dx) + 4 * f(x + dx/2)) * dx / 6
        x += dx
    return I
print(simpson(fonction, 1, 4, 3))
#Valeur réelle de l'intégrale : 128ln(64)-95/6, soit environ 43.315

Méthode probabiliste : algorithme de Monte-Carlo

Méthode de Monte-Carlo

On suppose que l’on souhaite intégrer une fonction 
fff
continue et positive sur un intervalle
[a;b][a;b][a;b]
. 
Le principe de l'algorithme de Monte-Carlo est le suivant : 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
fff
. On compte alors la proportion de points sous la courbe parmi ceux tirés au hasard et on utilise cette proportion pour estimer l’intégrale de 
fff
entre 
aaa
et
bbb
.
On note 
MMM
le maximum 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 
CCC
à 0, puis on recommence les étapes suivantes 
nnn
fois.
&nbsp;&nbsp;&nbsp;&nbsp;•&nbsp;On choisit alors un réel au hasard et de manière uniforme sur l’intervalle
[a;b][a;b][a;b]
: on note 
xxx
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.
&nbsp;&nbsp;&nbsp;&nbsp;•&nbsp;On choisit un autre réel 
yyy
au hasard, de manière uniforme et indépendante du premier réel sur l’intervalle
[0;M][0;M][0;M]
.
&nbsp;&nbsp;&nbsp;&nbsp;•&nbsp;Si 
y<f(x)y<f(x)y<f(x)
&nbsp;&nbsp;&nbsp;&nbsp;•&nbsp;On renvoie alors la valeur
Cn×M×(b−a)\dfrac{C}{n} \times M \times (b-a)nC​×M×(b−a)
.
Exercice
1.Expliquer pourquoi la valeur utilisée pour estimer l'intégrale est
Cn×M×(b−a)\dfrac{C}{n} \times M \times (b-a)nC​×M×(b−a)
.
2.Implémenter l'algorithme précédent à l'aide de la fonction suivante.
La fonction uniform permet de choisir un nombre aléatoire de manière uniforme.
3.Utiliser alors cet algorithme pour estimer l'intégrale entre
-1
et
1
de la fonction 
fff
définie par
f(x)=21−x2f(x)=2\sqrt{1-x^2}f(x)=21−x2​
 (on admettra que cette fonction est majorée par 2). Quelle valeur semble-t-on retrouver ?
from random import uniform
from math import sqrt
def f(x) :
    return ...
def montecarlo(f, a, b, M, n):
    '''Estime l'intégrale de f entre a et b à l'aide de la méthode de Monte-Carlo
    --------
    Entrées : 
    f : une fonction continue et positive sur [a,b]
    a : borne inférieure de l'intervalle d'intégration
    b : borne supérieure de l'intervalle d'intégration
    M : maximum ou majorant de la fonction
    n : nombre de points à tirer au hasard
    '''
    C = ...
    for i in range(n):
        x = uniform(a,b)
        y = uniform(0,M)
        if ... :
            C = C + 1
    return ...