Méthode de Ruffini-Horner - Définition

Introduction

Connue sous le nom de méthode de Horner, règle de Ruffini ou algorithme de Ruffini-Horner, cette méthode se décline sur plusieurs niveaux. Elle permet de calculer la valeur d'un polynôme en . Elle présente un algorithme simple effectuant la division euclidienne d'un polynôme par . Mais elle offre aussi une méthode de changement de variable dans un polynôme. C'est sous cette forme qu'elle est utilisée pour déterminer une valeur approchée d'une racine d'un polynôme.

Histoire

La méthode de Ruffini-Horner de recherche d'une valeur approchée de racine d'un polynôme est publiée à quelques années d'intervalle par Paolo Ruffini (1804-1807-1813) et par William George Horner (1819-1845 posthume) mais il semble bien que Horner n'ait pas eu connaissance des travaux de Ruffini. La méthode de Horner est ensuite popularisée par les mathématiciens De Morgan et J.R. Young. Dans leurs premières publications, ces deux auteurs utilisent des méthodes de dérivations pour effectuer le changement de variable X = x₀ + Y. Par la suite, ils présentent des versions ne faisant appel qu'à des techniques algébriques. La méthode de Ruffini-Horner est difficilement exploitable si le polynôme possède deux racines trop proches. Ruffini n'évoque pas ce problème mais Horner propose une procédure spéciale pour ce cas-là.

En tant que technique de changement de variable, on retrouve des algorithmes analogues, en Chine, pour l'extraction de racine n-ième, dans les Neuf Chapitres (263 après J.C)et dans l'œuvre de Al Samaw'al (XII^e siècle). Mais il semble bien que Sharaf al-Dīn al-Tūsī (XII^e siècle) soit le premier à l'utiliser dans le cas général d'une équation de degré 3.

Quotient d'un polynôme par X - x0

Cette même méthode permet aussi d'obtenir la division d'un polynôme par . Soit .

La division euclidienne de P par donne

où Q est un polynôme de degré n - 1.

Si on écrit et si on identifie les coefficients de même degré dans les deux membres, on obtient :

pour tout k tel que 0 < k < n

Soit encore

pour tout k tel que 0 < k < n

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 . La mémorisation de ces valeurs successives donne donc les coefficients du polynôme quotient, la dernière valeur étant celle du reste.

Application pratique : Division euclidienne de par

Il suffit de reprendre le tableau précédemment construit et de lire dans les cases de la seconde ligne les coefficients de Q.

Donc

Valeur d'un polynôme en un point

Soit un polynôme et un nombre. Le calcul de laisse à penser qu'il faut calculer chacune des puissances de , multiplier celle-ci par son coefficient a_k puis faire la somme de ce que l'on a trouvé.

Si on calcule en multipliant successivement 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 par une méthode d'exponentiation rapide, permettant de réduire le temps du calcul de à 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 :

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. La méthode consiste donc à multiplier le premier coefficient par et à lui ajouter le second coefficient. On multiplie alors le nombre obtenu par et on lui ajoute le troisième coefficient, etc. Elle s'organise très bien à l'aide d'un tableau dans lequel chaque case de la seconde ligne est obtenue en multipliant le coefficient de la case de gauche par et en lui ajoutant le coefficient de la case du dessus.

Exemple pratique : Calcul de pour

Cette méthode permet aussi d'effectuer une conversion rapide d'un nombre écrit en base en écriture en base 10. En effet, si un nombre s'écrit, en base , , ce nombre vaut .

Exemple pratique : écriture en base 10 du nombre hexadécimal DA78