En mathématiques et algorithmique, la méthode de Ruffini-Horner, connue aussi sous les noms de méthode de Horner, algorithme de Ruffini-Horner ou règle de Ruffini, 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 Auguste De Morgan et . Dans leurs premières publications, ces deux auteurs utilisent des méthodes de dérivations pour effectuer le changement de variable . 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àFlorian Cajori, « Horner's method of approximation anticipated by Ruffini », BAMS, vol. 17, , 1911, ..

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 ), introduction au chapitre 4. et dans le monde arabe, dans l'œuvre de Al Samaw'al ()Hélène Bellosta, « À propos de l'histoire des sciences arabes », Gazette des mathématiciens, , octobre 1999.. Mais il semble bien que le Perse, Sharaf al-Dīn al-Tūsī () soit le premier à l'utiliser dans le cas général d'une équation de degré 3 J. L. Berggren, « Innovation and Tradition in Sharaf al-Din al-Tusi's Muadalat », JAOS, vol. 110, , 1990, p. 304-309..

Valeur d'un polynôme en un point

Soit

un polynômeOn peut travailler sur R ou sur un anneau commutatif A quelconque et un nombreou un élément de l'anneau A. Le calcul de

laisse à penser qu'il faut calculer chacune des puissances de , multiplier celle-ci par son coefficient puis faire la somme de ce que l'on a trouvé.

Si on calcule les puissances de en multipliant successivement par lui-même, le nombre nécessaire de produits est alors de , 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 . Ou plus efficacement encore, on peut commencer par calculer toutes les puissances de , ce qui nécessite multiplications, puis multiplier par les coefficients, ce qui nécessite n nouvelles multiplications : le nombre total de produit est alors . La méthode de Horner consiste à combiner les deux itérations précédentes en une seule en effectuant le calcul comme suit : . Le nombre de produits est alors réduit à n et l'on peut montrer que ce nombre est minimal : il n'est pas possible d'évaluer une fonction polynomiale en moins de n produits en toute généralitéPan, V. Ia (1966). Methods of computing values of polynomials. Russian Math. Surveys. 21: 105–136..

La méthode consiste donc à multiplier le premier coefficient par et à lui ajouter le deuxième 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.

Coefficients de … Facteur …

Exemple pratique : Évaluation de en 2 Coefficients de 4 −7 3 −5 Facteur 2 48 − 7 = 12 + 3 = 5 P(2) = 10 − 5 = 5

Outre la réduction du nombre d'opérations, cette méthode peut éviter dans certains cas de manipuler des nombres très grands, et donc peut éviter les dépassements de capacité pour les calculs sur ordinateur. Si l'on prend par exemple le polynôme , alors avec la méthode « classique », pour évaluer , on doit calculer 10010 = 1020 auquel on retranche 99×1018, donnant un résultat erroné sur des logiciels calculant avec 15 chiffres significatifs. Avec la méthode de Ruffini-Horner, on a

conduisant au résultat correct 1009 = 1018 puisque le calcul de la mantisse n'a utilisé que trois chiffres significatifs.

Conversion de base de numération

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 . Il s'agit donc de l'évaluation d'un polynôme.

Exemple pratique : écriture en base 10 du nombre hexadécimal DA78 Coefficients D (13) A (10) 7 8Facteur 16 1313 × 16 + 10 = 218 218 ×16+ 7 = DA78 = × 16 + 8 =

Quotient d'un polynôme par

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

La division euclidienne de 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 . Coefficients de 4 − 73− 5Coefficients de 48 − 7 = 12 + 3 = 5Reste = 10 − 5 = 5

Donc

Changement de variable L'algorithme précédent permet donc d'effectuer la division euclidienne du polynôme par . On peut alors écrire, en posant .

En utilisant de nouveau l'algorithme pour , , ... , on obtient successivement

...

Les nombres , , ... sont donc les coefficients du polynôme tel que

Illustration pratique : Si et que l'on cherche à écrire , on applique 4 fois la méthode de division euclidienne par :

Coefficients de 4 − 73− 5Coefficients de 48 − 7 = 12 + 3 = 510 − 5 = 5Coefficients de 48 + 1 =918 + 5 = 23 Coefficients de 48 + 9 =17 Coefficients de 4

Donc

Valeur approchée d'une racine Pour chercher la valeur approchée x d'une racine d'un polynôme , on cherche un entier tel que et soient de signe contraire. On sait alors, d'après le théorème des valeurs intermédiaires, qu'il existe une racine entre et . On pose alors . Le nombre est racine de si et seulement si le nombre est racine de . Ce polynôme se détermine grâce à la méthode de Horner. Enfin est racine de P(X) si et seulement est racine d'un polynôme obtenu en multipliant les coefficients de par .

Il s'agit alors de chercher une racine de comprise entre 0 et 10 en utilisant un processus analogue : on cherche un entier compris entre 0 et 9 tels que et soient de signe contraire. On sait alors qu'il existe une racine de comprise entre et ...

On détermine ainsi les décimales successives du développement décimal de .

Exemple : algorithme de Ruffini-Horner pour l'extraction de la racine cubique de 18.

Il s'agit de trouver un réel , racine du polynôme . On sait immédiatement que et , est donc compris entre 2 et 3. On pose alors et on cherche le polynôme tel que .

Coefficients de 1 00- 18Coefficients de 124- 10 Coefficients de 1412 Coefficients de 16 Coefficients de 1

Le réel est racine cubique de 18 si où est racine de . La racine est comprise entre 6 et 7 (pour éviter de balayer tous les nombres, il suffit de remarquer que et 10000 doivent être très proches avec ). On pose alors et on cherche le polynôme tel que .

Coefficients de 1 601200-10000Coefficients de 1661596-424 Coefficients de 1722028 Coefficients de 178 Coefficients de 1

Le réel est racine de si où est racine de . La racine est comprise entre 2 et 3. Donc est compris entre 6,2 et 6,3 et est compris entre 2,62 et 2,63.

Dérivées successives de en Cette propriété apparaît ici en dernière position alors qu'elle est la propriété initiale mise en évidence par Ruffini et Horner. Cependant, comme une démarche purement algébrique est possible, celle-ci, plus simple, a été présentée d'abord. Le même algorithme permet de déterminer aussi la valeur de . En effet, le développement de Taylor de donne

Si on note , les coefficients de , trouvés par la méthode de Ruffini-Horner vérifient l'égalité

Annexes Notes et références

Catégorie:Équation polynomiale Catégorie:Algorithme numérique Catégorie:Algorithme de recherche d'un zéro d'une fonction