Neville Eric Harold

Imaginez trois mesures connues sur une courbe : à l'abscisse 0, la valeur vaut 1 ; à l'abscisse 1, elle vaut 3 ; à l'abscisse 2, elle vaut 2. L'algorithme de Neville donne une estimation à une abscisse située entre ces points, sans demander d'écrire d'abord toute l'équation de la courbe.

Pour obtenir la valeur en 0,5, il commence par mélanger les deux premiers points, puis les deux derniers, avant de combiner ces résultats. Chaque mélange est une moyenne pondérée par la position de 0,5. Les calculs successifs conduisent à 2, 3,5, puis 2,375 : la dernière valeur est l'estimation cherchée.

L'algorithme de Neville est une procédure récursive d'interpolation polynomiale. À partir de points de données distincts (x₀, y₀), …, (xₙ, yₙ), il calcule directement la valeur au point x d'un polynôme de degré au plus n qui passe par ces données. Il organise les résultats dans un tableau triangulaire : la diagonale initiale contient les yᵢ, puis chaque case combine deux cases du niveau précédent.

Si Pᵢ,ᵢ(x)=yᵢ, la récurrence de Neville est $P_{i,j}(x)=\frac{(x-x_i)P_{i+1,j-1}(x)-(x-x_j)P_{i,j-1}(x)}{x_j-x_i}P\_\{i,j\}(x)=\backslash frac\{(x-x\_i)P\_\{i+1,j-1\}(x)-(x-x\_j)P\_\{i,j-1\}(x)\}\{x\_j-x\_i\}$ pour i

Cette construction donne le même polynôme interpolateur que la forme de Lagrange, mais elle évite de développer explicitement tous ses termes. Elle est particulièrement adaptée à l'évaluation en un point ; elle ne constitue pas, à elle seule, une méthode de justification historique ou une garantie de bonne approximation hors de l'intervalle des données.

On reprend trois points : (x₀,y₀)=(0,1), (x₁,y₁)=(1,3) et (x₂,y₂)=(2,2). On cherche l'interpolation au point x=0,5. Les abscisses sont distinctes, donc les divisions de la récurrence sont possibles.

1. La diagonale de départ contient P₀,₀=1, P₁,₁=3 et P₂,₂=2.
2. Avec les deux premiers points, la formule donne $P_{0,1}(\mathrm{0,5})=2P\_\{0,1\}(0\{,\}5)=2$. Avec les deux derniers, elle donne $P_{1,2}(\mathrm{0,5})=\mathrm{3,5}P\_\{1,2\}(0\{,\}5)=3\{,\}5$.
3. On combine ces deux valeurs : $P_{0,2}(\mathrm{0,5})=\mathrm{2,375}P\_\{0,2\}(0\{,\}5)=2\{,\}375$.

Le résultat 2,375 est la valeur du polynôme de degré au plus 2 qui passe par les trois points à l'abscisse 0,5. Le tableau triangulaire peut être vérifié en remplaçant chaque case par la récurrence ; l'algorithme ne repose donc pas sur une lecture graphique approximative.

En pratique, on utilise l'algorithme de Neville lorsque plusieurs valeurs d'une fonction sont connues et qu'une valeur intermédiaire doit être estimée. On choisit les points les plus pertinents autour de l'abscisse visée, puis on remplit le tableau jusqu'à la case finale. Avec les données de l'exemple, cette case vaut 2,375 en 0,5.

Pour contrôler un calcul, on vérifie d'abord les valeurs de départ, puis chaque niveau du tableau et enfin la cohérence avec une représentation ou une autre forme de l'interpolant. Les points doivent être distincts et les unités doivent rester identiques pour les abscisses comme pour les ordonnées.

Interpolation et extrapolation. L'interpolation estime une valeur entre les abscisses connues, comme 0,5 entre 0 et 2 dans l'exemple. Une demande en dehors de cet intervalle est une extrapolation : le même polynôme peut y produire une valeur très sensible au choix des données.

Interpolation et ajustement. L'interpolation passe exactement par les points fournis. Un ajustement cherche plutôt une tendance qui peut laisser des écarts aux observations, par exemple lorsque les mesures comportent du bruit.

Neville et interpolation linéaire. Avec seulement deux points, Neville produit une interpolation linéaire. Avec trois points, comme (0,1), (1,3) et (2,2), il utilise un polynôme de degré au plus 2 ; le résultat 2,375 ne provient donc pas d'une simple droite entre les deux points voisins.

Abscisses répétées. Si deux abscisses xᵢ et xⱼ sont égales, le dénominateur xⱼ−xᵢ s'annule. La procédure présentée ne traite donc pas directement des abscisses répétées ; des données dérivées et une interpolation d'Hermite relèvent d'un cadre différent.

Degré et nombre de points. Avec n+1 points d'abscisses distinctes, l'interpolant est de degré au plus n. Ajouter des points ne garantit pas une meilleure approximation partout : un polynôme de degré élevé peut osciller, surtout près des extrémités.

Stabilité numérique. Des abscisses très proches ou des calculs effectués avec une précision limitée peuvent amplifier les erreurs d'arrondi. Pour une longue série de points, on choisit les points avec discernement et l'on compare le résultat à un calcul de contrôle.

Une estimation n'est pas une mesure nouvelle. La valeur 2,375 en 0,5 est imposée par le polynôme interpolateur construit à partir des trois données ; elle ne prouve pas que la fonction physique ou expérimentale étudiée prend réellement cette valeur si le modèle polynomial n'est pas justifié.

La fiche interpolation linéaire présente le cas élémentaire obtenu avec deux points.

La fiche interpolation polynomiale de Lagrange donne une autre écriture du même interpolant polynomial.

La fiche interpolation polynomiale d'Hermite prolonge la construction lorsque des valeurs de dérivées sont également imposées.

La fiche fonction elliptique rappelle l'un des domaines de recherche mentionnés dans le parcours de Neville.