12
Analyse num´ erique et ´ equations diff´ erentielles
On voit que la somme des coefficients d’erreur affect´ es aux termes |a k ||x|
k , soit
ε
n
k=0
(2k + 1) = ε(n + 1)
2 , est la mˆ eme que pour la m´ ethode na¨ ıve ; comme
2k + 1 ≤ 2(n + 1), l’erreur commise sera dans le pire des cas ´ egale ` a 2 fois celle de
la m´ ethode na¨ ıve. N´ eanmoins, les petits coefficients portent sur les premiers termes
calcul´ es, de sorte que la pr´ ecision de la m´ ethode de H¨ orner sera nettement meilleure
si le terme |a k ||x|
k d´ ecroˆ ıt rapidement : c’est le cas par exemple si P (x) est le d´ ebut
d’une s´ erie convergente.
Exercice – Evaluer dans les deux cas l’erreur commise sur les sommes partielles
de la s´ erie exponentielle
n
k=0
x
k
k!
, x ≥ 0
en tenant compte du fait qu’on a une certaine erreur d’arrondi sur a k =
1
k! .
R´ eponse. On trouve ∆P (x) ≤ ε(1 + (n + x)e
x ) pour la m´ ethode na¨ ıve, tandis que
la factorisation
P (x) = 1 + x
1 +
x
2
1 +
x
3
1 + . . .
1 +
x
n − 1
1 +
x
n
. . .
donne ∆P (x) ≤ ε(1 + 3xe
x ), ce qui est nettement meilleur en pratique puisque n
doit ˆ etre choisi assez grand.
½ººº ÙÑÙÐÐØØÓÒ ³³ÖÖÖÙÖ× ³³ÖÖÓÒÒÒ Ð ØÓÓÖÖ×
Les majorations d’erreurs que nous avons donn´ ees plus haut pˆ echent en g´ en´ eral par
exc` es de pessimisme, car nous n’avons tenu compte que de la valeur absolue des
erreurs, alors qu’en pratique elles sont souvent de signe al´ eatoire et se compensent
donc partiellement entre elles.
Supposons par exemple qu’on cherche `
a calculer une somme s n de rang ´ elev´ e d’une
s´ erie convergente S =
+∞
k=0 u k , les u k ´ etant des r´ eels ≥ 0 suppos´ es repr´ esent´ es sans
erreur. On pose donc
s k = s k−1 + u k , s 0 = u 0 ,
et les erreurs ∆s k v´ erifient
∆s k = ∆s k−1 + α k
avec ∆s 0 = 0 et |α k | ≤ ε(s k−1 + u k ) = εs k ≤ εS.
On en d´ eduit donc
∆s n = α 1 + α 2 + . . . + α n
et en particulier |∆s n | ≤ nεS. Dans le pire des cas, l’erreur est donc proportionnelle
` a n. On va voir qu’on peut en fait esp´ erer beaucoup mieux sous des hypoth` eses
raisonnables.
Analyse num´ erique et ´ equations diff´ erentielles
On voit que la somme des coefficients d’erreur affect´ es aux termes |a k ||x|
k , soit
ε
n
k=0
(2k + 1) = ε(n + 1)
2 , est la mˆ eme que pour la m´ ethode na¨ ıve ; comme
2k + 1 ≤ 2(n + 1), l’erreur commise sera dans le pire des cas ´ egale ` a 2 fois celle de
la m´ ethode na¨ ıve. N´ eanmoins, les petits coefficients portent sur les premiers termes
calcul´ es, de sorte que la pr´ ecision de la m´ ethode de H¨ orner sera nettement meilleure
si le terme |a k ||x|
k d´ ecroˆ ıt rapidement : c’est le cas par exemple si P (x) est le d´ ebut
d’une s´ erie convergente.
Exercice – Evaluer dans les deux cas l’erreur commise sur les sommes partielles
de la s´ erie exponentielle
n
k=0
x
k
k!
, x ≥ 0
en tenant compte du fait qu’on a une certaine erreur d’arrondi sur a k =
1
k! .
R´ eponse. On trouve ∆P (x) ≤ ε(1 + (n + x)e
x ) pour la m´ ethode na¨ ıve, tandis que
la factorisation
P (x) = 1 + x
1 +
x
2
1 +
x
3
1 + . . .
1 +
x
n − 1
1 +
x
n
. . .
donne ∆P (x) ≤ ε(1 + 3xe
x ), ce qui est nettement meilleur en pratique puisque n
doit ˆ etre choisi assez grand.
½ººº ÙÑÙÐÐØØÓÒ ³³ÖÖÖÙÖ× ³³ÖÖÓÒÒÒ Ð ØÓÓÖÖ×
Les majorations d’erreurs que nous avons donn´ ees plus haut pˆ echent en g´ en´ eral par
exc` es de pessimisme, car nous n’avons tenu compte que de la valeur absolue des
erreurs, alors qu’en pratique elles sont souvent de signe al´ eatoire et se compensent
donc partiellement entre elles.
Supposons par exemple qu’on cherche `
a calculer une somme s n de rang ´ elev´ e d’une
s´ erie convergente S =
+∞
k=0 u k , les u k ´ etant des r´ eels ≥ 0 suppos´ es repr´ esent´ es sans
erreur. On pose donc
s k = s k−1 + u k , s 0 = u 0 ,
et les erreurs ∆s k v´ erifient
∆s k = ∆s k−1 + α k
avec ∆s 0 = 0 et |α k | ≤ ε(s k−1 + u k ) = εs k ≤ εS.
On en d´ eduit donc
∆s n = α 1 + α 2 + . . . + α n
et en particulier |∆s n | ≤ nεS. Dans le pire des cas, l’erreur est donc proportionnelle
` a n. On va voir qu’on peut en fait esp´ erer beaucoup mieux sous des hypoth` eses
raisonnables.