Méthode de Horner

La méthode de Horner 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.

Soit P = λ_nX + λ_{n − 1}X + ... + λ₀ un polynôme sur un anneau commutatif A et a un élément de A. Le calcul de P(a) = λ_na + λ_{n − 1}a + ... + λ₀ 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 a 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 a 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 + ...) + λ₁)a + λ₀

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.

Reprenons le même polynôme P = λ_nX + λ_{n − 1}X + ... + λ₀ et cherchons son quotient dans la division euclidienne par X - a. On a :

P = (X − a)Q + P(a)

Si on écrit Q = q_{n − 1}X + q_{n − 2}X + ... + q₁X + q₀ et si on identifie les coefficients de même degré dans les deux membres, on obtient :

q_{n − 1} = λ_n

q_{k − 1} = λ_k + a**q_k pour tout k tel que 0 < k < n

La valeur de P(a) n'est autre que λ₀ + aq₀.

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.

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.

Exemple pratique : division de 4X − 7X + 3X − 5 par X − 2

Ce qui donne : 4X − 7X + 3X − 5 = (X − 2)(4X + X + 5) + 5