I – Calculs num´ eriques approch´ es
11
Si l’on pose
p k = a k + a k+1 x + . . . + a n x
n−k ,
cette m´ ethode revient `
a calculer P (x) = p 0 par r´ ecurrence descendante :
p n = a n
p k−1 = a k−1 + xp k ,
1 ≤ k ≤ n.
On effectue ainsi seulement une multiplication et une addition `
a chaque ´ etape,
ce qui ´ economise une multiplication et donc une fraction substantielle du temps
d’ex´ ecution.
Comparons maintenant les erreurs d’arrondi dans chacune des deux m´ ethodes, en
supposant que les r´ eels x, a 0 , a 1 , . . . , a n sont repr´ esent´ es sans erreur.
• M´ ethode na¨ ıve . On a ici P (x) = s n avec
∆(a k · x
k ) ≤ kε|a k ||x|
k ,
∆s k ≤ ∆s k−1 + kε|a k ||x|
k + ε(|s k−1 | + |u k |)
≤ ∆s k−1 + kε|a k ||x|
k + ε(|a 0 | + |a 1 ||x| + . . . + |a k ||x|
k ).
Comme ∆s 0 = 0, il vient apr` es sommation sur k :
∆s n ≤
n
k=1
kε|a k ||x|
k + ε
n
k=1
(|a 0 | + |a 1 ||x| + . . . + |a k ||x|
k )
≤
n
k=1
kε|a k ||x|
k + ε
n
k=0
(n + 1 − k)|a k ||x|
k .
On obtient par cons´ equent
∆P (x) ≤ (n + 1)ε
n
k=0
|a k ||x|
k .
• R` egle de H¨ orner. Dans ce cas, on a
∆p k−1 ≤ ∆(xp k ) + ε(|a k−1 | + |xp k |)
≤ (|x|∆p k + ε|xp k |) + ε(|a k−1 | + |xp k |)
= ε(|a k−1 | + 2|x||p k |) + |x|∆p k .
En d´ eveloppant ∆P (x) = ∆p 0 , il vient
∆p 0 ≤ ε(|a 0 | + 2|x||p 1 |) + |x|
ε|a 1 | + 2|x||p 2 | + |x|
ε|a 2 | + . . .
d’o` u
∆P (x) ≤ ε
n
k=0
|a k ||x|
k + 2ε
n
k=1
|x|
k
|p k |,
∆P (x) ≤ ε
n
k=0
|a k ||x|
k + 2ε
n
k=1
(|a k ||x|
k + . . . + |a n ||x|
n ),
∆P (x) ≤ ε
n
k=0
(2k + 1)|a k ||x|
k .