Mathématiques et algorithmique

Algorithme 7.2.1. Coefficients de la forme de Newton du polynôme interpolateur.

• Entrées :

  • Assigner à \(\text{n}\) le degré maximal du polynôme interpolateur.
  • Assigner à \(\text{x0},\text{x1},\ldots,\text{xn}\) les abscisses des points à interpoler.
  • Assigner à \(\text{y0},\text{y1},\ldots,\text{yn}\) les ordonnées des points à interpoler.

• Instructions :

  • Assigner la liste \(\text{y}\) comme premier élément de la liste \(\text{diffDiv}\) qui contiendra toutes les différences divisées.

  • Pour \(\text{j}\) allant de \(\text{1}\) à \(\text{n}\text{,}\)

    • initialiser \(\text{nouvelleColonne}\text{,}\) la liste qui contiendra toutes les différences divisées calculées à l'étape \(j\) : \(\text{nouvelleColonne}=\left[\;\right]\text{;}\)

    • pour \(\text{i}\) allant de \(\text{0}\) à \(\text{n-j}\text{,}\)

      • calculer la différence divisée \(\left[A_i,A_{i+1},\ldots,A_{i+j}\right]\) en utilisant la récursivité et l'assigner à \(\text{nouvelleDiffDiv}\) :

        \begin{equation*} \text{nouvelleDiffDiv} = \frac{\text{diffDiv}[j-1][i+1]-\text{diffDiv}[j-1][i]}{x[i+j]-x[i]}; \end{equation*}
      • ajouter la nouvelle différence divisée \(\text{nouvelleDiffDiv}\) à la liste \(\text{nouvelleColonne}\text{;}\)
    • ajouter \(\text{nouvelleColonne}\) à la liste \(\text{diffDiv}\text{.}\)

• Sortie : Pour \(\text{j}\) allant de \(\text{0}\) à \(\text{n}\text{,}\)

  • afficher \(\text{diffDiv}[j][0]\text{.}\)