Voir la source de Méthode de Ruffini-Horner

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 {{math|''x''{{ind|0}}}}. Elle présente un algorithme simple effectuant la [[division euclidienne]] d'un polynôme par {{math|''X'' − ''x''{{ind|0}}}}. Mais elle offre aussi une méthode de changement de variable {{math|''X'' {{=}} ''x''{{ind|0}} + ''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]].

== 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 (mathématicien)|Paolo Ruffini]] (1804-1807-1813) et par [[William George Horner]]<ref>{{ouvrage|lang=en|auteur=[[David Eugene Smith]]|titre=A Source Book in Mathematics|éditeur=[[Dover Publications|Dover]]|année première édition=1929|date=1959|url={{Google Livres|3TSKAAAAQBAJ|page=2232}}|page=232-252}}<!--ou pdf, mais très long à charger : https://ia600504.us.archive.org/3/items/sourcebookinmath00smit/sourcebookinmath00smit.pdf-->.</ref> (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 {{Lien|John Radford Young}}. Dans leurs premières publications, ces deux auteurs utilisent des méthodes de dérivations pour effectuer le changement de variable {{math|''X'' {{=}} ''x''{{ind|0}} + ''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à<ref>[[Florian Cajori]], « [https://projecteuclid.org/journals/bulletin-of-the-american-mathematical-society-new-series/volume-17/issue-8/Horners-method-of-approximation-anticipated-by-Ruffini/bams/1183421253.full Horner's method of approximation anticipated by Ruffini] », ''[[Bulletin of the American Mathematical Society|BAMS]]'', vol. 17, {{n°|8}}, 1911, {{p.|409-414}}.</ref>.

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 ''[[Les Neuf Chapitres sur l'art mathématique|Neuf Chapitres]]'' (263 {{ap JC}})<ref>{{ChemlaShuchun}}, introduction au chapitre 4.</ref> et dans le [[monde arabe]], dans l'œuvre de [[Ibn Yahyā al-Maghribī al-Samaw'al|Al Samaw'al]] ({{s-|XII|e}})<ref>Hélène Bellosta, « [https://archive.wikiwix.com/cache/index2.php?url=http%3A%2F%2Fsmf.emath.fr%2FPublications%2FGazette%2F1999%2F82%2Fsmf_gazette_82_37-44.pdf%2Findex.html#& À propos de l'histoire des sciences arabes] », ''[[Gazette des mathématiciens]]'', {{n°|82}}, octobre 1999.</ref>. Mais il semble bien que le [[Empire perse|Perse]], [[Sharaf al-Dīn al-Tūsī]] ({{s-|XII|e}}) soit le premier à l'utiliser dans le cas général d'une équation de degré 3<ref>{{en}} J. L. Berggren, « Innovation and Tradition in Sharaf al-Din al-Tusi's Muadalat », ''[[Journal of the American Oriental Society|JAOS]]'', vol. 110, {{n°|2}}, 1990, p. 304-309.</ref>.

== Valeur d'un polynôme en un point ==

Soit
:<math>P = a_n X^n + a_{n-1}X^{n-1} + \ldots + a_0</math>
un [[polynôme]]<ref>On peut travailler sur '''R''' ou sur un anneau commutatif A quelconque</ref> et {{math|''x''{{ind|0}}}} un nombre<ref>ou un élément de l'anneau A</ref>. Le calcul de {{math|''P''(''x''{{ind|0}})}}
: <math>P(x_0) = a_n x_0^n + a_{n-1}x_0^{n-1} + \ldots + a_0</math>
laisse à penser qu'il faut calculer chacune des puissances de {{math|''x''{{ind|0}}}}, multiplier celle-ci par son coefficient {{mvar|a{{ind|k}}}} puis faire la somme de ce que l'on a trouvé.

Si on calcule les puissances de {{math|''x''{{ind|0}}}} en multipliant successivement {{math|''x''{{ind|0}}}} par lui-même, le nombre nécessaire de produits est alors de {{nobr|''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 {{math|''x''{{indexp|0|''n''}}}} par une méthode d'[[exponentiation rapide]], permettant de réduire le temps du calcul de {{math|''P''(''x''{{ind|0}})}} à une quantité qui croît comme {{math|''n''×ln(''n'')}}. Ou plus efficacement encore, on peut commencer par calculer toutes les puissances de {{math|''x''{{ind|0}}}}, ce qui nécessite {{nobr|''n'' – 1}} multiplications, puis multiplier par les coefficients, ce qui nécessite ''n'' nouvelles multiplications : le nombre total de produit est alors {{nobr|2''n'' – 1}}. La méthode de Horner consiste à combiner les deux itérations précédentes en une seule en effectuant le calcul comme suit :
: <math>P(x_0) = ((\dots ((a_nx_0 + a_{n-1})x_0 + a_{n-2})x_0 + \dots ) x_0+ a_1)x_0 + a_0</math>.
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é<ref>[[Victor Pan|Pan, V. Ia]] (1966). [http://iopscience.iop.org/article/10.1070/RM1966v021n01ABEH004147/meta Methods of computing values of polynomials]. Russian Math. Surveys. 21: 105–136.</ref>.

La méthode consiste donc à multiplier le premier coefficient par {{math|''x''{{ind|0}}}} et à lui ajouter le deuxième coefficient. On multiplie alors le nombre obtenu par {{math|''x''{{ind|0}}}} 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 {{math|''x''{{ind|0}}}} et en lui ajoutant le coefficient de la case du dessus.

{| border cellspacing="0"
|-style="text-align:center"
| bgcolor="#b3e2d1" |Coefficients de {{mvar|P}}
|width = "50"|{{mvar|a{{ind|n}}}}
| {{math|''a''{{ind|''n'' – 1}}}}
| {{math|''a''{{ind|''n'' – 2}}}}
|width = "50"| …
|width = "50"| {{math|''a''{{ind|1}}}}
| {{math|''a''{{ind|0}}}}
|-style="text-align:center"
| bgcolor="#b3e2d1" | Facteur {{math|''x''{{ind|0}}}}
| {{mvar|a{{ind|n}}}}
| {{math|''a{{ind|n}}x''{{ind|0}} + ''a''{{ind|''n'' – 1}}}}
| {{math|(''a{{ind|n}}x''{{ind|0}} + ''a''{{ind|''n'' – 1}})''x''{{ind|0}} + ''a''{{ind|''n'' – 2}}}}
|width = "50"| …
|{{math|''q''{{ind|0}}}}
|bgcolor="#b3e2d1" | {{math|''P''(''x''{{ind|0}}) {{=}} ''q''{{ind|0}}''x''{{ind|0}} + ''a''{{ind|0}}}}
|}

Exemple pratique : Calcul de {{math|4''X''{{3}} - 7''X''{{2}} + 3''X'' – 5}} pour {{math|X {{=}} 2}}
{| border cellspacing="0"
|-style="text-align:center"
| bgcolor="#b3e2d1" | Coefficients de {{mvar|P}}
|width = "80"| 4
|width = "80"| −7
|width = "80"| 3
|width = "100"| −5
|-style="text-align:center"
| bgcolor="#b3e2d1" | Facteur 2 ||4||8 − 7 = 1||2 + 3 = 5
|bgcolor="#b3e2d1" | ''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épassement d'entier|dépassements de capacité]] pour les calculs sur ordinateur. Si l'on prend par exemple le polynôme {{math|''P''(''X'') {{=}} ''X''<sup>10</sup> – 99''X''<sup>9</sup>}}, alors avec la méthode « classique », pour évaluer {{math|''P''(100)}}, on doit calculer 100<sup>10</sup> = 10<sup>20</sup> auquel on retranche 99×10<sup>18</sup>, donnant un résultat erroné sur des logiciels calculant avec 15 [[Chiffre significatif|chiffres significatifs]]. Avec la méthode de Ruffini-Horner, on a
:<math>P(100) = (100 - 99) \times 100^9</math>
conduisant au résultat correct 100<sup>9</sup> = 10<sup>18</sup> 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 (arithmétique)|base]] {{math|''x''{{ind|0}}}} en écriture en base 10. En effet, si un nombre s'écrit, en base {{math|''x''{{ind|0}}}},
: <math>n = \overline{a_na_{n-1}\cdots a_0}</math>,
ce nombre vaut
: <math>n = a_nx_0^n + a_{n-1}x_0^{n-1} + \cdots + a_0</math>.
Il s'agit donc de l'évaluation d'un polynôme.

Exemple pratique : écriture en base 10 du nombre hexadécimal DA78
{| border cellspacing="0"
|-style="text-align:center"
| bgcolor="#b3e2d1" |Coefficients
|width = "80"| D (13)
|width = "80"| A (10)
|width = "100"| 7
|width = "160"| 8
|-style="text-align:center"
| bgcolor="#b3e2d1" |Facteur 16 ||13||13 × 16 + 10 = 218 ||218 ×16+ 7 = {{formatnum:3495}}
|bgcolor="#b3e2d1" |DA78 = {{formatnum:3495}} × 16 + 8 = {{formatnum:55928}}
|}

== Quotient d'un polynôme par {{math|''X – x''{{ind|0}}}} ==
{{article connexe|Division synthétique}}
Cette même méthode permet aussi d'obtenir la [[division d'un polynôme]] par {{math|''X – x''{{ind|0}}}}. Soit  <math>P = a_nX^n + a_{n-1}X^{n-1} + ... + a_0</math>.
 
La [[division euclidienne]] de {{mvar|P}} par {{math|''X – x''{{ind|0}}}} donne 
::<math>P = (X-x_0)Q + P(x_0)\,</math>
où Q est un polynôme de degré n - 1.

Si on écrit <math>Q = q_{n-1}X^{n - 1} + q_{n-2}X^{n-2}+ ...+ q_1X + q_0</math> et si on identifie les coefficients de même degré dans les deux membres, on obtient :
::<math>q_{n-1} = a_n \,</math>
::<math>q_{k-1} - q_kx_0=a_k \,</math> pour tout ''k'' tel que 0 < ''k'' < ''n''
Soit encore 
::<math>q_{k-1}=q_kx_0+a_k\, </math> 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 {{math|''P''(''x''{{ind|0}})}}. 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 {{math|4''X''{{3}} – 7''X''{{2}} + 3''X'' – 5}} par {{math|''X'' – 2}}

Il suffit de reprendre le tableau précédemment construit et de lire dans les cases de la seconde ligne les coefficients de {{mvar|Q}}. 
{| border cellspacing="0"
|-style="text-align:center"
| bgcolor="#b3e2d1" |Coefficients de {{mvar|P}}
|width = "80"|4
|width = "80"| − 7
|width = "80"|3
|width = "100"|− 5
|-style="text-align:center"
| bgcolor="#b3e2d1" |Coefficients de {{mvar|Q}}  ||4||8 − 7 = 1||2 + 3 = 5
|bgcolor="#b3e2d1" |Reste = 10 − 5 = 5
|}

Donc 
:<math>4X^3 - 7X^2 + 3X - 5 = (X-2)(4X^2 + X + 5) + 5\,</math>

== Changement de variable ==
L'algorithme précédent permet donc d'effectuer la division euclidienne du polynôme {{mvar|P}} par {{math|''X - x''{{ind|0}}}}. On peut alors écrire, en posant {{math|''Y {{=}} X - x''{{ind|0}}}}. 
:<math>P(X) = YP_1(X)+b_0\,</math>
En utilisant de nouveau l'algorithme pour {{math|''P''{{ind|1}}}}, {{math|''P''{{ind|2}}}}, ... {{mvar|P{{ind|n}}}}, on obtient successivement
: <math>P(X) = Y\left(YP_2(X)+b_1\right)+b_0\,</math>
...
: <math>P(X) = Y\left(Y\left(...Y\left(Yb_n + b_{n-1}\right)...\right)+b_1\right)+b_0\,</math>
Les nombres {{math|''b''{{ind|0}}}}, {{math|''b''{{ind|2}}}}, ... {{mvar|b{{ind|n}}}} sont donc les coefficients du polynôme {{mvar|Q}} tel que {{math|''Q''(''Y'') {{=}} ''P''(''x''{{ind|0}} + ''Y'')}}

Illustration pratique : Si {{math|''P''(''X'') {{=}} 4''X''{{3}} - 7''X''{{2}} + 3''X'' - 5}} et que l'on cherche à écrire {{math|''P''(2 + ''Y'')}}, on applique 4 fois la méthode de division euclidienne par {{math|''X'' - 2}} :

{| border cellspacing="0"
|-style="text-align:center"
| bgcolor="#b3e2d1" |Coefficients de {{mvar|P}}
|width = "80"|4
|width = "80"| − 7
|width = "80"|3
|width = "100"|− 5
|-style="text-align:center"
| bgcolor="#b3e2d1" |Coefficients de {{math|''P''{{ind|1}}}} ||4||8 − 7 = 1||2 + 3 = 5
|bgcolor="#b3e2d1" |10 − 5 = 5
|-style="text-align:center"
| bgcolor="#b3e2d1" |Coefficients de {{math|''P''{{ind|2}}}} ||4||8 + 1 =9
|bgcolor="#b3e2d1" |18 + 5 = 23|| 
|-style="text-align:center"
| bgcolor="#b3e2d1" |Coefficients de {{math|''P''{{ind|3}}}} ||4
|bgcolor="#b3e2d1"|8 + 9 =17|| || 
|-style="text-align:center"
| bgcolor="#b3e2d1" |Coefficients de {{math|''P''{{ind|4}}}}  
|bgcolor="#b3e2d1"|4|| || || 
|}

Donc
:<math> P(2 + Y) = 4Y^3+17Y^2+23Y+5\,</math>

== Valeur approchée d'une racine ==
Pour chercher la valeur approchée x d'une racine d'un polynôme {{mvar|P}}, on cherche un entier {{math|''x''{{ind|0}}}} tel que {{math|''P''(''x''{{ind|0}})}} et {{math|''P''(''x''{{ind|0}} + 1)}} soient de signe contraire. On sait alors, d'après le [[théorème des valeurs intermédiaires]], qu'il existe une racine entre {{math|''x''{{ind|0}}}} et {{math|''x''{{ind|0}} + 1}}. On pose alors {{math|''x {{=}} x''{{ind|0}} + ''y''/10}}. Le nombre {{mvar|x}} est racine de {{math|''P''(''X'')}} si et seulement si le nombre {{math|''y''/10}} est racine de {{math|''P''(''x''{{ind|0}} + ''Y'') {{=}} ''Q''(''Y'')}}. Ce polynôme {{mvar|Q}} se détermine grâce à la méthode de Horner. Enfin {{mvar|x}} est racine de P(X) si et seulement {{mvar|y}} est racine d'un polynôme {{math|''R''(''X'')}} obtenu en multipliant les coefficients {{mvar|b{{ind|k}}}} de {{mvar|Q}} par <math>10^{n-k}</math>.

Il s'agit alors de chercher une racine de {{mvar|R}} comprise entre 0 et 10 en utilisant un processus analogue : on cherche un entier {{math|''x''{{ind|1}}}} compris entre 0 et 9 tels que {{math|''R''(''x''{{ind|1}})}} et {{math|''R''(''x''{{ind|1}} + 1)}} soient de signe contraire. On sait alors qu'il existe une racine {{mvar|x}} de {{mvar|P}} comprise entre {{math|''x''{{ind|0}} + ''x''{{ind|1}}/10}} et {{math|''x''{{ind|0}} + (''x''{{ind|1}} + 1)/10}}...

On détermine ainsi les décimales successives du [[développement décimal]] de {{mvar|x}}.

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

Il s'agit de trouver un réel {{mvar|x}}, racine du polynôme {{math|''P''(''X'') {{=}} ''X''{{3}} - 18}}. On sait immédiatement que {{math|''P''(2) < 0}} et {{math|''P''(3) > 0}}, {{mvar|x}} est donc compris entre 2 et 3. On pose alors {{math|''x'' {{=}} 2+ ''y''/10}} et on cherche le polynôme {{mvar|Q}} tel que {{math|''P''(2 + ''Y'') {{=}} ''Q''(''Y'')}}.

{| border cellspacing="0"
|-style="text-align:center"
| bgcolor="#b3e2d1" |Coefficients de {{mvar|P}}
|width = "80"|1
|width = "80"| 0
|width = "80"|0
|width = "100"|- 18
|-style="text-align:center"
| bgcolor="#b3e2d1" |Coefficients de {{math|''P''{{ind|1}}}} ||1||2||4
|bgcolor="#b3e2d1" |- 10 
|-style="text-align:center"
| bgcolor="#b3e2d1" |Coefficients de {{math|''P''{{ind|2}}}} ||1||4
|bgcolor="#b3e2d1" |12|| 
|-style="text-align:center"
| bgcolor="#b3e2d1" |Coefficients de {{math|''P''{{ind|3}}}} ||1
|bgcolor="#b3e2d1"|6|| || 
|-style="text-align:center"
| bgcolor="#b3e2d1" |Coefficients de {{math|''P''{{ind|4}}}} 
|bgcolor="#b3e2d1"|1|| || || 
|}

Le réel {{mvar|x}} est racine cubique de 18 si {{math|''x'' {{=}} 2 + ''y''/10}} où {{mvar|y}} est racine de {{math|''R''(''X'') {{=}} ''X''{{3}} + 60''X''{{2}} + 1200''X'' - 10000}}. La racine {{mvar|y}} est comprise entre 6 et 7 (pour éviter de balayer tous les nombres, il suffit de remarquer que {{math|1200''y''}} et 10000 doivent être très proches avec {{math|1200''y'' < 10000}}). On pose alors {{math|''y'' {{=}} 6 + ''z''/10}} et on cherche le polynôme {{mvar|S}} tel que {{math|''R''(6  + ''Z'') {{=}} ''S''(''Z'')}}.

{| border cellspacing="0"
|-style="text-align:center"
| bgcolor="#b3e2d1" |Coefficients de {{mvar|R}}
|width = "80"|1
|width = "80"| 60
|width = "80"|1200
|width = "100"|-10000
|-style="text-align:center"
| bgcolor="#b3e2d1" |Coefficients de {{math|''R''{{ind|1}}}} ||1||66||1596
|bgcolor="#b3e2d1" |-424 
|-style="text-align:center"
| bgcolor="#b3e2d1" |Coefficients de {{math|''R''{{ind|2}}}} ||1||72
|bgcolor="#b3e2d1" |2028|| 
|-style="text-align:center"
| bgcolor="#b3e2d1" |Coefficients de {{math|''R''{{ind|3}}}} ||1
|bgcolor="#b3e2d1"|78|| || 
|-style="text-align:center"
| bgcolor="#b3e2d1" |Coefficients de {{math|''R''{{ind|4}}}}  
|bgcolor="#b3e2d1"|1|| || || 
|}

Le réel {{mvar|y}} est racine de {{mvar|R}} si {{math|''y'' {{=}} 6 + ''z''/10}} où {{mvar|z}} est racine de {{math|''T''(''X'') {{=}} ''X''{{3}} + 780''X''{{2}}  + 202800''X'' - 424000}}. La racine {{mvar|z}} est comprise entre 2 et 3. Donc {{mvar|y}} est compris entre 6,2 et 6,3 et {{mvar|x}} est compris entre 2,62 et 2,63.

== Dérivées successives de {{mvar|P}} en {{math|''x''{{ind|0}}}} ==
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 {{math|''P''{{exp|(''k'')}}(''x''{{ind|0}})}}. En effet, le développement de Taylor de {{math|''P''(''x''{{ind|0}} + ''Y'')}}  donne
: <math>P(x_0+Y) = P(x_0) + P'(x_0)Y + \frac{P^{(2)}(x_0)}{2}Y^2+\cdots+\frac{P^{(k)}(x_0)}{k!}Y^k + \cdots \,</math>
Si on note {{math|''Q''(''Y'') {{=}} ''P''(''x''{{ind|0}} + ''Y'')}}, les coefficients {{mvar|b{{ind|k}}}} de {{mvar|Q}}, trouvés par la méthode de Ruffini-Horner vérifient l'égalité
: <math>k!b_k=P^{(k)}(x_0)\,</math>

== Annexes ==
=== Notes et références ===
{{références}}

{{Palette|Polynômes}}
{{portail|informatique théorique|mathématiques}}

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