L’algorithme de Horner : Division euclidienne de polynômes

Dans cet article, nous allons vous expliquer l’algorithme de Horner, appelée aussi méthode de Horner, elle est notamment utile pour faire de la division euclidienne sur les polynômes.

Prérequis

• Degré d’un polynôme
• Racines d’un polynôme

Définition de l’algorithme de Horner

Soit \mathbb{K} un anneau. Soit P un polynôme de \mathbb{K}[X]. On pose P = \displaystyle \sum_{k = 0}^n a_k X^k

On peut faire la factorisation suivante sur P :

\begin{array}{ll}
P & = a_n X^n + \ldots + a_1X + a_0\\
P & = (a_n X^{n-1} + \ldots+ a_2X + a_1)X + a_0\\
P & = (  (a_n X^{n-2} + \ldots + a_2)X + a_1)X + a_0\\
P & =(  ( \ldots ((a_n X + a_{n-1})X+a_{n-2})X + \ldots)X +  a_1) X+ a_0\\
\end{array}

L’intérêt de cette écriture est qu’on minimise le nombre d’opération pour calculer P en un point x_0. On commence par le terme à l’intérieur de la parenthèse et on continue en calculant le résultant. Ainsi, on se limite à n additions et n multiplications.

Algorithmiquement c’est plus simple : calculer x_0^n nécessite déjà n-1 multiplications. (\lfloor\log_2(n)\rfloor me diront ceux qui veulent optimiser)

Applications à la division euclidienne

Cette méthode ne va fonctionner que pour faire la division euclidienne par un polynôme de degré 1. Pour un polynôme de degré k, il suffira alors de répéter k fois le processus.

Nous allons faire des exemples pour que ce soit plus simple à comprendre, mais voici la théorie générale. Supposons qu’on ait un polynôme P et qu’on souhaite faire sa division euclidienne par X- x_0.

  \begin{array}{ |c | c | }
     \hline
    \text{Coefficients de P} & \text{Facteur }x_0  \\ \hline
     a_n & b_{n-1} = a_n   \\ \hline
     a_{n-1} & b_{n-2}= a_n x_0+a_{n-1}  \\ \hline
     a_{n-2} & b_{n-3} = b_{n-1}x_0 + a_{n-2}  \\ \hline
     \vdots & \vdots  \\ \hline
     a_1 & b_0 = b_1 x_0 + a_1  \\ \hline
     a_0 & r = b_0 x_0 +a_0  \\ \hline
   \end{array}

On peut alors écrire P = (X- x_0) Q + r avec Q = \displaystyle \sum_{k=0}^{n-1} b_k X^k

Exemples

Faisons 2 exemples pour bien comprendre. Voici le premier : Faire la division euclidienne de P(X) = X^3 - 4X^2 - 3X +4 par X+2

  \begin{array}{ |c | c | }
     \hline
    \text{Coefficients de P} & \text{Facteur }-2 \\ \hline
     1 &1   \\ \hline
     -4 &-2 \times 1 - 4 = -6  \\ \hline
     -3 &-2 \times (-6) - 3=9  \\ \hline
     4 &-2 \times 9 + 4 = -14  \\ \hline
   \end{array}

Ainsi, on a P(X) = (X+2)(X^2 -6X+9) -14 = (X+2)Q(X) -14

Et voilà le second : Faire la division euclidienne de P(X) = X^4 + 2X^3 + 3X^2 +4X +5 par X-5

  \begin{array}{ |c | c | }
     \hline
    \text{Coefficients de P} & \text{Facteur }5  \\ \hline
     1 & 1   \\ \hline
     2 & 5 \times 1 + 2= 7  \\ \hline
     3 & 5\times 7 +3=38  \\ \hline
     4 & 5\times 38 + 4 = 194  \\ \hline
     5 & r = 975  \\ \hline
   \end{array}

Ainsi, on a P(X) = (X-5)(X^3 +7X^2 +38X + 194) + 975 = (X-5)Q(X) + 975