Mathématiques et Python : initiation au calcul formel avec Python,

Un billet blog de Denis Hulo

I. Introduction

Le calcul formel, ou parfois calcul symbolique, est le domaine des mathématiques et de l’informatique qui s’intéresse aux algorithmes opérant sur des objets de nature mathématique par le biais de représentations finies et exactes. Ainsi, un nombre entier est représenté de manière finie et exacte par la suite des chiffres de son écriture en base 2.

Étant donné les représentations de deux nombres entiers, le calcul formel se pose par exemple la question de calculer celle de leur produit.

On souhaite dans notre cas utiliser le calcul symbolique pour développer et réduire des expressions mathématiques, et obtenir ainsi des polynômes à une ou plusieurs variables. Ce processus va nous permettre ensuite de vérifier si deux expressions sont égales.

Pour cela, on va créer une classe Polynome dans laquelle on redéfinira les opérateurs d'addition, de multiplication et de puissance pour ces nouveaux objets.


II. Principe du calcul formel

Comment vérifier par exemple que l'identité (a + b)2 = a2 + b2 + 2(a∗b) est correcte ?

Une vérification naïve pourrait consister à examiner toutes les valeurs possibles de a, à les croiser avec toutes les valeurs possibles de b et, pour chaque couple, à calculer (a + b)2, puis a2 + b2 + 2(a∗b) et à s'assurer que l'on obtient le même résultat. Si les domaines de a et de b sont grands, cette vérification peut être très longue, et si les domaines sont infinis (par exemple les réels), elle ne peut pas être exhaustive.

En vérification formelle, on utilise des variables symboliques et on applique les règles qui régissent le « + » et le « ∗ ». Ici, les règles pourraient être :

∀x, x2 = x∗x (R1)
∀x,y,z, x∗(y + z) = x∗y + x∗z (R2)
∀x,y, x∗y = y∗x (R3)
∀x, x + x = 2x (R4)
∀x,y, x + y = y + x (R5)

En se servant de ces règles, on peut ainsi développer et réduire progressivement l'expression (a + b)2 pour aboutir finalement à l'égalité recherchée :

(a + b)2 = (a + b)∗(a + b) (R1)
‎(a + b)2 = (a + b)∗a + (a + b)∗b (R2)
(a + b)2 = a∗(a + b) + b∗(a + b) (R3)
(a + b)2 = a∗a + a∗b + b∗a + b∗b (R2)
(a + b)2 = a2 + a∗b + b∗a + b2 (R1)
(a + b)2 = a2 + a∗b + a∗b + b2 (R3)
(a + b)2 = a2 + 2(a∗b) + b2 (R4)
(a + b)2 = a2 + b2 + 2(a∗b) (R5)

On obtient ainsi un polynôme à 2 variables a et b.

Dans notre cas, on va donc déterminer à l'aide des règles précédentes l'expression polynomiale de chacun des membres de l'identité à vérifier :

(a + b)2 = a2 + 2(a∗b) + b2

Et :

a2 + b2 + 2(a∗b) = a2 + 2(a∗b) + b2


Puis, on va comparer les polynômes obtenus pour vérifier si l'identité de départ est vraie, un peu comme si on évaluait deux expressions numériques pour savoir si elles sont égales.

On remarquera également pour finir que ces expressions mathématiques peuvent être vues comme des combinaisons d'opérations entre polynômes.



III. Implémentation en Python

Pour représenter ces polynômes en Python et pouvoir réaliser des opérations entre eux, il nous faut créer une classe Polynome :

643099

Notre classe comportera en plus un constructeur, c'est à dire une méthode particulière __init__() dont le code est exécuté quand la classe est instanciée.

Elle va nous permettre de définir la liste de termes du polynôme au moment de la création de l'objet :

class Polynome:

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

# on s'assure que l'argument termes est une liste
if not isinstance(termes, list): termes =

# parcours des indices et des termes de la liste
for indice, terme in enumerate(termes):

# si le terme est de type string : 'a'
if isinstance(terme, str):
# on met à jout l'élément de la liste avec un tuple de la forme (1,('a',)) : (coef, var)
termes = (1,(terme,))
elif len(terme)==1: # ou si le terme est un tuple à un seul élément : ('a',) : (coef, var)
termes = (1,terme)

# regroupement des termes identiques en utilisant les règles R4 et R5
termes = regrouper_termes(termes)

