Avancer

Section 3.3 Méthode de Horner

Comment utiliser efficacement l'ordinateur pour évaluer un polynôme?

Algorithme 1 : Approche naïve.

Considérant le polynôme

\begin{equation*} P(x)=10+7x+3x^2+5x^3 \end{equation*}

combien d'opérations mathématiques sont-elles nécessaires pour évaluer \(P(9)\text{?}\)

On a

\begin{equation*} P(9)=10+7\cdot 9+3\cdot 9\cdot 9+5\cdot 9\cdot 9\cdot 9. \end{equation*}

Vu comme ça, il faut trois (comme le degré) additions et six (\(1+2+3\)) multiplications, soit neuf opérations.

Plus généralement, pour un polynôme de degré \(n\)

\begin{equation*} P(x)=a_0+a_1x+\cdots+a_nx^n \end{equation*}

défini par la liste de ses coefficients \(\left[a_0,a_1,\ldots,a_n\right]\text{,}\) le calcul de \(P(x)\) peut nécessiter jusqu'à \(n\) additions et

\begin{equation*} 1+2+\cdots+n=\frac{n(n+1)}{2} \end{equation*}

multiplications, soit

\begin{equation*} n+\frac{n(n+1)}{2}=0{,}5\,n^2+1{,}5\,n \end{equation*}

opérations.

Cette approche naïve conduit à l'implémentation algorithmique

dont la complexité

\begin{equation*} T(n)=0{,}5\,n^2+1{,}5\,n \end{equation*}

est qualifiée de quadratique, c'est-à-dire qu'elle est polynomiale de degré deux.

Algorithme 2 : Méthode de Horner.

Pour améliorer l'algorithme précédent, on pourrait bien sûr utiliser l'exponentiation rapide vue à la section 3.2. Mais on peut faire encore mieux.

Reprenons l'exemple ci-dessus et notons que par factorisations successives de \(x\text{,}\) on obtient

\begin{align*} P(x)&=10+7x+3x^2+5x^3\\ &=10+x\cdot(7+3x+5x^2)\\ &=10+x\cdot(7+x\cdot(3+x\cdot 5)). \end{align*}

Vue comme ça, l'évaluation de \(P(x)\) ne requiert plus que trois additions et trois multiplications, soit six opérations.

Plus généralement, on appelle forme de Horner du polynôme

\begin{equation*} P(x)=a_0+a_1x+\cdots+a_nx^n \end{equation*}

la factorisation

\begin{equation*} P(x)=a_0+x\cdot\left(a_1+x\cdot\left(a_2+x\cdot\left(\cdots +x\cdot\left(a_{n-1}+x\cdot a_n\right)\right)\right)\right) \end{equation*}

qui nécessite \(n\) additions et \(n\) multiplications, soit \(2n\) opérations.

Pour bien comprendre comment programmer cela, il suffit de penser à la façon dont on effectue le calcul de \(P(x)\) une paire de parenthèses après l'autre. Par exemple, pour le polynôme

\begin{equation*} P(x)=10+7x+3x^2+5x^3, \end{equation*}

le calcul de

\begin{align*} P(9)&=10+7\cdot 9+3\cdot 9^2+5\cdot 9^3\\ &=10+9\cdot(7+3\cdot 9+5\cdot 9^2)\\ &=10+9\cdot(7+9\cdot(3+9\cdot 5)) \end{align*}

par la méthode de Horner revient à calculer les valeurs successives

\begin{equation*} \begin{array}{llll} \text{Étape 0 :}&valeur&=&5\\ \text{Étape 1 :}&valeur&=&3+9\cdot 5=48\\ \text{Étape 2 :}&valeur&=&7+9\cdot 48=439\\ \text{Étape 3 :}&valeur&=&10+9\cdot 439=3961 \end{array} \end{equation*}

dont la dernière donne

\begin{equation*} P(9)=3961 \end{equation*}

après trois additions et trois multiplications.

Dans le cas général, cet algorithme de calcul de \(P(x)\) peut donc être décrit comme suit.

\begin{equation*} \begin{array}{llll} \text{Étape 0 :}&\text{Assigner à}&valeur&\text{le contenu de }&a_n.\\ \text{Étape 1 :}&\text{Assigner à}&valeur&\text{le contenu de }&a_{n-1}+x\cdot valeur.\\ \text{Étape 2 :}&\text{Assigner à}&valeur&\text{le contenu de }&a_{n-2}+x\cdot valeur.\\ \ldots&\ldots&\ldots&\ldots&\ldots\\ \text{Étape n-1 :}&\text{Assigner à}&valeur&\text{le contenu de }&a_1+x\cdot valeur.\\ \text{Étape n :}&\text{Assigner à}&valeur&\text{le contenu de }&a_0+x\cdot valeur.\\ \end{array} \end{equation*}

Voici une implémentation itérative de la méthode de Horner.

La complexité de cet algorithme

\begin{equation*} T(n)=2n \end{equation*}

est linéaire, donc bien meilleure que la complexité quadratique obtenue par l'approche naïve, comme l'illustrent les graphes ci-après.

Figure 3.3.2. Linéaire vs quadratique