Introduction
qui se résout en cascades : b n−1 = a n , puis b n−2 = a n−1 + ab n−1 ,. . . ,
b 0 = a 1 + ab 1 , P (a) = a 0 + ab 0 . Disposition pratique (avec n = 3 ; les
flèches indiquent une multiplication par a) :
a 3
a 2
a 1
a 0
+ab 2
+ab 1
+ab 0
b 2 = a 3
= b 1
= b 0
= P (a)
La méthode de Horner se prête particulièrement bien à une programmation informatique et s’avère très économe en temps de
calcul. Les variables d’entrée sont Ò (degré du polynôme, de type
entier), (suite des coefficients du polynôme par degrés croissants, de type tableau), ÐÔÔÔ, de type réel. La variable de sortie
est ÈÈÐÔÔÔ, de type réel.
ÔÖÓÓÖÖÑ ÓÖÒÒÖ
ÚÚÖ Ò¸¸¸¸ÒØØØØÖ ÐÔÔÔ¸ÈÈÐÔÔÔÔÖÖÖÐ ÖÖÖÝݽºº½¼¼¼
ÓÓ ÖÖÖÐ
ÁÆ
ÖÖÖÖÐÒ´ÒµµµÓÖ ¼ ØÓ Ò Ó ÖÖÖÖ´´´´´µµÖÖÖÖÐÒ´´ÐÔÔÔµµ
ÈÈÐÔÔÔÔÔÔÔÒÒÒ
ÓÖ Ò−½ ÓÛÒØÓ ¼ Ó
ÈÈÐÔÔÔÔÔÔÔÔÔ··ÐÔÔÔ¶ÈÈÐÔÔÔÔ
ÛÖÖØØÐÒ´ÈÈÐÔÔÔµµ
Æƺ
On compte avec cette méthode n additions et n multiplications,
à comparer avec la programmation directe du calcul de P (a), qui
conduirait à 1 + 2 + · · · + n =
n(n+1)
2
multiplications et n additions.
• Méthode de Horner pour factoriser par x − a. Dans le cas où a
est une racine de P, la méthode de Horner continue de s’appliquer, elle
aboutit au résultat 0, mais elle donne aussi les coefficients du polynôme
Q (x) tel que P (x) = (x − a) Q (x).
Exemple précédent : P (x) = x
3 + 5x
2
− 7x + 1, racine 1 :
1
5
−7
1
+1
+6
+(−1)
1
= 6
= −1
= 0
D’où le résultat P (x) = (x − 1)
x
2 + 6x − 1
.
• On dit que a est une racine d’ordre de multiplicité n du polynôme
P ssi P (x) = (x − a)
n Q (x), avec Q (x) polynôme n’ayant pas a pour
racine.
24