# on définit la liste de termes correspondant au polynôme. Ex. : [(1,('a','a')), (2,('a','b')), (1,('b','b'))] -> a^2 + 2ab + b^2
self.liste_termes = termes


def __str__(self): # permet d'afficher l'expression sous sa forme développée et réduite

# initialise la chaîne à renvoyer
chaine_expression = ''

...


La méthode __str__ permet d'afficher une expression sous la forme a^2 + 2*a*b + b^2. Le code de la fonction est disponible dans le module complet proposé à la fin du billet.

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

p = Polynome(['a','b']) # création de l'objet Polynome représentant l'expression (a+b)
print(p) # affiche l'expression

Le code affiche :

a+b


III-A. Surcharge de l'opérateur d'addition

Pour surcharger l'opérateur « + » et pouvoir ainsi réaliser l'addition entre 2 objets Polynome, nous devons ajouter une méthode __add __ () à la classe :

class Polynome:

...

def __add__(self, other): # méthode permettant de redéfinir l'opérateur « + » pour 2 objets Polynome : self + other
# concaténation des 2 listes de termes
# [(1,('a', 'a')), (1,('b',))] + [(1,('a', 'a')), (1,('b',))] = [(1,('a', 'a')), (1,('b',)), (1,('a', 'a')), (1,('b',))]

# tri et regroupement des termes identiques en utilisant les règles R4 et R5 :
# R5 : a*a + b + a*a + b -> a*a + a*a + b + b (tri)
# R4 : a*a + a*a + b + b -> 2*a*a + 2*b (regroupement)
# [(1,('a', 'a')), (1,('b',)), (1,('a', 'a')), (1,('b',))] -> [(2,('a','a')), (2,('b',))]

# concaténation des 2 listes de termes de self et other
liste_termes = self.liste_termes + other.liste_termes

# renvoie l'objet Polynome résultat de l'addition de self et other avec regroupement des termes identiques
return Polynome(liste_termes)


Cette méthode permet donc de redéfinir l'opération « + » pour des polynômes en utilisant les relations R4 et R5 :

(a + b) + (a + b) = (a + b + a + b)
(a + b) + (a + b) = (a + a + b + b) (R5)
(a + b) + (a + b) = 2a + 2b (R4)

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

a = Polynome('a') # création du 1er objet de la classe Polynome représentant la variable a
b = Polynome('b') # création du 2e objet de la classe Polynome représentant la variable b

print((a+b)+(a+b)) # affiche l'expression (a+b)+(a+b) sous sa forme réduite

Le code affiche :

2*a + 2*b


III-B. Surcharge de l'opérateur de multiplication

Pour surcharger l'opérateur « * » et l'appliquer à 2 objets Polynome, nous devons également ajouter une méthode __mul __ () à la classe :

class Polynome:

...

def __mul__(self, other): # méthode permettant de redéfinir l'opérateur « * » pour 2 objets Polynome : self * other
# règles R2, R3, R4 et R5
# R2 : (a+b)*(a+b) = (a+b)*a + (a+b)*b
# R3 : = a*(a+b) + b*(a+b)
# R2 : = a*a + a*b + b*a + b*b
# R3 = a*a + a*b + a*b + b*b
# R4 : = a*a + 2*a*b + b*b

# initialisation de la liste de termes
liste_termes = []

# si le 2e membre est un numérique
if isinstance(other, (int,float)):
# on multiplie les coefficients des termes de self.liste_termes par other
liste_termes = [(other*terme,terme) for terme in self.liste_termes]

return Polynome(liste_termes)

# parcours des termes de la liste de other
for terme_droite in other.liste_termes:

# parcours des termes de la liste de self
for terme_gauche in self.liste_termes:

coef = terme_droite*terme_gauche
var = terme_droite + terme_gauche

# tri des variables
var = tuple(sorted(var))

# ajout du tuple (coef,var) à la liste
liste_termes.append((coef,var))

# renvoie l'objet Polynome résultat de la multiplication de self et other avec regroupement des termes identiques
return Polynome(liste_termes)


Cette méthode permet donc de redéfinir l'opération de multiplication pour 2 polynômes en utilisant les règles R2, R3, R4 et R5 :

(a+b)∗(a+b) = (a+b)∗a + (a+b)∗b (R2)
(a+b)∗(a+b) = a∗(a+b) + b∗(a+b) (R3)
(a+b)∗(a+b) = a∗a + a∗b + b∗a + b∗b (R2)
(a+b)∗(a+b) = a∗a + a∗b + a∗b + b∗b (R3)
(a+b)∗(a+b) = a∗a + 2∗a∗b + b∗b (R4)

