Méthode de Ruffini-Horner - Définition

Valeur approchée d'une racine

Pour chercher la valeur approchée x d'une racine d'un polynôme P, 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 x est racine de P(X) si et seulement si le nombre y/10 est racine de . Ce polynôme Q se détermine grâce à la méthode de Horner. Enfin x est racine de P(X) si et seulement y est racine d'un polynôme R(X) obtenu en multipliant les coefficients b_k de Q par 10^{n − k}.

Il s'agit alors de chercher une racine de R 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 x de P comprise entre et ...

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

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

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

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

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

Changement de variable

L'algorithme précédent permet donc d'effectuer la division euclidienne du polynome P 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 Q tel que Q(Y) = P(x₀+Y)

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

Donc

Dérivées successives de P en x0

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 P(x₀ + Y) donne

Si on note Q(Y) = P(a + Y), les coefficients b_k de Q, trouvés par la méthode de Ruffini-Horner vérifient l'égalité