8.6 Int´ egration automatique
311
Pour cela, le programme g´ en` ere une suite {I k , E k }, pour k = 1, . . . , N, o` u
I k est l’approximation de I(f) `
a la k-i` eme ´ etape du processus de calcul, E k
est une estimation de l’erreur I(f) − I k , et N un entier fix´ e.
Le calcul s’ach` eve ` a la s-i` eme ´ etape, avec s ≤ N , quand la condition
suivante est remplie
max
ε a , ε r |
I(f)|
≥ |E s |( |I(f) − I s |),
(8.33)
o` u ε a est une tol´ erance absolue, ε r une tol´ erance relative et
I(f) une estimation
raisonnable de l’int´ egrale I(f) (ces trois valeurs sont fournies `
a l’initialisation
par l’utilisateur). Si cette condition n’est pas satisfaite au bout de N ´ etapes,
l’int´ egrateur retourne la derni` ere approximation calcul´ ee I N , avec un message
d’erreur avertissant l’utilisateur que l’algorithme n’a pas converg´ e.
Id´ ealement, un int´ egrateur automatique devrait :
(a) fournir un crit` ere fiable pour d´ eterminer |E s | afin de pouvoir effectuer le
test de convergence (8.33) ;
(b) garantir une impl´ ementation efficace qui minimise le nombre d’´ evaluations
de la fonction n´ ecessaire ` a l’obtention de l’approximation voulue I s .
En pratique, pour chaque k ≥ 1, on peut passer de l’´ etape k ` a l’´ etape k + 1
du processus d’int´ egration automatique en suivant, au choix, une strat´ egie
adaptative ou non adaptative.
Dans le cas non adaptatif, la loi de distribution des noeuds de quadrature
est fix´ ee a priori et on am´ eliore la qualit´ e de l’estimation I k en augmentant
` a chaque ´ etape le nombre de noeuds. Un exemple d’int´ egrateur automatique
bas´ e sur cette technique est donn´ e ` a la Section 8.6.1 o` u on utilise les formules
composites de Newton-Cotes sur m et 2m sous-intervalles, respectivement,
aux ´ etapes k et k + 1.
Dans le cas adaptatif, les positions des noeuds ne sont pas fix´ ees a priori :
elles d´ ependent `
a l’´ etape k de l’information stock´ ee durant les k − 1 ´ etapes
pr´ ec´ edentes. On obtient un algorithme adaptatif d’int´ egration automatique en
partitionnant l’intervalle [a, b] en subdivisions successives ayant une densit´ e
de noeuds non uniforme, cette densit´ e ´ etant typiquement plus grande aux
voisinages des zones o` u f a un fort gradient ou une singularit´ e. Un exemple
d’int´ egrateur adaptatif bas´ e sur la formule de Cavalieri-Simpson est d´ ecrit ` a
la Section 8.6.2.
8.6.1 Algorithmes d’int´ egration non adaptatifs
Nous utilisons dans cette section les formules composites de Newton-Cotes.
Notre but est de d´ efinir un crit` ere pour estimer l’erreur absolue |I(f) − I k |
en utilisant l’extrapolation de Richardson. On d´ eduit de (8.26) et (8.27) que,
pour m ≥ 1 et n ≥ 0, I n,m (f) a un ordre infinit´ esimal ´ egal ` a H
n+p , avec
p = 2 pour n pair et p = 1 pour n impair, o` u m, n et H = (b − a)/m
sont respectivement le nombre de partitions de [a, b], le nombre de noeuds
311
Pour cela, le programme g´ en` ere une suite {I k , E k }, pour k = 1, . . . , N, o` u
I k est l’approximation de I(f) `
a la k-i` eme ´ etape du processus de calcul, E k
est une estimation de l’erreur I(f) − I k , et N un entier fix´ e.
Le calcul s’ach` eve ` a la s-i` eme ´ etape, avec s ≤ N , quand la condition
suivante est remplie
max
ε a , ε r |
I(f)|
≥ |E s |( |I(f) − I s |),
(8.33)
o` u ε a est une tol´ erance absolue, ε r une tol´ erance relative et
I(f) une estimation
raisonnable de l’int´ egrale I(f) (ces trois valeurs sont fournies `
a l’initialisation
par l’utilisateur). Si cette condition n’est pas satisfaite au bout de N ´ etapes,
l’int´ egrateur retourne la derni` ere approximation calcul´ ee I N , avec un message
d’erreur avertissant l’utilisateur que l’algorithme n’a pas converg´ e.
Id´ ealement, un int´ egrateur automatique devrait :
(a) fournir un crit` ere fiable pour d´ eterminer |E s | afin de pouvoir effectuer le
test de convergence (8.33) ;
(b) garantir une impl´ ementation efficace qui minimise le nombre d’´ evaluations
de la fonction n´ ecessaire ` a l’obtention de l’approximation voulue I s .
En pratique, pour chaque k ≥ 1, on peut passer de l’´ etape k ` a l’´ etape k + 1
du processus d’int´ egration automatique en suivant, au choix, une strat´ egie
adaptative ou non adaptative.
Dans le cas non adaptatif, la loi de distribution des noeuds de quadrature
est fix´ ee a priori et on am´ eliore la qualit´ e de l’estimation I k en augmentant
` a chaque ´ etape le nombre de noeuds. Un exemple d’int´ egrateur automatique
bas´ e sur cette technique est donn´ e ` a la Section 8.6.1 o` u on utilise les formules
composites de Newton-Cotes sur m et 2m sous-intervalles, respectivement,
aux ´ etapes k et k + 1.
Dans le cas adaptatif, les positions des noeuds ne sont pas fix´ ees a priori :
elles d´ ependent `
a l’´ etape k de l’information stock´ ee durant les k − 1 ´ etapes
pr´ ec´ edentes. On obtient un algorithme adaptatif d’int´ egration automatique en
partitionnant l’intervalle [a, b] en subdivisions successives ayant une densit´ e
de noeuds non uniforme, cette densit´ e ´ etant typiquement plus grande aux
voisinages des zones o` u f a un fort gradient ou une singularit´ e. Un exemple
d’int´ egrateur adaptatif bas´ e sur la formule de Cavalieri-Simpson est d´ ecrit ` a
la Section 8.6.2.
8.6.1 Algorithmes d’int´ egration non adaptatifs
Nous utilisons dans cette section les formules composites de Newton-Cotes.
Notre but est de d´ efinir un crit` ere pour estimer l’erreur absolue |I(f) − I k |
en utilisant l’extrapolation de Richardson. On d´ eduit de (8.26) et (8.27) que,
pour m ≥ 1 et n ≥ 0, I n,m (f) a un ordre infinit´ esimal ´ egal ` a H
n+p , avec
p = 2 pour n pair et p = 1 pour n impair, o` u m, n et H = (b − a)/m
sont respectivement le nombre de partitions de [a, b], le nombre de noeuds