Développement : Un algorithme de programmation dynamique pour les polynômes d'interpolation de Lagrange

Détails/Enoncé :

On trouve une relation de récurrence entre le polynôme d'interpolation de $f$ en $(x_0,x_1,\dots,x_{n-1})$ et celui de $f$ en $(x_0,x_1,\dots,x_n)$, ce qui permet d'écrire un algorithme dynamique pour évaluer ces polynômes d'interpolation en $x$.

Autres années :

Versions :

  • Auteur :
  • Remarque :
    La preuve de la relation de récurrence sert aussi de preuve de correction de l'algorithme, ce qui justifie le recasage dans la leçon 927, car les preuves de correction des algorithmes dynamiques sont particulières : elles interviennent avant même l'écriture de l'algorithme, car cette preuve revient à prouver la relation de récurrence sur laquelle repose l'algorithme.
  • Référence :
  • Fichier :