Interpolation newtonienne

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En analyse numérique, l'interpolation newtonienne, du nom d'Isaac Newton, est une méthode d'interpolation polynomiale permettant d'obtenir le polynôme de Lagrange comme combinaison linéaire de polynômes de la base newtonienne.

Contrairement à l'interpolation d'Hermite par exemple, cette méthode ne diffère de l'interpolation lagrangienne que par la façon dont le polynôme est calculé, le polynôme d'interpolation qui en résulte est le même. Pour cette raison on parle aussi plutôt de la forme de Newton du polynôme de Lagrange.

Définition[modifier | modifier le code]

Étant donné un ensemble de k+1 points

(x_0, y_0),\ldots,(x_k, y_k) (les xj tous distincts 2 à 2), l'interpolation polynomiale dans une base de Newton est une combinaison linéaire de polynômes appartenant à cette base
N(x) = \sum_{j=0}^{k} a_{j} n_{j}(x)

avec les polynômes de Newton définis de la manière suivante

n_j(x) = \prod_{i=0}^{j-1} (x - x_i)

et les coefficients comme ceci

a_j = [y_0,\ldots,y_j]

[y_0,\ldots,y_j]

est la notation pour les différences divisées.

Par conséquent, le polynôme d'interpolation peut être écrit ainsi

N(x) = [y_0] + [y_0,y_1](x-x_0) + \ldots + [y_0,\ldots,y_k](x-x_0)\ldots(x-x_{k-1})

Idée principale[modifier | modifier le code]

Résoudre un problème d'interpolation conduit à un problème d'algèbre linéaire où nous devons inverser une matrice. En utilisant une méthode standard d'interpolation polynomiale, on obtient une matrice du type matrice de Vandermonde qui est très difficile à inverser. En choisissant une base newtonienne de polynômes, on obtient une matrice triangulaire inférieure qui s'inverse beaucoup plus facilement.

Pour k+1 points, on construit la base de Newton ainsi

n_j(x) = \prod_{i=0}^{j-1} (x - x_i) \qquad j=1,\ldots,k

En utilisant ces polynômes, nous devons inverser

 
\begin{bmatrix}
      1 &         &        &        & 0  \\
      1 & x_1-x_0 &        &        &    \\
      1 & x_2-x_0 & (x_2-x_0)(x_2-x_1) &        &    \\
 \vdots & \vdots  &        & \ddots &    \\
      1 & x_k-x_0 & \ldots & \ldots & \prod_{j=0}^{k-1}(x_k - x_j)
\end{bmatrix}
\begin{bmatrix}
     a_0 \\
     \vdots \\
     a_{k} 
\end{bmatrix}
=
\begin{bmatrix}
     y_0 \\
     \vdots \\
     y_{k}
\end{bmatrix}

pour résoudre le problème d'interpolation polynomiale.

Cette matrice peut être inversée successivement en résolvant

 \sum_{i=0}^{j} a_{i} n_{i}(x_j) = y_j \qquad j = 0,...,k

On commence par j=0 qui nous donne a_0 puis pour j=1, le calcul de a_0 nous permet de déduire a_1. Et ainsi de suite jusqu'à j=k.

Application[modifier | modifier le code]

Comme le montre la définition des différences divisées, des points supplémentaires peuvent être ajoutés pour créer un nouveau polynôme d'interpolation sans recalculer les coefficients. De plus, si un point est modifié, il est inutile de recalculer l'ensemble des coefficients. Autre avantage, si les xi sont équi-répartis, le calcul des différences divisées devient nettement plus rapide. Par conséquent, l'interpolation polynomiale dans une base de Newton est privilégiée par rapport à une interpolation lagrangienne pour des raisons pratiques.

Lien externe[modifier | modifier le code]

Interpolation polynômiale (sic) de type Newton et différences divisées sur math-linux.com