Interpolation lagrangienne

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

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 d'interpolation polynomiale a été découverte par Edward Waring en 1779 et redécouverte plus tard par Leonhard Euler en 1783. C'est un cas particulier du théorème des restes chinois.

Définition[modifier | modifier le code]

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.

On se donne n+1 points (x_0, y_0),\dots,(x_n, y_n) (avec les x_i distincts deux à deux). On se propose de construire un polynôme de degré minimal qui aux abscisses x_i prend les valeurs y_i, ce que la méthode suivante permet de réaliser.

L'étude suivante propose de montrer que le polynôme L(X) = \sum_{j=0}^{n} y_j \left( \prod_{i=0, i\neq j}^{n} \frac{X-x_i}{x_j-x_i} \right) est le seul polynôme de degré au plus n à satisfaire cette propriété.

Polynômes de Lagrange[modifier | modifier le code]

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

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

On a en particulier deux propriétés :

  1. l_i est de degré n pour tout i
  2. 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 j\ne i

Polynôme d'interpolation[modifier | modifier le code]

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 :

  • d'une part L(x_i) = \sum_{j=0}^{n} y_j l_j(x_i) = y_i ;
  • d'autre part, étant combinaison linéaire de polynômes de degré n, L est de degré au plus n ; si un autre polynôme Q vérifie ces propriétés, alors L-Q est de degré au plus n et il s'annule en n+1 points distincts (les x_k) : L-Q est donc nul, ce qui prouve l'unicité.

Exemple[modifier | modifier le code]

Pour les points (x_{0}=1,y_{0}=3),(x_{1}= -1,y_{1}=2),(x_{2}=2,y_{2}= -1) On calcule d'abord les multiplicateurs de Lagrange :

  • l_{0}(X)=\frac{(X+1)(X-2)}{(1+1)(1-2)}= - \frac{1}{2} (X^{2}-X-2)
  • l_{1}(X)= \frac{(X-1)(X-2)}{(-1-1)(-1-2)}= \frac{1}{6} (X^{2}-3X+2)
  • l_{2}(X)= \frac{(X-1)(X+1)}{(2-1)(2+1)}= \frac{1}{3} (X^{2}-1)

Puis on calcule la fonction polynomiale passant par ces points

  • L(X) = P(X) = 3 l_{0} (X) + 2 l_{1} (X) - l_{2} (X)
  • L(X) = P(X) = - \frac{3}{2} X^{2} + \frac{1}{2} X + 4

Autre écriture[modifier | modifier le code]

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)P est un polynôme quelconque.

Base de polynômes[modifier | modifier le code]

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. 1=\sum_{j=0}^{n} l_j(X)
  2. X=\sum_{j=0}^{n} x_jl_j(X)

En fait c'est la base dont la base duale est la famille des n+1 formes linéaires u_i de Dirac définies par u_i(P)=P(x_i).

Applications[modifier | modifier le code]

Idée principale[modifier | modifier le code]

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.

Voir aussi[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Liens externes[modifier | modifier le code]