Algorithmique ii - Factorisation de Hörner

Présentation de l'algorithme.

On veut calculer efficacement l'image \(P(x)\) d'un nombre réel \(x\) par une fonction polynomiale associée à un polynôme \(P\) de degré \(n\) : \begin{equation}\label{exp} P(X) = a_nX^n + a_{n-1}X^{n-1} + \cdots + a_2X²+a_1X+a_0. \end{equation}

L'écriture du polynôme suggère de procéder itérativement en sommant chacun des monômes évalué en \(x\), ce qui implique de calculer à chaque fois une exponentielle dont le coût est prohibitif comme nous le verrons à la section suivante.

La méthode dite de la factorisation de Horner (qui n'est pas réellement une factorisation au sens usuel) consiste à écrire le polynôme \(P(X)\) sous la forme \({\color{#46F}P_1(X)}.X+a_0\) et à répéter cette opération pour le polynôme \(P_1(X)\) et ainsi de suite jusqu'au polynôme constant \({\color{yellow}P_{n}(X)}=a_n\) qui achève le pro­ces­sus : \begin{align*} P(X) &= \big({\color{#46F}a_nX^{n-1} + a_{n-1}X^{n-2} + \cdots + a_2X+a_1}\big)X+a_0\\ &= \big((a_nX^{n-2} + a_{n-1}X^{n-3} + \cdots + a_2)X+a_1\big)X+a_0\\ &\ \,\vdots\\ &= \Big(\big(\ldots({\color{#FF0}a_n}X + a_{n-1})X + a_{n-2})X + \cdots + a_2\big)X+a_1\Big)X+a_0 \end{align*}

On peut construire cette suite de polynômes \(P_k(X)\) par la relation de récurrence suivante, où le premier terme \(P_0(X)\) de la suite est défini par le polynôme \(P(X)\) : \begin{align}\label{rec} P_k(X):= \begin{cases} P(X),&\text{si}\ k=0.\\ \frac{1}{X}(P_{k-1}(X)-a_{k-1}),&\text{si}\ 1\leq k \leq n. \end{cases} \end{align}

Avec la définition récurrente des polynômes \(P_k\) ci-dessus, vérifiez que \(P_n(X)=a_n\).

L'algorithme itératif de Horner consiste à remonter le processus défini par la relation de récurrence \((\ref{rec})\) en partant du polynôme constant \(P_n=a_n\). On évalue alors à chaque étape une fonction affine dont le résultat devient le coefficient du monôme \(X\) pour la suivante.

Horner(P,x):réel
données
   P: liste de n + 1 réels 
   x: réel
variables
   R: réel
   i: entier
debut
   R ← 0
   i ← 0
   TQ (i ≤ n) FAIRE
      R ← R * x + P[n - i]
      i ← i + 1
   FTQ
   retourner R
fin

Notons que la méthode est plus générale et qu'elle s'applique à tout polynôme, que les coefficients soient réels ou non.

Complexité.

Pour les même raisons que pour l'exponentiation, c'est le coût en nombre de multiplications qui va nous intéresser, nous faisons donc l'hypothèse que les valeurs sont bornées ce qui nous évite d'intégrer le coût de ces opérations (le tp sur le calcul multiprécision a pour objet de mettre en évidence que cette hypothèse n'est pas toujours pertinente). Étudions brièvement le cas de l'algorithme naïf ci-dessous au préalable:

EvalNaive(P,x):réel
données
   P: liste de n + 1 réels
   x: réel
variables
   R: réel
   i: entier
debut
   R ← P[0]
   i ← 1
   TQ (i ≤ n) FAIRE
      R ← R + P[i] * Exp(x,i)
      i ← i + 1
   FTQ
   retourner R
fin

Cet algorithme est basé sur une boucle qui calcule chaque terme \(a_kX^k\) du polynôme \(P(X)\) et l'additionne aux résultats qui précèdent. L'évaluation de ce terme demande exactement \(k\) produits dont \(k-1\) pour l'exponentiation Exp (en supposant qu'elle se fait naïvement elle aussi) et \(1\) pour multiplier le coefficient. On a donc au total:

\(\displaystyle \sum_{i=0}^n i=\frac{n(n+1)}{2}\) multiplications.

Le nombre de multiplications effectuées dans l'algorithme de Horner est \(n+1\) puisqu'il n'y a qu'une seule opération de multiplication dans la boucle et que l'on y passe \(n+1\) fois. Finalement, on passe d'une complexité quadratique en nombre de multiplications avec l'algorithme naïf à une complexité linéaire. L'exercice montre que l'utilisation de l'algorithme square & multiply donnerait une complexité en \(n\log_2 n\), donc intermédiaire entre les deux.

En supposant que l'algorithme naïf utilise non pas l'exponentiation naïve mais l'algorithme Square & Multiply pour calculer \(X^k\), quelle serait le nombre de multiplications réalisées ?

Travaux pratiques

On se propose de comparer trois algorithmes pour évaluer une fonction polynomiale \(P\) en \(a\). Chacun des trois algorithmes suivants doit renvoyer non seulement la valeur \(P(a)\) mais également le nombre de multiplications effectuées pour l'obtenir.

Écrivez une fonction Eval-Naif(P,a) qui calcule la valeur de la fonction polynomiale \(P\) en \(a\) de manière directe en utilisant l'algorithme d'exponentiation naïf. Attention, si vous utilisez l'exponentiation de Python, à savoir x**n pour écrire l'algorithme naïf, vous utiliserez indirectement l'algorithme Square & Multiply, il est donc indispensable pour que la comparaison ait un sens d'écrire une fonction d'exponentiation naïve (cf. algorithme présenté plus haut).
Écrivez une fonction Eval-SM(P,a) qui calcule la valeur de la fonction polynomiale \(P\) en \(a\) de manière directe en utilisant la fonction d'exponentiation vue dans l'algorithme Square & Multiply.
Écrivez une fonction Eval-Horner(P,a) qui calcule la valeur de la fonction polynomiale \(P\) en \(a\) en implantant la méthode de Hörner décrite plus haut;
Écrivez une fonction Creer-Poly(n) qui renvoie un polynôme de degré \(n\), donc une liste de \(n+1\) termes non-nuls. Cette liste servira pour l'évaluation empirique de la complexité des trois algorithme, les coefficients peuvent être tirés au hasard ou fixés arbitrairement du moment qu'aucun d'entre eux n'est égal à 0;
Comparez le nombre de multiplications nécessaires aux trois algorithmes pour calculer \(P(a)\) en fonction du degré \(n\) du polynôme \(P(X)\). Pour cela, tracez les fonctions de coût en multiplications en fonction du degré \(n\) du polynôme \(P\) de ces trois algorithmes sur un graphique. Utilisez la commande gnuplot.

Pour cet exercice, les couples \((n,T(n))\) doivent être rangés sur deux colonnes dans un fichier texte (sans parenthèse, ni virgule, l'espacement faisant office de séparateur entre \(n\) et \(T(n)\)). Pour tracer les trois courbes simultanément dans la même fenêtre graphique, sous l'environnement gnuplot, lancez la commande plot NomFichier1, puis replot NomFichier2 et replot NomFichier3.

Les données des trois fonctions de complexité sont à générer automatiquement dans des fichiers textes à l'aide d'un programme Python, pas à la main! De la même manière, on écrira le script gnuplot dans un fichier intitulé comparer-eval.gnu dont la dernière commande sera pause -1 afin de conserver l'affichage des trois courbes à l'écran. Le lancement du script se fait sous un terminal avec la commande gnuplot comparer-eval.gnu.

Solutions des tp en Python : Horner.py