Interpolation de Neville

L'algorithme de Neville-Aikten permet d'interpoler un ensemble de points $ (x_i,y_i) $ et, si nécessaire, d'obtenir l'expression du polynôme d'interpolation.

La méthode repose sur la construction récursive de polynômes $ P_{ij}(x) $ qui convergent progressivement vers le polynôme final.

L'interpolation de Neville utilise 3 étapes :

1 - Initialiser des polynomes de degre 0 : $ P_i(x) = y_i $ pour chaque point $ (x_i,y_i) $.

2 - Construire les polynomes d'ordre superieur par la relation de recurrence : $$ P_{ij}(x) = \frac{(x_j-x)P_i(x) + (x-x_i)P_j(x)}{x_j-x_i} $$

3 - Réitérer jusqu'à obtenir le polynome final

L'algorithme peut etre represente sous forme de pyramide, chaque niveau combinant deux polynomes du niveau precedent jusqu'a obtenir le polynome final (la fonction d'interpolation).

L'interpolation par Neville-Aikten presente plusieurs limitations pratiques. Les calculs deviennent rapidement couteux lorsque le nombre de points augmente, car l'algorithme requiert la construction de $ O(n^2) $ valeurs intermédiaires.

Ces contraintes conduisent dCode à limiter le nombre d'ordonnées distinctes dans l'ensemble Q.

L'algorithme de Neville applique de manière récursive la formule barycentrique qui sous-tend l'interpolation de Lagrange. Le polynome final construit par Neville est algébriquement identique au polynome de Lagrange. Neville fournit cependant une méthode numériquement plus stable pour évaluer ce polynome en un point donné, sans nécessiter d'écrire préciser la somme des termes de Lagrange.