Pour tester l'opérateur de multiplication portant sur 2 objets de la classe Polynome, nous ajoutons maintenant ces lignes :

a = Polynome('a') # création du 1er objet de la classe Polynome représentant la variable a
b = Polynome('b') # création du 2e objet de la classe Polynome représentant la variable b

print((a+b)*(a+b)) # affiche l'expression (a+b)*(a+b) sous sa forme développée et réduite

Le code affiche :

a^2 + 2*a*b + b^2


III-C. Surcharge de l'opérateur de puissance

Maintenant que nous avons redéfini l'opérateur de multiplication dans notre classe Polynome, nous pouvons ajouter une méthode __pow__() qui va permettre d'obtenir le résultat d'un polynôme élevé à la puissance n.

class Polynome:

...

def __mul__(self, other): # méthode permettant de redéfinir l'opérateur « * » pour 2 objets Polynome : self * other
# règles R2, R3, R4 et R5
# R2 : (a+b)*(a+b) = (a+b)*a + (a+b)*b
# R3 : = a*(a+b) + b*(a+b)
# R2 : = a*a + a*b + b*a + b*b
# R3 = a*a + a*b + a*b + b*b
# R4 : = a*a + 2*a*b + b*b

# initialisation de la liste de termes
liste_termes = []

# si le 2e membre est un numérique
if isinstance(other, (int,float)):
# on multiplie les coefficients des termes de self.liste_termes par other
liste_termes = [(other*terme,terme) for terme in self.liste_termes]

return Polynome(liste_termes)

# parcours des termes de la liste de other
for terme_droite in other.liste_termes:

# parcours des termes de la liste de self
for terme_gauche in self.liste_termes:

coef = terme_droite*terme_gauche
var = terme_droite + terme_gauche

# tri des variables
var = tuple(sorted(var))

# ajout du tuple (coef,var) à la liste
liste_termes.append((coef,var))

# renvoie l'objet Polynome résultat de la multiplication de self et other avec regroupement des termes identiques
return Polynome(liste_termes)


def __pow__(self, n): # méthode permettant de redéfinir l'opérateur de puissance : self ** n

# on utilise pour cela la règles R1 :
# R1 : ∀x, x^2 = x∗x

# a^2 = a*a
# a^3 = a*a*a
#...

# on initialise la variable objet p avec un polynôme égal à 1
p = Polynome((1,()))

# on multiplie n fois p par self à l'aide de l'opérateur *
for i in range(n):
p = p*self # équivalent à : p = p.__mul__(self)

# renvoie l'objet Polynome résultat de l'opération (self ** n)
return p


Nous testons maintenant l'opérateur pour (a + b) ** 2 :

a = Polynome('a') # création du 1er objet de la classe Polynome représentant la variable a
b = Polynome('b') # création du 2e objet de la classe Polynome représentant la variable b

print((a+b)**2) # affiche l'expression (a+b)^2 sous sa forme développée et réduite

Le code renvoie :

a^2 + 2*a*b + b^2


Tableau de quelques opérateurs et de leur méthode correspondante en Python :



Opérateur
Expression
Interprétation Python


Addition
p1 + p2
p1.__add__(p2)


Soustraction
p1 - p2
p1.__sub__(p2)


Multiplication
p1 * p2
p1.__mul__(p2)


Puissance
p1 ** n
p1.__pow__(n)


Division
p1 / p2
p1.__truediv__(e2)


...
...
...




III-D. Surcharge de l'opérateur de comparaison « == »

Pour surcharger l'opérateur « == » et pouvoir ainsi tester si 2 polynômes sont égaux, nous ajoutons finalement une méthode __eq__ () à notre classe :

class Polynome:
...

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

# renvoie True si les listes de termes des 2 polynômes sont égales
return (self.liste_termes==other.liste_termes)


Vérifions pour terminer notre identité de départ :

a = Polynome('a') # création d'un 1er objet représentant la variable a
b = Polynome('b') # création d'un 2e objet représentant la variable b

# création d'un objet Polynome à partir de l'expression (a+b)^2
p1 = (a+b)**2

# affiche l'expression de p1
print(p1)

# création d'un objet Polynôme à partir de l'expression a^2 + b^2 + 2*a*b
p2 = a**2 + b**2 + a*b*2

