Calcul formel en Python : les polynômes d'interpolation de Lagrange vus comme des vecteurs,

Un billet blog de Denis Hulo

I. Introduction

D'après Wikipedia, en algèbre linéaire, un espace vectoriel est un ensemble d'objets, appelés vecteurs, que l'on peut additionner entre eux, et que l'on peut multiplier par un scalaire (pour les étirer ou les rétrécir, les tourner, etc.).

On va d'abord montrer que l'ensemble des polynômes pouvant être construits sur la base des polynômes de Lagrange (l0, l1, …, ln) constitue un espace vectoriel.

Dans un second temps, on va représenter les polynômes d'interpolation de Lagrange à l'aide d'une classe en Python, puis définir les opérations d'addition entre ces vecteurs et de multiplication par un scalaire en utilisant la surcharge d'opérateur.

Enfin, on va tester le code Python en effectuant différentes opérations sur ces nouveaux objets comme on le ferait sur des vecteurs.


II. Espace vectoriel

652083

II-A. Définition

Soit K un corps commutatif, comme le corps commutatif ℚ des rationnels, celui, ℝ, des réels ou celui, ℂ, des complexes (on parlera dans ces cas d'espace vectoriel rationnel, réel ou complexe).

D'après Wikipedia, un espace vectoriel sur K, est un ensemble E, dont les éléments sont appelés vecteurs, muni de deux lois :

• une loi de composition interne « + » : E2 → E, appelée addition ou somme vectorielle ;
  
• une loi de composition externe à gauche « • » : K × E → E, appelée multiplication par un scalaire.
  

Une loi de composition interne est donc une application qui, à deux éléments d'un ensemble E, associe un élément de E, comme la multiplication ou l'addition dans l'ensemble des naturels.

Contrairement à une loi de composition interne, une loi de composition externe fait intervenir des éléments de l’extérieur, ici un scalaire dans K.

On admettra sans les démontrer les propriétés suivantes :

• La loi « + » est commutative, associative, admet un élément neutre et tout élément de cette espace possède un opposé.
  
• La loi « • » est distributive par rapport à la loi « + », vérifie une associativité mixte et admet un élément neutre à gauche.
  

II-B. Base d'un espace vectoriel

652051

En algèbre linéaire, une base d'un espace vectoriel V est une famille de vecteurs de V linéairement indépendants et dont tout vecteur de V est combinaison linéaire.

Autrement dit, une base de V est une famille libre de vecteurs de V qui engendre V.



III. Polynômes d'interpolation de Lagrange

Soit n + 1 points (x0 ,y0) , … , (xn , yn) (avec les xi des réels distincts deux à deux).

Le polynôme d'interpolation de Lagrange de degré au plus n qui passe par ces points est défini par :

652058


III-A. Espace ℝn des polynômes

652239

L étant une combinaison linéaire de polynômes de degré n, il est de degré au plus n et appartient donc à l'ensemble ℝn.

Quel que soit le polynôme P appartenant à ℝn, on peut également écrire :

652046

Proposition :

Étant donné n + 1 réels distincts x0, …, xn, l'ensemble des polynômes que l'on peut construire avec la famille de polynômes (l0, l1, …, ln) constitue un espace vectoriel muni de deux lois :

• une loi de composition interne « + », appelée addition ou somme vectorielle ;
  
• une loi de composition externe à gauche « • », appelée multiplication par un scalaire.
  

Décrivons maintenant pour le vérifier les opérations pouvant être réalisées sur ces vecteurs.


III-A-1. Addition de polynômes

Soit deux polynômes d'interpolation de Lagrange P et Q construits avec la même famille de polynômes (l0, l1, …, ln) :

652043

L'addition de ces deux polynômes donne :

652044

On obtient donc un nouveau polynôme d'interpolation de Lagrange construit avec la même famille de polynômes (l0, l1, …, ln) et appartenant au même espace ℝn.

Cette addition est donc bien une loi de composition interne dans cet espace vectoriel.


III-A-2. Multiplication d'un polynôme par un scalaire

La multiplication de P(X) par un scalaire s donne :

652045

On obtient donc un nouveau polynôme d'interpolation de Lagrange construit avec la même famille de polynômes (l0, l1, …, ln) et appartenant au même espace.

Cette opération est donc bien une loi de composition externe dans cet espace vectoriel.

Ces deux opérations vérifient également les propriétés citées plus haut.


III-B. Base de polynômes

On se donne à nouveau n + 1 réels distincts x0, …, xn. Pour tout polynôme P appartenant à un espace ℝn des polynômes, si on pose yi = P(xi), P étant le polynôme d'interpolation correspondant aux points, il est égal au polynôme L défini précédemment.

On a donc :

652046

Et donc (l0, l1, …, ln) forme une famille génératrice de ℝn et son cardinal (égal à n + 1) est égal à la dimension de l'espace.

Par exemple, en choisissant P = 1 ou P = X, on obtient :

652047

On peut remarquer également que le polynôme nul P = 0 est tel que :

652196

Cela implique nécessairement que :

652197

On en déduit que cette famille génératrice (l0, l1, …, ln) est également libre, et par conséquent c'est une base de l'espace des polynômes qu'elle engendre.

Cette famille forme en fait une base orthonormée de ℝn.

Si vous souhaitez avoir plus d'information sur le sujet je vous invite à consulter la page Wikipedia Interpolation lagrangienne.



IV. Implémentation en Python

Ces polynômes peuvent donc être vus comme des vecteurs sur lesquels on peut réaliser les opérations d'addition et de multiplication par un scalaire.

On va maintenant représenter les polynômes d'interpolation de Lagrange en Python à l'aide d'une classe, puis définir ces opérations en utilisant la surcharge d'opérateur.


IV-A. Création de la classe Polynome_lagrange

Pour définir ces polynômes en Python et pouvoir réaliser des opérations entre eux, il nous faut donc créer une classe Polynome_lagrange.

652052

Sa méthode constructeur __init__() va nous permettre de définir les listes de valeurs x et y du polynôme d'interpolation de Lagrange au moment de créer l'objet :

import numpy as np

class Polynome_lagrange:

def __init__(self, x, y):
# méthode constructeur de la classe

# on définit la liste de valeurs en x permettant d'obtenir la famille de polynômes (l0, l1, ..., ln) représentant une base dans ℝn
self.x = x

# on définit le tableau de valeurs en y représentant les coordonnées du vecteur (tableau numpy)
self.y = np.array(y)


def __str__(self):
...

En python, les tableaux de la librairie numpy représentent également des vecteurs sur lesquels on peut réaliser les mêmes opérations (addition, multiplication par un scalaire, etc.) :

La méthode __str__ permet d'afficher un polynôme sous la forme y0∙L0(X) + y1∙L1(X) + y2∙L2(X).

La classe comporte également deux autres méthodes espace() et base() permettant de connaître l'espace vectoriel du polynôme et sa base.

Pour tester ces méthodes, nous ajoutons ces quelques lignes au module :

# création de l'objet Polynome_lagrange : 1∙L0(X) + 2∙L1(X) + 5∙L2(X)
p = Polynome_lagrange(x=[0, 1, 2], y=[1, 2, 5])

print(p) # affiche l'expression du polynôme

print()

# affiche l'appartenance de p à son espace vectoriel
print("p ∈ " + p.espace() + ", Base = " + p.base())


Le code affiche :

1∙L0(X) + 2∙L1(X) + 5∙L2(X)

p ∈ ℝ2, Base = (L0, L1, L2), x = [0, 1, 2]


IV-A-1. Addition de deux polynômes

Pour surcharger l'opérateur « + » et pouvoir ainsi réaliser l'addition de 2 polynômes de même base, nous devons ajouter une méthode __add __ () à la classe :

class Polynome_lagrange:
...
def __add__(self, other):
# méthode permettant de redéfinir l'opérateur « + » pour 2 polynômes d'interpolation de Lagrange ou 2 vecteurs
# (y0*L0(X) + ... + yn*Ln(X)) + (z0*L0(X) + ... + zn*Ln(X)) = (y0 + z0)*L0(X) + ... + (yn + zn)*Ln(X)

# si les 2 vecteurs self et other ont la même base
if self.x==other.x:

# addition des 2 vecteurs self.y et other.y (2 tableaux numpy)
y = self.y + other.y

# renvoie le polynômes résultat de l'addition des 2 polynômes self et other
return Polynome_lagrange(self.x, y)

else: # sinon

print("Les 2 polynômes n'ont pas la même base !")


Cette méthode permet donc de redéfinir l'opération « + » pour les polynômes de même base en les additionnant comme des vecteurs d'un même espace.

Pour tester l'opérateur d'addition portant sur 2 objets de la classe Polynome_lagrange, nous ajoutons ces lignes de code :

# création du 1er objet de la classe Polynome_lagrange
p1 = Polynome_lagrange(x=[0, 1, 2], y=[0, 1, 4])

# création du 2e objet de la classe Polynome_lagrange
p2 = Polynome_lagrange(x=[0, 1, 2], y=[1, 2, 5])

# affiche l'expression des polynômes p1 et p2
print("p1 = " + str(p1))
print("p2 = " + str(p2))

print()

# affiche l'appartenance de p1 et p2 à son espace vectoriel : R2, Base = [L0, L1, L2], x = [0, 1, 2]
print("p1 ∈ " + p1.espace() + ", Base = " + p1.base())
print("p2 ∈ " + p1.espace() + ", Base = " + p2.base())

print()

print("p = p1 + p2")

# addition des 2 polynômes
p = p1 + p2

print()

# affiche le résultat de l'addition
print("p = " + str(p))
print()

# affiche l'appartenance de p à son espace vectoriel
print("p ∈ " + p.espace() + ", Base = " + p.base())


Le code affiche :

p1 = 0∙L0(X) + 1∙L1(X) + 4∙L2(X)
p2 = 1∙L0(X) + 2∙L1(X) + 5∙L2(X)

p1 ∈ ℝ2, Base = (L0, L1, L2), x = [0, 1, 2]
p2 ∈ ℝ2, Base = (L0, L1, L2), x = [0, 1, 2]

p = p1 + p2

p = 1∙L0(X) + 3∙L1(X) + 9∙L2(X)

p ∈ ℝ2, Base = (L0, L1, L2), x = [0, 1, 2]


IV-A-2. Multiplication d'un polynôme par un scalaire

Pour réaliser la multiplication d'un objet Polynome_lagrange par un scalaire, on va ajouter une méthode __mul __ () qui va permettre de surcharger l'opérateur « * » :

class Polynome_lagrange:
...
def __mul__(self, s):
# méthode permettant de multiplier le polynôme self par un scalaire
# : s*(y0*L0(X) + ... + yn*Ln(X)) = s*y0*L0(X) + ... + s*yn*Ln(X)

# multiplication du vecteur self.y par le scalaire s
y = s*self.y

# renvoie le polynôme d'interpolation de Lagrange résultat de la multiplication de self par le scalaire s
return Polynome_lagrange(self.x, y)


Le scalaire s est passé comme deuxième argument à la fonction car le premier argument doit obligatoirement être un objet de la classe.

Pour tester l'opérateur de multiplication d'un objet de la classe Polynome_lagrange par un scalaire s, nous ajoutons maintenant ces lignes :

# création de l'objet de la classe Polynome_lagrange :
p1 = Polynome_lagrange(x=[0, 1, 2], y=[1, 2, 5])

# affiche l'expression du polynôme p1
print("p1 = " + str(p1))

print()

# affiche l'appartenance de p1 à son espace vectoriel
print("p1 ∈ " + p1.espace() + ", Base = " + p1.base())

print()

# définition du scalaire s
s = 2

print("s = " + str(s))

print()

print("p = p1*s ")

# multiplication du polynôme p1 par le scalaire s
p = p1*s

print()

# affiche le résultat de la multiplication de p1 par s
print("p = " + str(p))
print()

# affiche l'appartenance de p à son espace vectoriel
print("p ∈ " + p.espace() + ", Base = " + p.base())


Le code affiche :

p1 = 1∙L0(X) + 2∙L1(X) + 5∙L2(X)

p1 ∈ ℝ2, Base = (L0, L1, L2), x = [0, 1, 2]

s = 2

p = p1*s

p = 2∙L0(X) + 4∙L1(X) + 10∙L2(X)

p ∈ ℝ2, Base = (L0, L1, L2), x = [0, 1, 2]


On peut également imaginer d'effectuer la somme, la moyenne ou toute combinaison linéaire de vecteurs de la même base pour obtenir un nouveau vecteur de cette même base.


IV-A-3. Évaluation du polynôme

On souhaite pour terminer évaluer nos polynômes en faisant simplement p(2).

Pour cela, on va donc rendre nos objets callable en ajoutant une méthode __call__() à notre classe :

class Polynome_lagrange:
...
def __call__(self, X):
# permet d'évaluer le polynôme d'interpolation de Lagrange en fonction de X et des valeurs de x et y

# initialisation de la variable Lx
Lx = 0

# parcours des y
for j in range(len(self.y)):
lj = 1
# parcours des x
for i in range(len(self.x)):
if i!=j:
lj *= (X - self.x)/(self.x - self.x)
# ajour de la valeur de lj*y à Lx
Lx +=self.y*lj

# renvoie la valeur de Lx
return Lx


Testons maintenant cette méthode :

# création de l'objet de la classe Polynome_lagrange :
p = Polynome_lagrange(x=[0, 1, 2],y=[1, 2, 5])

# valeur de x
x = 2

# évaluation de p(x)
print("p({0}) = ".format(x) + str(p(x)))


Le code affiche :

p(2) = 5.0


IV-B. Module complet

On donne pour finir le code complet du module contenant la classe Polynome_lagrange :

import numpy as np

class Polynome_lagrange():

def __init__(self, x, y):
# méthode constructeur de la classe

# on définit la liste de valeurs en x permettant d'obtenir la famille de polynômes (l0, l1, ..., ln) représentant une base dans ℝn
self.x = x

# on définit le tableau de valeurs en y représentant les coordonnées du vecteur (tableau numpy)
self.y = np.array(y)


def __str__(self):
# permet d'afficher le polynôme sous la forme y0*L0(X) + ... + yn*Ln(X)

Lx = ''
# parcours des y
for j in range(len(self.y)):
Lx += str(self.y) + "∙L" + str(j) + "(X)" + " + "

return Lx[:-3]

def espace(self):
# retourne l'espace vectoriel du polynôme self : R2

n = len(self.x)-1

# retourne l'espace vectoriel du polynôme d'interpolation de Lagrange
return "ℝ{0}".format(n)


def base(self):
# retourne la base de polynômes de self : (L0, L1, L2), x = [0, 1, 2]

n = len(self.x)-1
base = ""

# parcours des indices des polynômes de lagrange Li
for i in range(n+1):
base += "L" + str(i) + ", "

# création de la famille : (L0, L1, L2)
base = "(" + base[:-2] + ")"

# retourne la base du polynôme d'interpolation de Lagrange
return "{0}, x = {1}".format(base, self.x)



def __add__(self, other):
# méthode permettant de redéfinir l'opérateur « + » pour 2 polynômes d'interpolation de Lagrange ou 2 vecteurs
# (y0*L0(X) + ... + yn*Ln(X)) + (z0*L0(X) + ... + zn*Ln(X)) = (y0 + z0)*L0(X) + ... + (yn + zn)*Ln(X)

# si les 2 vecteurs self et other ont la même base
if self.x==other.x:

# addition des 2 vecteurs self.y et other.y (2 tableaux numpy)
y = self.y + other.y

# renvoie le polynômes résultat de l'addition des 2 polynômes self et other
return Polynome_lagrange(self.x, y)

else: # sinon

print("Les 2 polynômes n'ont pas la même base !")


def __mul__(self, s):
# méthode permettant de multiplier le polynôme self par un scalaire
# : s*(y0*L0(X) + ... + yn*Ln(X)) = s*y0*L0(X) + ... + s*yn*Ln(X)

# multiplication du vecteur self.y par le scalaire s
y = s*self.y

# renvoie le polynôme d'interpolation de Lagrange résultat de la multiplication de self par le scalaire s
return Polynome_lagrange(self.x, y)


def __eq__(self, other):
# méthode permettant de redéfinir l'opérateur « == » pour 2 polynômes d'interpolation de Lagrange

# renvoie True si les bases et les listes de coordonnées des vecteurs sont identiques
return (self.x==other.x) and np.array_equal(self.y,other.y)


def __call__(self, X):
# permet d'évaluer le polynôme d'interpolation de Lagrange en fonction de X et des valeurs de x et y

# initialisation de la variable Lx
Lx = 0

# parcours des y
for j in range(len(self.y)):
lj = 1
# parcours des x
for i in range(len(self.x)):
if i!=j:
lj *= (X - self.x)/(self.x - self.x)
# ajour de la valeur de lj*y à Lx
Lx +=self.y*lj

# renvoie la valeur de Lx
return Lx


# addition de 2 polynômes

print("I-A. Addition de 2 polynômes d'interpolation de Lagrange\n")

# création du 1er objet de la classe Polynome_lagrange
p1 = Polynome_lagrange(x=[0, 1, 2], y=[0, 1, 4])

# création du 2e objet de la classe Polynome_lagrange
p2 = Polynome_lagrange(x=[0, 1, 2], y=[1, 2, 5])

# affiche l'expression des polynômes p1 et p2
print("p1 = " + str(p1))
print("p2 = " + str(p2))

print()

# affiche l'appartenance de p1 et p2 à leur espace vectoriel : R2, Base = [L0, L1, L2], x = [0, 1, 2]
print("p1 ∈ " + p1.espace() + ", Base = " + p1.base())
print("p2 ∈ " + p1.espace() + ", Base = " + p2.base())

print()

print("p = p1 + p2")

# addition des 2 polynômes
p = p1 + p2

print()

# affiche le résultat de l'addition
print("p = " + str(p))
print()

# affiche l'appartenance de p à son espace vectoriel
print("p ∈ " + p.espace() + ", Base = " + p.base())

print();print()

# multiplication d'un polynôme par un scalaire

print("I-B. Multiplication d'un polynôme d'interpolation de Lagrange par un scalaire\n")

# création de l'objet de la classe Polynome_lagrange :
p1 = Polynome_lagrange(x=[0, 1, 2], y=[1, 2, 5])

# affiche l'expression du polynôme p1
print("p1 = " + str(p1))

print()

# affiche l'appartenance de p1 à son espace vectoriel
print("p1 ∈ " + p1.espace() + ", Base = " + p1.base())

print()

# définition du scalaire s
s = 2

print("s = " + str(s))

print()

print("p = p1*s ")

# multiplication du polynôme p1 par le scalaire s
p = p1*s

print()

# affiche le résultat de la multiplication de p1 par s
print("p = " + str(p))
print()

# affiche l'appartenance de p à son espace vectoriel
print("p ∈ " + p.espace() + ", Base = " + p.base())

print();print()

print("I-C. Évaluation d'un polynôme d'interpolation de Lagrange\n")

# création de l'objet de la classe Polynome_lagrange :
p = Polynome_lagrange(x=[0, 1, 2],y=[1, 2, 5])

# affiche l'expression du polynômes p
print("p = " + str(p))

print()

# affiche l'appartenance de p à son espace vectoriel
print("p ∈ " + p.espace() + ", Base = " + p.base())

# définition de la valeur de x
x = 2

print()

# évaluation de p(x)
print("p({0}) = ".format(x) + str(p(x)))


Note : la librairie scipy propose également une classe lagrange permettant de définir ce type de polynôme.



V. Conclusion

Comme on a pu le montrer, l'ensemble des polynômes construits sur la base des polynômes de Lagrange (l0, l1, …, ln) constitue donc un espace vectoriel muni de lois de composition interne et externe, à savoir l'addition et la multiplication par un scalaire.

Les éléments de cet espace peuvent facilement être représentés en Python afin de pouvoir ensuite réaliser des opérations entre ces objets mathématiques comme on le ferait sur des vecteurs.

On peut bien sûr imaginer de construire l'ensemble ℝn des polynômes sur la base usuelle des monômes Xn.


Sources :

https://fr.wikipedia.org/wiki/Espace_vectoriel
https://fr.wikipedia.org/wiki/Corps_commutatif
https://fr.wikipedia.org/wiki/Loi_de_composition
https://fr.wikipedia.org/wiki/Base_(alg%C3%A8bre_lin%C3%A9aire)
https://fr.wikipedia.org/wiki/Combinaison_lin%C3%A9aire
https://fr.wikipedia.org/wiki/Interpolation_lagrangienne
https://pyspc.readthedocs.io/fr/latest/05-bases/08-tableaux_numpy.html