8.6 Int´ egration automatique
313
Table 8.10. Formule automatique non adaptative de Simpson pour l’approximation
de
π
0
(e
x/2 + cos 4x)dx
k |E k | |E
V
k | k
|E k |
| E
V
k |
0
3.156 2
0.10
4.52 · 10
−5
1 0.42 1.047 3 5.8 · 10
−6
2 · 10
−9
Une alternative pour satisfaire les contraintes (a) et (b) consiste `
a utiliser
une suite emboˆ ıt´ ee de quadratures de Gauss I k (f) (voir Chapitre 9) dont le degr´ e d’exactitude est croissant pour k = 1, . . . , N. Ces formules sont construites
de mani` ere ` a ce que S nk ⊂ S nk+1 pour k = 1, . . . , N−1, o` u S nk = {x 1 , . . ., x nk }
est l’ensemble des noeuds de quadrature relatif ` a I k (f). Ainsi, pour k ≥ 1, la
formule au k + 1-i` eme niveau utilise tous les noeuds de la formule du niveau k,
ce qui rend l’impl´ ementation des formules emboˆ ıt´ ees particuli` erement efficace.
Donnons l’exemple des formules de Gauss-Kronrod `
a 10, 21, 43 et 87
points, qui sont disponibles dans [PdK ¨
UK83] (dans ce cas N = 4). Les
formules de Gauss-Kronrod ont un degr´ e d’exactitude r nk (optimal) ´ egal ` a
2n k − 1, o` u n k est le nombre de noeuds de chaque formule, avec n 1 = 10 et
n k+1 = 2n k + 1 pour k = 1, 2, 3. On obtient une estimation d’erreur en comparant les r´ esultats donn´ es par deux formules successives I nk (f) et I nk+1 (f)
avec k = 1, 2, 3 et le calcul s’arrˆ ete ` a l’´ etape k pour laquelle
|I k+1 − I k | ≤ max {ε a , ε r |I k+1 |} ,
(voir aussi [DR75], p. 321).
8.6.2 Algorithmes d’int´ egration adaptatifs
Le but d’un int´ egrateur adaptatif est de fournir une approximation de I(f) =
b
a
f(x) dx avec une tol´ erance fix´ ee ε ` a l’aide d’une distribution non uniforme
des sous-intervalles d’int´ egration dans [a, b]. Un algorithme optimal est capable
d’adapter automatiquement la longueur des sous-intervalles en fonction de
l’int´ egrande en augmentant la densit´ e des noeuds de quadrature aux endroits
o` u la fonction subit de fortes variations.
Il est commode, pour d´ ecrire la m´ ethode, de restreindre notre attention `
a
un sous-intervalle arbitraire [α, β] ⊆ [a, b]. Afin d’assurer une pr´ ecision donn´ ee, disons ε(β − α)/(b − a), on doit fixer une longueur h ; au regard des
estimations d’erreur des formules de Newton-Cotes, on voit qu’il faut pour
cela ´ evaluer les d´ eriv´ ees de f jusqu’` a un certain ordre. Cette proc´ edure, qui
est irr´ ealisable dans les calculs pratiques, est effectu´ ee comme suit par un int´ egrateur automatique. Nous consid´ erons dans toute la section la formule de
Cavalieri-Simpson (8.15), bien que la m´ ethode puisse ˆ etre ´ etendue `
a d’autres
formules de quadrature.
Soit I f (α, β) =
β
α f(x)dx, h = h 0 = (β − α)/2 et
S f (α, β) = (h 0 /3) [f(α) + 4f(α + h 0 ) + f(β)] .
313
Table 8.10. Formule automatique non adaptative de Simpson pour l’approximation
de
π
0
(e
x/2 + cos 4x)dx
k |E k | |E
V
k | k
|E k |
| E
V
k |
0
3.156 2
0.10
4.52 · 10
−5
1 0.42 1.047 3 5.8 · 10
−6
2 · 10
−9
Une alternative pour satisfaire les contraintes (a) et (b) consiste `
a utiliser
une suite emboˆ ıt´ ee de quadratures de Gauss I k (f) (voir Chapitre 9) dont le degr´ e d’exactitude est croissant pour k = 1, . . . , N. Ces formules sont construites
de mani` ere ` a ce que S nk ⊂ S nk+1 pour k = 1, . . . , N−1, o` u S nk = {x 1 , . . ., x nk }
est l’ensemble des noeuds de quadrature relatif ` a I k (f). Ainsi, pour k ≥ 1, la
formule au k + 1-i` eme niveau utilise tous les noeuds de la formule du niveau k,
ce qui rend l’impl´ ementation des formules emboˆ ıt´ ees particuli` erement efficace.
Donnons l’exemple des formules de Gauss-Kronrod `
a 10, 21, 43 et 87
points, qui sont disponibles dans [PdK ¨
UK83] (dans ce cas N = 4). Les
formules de Gauss-Kronrod ont un degr´ e d’exactitude r nk (optimal) ´ egal ` a
2n k − 1, o` u n k est le nombre de noeuds de chaque formule, avec n 1 = 10 et
n k+1 = 2n k + 1 pour k = 1, 2, 3. On obtient une estimation d’erreur en comparant les r´ esultats donn´ es par deux formules successives I nk (f) et I nk+1 (f)
avec k = 1, 2, 3 et le calcul s’arrˆ ete ` a l’´ etape k pour laquelle
|I k+1 − I k | ≤ max {ε a , ε r |I k+1 |} ,
(voir aussi [DR75], p. 321).
8.6.2 Algorithmes d’int´ egration adaptatifs
Le but d’un int´ egrateur adaptatif est de fournir une approximation de I(f) =
b
a
f(x) dx avec une tol´ erance fix´ ee ε ` a l’aide d’une distribution non uniforme
des sous-intervalles d’int´ egration dans [a, b]. Un algorithme optimal est capable
d’adapter automatiquement la longueur des sous-intervalles en fonction de
l’int´ egrande en augmentant la densit´ e des noeuds de quadrature aux endroits
o` u la fonction subit de fortes variations.
Il est commode, pour d´ ecrire la m´ ethode, de restreindre notre attention `
a
un sous-intervalle arbitraire [α, β] ⊆ [a, b]. Afin d’assurer une pr´ ecision donn´ ee, disons ε(β − α)/(b − a), on doit fixer une longueur h ; au regard des
estimations d’erreur des formules de Newton-Cotes, on voit qu’il faut pour
cela ´ evaluer les d´ eriv´ ees de f jusqu’` a un certain ordre. Cette proc´ edure, qui
est irr´ ealisable dans les calculs pratiques, est effectu´ ee comme suit par un int´ egrateur automatique. Nous consid´ erons dans toute la section la formule de
Cavalieri-Simpson (8.15), bien que la m´ ethode puisse ˆ etre ´ etendue `
a d’autres
formules de quadrature.
Soit I f (α, β) =
β
α f(x)dx, h = h 0 = (β − α)/2 et
S f (α, β) = (h 0 /3) [f(α) + 4f(α + h 0 ) + f(β)] .