# affiche l'expression de p2
print(p2)

# affiche le résultat de la comparaison p1=p2
print("p1=p2 ? : " + str(p1==p2))


Le code affiche :

p1=p2 ? : True


Tableau de quelques opérateurs de comparaison et de leur méthode correspondante en Python :



Opérateur
Expression
Interprétation Python


Inférieur à
p1 < p2
p1.__lt__(p2)


Inférieur ou égal
p1 <= p2
p1.__le__(p2)


Egal
p1 == p2
p1.__eq__(p2)


...
...
...




Si vous souhaitez avoir une liste plus complète des opérateurs, je vous invite à consulter cette page.


IV. Module complet

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

def regrouper_termes(liste_termes):
# permet de regrouper les termes identiques dans une liste triée en utilisant les règles R4 et R5 :
# R5 : a*a + b + a*a + b + c = a*a + a*a + b + b + c (tri)
# R4 : a*a + a*a + b + b + c = 2*a*a + 2*b + c (regroupement)
# [(1,('a', 'a')), (1,('b',)), (1,('a', 'a')), (1,('b',)), (1,('c',))] -> [(2,('a','a')), (2,('b',)), (1,('c',))]

# créer une liste triée de variables ou de tuples uniques : [(1,('a', 'a')), (1,('b',)), (1,('a', 'a')), (1,('b',)), (1,('c',)] -> [('a','a'), ('b',), ('c',)]
liste_vars = [t for t in liste_termes]
liste_vars_uniques = sorted(set(liste_vars)) # règle R5

# initialisation de la liste de termes à renvoyer
liste_termes_groupes = []

# parcours les variables uniques de la liste
for var in liste_vars_uniques:

# compte le nombre de fois que la variable est présente dans la liste
coef = sum([t for t in liste_termes if t==var]) # Règle R4
if coef!=0: # si le coef. n'est pas égal à 0
# ajout du tuple (coef,var) à la liste : liste_termes_groupes.append((2,('a',)))
liste_termes_groupes.append((coef,var))

# renvoie de la liste des termes groupés
return liste_termes_groupes


class Polynome:

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

# on s'assure que l'argument termes est une liste
if not isinstance(termes, list): termes =

# parcours des indices et des termes de la liste
for indice, terme in enumerate(termes):

# si le terme est de type string : 'a'
if isinstance(terme, str):
# on met à jout l'élément de la liste avec un tuple de la forme (1,('a',)) : (coef, var)
termes = (1,(terme,))
elif len(terme)==1: # ou si le terme est un tuple à un seul élément : ('a',) : (coef, var)
termes = (1,terme)

# regroupement des termes identiques en utilisant les règles R4 et R5
termes = regrouper_termes(termes)

# on définit la liste de termes correspondant au polynôme. Ex. : [(1,('a','a')), (2,('a','b')), (1,('b','b'))] -> a^2 + 2ab + b^2
self.liste_termes = termes


def __str__(self): # permet d'afficher l'expression sous sa forme développée et réduite

# initialise la chaîne à renvoyer
chaine_expression = ''

# si le polynôme est égal à un nombre : p=1
if (len(self.liste_termes)==1) and self.liste_termes==():
return str(self.liste_termes) # renvoie le nombre

# parcours de la liste de termes du polynôme
for terme in self.liste_termes:

# création de la liste de variables uniques : ['a', 'b', 'c']
liste_vars = sorted(set(terme))

if liste_vars==[]: # si c'est un nombre
chaine_terme=str(terme)
else: # sinon
# si le coefficient du terme vaut 1 : (1,'a')
if terme==1:
chaine_terme='' # on part d'une chaîne vide
else: # sinon
chaine_terme=str(terme) + '*' # on part d'une chaîne contenant le coef. : '2*'

# parcours des variables du terme : ('a','a','b') -> a*a*b = (a^2)*b
for var in liste_vars:

# évalue l'exposant de la variable : ('a','a','a') -> a^3 (R1)
exp = len([v for v in terme if v==var])

# si l'exposant vaut 1
if exp==1:
chaine_terme += var + '*'
else: # sinon
chaine_terme += var + '^' + str(exp) + '*'

chaine_terme = chaine_terme[:-1]

chaine_expression += chaine_terme + " + "

# renvoie la chaîne représentant l'expression du polynôme
return chaine_expression[:-3]


