Algorithme de Neville

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] .

Sommaire

Description de l'algorithme

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

p(xi) = yi pour tout i = 0,…,n

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

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

Les pi,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 p0,n(x), qui est la valeur cherchée. Il nécessite O(n2) 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 p0,4(x), la valeur à l'abscisse x du polynôme d'interpolation passant par les 4 points donnés.


Démonstration

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

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

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

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

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

pi,j+1(x) et pi,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, pi,j+1(x) - pi,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 pi,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

Liens externes


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Algorithme de Neville de Wikipédia en français (auteurs)

Игры ⚽ Нужен реферат?

Regardez d'autres dictionnaires:

  • Epsilon algorithme — Pour les articles homonymes, voir Epsilon (homonymie). En analyse numérique, l ε algorithme est un algorithme non linéaire d accélération de la convergence de suites numériques. Cette algorithme a été proposé par Peter Wynn[1] en 1956 pour… …   Wikipédia en Français

  • Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… …   Wikipédia en Français

  • Interpolation polynomiale — En mathématiques, en analyse numérique, l interpolation polynomiale est une technique d interpolation d un ensemble de données ou d une fonction par un polynôme. En d autres termes, étant donné un ensemble de points (obtenu, par exemple, à la… …   Wikipédia en Français

  • Extrapolation de Richardson — En analyse numérique, le procédé d extrapolation de Richardson est une technique d accélération de la convergence. Il est ainsi dénommé en l honneur de Lewis Fry Richardson[1],[2], qui l a introduit au début du XXe siècle. Ce procédé est… …   Wikipédia en Français

  • Harold Scott MacDonald Coxeter — Harold Coxeter, 1970 Harold Scott MacDonald «Donald» Coxeter (9 février 1907, Londres 31 mars 2003, Toronto, Canada) est un mathématicien britannique. Il est considéré comme un des grands géomètres du XXe siècle. Une de ses idées originales… …   Wikipédia en Français

  • Liste D'économistes — Vous trouverez classés alphabétiquement des économistes célèbres, parce qu ils ont reçu le prix de la Banque de Suède en sciences économiques en mémoire d Alfred Nobel ou un prix internationalement reconnu, ou parce que qu ils sont auteurs de… …   Wikipédia en Français

  • Liste d'economistes — Liste d économistes Vous trouverez classés alphabétiquement des économistes célèbres, parce qu ils ont reçu le prix de la Banque de Suède en sciences économiques en mémoire d Alfred Nobel ou un prix internationalement reconnu, ou parce que qu ils …   Wikipédia en Français

  • Liste d'économistes — Vous trouverez classés alphabétiquement une liste d économistes reconnus internationalement, parce qu ils ont reçu le prix de la Banque de Suède en sciences économiques en mémoire d Alfred Nobel ou un prix internationalement reconnu, ou parce que …   Wikipédia en Français

  • Liste des économistes — Liste d économistes Vous trouverez classés alphabétiquement des économistes célèbres, parce qu ils ont reçu le prix de la Banque de Suède en sciences économiques en mémoire d Alfred Nobel ou un prix internationalement reconnu, ou parce que qu ils …   Wikipédia en Français

  • Liste des économistes célèbres — Liste d économistes Vous trouverez classés alphabétiquement des économistes célèbres, parce qu ils ont reçu le prix de la Banque de Suède en sciences économiques en mémoire d Alfred Nobel ou un prix internationalement reconnu, ou parce que qu ils …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”