Méthode de Horner
Un article de Wikipédia, l'encyclopédie libre.
La méthode de Horner doit son nom à William George Horner, mathématicien anglais. Elle est utilisée dans le calcul polynomial, soit pour calculer la valeur d'une fonction polynomiale en un point, soit pour calculer le quotient d'un polynôme par X - a.
[modifier] Valeur d'un polynôme en un point
Soit P = λnXn + λn − 1Xn − 1 + ... + λ0 un polynôme sur un anneau commutatif A et a un élément de A. Le calcul de P(a) = λnan + λn − 1an − 1 + ... + λ0 laisse à penser qu'il faut calculer chacune des puissances de a, multiplier celle-ci par son coefficient λk puis faire la somme de ce que l'on a trouvé.
Si on calcule an en multipliant successivement a par lui-même, le nombre de produits nécessaire est alors de n + (n − 1) + ... + 2 + 1 = n(n + 1) / 2, quantité qui croît comme le carré du degré du polynôme.
On peut améliorer la vitesse du calcul de an par une méthode d'exponentiation rapide, permettant de réduire le temps du calcul de P(a) à une quantité qui croît comme nln(n).
La méthode de Horner consiste à améliorer encore ce résultat en effectuant le calcul comme suit :
-
- P(a) = ((...((λna + λn − 1)a + λn − 2)a + ...) + λ1)a + λ0
Le nombre de produits est alors réduit à n, de sorte que le temps de calcul d'une fonction polynomiale en un point a est seulement proportionnel au degré du polynôme.
[modifier] Quotient d'un polynôme par X - a
Reprenons le même polynôme P = λnXn + λn − 1Xn − 1 + ... + λ0 et cherchons son quotient dans la division euclidienne par X - a. On a :
-
- P = (X − a)Q + P(a)
Si on écrit Q = qn − 1Xn − 1 + qn − 2Xn − 2 + ... + q1X + q0 et si on identifie les coefficients de même degré dans les deux membres, on obtient :
-
- qn − 1 = λn
- qk − 1 = λk + aqk pour tout k tel que 0 < k < n
La valeur de P(a) n'est autre que λ0 + aq0.
Les n valeurs de la suite q calculées ici sont précisément les n valeurs successives calculées dans le paragraphe précédent pour évaluer P(a). La mémorisation de ces valeurs successives donne donc les coefficients du polynôme quotient, la dernière valeur étant celle du reste.
[modifier] Illustration dans un tableau
Une présentation de la méthode de Horner dans un tableau montre la simplicité de l'algorithme : chaque coefficient de Q s'obtient en multipliant le coefficient de la case de gauche par a et en lui ajoutant le coefficient de la case du dessus.
| Coefficients de P | λn | λn - 1 | λn - 2 | ... | λ1 | λ0 |
| Coefficients de Q | qn - 1 λn |
qn - 2 aqn - 1 + λn - 1 |
qn - 3 aqn - 2 + λn - 2 |
... | q0 aq1 + λ1 |
r aq0 + λ0 |
Exemple pratique : division de 4X3 − 7X2 + 3X − 5 par X − 2
| Coefficients de P | 4 | − 7 | 3 | − 5 |
| Coefficients de Q | 4 | 8 − 7 = 1 | 2 + 3 = 5 | r = 10 − 5 = 5 |
Ce qui donne : 4X3 − 7X2 + 3X − 5 = (X − 2)(4X2 + X + 5) + 5
