Interpolation newtonienne

Un article de Wikipédia, l'encyclopédie libre.

En analyse numérique, l'interpolation newtonienne, du nom d'Isaac Newton, est une méthode d'interpolation polynomiale d'un ensemble de points par l'intermédiaire de polynômes appartenant à une base newtonienne.

Il n'existe qu'un seul polynôme d'interpolation pour un ensemble donné de points, par conséquent, il est abusif de parler d'Interpolation newtonienne, il faudrait plutôt dire : Interpolation polynomiale dans une base de Newton.

[modifier] Définition

Étant donné un ensemble de k+1 points

$(x_0, y_0),\ldots,(x_k, y_k)$ (les x_j 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]$

où

$[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})$

[modifier] Idée principale

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=0,\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$ .

[modifier] Application

Comme vous pouvez le voir dans 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 x_i 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 priviligiée par rapport à une interpolation lagrangienne pour des raisons pratiques.