Algorithme de Neville

En analyse numérique, l'algorithme de Neville^[1] est un algorithme d'interpolation polynomiale dû à Eric Harold Neville.

L'algorithme de Neville est une méthode récursive du calcul de la valeur du polynôme d'interpolation en un point donné, avec lequel il est aisé d'ajouter des points d'interpolation au fur et à mesure. Il est moins adapté pour fournir une expression du polynôme d'interpolation. Il est parfois confondu avec l'algorithme d'Aitken^[2] .

Description de l'algorithme

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

p(x_i) = y_i pour tout i = 0,…,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

$p_{i,0}(x) = y_i, \,$	$0 \le i \le n, \,$
$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}}, \,$	$0\le j < n \text{ et } 0\le 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.

$p_{0,0}(x) = y_0 \,$
	$p_{0,1}(x) \,$
$p_{1,0}(x) = y_1 \,$		$p_{0,2}(x) \,$
	$p_{1,1}(x) \,$		$p_{0,3}(x) \,$
$p_{2,0}(x) = y_2 \,$		$p_{1,2}(x) \,$		$p_{0,4}(x) \,$
	$p_{2,1}(x) \,$		$p_{1,3}(x) \,$
$p_{3,0}(x) = y_3 \,$		$p_{2,2}(x) \,$
	$p_{3,1}(x) \,$
$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 4 points donnés.

Démonstration

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:

$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

p_i,j+1(x) et p_i,j(x) ont les points i, i + 1, …, i+j en commun, donc la soustraction de ces deux polynômes s'annulera pour les j + 1 abscisses de ces points.

Or, p_i,j+1(x) - p_i,j(x) est un polynôme de degré j + 1, qui possède j + 1 racines. Donc, nous connaissons toutes ses racines, et nous pouvons écrire ce polynôme sous forme factorisée:

$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:

$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:

$\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:

$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:

$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:

$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:

$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:

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

Ces coefficients sont appelés différences divisées, notées: $f_{i,j}=f[x_{i},\ldots,x_{i+j}],$

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

Exemple

Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue !

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 toute les différences divisés, 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.

Voir aussi

Interpolation polynomiale

Interpolation lagrangienne

Interpolation newtonienne

Extrapolation de Richardson

Notes

1. ↑ Iterative Interpolation, Eric Harold Neville, Indian Math. Soc., Jn., v. 20, 1933, p. 87-120.
2. ↑ On interpolation by iteration of proportional parts, without the use of differences, A. C. Aitken, Edinburgh Math. Soc., Proc., ser. 2, v. 3, 1932, p. 56-76.

Références

• , Numerical Recipes, Cambridge University Press, 1992 ([[Spécial:Ouvrages de référence/978-0-521-43108-8, DOI:10.2277/0521431085|ISBN 978-0-521-43108-8, DOI:10.2277/0521431085]]) [lire en ligne] 

Liens externes

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