Algorithme et programmation

Méthode des rectangles

La méthode historique, celle qui explique la notation

\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 l'aire sous la courbe. Il y a toutefois trois possibilités pour construire un rectangle entre les abscisses 

x

et

x+dx

:

&nbsp;&nbsp;&nbsp;&nbsp;•&nbsp;on le construit d’une hauteur

f(x)

 : les sommets en haut à gauche de chaque rectangle correspondent à des points de la courbe ;

&nbsp;&nbsp;&nbsp;&nbsp;•&nbsp;on le construit d’une hauteur

f(x+dx)

 : les sommets en haut à droite de chaque rectangle correspondent à des points de la courbe ;

&nbsp;&nbsp;&nbsp;&nbsp;•&nbsp;on le construit d’une hauteur

f\left(x+\dfrac{dx}{2}\right)

 : 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

\displaystyle\int_a^bf(x)dx

 est 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

&nbsp;&nbsp;&nbsp;&nbsp;•&nbsp;On assigne à une variable 

x

la valeur de 

a

.

&nbsp;&nbsp;&nbsp;&nbsp;•&nbsp;On assigne à une variable 

I

la valeur 0.

&nbsp;&nbsp;&nbsp;&nbsp;•&nbsp;On assigne à une variable

dx

la valeur de 

\dfrac{b-a}{n}

.

Algorithme

On répète n fois ce qui suit.

&nbsp;&nbsp;&nbsp;&nbsp;•&nbsp;On ajoute à

I

 la valeur de 

f(x) \times dx

;

&nbsp;&nbsp;&nbsp;&nbsp;•&nbsp;On ajoute à 

x

la valeur de 

dx

.

&nbsp;&nbsp;&nbsp;&nbsp;•&nbsp;On renvoie la valeur de 

I

.

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 

f

pour qu'elle prenne en argument un réel 

x

et renvoie la valeur 

f(x)=x^3+2x^2-x+3

.

3.À l'aide de ces deux fonctions, donner une valeur approchée de

\displaystyle\int_1^4 f(x)dx

. On prendra 

n=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]

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é.
La somme des aires des trapèzes ainsi construits fournit 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 

B

vaut

\dfrac{B+b}{2} \times h

.
L'algorithme est donc le même que celui des rectangles. La seule différence est que, au lieu d'ajouter à la variable 

I

l'aire du rectangle de largeur 

dx

et de longueur

f(x)

, on ajoute cette fois l'aire d'un trapèze dont les bases sont de longueurs

f(x)

et

f(x+dx)

 et dont la hauteur vaut

dx

.

Exercice

1.Compléter l'algorithme suivant permettant d'implémenter la méthode des trapèzes.
2.Donner une valeur approchée de

\displaystyle\int_1^4 (x^3+2x^2-x+3)dx

 en prenant

n=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]

et on note 

m=\dfrac{s+t}{2}

.
On considère la fonction 

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)}

1.La fonction 

P

est-elle polynômiale ? Quel est son degré ?

2.Calculer 

P(t)

,

P(s)

et

P(m)

.

On utilise alors la fonction 

P

définie ci-dessus pour approcher la fonction 

f

sur l'intervalle

[s;t]

.
L'intégrale de

f

sur

[s;t]

 peut alors être approchée par l'intégrale de

P

sur ce même intervalle.
On peut par ailleurs montrer que

\displaystyle\int_s^t P(x)dx = \dfrac{t-s}{6} \times (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]

.

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 de Monte-Carlo

On suppose que l’on souhaite intégrer une fonction 

f

continue et positive sur un intervalle

[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

f

. 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 

f

entre 

a

et

b

.

On note 

M

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 

C

à 0, puis on recommence les étapes suivantes 

n

fois.

&nbsp;&nbsp;&nbsp;&nbsp;•&nbsp;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.

&nbsp;&nbsp;&nbsp;&nbsp;•&nbsp;On choisit un autre réel 

y

au hasard, de manière uniforme et indépendante du premier réel sur l’intervalle

[0;M]

.

&nbsp;&nbsp;&nbsp;&nbsp;•&nbsp;Si 

y<f(x)

&nbsp;&nbsp;&nbsp;&nbsp;•&nbsp;On renvoie alors la valeur

\dfrac{C}{n} \times M \times (b-a)

.

Exercice

1.Expliquer pourquoi la valeur utilisée pour estimer l'intégrale est

\dfrac{C}{n} \times M \times (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 

f

définie par

f(x)=2\sqrt{1-x^2}

 (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 ...

Algorithme et programmation

Algorithme de calcul approché d'intégrales

Énoncé du problème

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

Méthodes déterministes

Méthode des rectangles

Méthode des trapèzes

Méthode de Simpson

Méthode probabiliste : algorithme de Monte-Carlo

Méthode de Monte-Carlo