Interpolation lagrangienne

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

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₀(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 Modèle:Math points $(x_0,y_0),\dots ,(x_n,y_n)$ (avec les Modèle:Math distincts deux à deux). On se propose de construire un polynôme de degré minimal qui aux abscisses Modèle:Math prend les valeurs Modèle:Math, 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\ne 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

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

$l_i(X)=\prod _{j=0,j\ne 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. Modèle:Math est de degré Modèle:Math pour tout Modèle:Math ;
2. $l_i(x_j)={\delta }_{i,j},0\le i,j\le n$ c'est-à-dire $l_i(x_i)=1$ et $l_i(x_j)=0$ pour $j\ne i$

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 Modèle:Math vérifiant $L(x_i)=y_i$ pour tout Modèle:Math.

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é Modèle:Math, Modèle:Math est de degré au plus Modèle:Math ; si un autre polynôme Modèle:Math vérifie ces propriétés, alors Modèle:Math est de degré au plus Modèle:Math et il s'annule en Modèle:Math points distincts (les Modèle:Math) : Modèle:Math est donc nul, ce qui prouve l'unicité.

Exemple

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 polynômes 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)=3l_0(X)+2l_1(X)-l_2(X)$ ;
• $L(X)=P(X)=-\frac{3}{2}{X}^2+\frac{1}{2}X+4$.

Autre écriture

Posons le polynôme $N(X)=\prod _{j=0}^n(X-x_j)$. On voit immédiatement qu'il vérifie Modèle:Math et, en utilisant la formule de Leibniz, sa dérivée vaut :

$N^{\prime }(X)=\sum _{j=0}^n\prod _{i=0,i\ne j}^n(X-x_i)$.

En particulier, en chaque nœud Modèle:Math, tous les produits s'annulent sauf un, ce qui donne la simplification :

$N^{\prime }(x_k)=\prod _{i=0,i\ne k}^n(x_k-x_i)$.

Ainsi, les polynômes de Lagrange peuvent être définis à partir de N :

$l_i(X)=\frac{N(X)}{N^{\prime }(x_i)(X-x_i)}$.

On peut utiliser Modèle:Math pour traduire l'unicité : si Modèle:Math vérifie $Q(x_i)=y_i$ pour tout Modèle:Math alors Modèle:Math s'annule aux points Modèle:Math donc est un multiple de Modèle:Math. Il est donc de la forme $Q(X)=L(X)+N(X)\cdot P(X)$ où Modèle:Math est un polynôme quelconque. On a ainsi l'ensemble des polynômes interpolateurs liés aux points Modèle:Math, et Modèle:Math est celui de degré minimal.

Algorithme efficace

L'écriture alternative est à la base de l'algorithme rapide de calcul du polynôme d'interpolation de Lagrange. Avec les mêmes notations que précédemment, l'algorithme consiste à calculer $N(X)$ par une approche diviser pour régner, puis sa dérivée $N^{\prime }(X)$ qu'on évalue ensuite sur les $x_i$ par évaluation multipoint. Puisque $L(X)=\sum _{j=0}^n{y}_j{l}_j(X)$, on en déduit que$$\frac{L(X)}{N(X)}=\sum _{j=1}^m\frac{y_j}{N^{\prime }(x_j)(X-x_j)}.$$Étant donnés toutes les valeurs des $N^{\prime }(x_j)$, on peut calculer le numérateur et le dénominateur de la fraction rationnelle, en utilisant à nouveau via une approche diviser pour régner. En utilisant des algorithmes de Modèle:Lien, le polynôme d'interpolation de Lagrange peut être calculé avec un nombre d'opérations algébriques quasi linéaire.

Base de polynômes

On se donne Modèle:Math scalaires distincts $x_0,\dots ,x_n$. Pour tout polynôme Modèle:Math appartenant à $K_n[X]$, si on pose $y_i=P(x_i)$, Modèle:Math est le polynôme d'interpolation correspondant aux points : il est égal au polynôme Modèle:Math 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 à Modèle:Math) est égal à la dimension de l'espace, elle en est une base.

Exemples : en choisissant Modèle:Math ou Modèle:Math, on a :

1. $1=\sum _{j=0}^n{l}_j(X)$ ;
2. $X=\sum _{j=0}^n{x}_j{l}_j(X)$.

En fait c'est la base dont la base duale est la famille des Modèle:Math formes linéaires $u_i$ de Dirac définies par

$\mathrm{\forall }i\in \{0,\dots ,n\},u_i(P)=P(x_i)$.

Si l'on considère le produit scalaire :

$\mathrm{\forall }P,Q,\sum _{i=0}^{n}P(x_i)Q(x_i)$,

la famille $(l_0,\dots ,l_n)$ forme une base orthonormée de ${ℝ}_n[X]$.

Applications

• L'interpolation lagrangienne peut être utilisée pour calculer la matrice inverse d'une matrice de Vandermonde.
• Elle est utilisée en cryptographie, pour le partage de clés secrètes de Shamir.
• Elle peut servir au calcul numérique d'une intégrale (via les formules de Newton-Cotes), ou plus généralement à l'approximation de fonction.
• Elle peut servir à approximer la dérivée d'une fonction. La dérivée d'un polynôme de Lagrange est

  $L^{\prime }(x):=\sum _{j=0}^k{y}_j{{\ell }_j}^{\prime }(x)$ où ${{\ell }_j}^{\prime }(x)={\ell }_j(x)\cdot \sum _{m=0,m\ne j}^n\frac{1}{x-x_m}$.

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

Polynôme d'interpolation de Lagrange-Sylvester

Pour tout multiensemble $(X,m)$ de scalaires et tout élément $Y=(y_{x,k}{)}_{x\in X,0\le k<m(x)}$ de $\prod _{x\in X}{K}^{m(x)}$, il existe un unique polynôme $L$ de degré $<\sum _{x\in X}m(x)$ tel que

$\mathrm{\forall }x\in X\mathrm{\forall }k<m(x)L^{(k)}(x)=y_{x,k}$.

Ce polynôme s'écrit donc $L=\sum _{x\in X,0\le k<m(x)}{y}_{x,k}{\ell }_{x,k}$, où ${\ell }_{x,k}$ est l'unique polynôme de degré $<\sum _{z\in X}m(z)$ tel que ${\ell }_{x,k}^{(k)}(x)=1$ et tous les autres ${\ell }_{x,k}^{(j)}(z)$ sont nuls. Cela généralise à la fois l'interpolation de Lagrange et celle d'Hermite.

Voir aussi

Articles connexes

• Interpolation newtonienne
• Phénomène de Runge
• Constante de Lebesgue

Liens externes

• Modèle:Mathworld
• Interpolation polynômiale (sic) de type Lagrange sur math-linux.com
• Calcul du polynôme de Lagrange en donnant les coordonnées des points sur homeomath2.imingo.net