====== Polynômes : la méthode de Horner ======

<note important>Avez vous remarqué que 7x<sup>4</sup> + 11x<sup>3</sup> + 3x<sup>2</sup> + 5x +2 =  ( ( ( 7 x + 11 ) x + 3 ) x + 5 ) x + 2 ?</note>
Cela revient à effectuer les opérations successives suivantes :

  * prendre le coefficient de x<sup>4</sup>
  * multiplier par x
  * ajouter le coefficient de x<sup>3</sup>
  * multiplier par x
  * ajouter le coefficient de x<sup>2</sup>
  * multiplier par x
  * ajouter le coefficient de x<sup>1</sup>
  * multiplier par x
  * ajouter le coefficient de x<sup>0</sup>

Nous avons donc 4 multiplications à effectuer, et pas 4 + 3 + 2 + 1 multiplications en absence de réarrangement.  De plus, on répète systématiquement l'alternance des opérations "multiplier par x" et "ajouter un coefficient".

Cette façon d'évaluer le polynôme s'appelle la [[wp>fr:Méthode_de_Ruffini-Horner|méthode de Horner]] et est particulièrement efficace lorsque n est grand. La méthode débouche sur un algorithme facile à écrire sous forme d'une instruction de répétition.

<note tip>Plutôt que de lire tout de suite la solution ci-dessous, trouvez cet algorithme seul. Il est très court !</note>

<code python poly06-horner.py>
#!/usr/bin/env python
# -*- coding: UTF-8 -*-
"""
écriture d'un programme pour évaluer
des polynomes
"""
from math import *

def polyeval(x,a):
    """
    application de l'agorithme de Horner
    cf. http://fr.wikipedia.org/wiki/M%C3%A9thode_de_Ruffini-Horner
    """
    n = len(a) - 1
    p = 0.
    for i in range(n,-1,-1):
        p = p * x + a[i]
    return p
    
x = 2.   # x particulier
a = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] # coefficients particuliers
print(polyeval(x,a))   # on doit obtenir un exposant de deux moins un

varx = 0.5
varcoef = [1., 2., 3., 4., 5., 6., 7., 8., 9., 10.]
print(polyeval(varx,varcoef))

for j in range(0,11,1):
    vax = float(j) * 0.1
    rep = sin(polyeval(vax,varcoef))
    print(rep)
</code>

Écrivons à présent d'autres fonctions qui seront très utiles pour manipuler des polynômes. Pour commencer :
  - la fonction de multiplication d'un polynôme pas un scalaire
  - la fonction d'addition de deux polynômes

<note tip>La première fonction est facile. Demandez-vous avant tout les paramètres à fournir à la fonction, et ce qu'elle doit renvoyer !

Pour la deuxième fonction, décortiquez la façon de procéder sur quelques exemples simples.</note>

[[polynomes-7|Proposition à la page suivante !]]