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
[modifier | modifier le code]![](http://upload.wikimedia.org/wikipedia/commons/f/f0/Lagrangepolys.png)
On se donne n + 1 points (avec les xi distincts deux à deux). On se propose de construire un polynôme de degré minimal qui aux abscisses xi prend les valeurs yi, ce que la méthode suivante permet de réaliser.
L'étude suivante propose de montrer que le polynôme est le seul polynôme de degré au plus n à satisfaire cette propriété[1].
Polynômes de Lagrange
[modifier | modifier le code]Les polynômes de Lagrange associés à ces points sont les polynômes définis par :
On a en particulier deux propriétés :
- li est de degré n pour tout i ;
- c'est-à-dire et pour
Polynôme d'interpolation
[modifier | modifier le code]Le polynôme défini par est l'unique polynôme de degré au plus n vérifiant pour tout i.
En effet :
- d'une part ;
- 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 xk) : L – Q est donc nul, ce qui prouve l'unicité.
Exemple
[modifier | modifier le code]Pour les points , on calcule d'abord les polynômes de Lagrange :
- ;
- ;
- .
Puis on calcule la fonction polynomiale passant par ces points :
- ;
- .
Autre écriture
[modifier | modifier le code]Posons le polynôme . On voit immédiatement qu'il vérifie N(xi) = 0 et, en utilisant la formule de Leibniz, sa dérivée vaut :
- .
En particulier, en chaque nœud xk, tous les produits s'annulent sauf un, ce qui donne la simplification :
- .
Ainsi, les polynômes de Lagrange peuvent être définis à partir de N :
- .
On peut utiliser N pour traduire l'unicité : si Q vérifie pour tout i alors Q – L s'annule aux points xi donc est un multiple de N. Il est donc de la forme où P est un polynôme quelconque. On a ainsi l'ensemble des polynômes interpolateurs liés aux points (xi, yi), et L est celui de degré minimal.
Algorithme efficace
[modifier | modifier le code]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 par une approche diviser pour régner, puis sa dérivée qu'on évalue ensuite sur les par évaluation multipoint. Puisque , on en déduit queÉtant donnés toutes les valeurs des , on peut calculer le numérateur et le dénominateur de la fraction rationnelle, en utilisant à nouveau via une approche diviser pour régner[2]. En utilisant des algorithmes de multiplication rapide (en), 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
[modifier | modifier le code]On se donne n + 1 scalaires distincts . Pour tout polynôme P appartenant à , si on pose , P est le polynôme d'interpolation correspondant aux points : il est égal au polynôme L défini ci-dessus.
On a donc donc forme une famille génératrice de . 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 :
- ;
- .
En fait c'est la base dont la base duale est la famille des n + 1 formes linéaires de Dirac définies par
- .
Si l'on considère le produit scalaire :
- ,
la famille forme une base orthonormée de .
Applications
[modifier | modifier le code]- 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
- où .
Idée principale
[modifier | modifier le code]Résoudre un problème d'interpolation conduit à inverser une matrice pleine de type matrice de Vandermonde[3]. 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
[modifier | modifier le code]Pour tout multiensemble de scalaires et tout élément de , il existe un unique polynôme de degré tel que
- .
Ce polynôme s'écrit donc , où est l'unique polynôme de degré tel que et tous les autres sont nuls[4]. Cela généralise à la fois l'interpolation de Lagrange et celle d'Hermite.
Voir aussi
[modifier | modifier le code]Articles connexes
[modifier | modifier le code]Liens externes
[modifier | modifier le code]- (en) Eric W. Weisstein, « Lagrange Interpolating Polynomial », sur 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
Notes et références
[modifier | modifier le code]- Calcul Scientifique: Cours, exercices corrigés et illustrations en Matlab sur Google Livres.
- Alin Bostan, Frédéric Chyzak, Marc Giusti, Romain Lebreton, Grégoire Lecerf, Bruno Salvy et Éric Schost, Algorithmes efficaces en calcul formel, (ISBN 979-10-699-0947-2, lire en ligne)
- Mathématiques L3 - Mathématiques appliquées sur Google Livres.
- (en) F. R. Gantmacher, The Theory of Matrices, vol. 1, Chelsea Publishing Company, (lire en ligne), p. 101-102.