124
4 Intégration et différentiation numérique
sous-intervalles d’intégration de tailles non uniformes. Ainsi, on conserve
la même précision qu’avec la formule composite de Simpson, mais avec
moins de noeuds de quadrature et, par conséquent, moins d’évaluations
de f.
Pour mettre en oeuvre cette méthode et atteindre une tolérance fixée,
on doit trouver un estimateur d’erreur et un procédé automatique pour
modifier le pas d’intégration H. Commençons par analyser ce procédé,
qui est indépendant de la formule de quadrature considérée.
A la première étape de l’algorithme adaptatif, on calcule une approximation I s (f) de I(f) =
b
a
f(x) dx. On pose H = b − a et on essaie
d’estimer l’erreur de quadrature. Si cette erreur est inférieure à la tolérance fixée, on arrête ; sinon le pas H est réduit de moitié jusqu’à ce que
l’intégrale
a+H
a
f(x) dx soit calculée avec la précision voulue. Quand
l’opération réussie, on considère l’intervalle ]a + H, b[ et on répète le
procédé, en choisissant comme premier pas la longueur b − (a + H) de
l’intervalle.
Définissons les notations suivantes :
1. A : l’intervalle d’intégration actif, i.e. l’intervalle où l’intégrale est
en train d’être calculée ;
2. S : l’intervalle d’intégration déjà examiné, pour lequel l’erreur est
inférieure à la tolérance fixée ;
3. N : l’intervalle d’intégration qu’il reste à examiner.
Au début de la procédure, on a A = [a, b], N = ∅ et S = ∅. La situation à
une étape quelconque de l’algorithme est décrite sur la Figure 4.6. Notons
J S (f) la valeur approchée de
α
a
f(x)dx déjà calculée (avec J S (f) = 0 à
l’initialisation) ; si l’algorithme s’achève avec succès, J S (f) contient l’approximation voulue de I(f). Notons aussi J (α,β) (f) l’intégrale approchée
de f sur l’intervalle actif [α, β]. Cet intervalle est dessiné en blanc sur
la Figure 4.6. Une étape type de l’algorithme adaptatif d’intégration se
déroule ainsi :
1. si l’erreur estimée est inférieure à la tolérance fixée, alors :
(i) J S (f) est “augmenté” de J (α,β) (f), c’est-à-dire J S (f) ← J S (f) +
J (α,β) (f) ;
(ii) on pose S ← S ∪ A, A = N , N = ∅ (branche (I) de la Figure
4.6), α ← β et β ← b ;
2. si l’erreur estimée est plus grande que la tolérance fixée, alors :
(j) A est réduit de moitié et le nouvel intervalle actif devient A =
[α, α
] avec α
= (α + β)/2 (branche (II) de la Figure 4.6) ;
(jj) on pose N ← N ∪ [α
, β], β ← α
;
(jjj) une nouvelle estimation de l’erreur est calculée.
4 Intégration et différentiation numérique
sous-intervalles d’intégration de tailles non uniformes. Ainsi, on conserve
la même précision qu’avec la formule composite de Simpson, mais avec
moins de noeuds de quadrature et, par conséquent, moins d’évaluations
de f.
Pour mettre en oeuvre cette méthode et atteindre une tolérance fixée,
on doit trouver un estimateur d’erreur et un procédé automatique pour
modifier le pas d’intégration H. Commençons par analyser ce procédé,
qui est indépendant de la formule de quadrature considérée.
A la première étape de l’algorithme adaptatif, on calcule une approximation I s (f) de I(f) =
b
a
f(x) dx. On pose H = b − a et on essaie
d’estimer l’erreur de quadrature. Si cette erreur est inférieure à la tolérance fixée, on arrête ; sinon le pas H est réduit de moitié jusqu’à ce que
l’intégrale
a+H
a
f(x) dx soit calculée avec la précision voulue. Quand
l’opération réussie, on considère l’intervalle ]a + H, b[ et on répète le
procédé, en choisissant comme premier pas la longueur b − (a + H) de
l’intervalle.
Définissons les notations suivantes :
1. A : l’intervalle d’intégration actif, i.e. l’intervalle où l’intégrale est
en train d’être calculée ;
2. S : l’intervalle d’intégration déjà examiné, pour lequel l’erreur est
inférieure à la tolérance fixée ;
3. N : l’intervalle d’intégration qu’il reste à examiner.
Au début de la procédure, on a A = [a, b], N = ∅ et S = ∅. La situation à
une étape quelconque de l’algorithme est décrite sur la Figure 4.6. Notons
J S (f) la valeur approchée de
α
a
f(x)dx déjà calculée (avec J S (f) = 0 à
l’initialisation) ; si l’algorithme s’achève avec succès, J S (f) contient l’approximation voulue de I(f). Notons aussi J (α,β) (f) l’intégrale approchée
de f sur l’intervalle actif [α, β]. Cet intervalle est dessiné en blanc sur
la Figure 4.6. Une étape type de l’algorithme adaptatif d’intégration se
déroule ainsi :
1. si l’erreur estimée est inférieure à la tolérance fixée, alors :
(i) J S (f) est “augmenté” de J (α,β) (f), c’est-à-dire J S (f) ← J S (f) +
J (α,β) (f) ;
(ii) on pose S ← S ∪ A, A = N , N = ∅ (branche (I) de la Figure
4.6), α ← β et β ← b ;
2. si l’erreur estimée est plus grande que la tolérance fixée, alors :
(j) A est réduit de moitié et le nouvel intervalle actif devient A =
[α, α
] avec α
= (α + β)/2 (branche (II) de la Figure 4.6) ;
(jj) on pose N ← N ∪ [α
, β], β ← α
;
(jjj) une nouvelle estimation de l’erreur est calculée.