8.6 Int´ egration automatique
315
a
α
b
b
b
α
β
S
A
N
(I)
S
a
a
α
A
α
S
A
N
(II)
Fig. 8.3. Distribution des intervalles d’int´ egration `
a une ´ etape de l’algorithme adaptatif et mise `
a jour de la grille d’int´ egration
1. A : l’intervalle d’int´ egration actif, i.e. l’intervalle o` u l’int´ egrale doit ˆ etre
calcul´ ee ;
2. S : l’intervalle d’int´ egration d´ ej` a examin´ e, sur lequel le test d’erreur (8.40)
a ´ et´ e effectu´ e avec succ` es ;
3. N : l’intervalle d’int´ egration `
a examiner.
Au d´ ebut de l’algorithme d’int´ egration on a N = [a, b], A = N et S = ∅ ; la
situation `
a une ´ etape quelconque de l’algorithme est d´ ecrite sur la Figure 8.3.
On a J S (f)
α
a
f(x)dx, avec J S (f) = 0 au d´ ebut du processus ; si l’algorithme s’ach` eve avec succ` es, J S (f) contient l’approximation voulue de I(f).
On note J (α,β) (f) l’int´ egrale approch´ ee de f sur l’intervalle actif [α, β]. Cet
intervalle est dessin´ e en gras sur la Figure 8.3. A chaque ´ etape de la m´ ethode
d’int´ egration adaptative les d´ ecisions suivantes sont prises :
1. si le test d’erreur locale (8.40) r´ eussit alors :
(i) J S (f) est augment´ e de J (α,β) (f), c’est-` a-dire J S (f) ← J S (f) +
J (α,β) (f) ;
(ii) on pose S ← S ∪ A, A = N et β = b (ce qui correspond au chemin
(I) sur la Figure 8.3) ;
2. si le test d’erreur local (8.40) ´ echoue alors :
(j) A est divis´ e par deux, et le nouvel intervalle actif est A = [α, α
] avec
α
= (α + β)/2 (ce qui correspond au chemin (II) sur la Figure 8.3) ;
(jj) on pose N ← N ∪ [α
, β], β ← α
;
(jjj) on fournit une nouvelle estimation d’erreur.
Afin d’empˆ echer l’algorithme de produire de trop petits intervalles, on peut
surveiller la longueur de A et, au cas o` u elle deviendrait trop petite, pr´ evenir
l’utilisateur de la pr´ esence possible d’une singularit´ e de la fonction `
a int´ egrer
(voir Section 8.7).
315
a
α
b
b
b
α
β
S
A
N
(I)
S
a
a
α
A
α
S
A
N
(II)
Fig. 8.3. Distribution des intervalles d’int´ egration `
a une ´ etape de l’algorithme adaptatif et mise `
a jour de la grille d’int´ egration
1. A : l’intervalle d’int´ egration actif, i.e. l’intervalle o` u l’int´ egrale doit ˆ etre
calcul´ ee ;
2. S : l’intervalle d’int´ egration d´ ej` a examin´ e, sur lequel le test d’erreur (8.40)
a ´ et´ e effectu´ e avec succ` es ;
3. N : l’intervalle d’int´ egration `
a examiner.
Au d´ ebut de l’algorithme d’int´ egration on a N = [a, b], A = N et S = ∅ ; la
situation `
a une ´ etape quelconque de l’algorithme est d´ ecrite sur la Figure 8.3.
On a J S (f)
α
a
f(x)dx, avec J S (f) = 0 au d´ ebut du processus ; si l’algorithme s’ach` eve avec succ` es, J S (f) contient l’approximation voulue de I(f).
On note J (α,β) (f) l’int´ egrale approch´ ee de f sur l’intervalle actif [α, β]. Cet
intervalle est dessin´ e en gras sur la Figure 8.3. A chaque ´ etape de la m´ ethode
d’int´ egration adaptative les d´ ecisions suivantes sont prises :
1. si le test d’erreur locale (8.40) r´ eussit alors :
(i) J S (f) est augment´ e de J (α,β) (f), c’est-` a-dire J S (f) ← J S (f) +
J (α,β) (f) ;
(ii) on pose S ← S ∪ A, A = N et β = b (ce qui correspond au chemin
(I) sur la Figure 8.3) ;
2. si le test d’erreur local (8.40) ´ echoue alors :
(j) A est divis´ e par deux, et le nouvel intervalle actif est A = [α, α
] avec
α
= (α + β)/2 (ce qui correspond au chemin (II) sur la Figure 8.3) ;
(jj) on pose N ← N ∪ [α
, β], β ← α
;
(jjj) on fournit une nouvelle estimation d’erreur.
Afin d’empˆ echer l’algorithme de produire de trop petits intervalles, on peut
surveiller la longueur de A et, au cas o` u elle deviendrait trop petite, pr´ evenir
l’utilisateur de la pr´ esence possible d’une singularit´ e de la fonction `
a int´ egrer
(voir Section 8.7).