Algorithme de Neville

Soit un jeu de n+1 points donnés (x_i, y_i) où les x_i sont distincts deux à deux, et le polynôme d'interpolation p(x) de degré au plus n vérifiant:

${\displaystyle p(x_{i})=y_{i},\,i=0,\ldots ,n.}$

L'algorithme de Neville évalue ce polynôme pour le point d'abscisse x.

Soit p_i,j(x) le polynôme de degré j qui passe par les points (x_k, y_k) pour k = i, i + 1, …, i+j.

Les p_i,j(x) satisfont à la relation de récurrence

${\displaystyle p_{i,0}(x)=y_{i},\,}$	${\displaystyle 0\leq i\leq n,\,}$
${\displaystyle p_{i,j+1}(x)={\frac {(x_{i}-x)p_{i-1,j}(x)+(x-x_{i-j-1})p_{i,j}(x)}{x_{i}-x_{i-j-1}}},\,}$	${\displaystyle 0\leq j<n{\text{ et }}0\leq i<n-j.\,}$

Cette relation de récurrence permet de calculer p_0,n(x), qui est la valeur cherchée. Il nécessite O(n²) opérations en virgule flottante.

Par exemple, pour n = 4, on peut utiliser la relation de récurrence pour remplir le tableau triangulaire ci-dessous, de gauche à droite.

${\displaystyle p_{0,0}(x)=y_{0}\,}$
	${\displaystyle p_{0,1}(x)\,}$
${\displaystyle p_{1,0}(x)=y_{1}\,}$		${\displaystyle p_{0,2}(x)\,}$
	${\displaystyle p_{1,1}(x)\,}$		${\displaystyle p_{0,3}(x)\,}$
${\displaystyle p_{2,0}(x)=y_{2}\,}$		${\displaystyle p_{1,2}(x)\,}$		${\displaystyle p_{0,4}(x)\,}$
	${\displaystyle p_{2,1}(x)\,}$		${\displaystyle p_{1,3}(x)\,}$
${\displaystyle p_{3,0}(x)=y_{3}\,}$		${\displaystyle p_{2,2}(x)\,}$
	${\displaystyle p_{3,1}(x)\,}$
${\displaystyle p_{4,0}(x)=y_{4}\,}$

On obtient ainsi p_0,4(x), la valeur à l'abscisse x du polynôme d'interpolation passant par les 5 points donnés.

Soit p_i,j(x) le polynôme de degré j qui passe par les points (x_k, y_k) pour k = i, i + 1, …, i+j, et soit f_i,j le coefficient du terme de degré j de ce polynôme, c'est-à-dire:

${\displaystyle p_{i,j}(x)=f_{i,j}x^{j}+...~}$

p_i,j(x) passe par les points numérotés i, i + 1, …, i+j

p_i+1,j(x) passe par les points numérotés i + 1, …, i+j,i+j+ 1

p_i,j+1(x) passe par les points numérotés i, i + 1, …, i+j,i+j+ 1

Les polynômes p_i,j+1(x) et p_i,j(x) ont les points i, i + 1, …, i+j en commun. Il suit que la soustraction p_i,j+1(x) - p_i,j(x) de ces deux polynômes s'annulera pour les j+1 abscisses de ces points. Autrement dit les abscisses ${\displaystyle x_{i}}$, ... , ${\displaystyle x_{i+j}}$ sont racines du polynôme p_i,j+1(x) - p_i,j(x). Comme p_i,j+1(x) - p_i,j(x) est un polynôme de degré j+1, il possède au plus j+1 racines. Donc finalement nous connaissons toutes ses racines, ce sont les abscisses: ${\displaystyle x_{i}}$, ... , ${\displaystyle x_{i+j}}$. Nous pouvons dès lors écrire ce polynôme sous forme factorisée:

${\displaystyle p_{i,j+1}(x)-p_{i,j}(x)=f_{i,j+1}(x-x_{i})(x-x_{i+1})...(x-x_{i+j})~}$

En employant la même méthode, on trouve aussi :

${\displaystyle p_{i,j+1}(x)-p_{i+1,j}(x)=f_{i,j+1}(x-x_{i+1})(x-x_{i+2})...(x-x_{i+j+1})~}$

En divisant ces deux relations membre à membre, on obtient :

${\displaystyle {\frac {p_{i,j+1}(x)-p_{i,j}(x)}{p_{i,j+1}(x)-p_{i+1,j}(x)}}={\frac {x-x_{i}}{x-x_{i+j+1}}}}$

dont on peut isoler p_i,j+1 pour retrouver la relation de récurrence de Neville :

${\displaystyle p_{i,j+1}(x)={\frac {(x_{i}-x)p_{i+1,j}(x)+(x-x_{i+j+1})p_{i,j}(x)}{x_{i}-x_{i+j+1}}}~}$

Par ailleurs, en employant la même méthode que précédemment, on peut obtenir:

${\displaystyle p_{i+1,j}(x)-p_{i,j}(x)=(f_{i+1,j}-f_{i,j})(x-x_{i+1})(x-x_{i+2})...(x-x_{i+j})~}$

et en utilisant l'égalité évidente :

${\displaystyle p_{i,j+1}(x)-p_{i,j}(x)=p_{i,j+1}(x)-p_{i+1,j}(x)+p_{i+1,j}(x)-p_{i,j}(x)~}$

on obtient :

${\displaystyle f_{i,j+1}(x-x_{i})=f_{i,j+1}(x-x_{i+j+1})+(f_{i+1,j}-f_{i,j})~}$

qui fournit un algorithme récursif de calcul de ces coefficients :

${\displaystyle f_{i,0}=y_{i},\,}$	${\displaystyle 0\leq i\leq n,\,}$
${\displaystyle f_{i,j+1}={\frac {f_{i+1,j}-f_{i,j}}{x_{i+j+1}-x_{i}}}}$	${\displaystyle 0\leq j<n{\text{ et }}0\leq i<n-j.\ }$

Ces coefficients sont appelés différences divisées, notées :

${\displaystyle f_{i,j}=f[x_{i},\ldots ,x_{i+j}],}$

et sont utilisés pour calculer le polynôme d'interpolation de Newton.

L'algorithme de Neville est plus économique numériquement que l'interpolation newtonienne lorsque le nombre de points à évaluer est faible (typiquement, inférieur aux nombre de points d'interpolation). Au delà, il vaut mieux calculer une fois pour toutes les différences divisées, et utiliser la méthode de Newton.

L'algorithme de Neville est utilisé notamment dans la méthode de Romberg, une méthode d'intégration numérique.

• Interpolation polynomiale
• Interpolation lagrangienne
• Interpolation newtonienne
• Extrapolation de Richardson

• (en) William Press, Saul Teukolsky, William Vetterling et Brian Flannery, Numerical Recipes, Cambridge University Press, 1992, 2^e éd., 994 p. (ISBN 978-0-521-43108-8, DOI 10.2277/0521431085, lire en ligne), « §3.1 Polynomial Interpolation and Extrapolation »

• (en) Eric W. Weisstein, « Neville's Algorithm », sur MathWorld
• Module for Neville Interpolation by John H. Mathews

• Portail de l'analyse