Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Méthode de Ruffini-Horner
Résumé
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 x. Elle présente un algorithme simple effectuant la division euclidienne d'un polynôme par X − x. Mais elle offre aussi une méthode de changement de variable X = x + Y 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.
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 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 ) et dans l'œuvre de Al Samaw'al (). Mais il semble bien que Sharaf al-Dīn al-Tūsī () soit le premier à l'utiliser dans le cas général d'une équation de degré 3.
Soit
un polynôme et x un nombre. Le calcul de P(x)
laisse à penser qu'il faut calculer chacune des puissances de x, multiplier celle-ci par son coefficient a puis faire la somme de ce que l'on a trouvé.
Si on calcule les puissances de x en multipliant successivement x 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.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.