Interpolation lagrangienne

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

En analyse numérique, les polynômes de Lagrange, du nom de Joseph Louis Lagrange, permettent d'interpoler une série de points par un polynôme qui passe exactement par ces points appelés aussi nœuds. Cette technique a été découverte par Edward Waring en 1779 et redécouverte plus tard par Leonhard Euler en 1783.

Étant donné qu'il n'existe qu'une seule interpolation pour un ensemble donné de points, en toute rigueur, il faut appeler cette méthode : Interpolation polynomiale.

[modifier] Définition

Cette image montre, pour 4 points ((-9, 5), (-4, 2), (-1, -2), (7, 9)), l'interpolation polynomiale L(x) (de degré 3), qui est la somme des polynômes de base y0.l0(x), y1.l1(x), y2.l2(x) et y3.l3(x).Le polynôme d'interpolation passe par les 4 points de contrôle, et chaque polynôme de base passe par son point de contrôle respectif et vaut 0 pour les x correspondant aux autres points de contrôle.

Cette image montre, pour 4 points ((-9, 5), (-4, 2), (-1, -2), (7, 9)), l'interpolation polynomiale L(x) (de degré 3), qui est la somme des polynômes de base y_0.l_{0_(x)}_{, y_1.l₁(x), y_2.l₂(x) et y_3.l₃(x).Le polynôme d'interpolation passe par les 4 points de contrôle, et chaque polynôme de base passe par son point de contrôle respectif et vaut 0 pour les x correspondant aux autres points de contrôle.}

On se donne $n + 1$ points $(x_0, y_0),\ldots,(x_n, y_n)$ (avec les $x i$ distincts 2 à 2).

[modifier] Polynômes de Lagrange

Les polynômes de Lagrange associés aux points sont les polynômes définis par :

$l_j(X) := \prod_{i=0, j\neq i}^{n} \frac{X-x_i}{x_j-x_i} = \frac{X-x_0}{x_j-x_0} \cdots \frac{X-x_{j-1}}{x_j-x_{j-1}} ~ \frac{X-x_{j+1}}{x_j-x_{j+1}} \cdots \frac{X-x_{k}}{x_j-x_{k}}.$

On a en particulier deux propriétés :

$l j$ est de degré $n$ pour tout $j$
$l_i(x_j) = \delta_{i,j}, 0 \leq i,j \leq n$ c'est-à-dire $l i (x i) = 1$ et $l i (x j) = 0$ pour $i\ne j$

[modifier] Polynôme d'interpolation

Le polynôme défini par $L(X) = \sum_{j=0}^{n} y_j l_j(X)$ est l'unique polynôme de degré au plus $n$ vérifiant $L (x i) = y i$ pour tout $i$ .

En effet $L(x_i) = \sum_{j=0}^{n} y_j l_j(x_i)=y_i$ et $L$ est une combinaison linéaire de polynômes de degré au plus $n$ donc appartient à $K n [X]$ .

Si un autre polynôme, $Q$ , vérifie ces propriétés alors $L - Q$ appartient à $K n [X]$ et s'annule en $n + 1$ points (les $x k$ ) donc est nul ce qui prouve l'unicité.

[modifier] Autre écriture

Posons $N(X)=\prod^{n}_{j=0}(X-x_j)$ . On a $N (x i) = 0$ et, en utilisant la formule de Leibniz $N'(X)=\sum^{n}_{j=0}\prod^{n}_{i=0,i\ne j}(X-x_i)$ .

En particulier, comme tous les produits sont nuls en $x k$ sauf un : $N'(x_k)=\prod^{n}_{i=0,i\ne k}(x_k-x_i)$ .

Ainsi $l_i(X)={N(X) \over N'(x_i)(X-x_i)}$

On peut utiliser $N$ pour traduire l'unicité : si $Q$ vérifie $Q (x i) = y i$ pour tout $i$ alors $Q - L$ s'annule aux points $x i$ donc est un multiple de $N$ . Il est donc de la forme $Q (X) = L (X) + N (X). P (X)$ où $P$ est un polynôme quelconque.

[modifier] Base de polynômes

On se donne $n + 1$ scalaires distincts $x_0,\ldots,x_n$ . Pour tout polynôme $P$ appartenant à $K n [X]$ , si on pose $y i = P (x i)$ , $P$ est le polynôme d'interpolation correspondant aux points : il est égal au polynôme $L$ défini ci-dessus.

On a donc $P(X)=\sum_{j=0}^{n} P(x_j) l_j(X)$ donc $(l_0,l_1,\dots,l_n)$ forme une famille génératrice de $K n [X]$ . Comme son cardinal (égal à $n + 1$ ) est égal à la dimension de l'espace, elle en est une base.

Exemples : en choisissant $P = 1$ ou $P = X$ on a

$1=\sum_{j=0}^{n} l_j(X)$
$X=\sum_{j=0}^{n} x_jl_j(X)$

En fait c'est la base dont la base duale est la famille des formes linéaires définies par $u i (P) = P (x i)$ .

[modifier] Applications

Ils peuvent être utilisés pour calculer le déterminant d'une matrice de Vandermonde
Ils interviennent dans la démonstration du critère de diagonalisabilité par les polynômes annulateurs.

[modifier] Idée principale

Résoudre un problème d'interpolation conduit à inverser une matrice pleine de type matrice de Vandermonde. C'est un calcul lourd en nombre d'opérations. Les polynômes de Lagrange définissent une nouvelle base de polynômes qui permet de ne plus avoir une matrice pleine mais une matrice diagonale. Or, inverser une matrice diagonale est une opération instantanée.