AlgèbreMéthode · Glossaire
méthode de Horner
La méthode de Horner est un algorithme d'évaluation efficace d'un polynôme de degré n en un point donné x. Elle repose sur une réécriture du polynôme sous forme factorisée emboîtée : a₀ + a₁x + ... + aₙxⁿ = (…((aₙx + aₙ₋₁)x + aₙ₋₂)x + …)x + a₀, ce qui permet de calculer la valeur du polynôme en n'effectuant que n multiplications et n additions, au lieu de l'évaluation naïve bien plus coûteuse. Cette procédure d'évaluation peut aussi servir de sous-calcul dans une méthode de recherche ou d'approximation des racines par resserrement successif. Bien que publiée à quelques années d'intervalle par Paolo Ruffini en 1804, François Budan en 1807 et William George Horner en 1819, la méthode était déjà connue d'Isaac Newton en 1669, et avait été utilisée auparavant par le mathématicien chinois Qin Jiushao.
Sommaire
Ce que vous allez apprendre
- Réécrire un polynôme sous forme emboîtée.
- Appliquer la succession multiplier puis ajouter.
- Évaluer P(x) en n multiplications et n additions.
- Contrôler le calcul sur P(3) = 5.
- Éviter les erreurs d'ordre et de coefficients nuls.
En clair
Prenez une liste de coefficients et une valeur de x. Au lieu de calculer séparément x, x², x³, puis de réunir tous les termes, la méthode de Horner avance de coefficient en coefficient. À chaque tour, elle multiplie le résultat courant par x et ajoute le coefficient suivant.
Le calcul forme ainsi une chaîne courte, sans puissances à préparer. Pour un polynôme de degré n, cette chaîne compte exactement n multiplications et n additions.
Définition
La méthode de Horner est un algorithme qui évalue un polynôme à partir de ses coefficients. Soit P un polynôme de degré n, dont les coefficients sont a0, a1, …, an, rangés des puissances croissantes de la variable x. La valeur an est le coefficient du terme de plus haut degré.
La réécriture emboîtée est . Elle donne une récurrence équivalente : on part de bn = an, puis, pour chaque indice k décroissant de n − 1 à 0, on calcule . La dernière valeur b0 est P(x).
Le procédé demande n multiplications et n additions. La même organisation peut aussi accompagner la recherche approchée de racines par resserrements successifs. Des formes de la méthode ont été publiées par Paolo Ruffini en 1804, François Budan en 1807 et William George Horner en 1819 ; Isaac Newton la connaissait en 1669, après un usage antérieur par Qin Jiushao.
Le principe
Pour évaluer un polynôme de degré n en une valeur x, rangez tous ses coefficients du degré n au degré 0, sans omettre les coefficients nuls. Prenez le premier coefficient comme valeur courante. Multipliez cette valeur par x, puis ajoutez le coefficient suivant. Répétez ces deux opérations jusqu'au terme constant. La valeur obtenue après le dernier ajout est P(x) ; l'arrêt survient donc lorsque tous les coefficients ont été utilisés.
Quand l'utiliser
Le procédé s'applique lorsqu'une expression est un polynôme en une variable et que sa valeur x ainsi que tous ses coefficients sont connus. Les coefficients doivent suivre les degrés dans un ordre continu. Un terme absent est représenté par le coefficient 0, afin que chaque multiplication corresponde bien à une baisse d'un degré. Le calcul fournit alors la valeur exacte de P(x) avec des nombres exacts.
Pour l'expression 1/x, il n'existe pas de liste finie de coefficients polynomiaux ordonnée par degrés entiers naturels : le schéma de Horner ne s'applique pas tel quel. Il faut évaluer directement cette expression, avec x différent de 0.
Un exemple, pas à pas
On veut évaluer le polynôme P défini par à la valeur x = 3. Les données sont donc x = 3 et, du degré 3 au degré 0, les coefficients 2, −6, 2 et −1.
1. La valeur courante commence à 2.
2. Première étape : 2 × 3 + (−6) = 0.
3. Deuxième étape : 0 × 3 + 2 = 2.
4. Troisième étape : 2 × 3 + (−1) = 5. La dernière valeur donne donc P(3) = 5. Le schéma associé rend visible la transmission de chaque résultat vers l'étape suivante.
Un contrôle direct confirme le résultat : 2 × 3³ − 6 × 3² + 2 × 3 − 1 = 54 − 54 + 6 − 1 = 5.
En pratique
Pour calculer la valeur d'un polynôme en un point, Horner évite de former séparément toutes les puissances. Une évaluation directe reste cependant plus courte si l'expression ne comporte qu'un ou deux termes immédiatement calculables.
Pour tester si un nombre r est une racine, on applique le schéma en prenant x = r. Si la dernière valeur est 0, alors P(r) = 0 ; sinon, P(r) est le résidu signé, et l'écart absolu à zéro est |P(r)|.
Les valeurs intermédiaires organisent aussi les coefficients obtenus lorsqu'on retire un facteur x − r. On peut alors relier le schéma à la division euclidienne des polynômes ; une division posée reste préférable lorsqu'on divise par un polynôme qui n'est pas de degré 1.
À ne pas confondre
Évaluation et factorisation. Horner calcule P(x) pour une valeur donnée ; une factorisation cherche une écriture de P comme produit. Pour P(3) = 5, le schéma a terminé une évaluation, mais il n'a fourni aucun facteur.
Schéma de Horner et recherche de racine. Une exécution du schéma répond à la question « quelle est la valeur de P en x ? ». Une recherche approchée de racine répète des calculs avec plusieurs valeurs de x et un resserrement successif. Obtenir P(3) = 5 ne signifie donc pas que 3 est une racine.
Limites et pièges
Coefficient nul oublié. Dans 2x³ + 2x − 1, le coefficient de x² vaut 0. L'omettre décale toutes les étapes ; il faut utiliser la liste 2, 0, 2, −1.
Ordre inversé. Le schéma commence par le coefficient du plus haut degré et finit par le terme constant. Pour l'exemple, partir de −1 au lieu de 2 évalue une autre expression.
Degré 0. Un polynôme constant ne déclenche aucune étape : P(x) = a0 pour toute valeur de x. La borne de n multiplications et n additions donne bien 0 opération lorsque n = 0.
Puissances très espacées. Pour un polynôme comme x¹⁰⁰, le schéma standard traverse 100 degrés, dont 99 coefficients nuls. Une évaluation directe de la puissance peut être plus adaptée ; l'avantage annoncé concerne la forme générale dense.
Pour aller plus loin
algorithme — Situer Horner parmi les procédures finies et ordonnées qui transforment des données en résultat.
Division euclidienne — Relier les valeurs intermédiaires de Horner à la division d'un polynôme par un facteur de degré 1.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres