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 Modèle:Math. Elle présente un algorithme simple effectuant la division euclidienne d'un polynôme par Modèle:Math. Mais elle offre aussi une méthode de changement de variable Modèle:Math 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 Modèle:Lien. Dans leurs premières publications, ces deux auteurs utilisent des méthodes de dérivations pour effectuer le changement de variable Modèle:Math. 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 Modèle:Ap JC) et dans le monde arabe, dans l'œuvre de Al Samaw'al (Modèle:S-). Mais il semble bien que le Perse, Sharaf al-Dīn al-Tūsī (Modèle:S-) soit le premier à l'utiliser dans le cas général d'une équation de degré 3.

Valeur d'un polynôme en un point

Soit

$P=a_n{X}^n+a_{n-1}{X}^{n-1}+\dots +a_0$

un polynôme et Modèle:Math un nombre. Le calcul de Modèle:Math

$P(x_0)=a_n{x}_0^n+a_{n-1}{x}_0^{n-1}+\dots +a_0$

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

Si on calcule les puissances de Modèle:Math en multipliant successivement Modèle:Math par lui-même, le nombre nécessaire de produits est alors de Modèle:Nobr, quantité qui croît comme le carré du degré du polynôme. On peut améliorer la vitesse du calcul de Modèle:Math par une méthode d'exponentiation rapide, permettant de réduire le temps du calcul de Modèle:Math à une quantité qui croît comme Modèle:Math. Ou plus efficacement encore, on peut commencer par calculer toutes les puissances de Modèle:Math, ce qui nécessite Modèle:Nobr multiplications, puis multiplier par les coefficients, ce qui nécessite n nouvelles multiplications : le nombre total de produit est alors Modèle:Nobr. La méthode de Horner consiste à combiner les deux itérations précédentes en une seule en effectuant le calcul comme suit :

$P(x_0)=((\dots ((a_n{x}_0+a_{n-1})x_0+a_{n-2})x_0+\dots )x_0+a_1)x_0+a_0$.

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é.

La méthode consiste donc à multiplier le premier coefficient par Modèle:Math et à lui ajouter le deuxième coefficient. On multiplie alors le nombre obtenu par Modèle:Math 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 Modèle:Math et en lui ajoutant le coefficient de la case du dessus.

Coefficients de Modèle:Mvar	Modèle:Mvar	Modèle:Math	Modèle:Math	…	Modèle:Math	Modèle:Math
Facteur Modèle:Math	Modèle:Mvar	Modèle:Math	Modèle:Math	…	Modèle:Math	Modèle:Math

Exemple pratique : Calcul de Modèle:Math pour Modèle:Math

Coefficients de Modèle:Mvar	4	−7	3	−5
Facteur 2	4	8 − 7 = 1	2 + 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 Modèle:Math, alors avec la méthode « classique », pour évaluer Modèle:Math, on doit calculer 100¹⁰ = 10²⁰ auquel on retranche 99×10¹⁸, donnant un résultat erroné sur des logiciels calculant avec 15 chiffres significatifs. Avec la méthode de Ruffini-Horner, on a

$P(100)=(100-99)\times 100^9$

conduisant au résultat correct 100⁹ = 10¹⁸ 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 Modèle:Math en écriture en base 10. En effet, si un nombre s'écrit, en base Modèle:Math,

$n=\overline{a_n{a}_{n-1}\cdots a_0}$,

ce nombre vaut

$n=a_n{x}_0^n+a_{n-1}{x}_0^{n-1}+\cdots +a_0$.

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	8
Facteur 16	13	13 × 16 + 10 = 218	218 ×16+ 7 = 3 495	DA78 = 3 495 × 16 + 8 = 55 928

Quotient d'un polynôme par Modèle:Math

Modèle:Article connexe Cette même méthode permet aussi d'obtenir la division d'un polynôme par Modèle:Math. Soit $P=a_n{X}^n+a_{n-1}{X}^{n-1}+...+a_0$.

La division euclidienne de Modèle:Mvar par Modèle:Math donne

$P=(X-x_0)Q+P(x_0)$

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

Si on écrit $Q=q_{n-1}{X}^{n-1}+q_{n-2}{X}^{n-2}+...+q_{1}X+q_0$ et si on identifie les coefficients de même degré dans les deux membres, on obtient :

$q_{n-1}=a_n$

$q_{k-1}-q_k{x}_0=a_k$ pour tout k tel que 0 < k < n

Soit encore

$q_{k-1}=q_k{x}_0+a_k$ 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 Modèle:Math. 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 Modèle:Math par Modèle:Math

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

Coefficients de Modèle:Mvar	4	− 7	3	− 5
Coefficients de Modèle:Mvar	4	8 − 7 = 1	2 + 3 = 5	Reste = 10 − 5 = 5

Donc

$4X^3-7X^2+3X-5=(X-2)(4X^2+X+5)+5$

Changement de variable

L'algorithme précédent permet donc d'effectuer la division euclidienne du polynôme Modèle:Mvar par Modèle:Math. On peut alors écrire, en posant Modèle:Math.

$P(X)=Y{P}_1(X)+b_0$

En utilisant de nouveau l'algorithme pour Modèle:Math, Modèle:Math, ... Modèle:Mvar, on obtient successivement

$P(X)=Y(Y{P}_2(X)+b_1)+b_0$

...

$P(X)=Y(Y(...Y(Y{b}_n+b_{n-1})...)+b_1)+b_0$

Les nombres Modèle:Math, Modèle:Math, ... Modèle:Mvar sont donc les coefficients du polynôme Modèle:Mvar tel que Modèle:Math

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

Coefficients de Modèle:Mvar	4	− 7	3	− 5
Coefficients de Modèle:Math	4	8 − 7 = 1	2 + 3 = 5	10 − 5 = 5
Coefficients de Modèle:Math	4	8 + 1 =9	18 + 5 = 23
Coefficients de Modèle:Math	4	8 + 9 =17
Coefficients de Modèle:Math	4

Donc

$P(2+Y)=4Y^3+17Y^2+23Y+5$

Valeur approchée d'une racine

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

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

On détermine ainsi les décimales successives du développement décimal de Modèle:Mvar.

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

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

Coefficients de Modèle:Mvar	1	0	0	- 18
Coefficients de Modèle:Math	1	2	4	- 10
Coefficients de Modèle:Math	1	4	12
Coefficients de Modèle:Math	1	6
Coefficients de Modèle:Math	1

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

Coefficients de Modèle:Mvar	1	60	1200	-10000
Coefficients de Modèle:Math	1	66	1596	-424
Coefficients de Modèle:Math	1	72	2028
Coefficients de Modèle:Math	1	78
Coefficients de Modèle:Math	1

Le réel Modèle:Mvar est racine de Modèle:Mvar si Modèle:Math où Modèle:Mvar est racine de Modèle:Math. La racine Modèle:Mvar est comprise entre 2 et 3. Donc Modèle:Mvar est compris entre 6,2 et 6,3 et Modèle:Mvar est compris entre 2,62 et 2,63.

Dérivées successives de Modèle:Mvar en Modèle:Math

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 Modèle:Math. En effet, le développement de Taylor de Modèle:Math donne

$P(x_0+Y)=P(x_0)+P^{\prime }(x_0)Y+\frac{P^{(2)}(x_0)}{2}{Y}^2+\cdots +\frac{P^{(k)}(x_0)}{k!}{Y}^k+\cdots$

Si on note Modèle:Math, les coefficients Modèle:Mvar de Modèle:Mvar, trouvés par la méthode de Ruffini-Horner vérifient l'égalité

$k!b_k=P^{(k)}(x_0)$