def __add__(self, other): # méthode permettant de redéfinir l'opérateur « + » pour 2 objets Polynome : self + other
# concaténation des 2 listes de termes
# [(1,('a', 'a')), (1,('b',))] + [(1,('a', 'a')), (1,('b',))] = [(1,('a', 'a')), (1,('b',)), (1,('a', 'a')), (1,('b',))]

# tri et regroupement des termes identiques en utilisant les règles R4 et R5 :
# R5 : a*a + b + a*a + b -> a*a + a*a + b + b (tri)
# R4 : a*a + a*a + b + b -> 2*a*a + 2*b (regroupement)
# [(1,('a', 'a')), (1,('b',)), (1,('a', 'a')), (1,('b',))] -> [(2,('a','a')), (2,('b',))]

# concaténation des 2 listes de termes de self et other
liste_termes = self.liste_termes + other.liste_termes

# renvoie l'objet Polynome résultat de l'addition de self et other avec regroupement des termes identiques
return Polynome(liste_termes)


def __mul__(self, other): # méthode permettant de redéfinir l'opérateur « * » pour 2 objets Polynome : self * other
# règles R2, R3, R4 et R5
# R2 : (a+b)*(a+b) = (a+b)*a + (a+b)*b
# R3 : = a*(a+b) + b*(a+b)
# R2 : = a*a + a*b + b*a + b*b
# R3 = a*a + a*b + a*b + b*b
# R4 : = a*a + 2*a*b + b*b

# initialisation de la liste de termes
liste_termes = []

# si le 2e membre est un numérique
if isinstance(other, (int,float)):
# on multiplie les coefficients des termes de self.liste_termes par other
liste_termes = [(other*terme,terme) for terme in self.liste_termes]

return Polynome(liste_termes)

# parcours des termes de la liste de other
for terme_droite in other.liste_termes:

# parcours des termes de la liste de self
for terme_gauche in self.liste_termes:

coef = terme_droite*terme_gauche
var = terme_droite + terme_gauche

# tri des variables
var = tuple(sorted(var))

# ajout du tuple (coef,var) à la liste
liste_termes.append((coef,var))

# renvoie l'objet Polynome résultat de la multiplication de self et other avec regroupement des termes identiques
return Polynome(liste_termes)


def __pow__(self, n): # méthode permettant de redéfinir l'opérateur de puissance : self ** n

# on utilise pour cela la règles R1 :
# R1 : ∀x, x^2 = x∗x

# a^2 = a*a
# a^3 = a*a*a
#...

# on initialise la variable objet p avec un polynôme égal à 1
p = Polynome((1,()))

# on multiplie n fois p par self à l'aide de l'opérateur *
for i in range(n):
p = p*self # équivalent à : p = p.__mul__(self)

# renvoie l'objet Polynome résultat de l'opération (self ** n)
return p


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

# renvoie True si les listes de termes des 2 polynômes sont égales
return (self.liste_termes==other.liste_termes)


a = Polynome('a') # création d'un 1er objet représentant la variable a
b = Polynome('b') # création d'un 2e objet représentant la variable b

# création d'un objet Polynome à partir de l'expression (a+b)^2
p1 = (a+b)**2

# affiche l'expression de p1
print(p1)

# création d'un objet Polynôme à partir de l'expression a^2 + b^2 + 2*a*b
p2 = a**2 + b**2 + a*b*2

# affiche l'expression de p2
print(p2)

# affiche le résultat de la comparaison p1=p2
print("p1=p2 ? : " + str(p1==p2))


A noter qu'il existe des bibliothèques en Python spécialisées dans le calcul formel, comme par exemple la librairie Sympy.


V. Conclusion

Ce billet nous aura donc permis de mieux comprendre l'intérêt du calcul symbolique et comment le mettre en œuvre en Python.

Chacun pourra ensuite librement ajouter de nouvelles méthodes à cette classe Polynome en utilisant de nouvelles règles mathématiques, pour par exemple redéfinir les opérateurs de soustraction ou de division entre deux polynômes.


Sources :

https://fr.wikipedia.org/wiki/Calcul_formel
https://en.wikipedia.org/wiki/Computer_algebra
https://fr.wikipedia.org/wiki/M%C3%A9thode_formelle_(informatique)
https://fr.wikipedia.org/wiki/Polyn%C3%B4me
https://www.sympy.org/en/index.html
https://docs.python.org/fr/3/library/operator.html