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

Un billet blog de Denis Hulo

[SIZE=3]
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 (l₀, l₁, …, l_n) 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


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 « + » : E² → 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


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 (x₀ ,y₀) , … , (x_n , y_n) (avec les x_i 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 :



III-A. Espace ℝ_n[X] des polynômes


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[X].

Quel que soit le polynôme P appartenant à ℝ_n[X], on peut également écrire :



Proposition :

Étant donné n + 1 réels distincts x₀, …, x_n, l'ensemble des polynômes que l'on peut construire avec la famille de polynômes (l₀, l₁, …, l_n) 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 (l₀, l₁, …, l_n) :



L'addition de ces deux polynômes donne :



On obtient donc un nouveau polynôme d'interpolation de Lagrange construit avec la même famille de polynômes (l₀, l₁, …, l_n) et appartenant au même espace ℝ_n[X].

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 :



On obtient donc un nouveau polynôme d'interpolation de Lagrange construit avec la même famille de polynômes (l₀, l₁, …, l_n) 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 x₀, …, x_n. Pour tout polynôme P appartenant à un espace ℝ_n[X] des polynômes, si on pose y_i = P(x_i), 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 :



Et donc (l₀, l₁, …, l_n) forme une famille génératrice de ℝ_n[X] et son cardinal (égal à n + 1) est égal à la dimension de l'espace.

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



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



Cela implique nécessairement que :



On en déduit que cette famille génératrice (l₀, l₁, …, l_n) 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[X].

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.


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 :


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 :


Le code affiche :

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

p ∈ ℝ2[X], 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 :


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 :


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[X], Base = (L0, L1, L2), x = [0, 1, 2]
p2 ∈ ℝ2[X], Base = (L0, L1, L2), x = [0, 1, 2]

p = p1 + p2

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

p ∈ ℝ2[X], 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 « * » :


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 :


Le code affiche :

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

p1 ∈ ℝ2[X], 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[X], 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 :


Testons maintenant cette méthode :


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 :

[Code=Python]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[X]
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[j]) + "∙L" + str(j) + "(X)" + " + "

return Lx[:-3]

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

n = len(self.x)-1

# retourne l'espace vectoriel du polynôme d'interpolation de Lagrange
return "ℝ{0}[X]".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[/:-2]...