I. Introduction
On souhaite créer une fonction Python qui pourra déterminer le polynôme caractéristique d'une matrice carrée.
Ce polynôme renferme d'importantes informations sur la matrice, comme ses valeurs propres, son déterminant, etc. Il permet aussi d'obtenir l'équation caractéristique associée à une suite récurrente linéaire.
II. Définitions mathématiques
II-A. Polynôme caractéristique
D'après Wikipedia, si on considère M une matrice carrée d'ordre n. Le polynôme caractéristique de M, noté pM(X), est le polynôme défini par :
647407
où det est le déterminant des matrices, In désigne la matrice identité d'ordre n.
Par exemple, pour une matrice M d'ordre 2 :
647408
II-B. Calcul du déterminant - Formule de Laplace
En algèbre linéaire, la comatrice d'une matrice carrée A est une matrice carrée de même taille, dont les coefficients, appelés les cofacteurs de A, interviennent dans le développement du déterminant de A suivant une ligne ou une colonne.
Si A est une matrice inversible, sa comatrice intervient également dans une expression de son inverse.
Le cofacteur d'indice i, j de A est :
647386
La comatrice de A est la matrice de ses cofacteurs.
Formule de développement d'un déterminant d'ordre n par rapport à la ligne i :
647423
Prenons comme exemple la matrice :
647388
Son développement nous donne :
647389
On peut également développer le déterminant par rapport à j.
III. Implémentation en Python
On utilise à nouveau notre classe Polynome pour obtenir le polynôme caractéristique à partir de la matrice carrée.
III-A. Création de la matrice du polynôme caractéristique
On va d'abord transformer la matrice M en matrice du polynôme résultat de l'expression X.In - M :
def matrice_polynome(mat):
# création de la matrice du polynôme caractéristique
# parcours des indices des lignes de la matrice
for i in range(len(mat)):
# parcours des indices des colonnes de la matrice
for j in range(len(mat)):
if i==j: # si le coefficient est sur la diagonale
# On copie à cet emplacement le polynôme P(X) = X - mat
mat = Polynome([-mat, 1])
else: # sinon le polynôme P(X) = - mat
mat = Polynome([-mat])
# renvoi la matrice du polynôme caractéristique
return mat
III-B. Développement du déterminant de la matrice du polynôme
On va utiliser ensuite la formule de développement de Laplace par rapport à la ligne i pour obtenir le polynôme caractéristique de la matrice.
La fonction suivante renvoie donc le polynôme caractéristique recherché :
def determinant(mat):
# développement du déterminant de la matrice mat par rapport la ligne i
# si la matrice est d'ordre 1
if len(mat)==1:
# on renvoie l'unique élément de la matrice
return mat
else: # sinon
# création du polynôme nul
d = Polynome()
# parcours des indices des colonnes de la matrice
for j, element in enumerate(mat):
# suppression de la 1re ligne de la matrice : mat[1:]
# + suppression de la colonne j dans la matrice mat
comat= [ligne[:j] + ligne[j+1:] for ligne in mat[1:]]
# det(M) = (-1)**(j)*a(1,j)*(com M)(0,j)
d += Polynome([pow(-1,j)])*element*determinant(comat)
# on renvoie le polynôme caractéristique
return d
Testons maintenant nos fonctions :
# matrice exemple
m = [[2, 1], [-1, 0]]
# création de la matrice du polynôme caractéristique
mp = matrice_polynome(m)
# détermination du polynôme caractéristique associé à la matrice m
p = determinant(mp)
# affiche le polynôme caractéristique
print("Pm(X) = " + str(p))
Le code affiche :
Pm(X) = 1 - 2.X + X^2
III-C. Application - Suite récurrence linéaire et matrice compagnon
Soit une suite récurrente linéaire définie sous sa forme générale par la relation :
647390
Sa matrice compagnon est alors de la forme :
647391
Si on considère maintenant la suite de Fibonacci et sa relation de récurrence :
647392
On peut alors obtenir sa matrice compagnon :
647393
D'où l'on déduit son polynôme caractéristique :
647394
On voit tout de suite le lien avec le nombre d'or 𝜑 qui est racine de l'équation caractéristique :
647395
Si l'on multiplie les deux côtés par 𝜑n, on obtient:
𝜑n+2 = 𝜑n+1 + 𝜑n
Donc la suite (𝜑n) est une suite de Fibonacci.
Mise en œuvre en Python :
# matrice compagnon associée à la suite de Fibonacci
m = [[0, 1], [1, 1]]
# création de la matrice du polynôme caractéristique
mp = matrice_polynome(m)
# détermination du polynôme caractéristique associé à la matrice m
p = determinant(mp)
# affiche le polynôme caractéristique
print("Pm(X) = " + str(p))
Le code affiche :
Pm(X) = -1 - X + X^2
III-D. Module complet
On donne enfin le code complet du module :
class Polynome:
def __init__(self, liste_coefs=): # méthode constructeur de la classe
# on définit la liste des coefficients du polynôme [a0, a1, ..., an]
self.coefs = liste_coefs
# suppression si nécessaire des zéros en queue de liste de coefficients. Exemple : [2, 3, 1, 0, 0] -> [2, 3, 1]
self.reduire()
def __str__(self): # permet d'afficher le polynôme sous la forme 1 + 2x + 3x^2
s="" # initialisation de la chaîne de caractères
# on vérifie d’abord si le degré du polynôme est nul
if (len(self.coefs)-1==0):
return str(self.coefs)
else: # sinon
if self.coefs!=0:
s=str(self.coefs) + " + "
for i in range(1, len(self.coefs)): # parcours des indices des coefficients du polynôme : [a1, a2, ..., an]
if self.coefs!=0: # si le coefficient de degré i n'est pas nul
if self.coefs!=1: # si le coefficient de degré i est différent de 1
s+="{}.X^{} + ".format(self.coefs,i)
else: s+="X^{} + ".format(i)
# élimination des caractères en trop
s = s[:-3].replace("+ -", "- ").replace("X^1 ","X ").replace(" 1.X"," X")
if s[-2:]=="^1": s = s[:-2]
if s[:3]=="1.X": s = s[3:]
return s # on retourne l'expression du polynôme
def degre(self): # retourne le degré du polynôme
return (len(self.coefs)-1)
def __add__(self, other): # méthode permettant de redéfinir l'opérateur « + » pour 2 polynômes : (1 + 2x + x^2) + (1 + x) = 2 + 3x + x^2
# p1 = self, p2 = other
if len(other.coefs) >len(self.coefs): # si degré de p2 > degré de p1
liste_coefs = other.coefs[:]; n = len(self.coefs) # on copie les coefs du polynôme de degré le plus élevé et la longueur de la liste de coefs la plus petite.
else: liste_coefs = self.coefs[:]; n = len(other.coefs) # sinon, ...
for i in range(n): # parcours des indices de liste_coefs
liste_coefs = self.coefs + other.coefs # addition des coefficients de degré i
return Polynome(liste_coefs) # renvoie le polynôme résultat de l'addition
def __sub__(self, other): # méthode permettant de redéfinir l'opérateur « + » pour 2 polynômes : (1 + 2x + x^2) + (1 + x) = 2 + 3x + x^2
# p1 = self, p2 = other
if len(other.coefs) >len(self.coefs): # si degré de p2 > degré de p1
liste_coefs = other.coefs[:]; n = len(self.coefs) # on copie les coefs du polynôme de degré le plus élevé et la longueur de la liste de coefs la plus petite.
else: liste_coefs = self.coefs[:]; n = len(other.coefs) # sinon, ...
for i in range(n): # parcours des indices de liste_coefs
liste_coefs = self.coefs - other.coefs # addition des coefficients de degré i
return Polynome(liste_coefs) # renvoie le polynôme résultat de l'addition
def reduire(self):
# tant que le dernier élément de la liste est nul
while round(self.coefs[-1],12) == 0 and len(self.coefs)>1:
self.coefs.pop() # supprimer le dernier élément
for i in range(len(self.coefs)):
self.coefs = round(self.coefs,12)
def __mul__(self, other): # méthode permettant de redéfinir l'opérateur « * » pour 2 polynômes : (1 + x) * (1 + 2x) = 1 + 3x + 2x^2
if isinstance(other,tuple):
coef = other; degre = other
liste_coefs = *degre + self.coefs
for i in range(degre, len(liste_coefs)):
liste_coefs = liste_coefs*coef
else:
# initialisation de la liste des coefficients qu'avec des zéros
liste_coefs=*(len(self.coefs)+len(other.coefs)-1) # exemple : [0, 0, 0]
for i1 in range(len(self.coefs)): # parcours des indices des coefs du polynôme n°1
for i2 in range(len(other.coefs)): # parcours des indices des coefs du polynôme n°2
# multiplication des coefficients d'indices i1 et i2
liste_coefs[i1+i2] = liste_coefs[i1+i2] + self.coefs*other.coefs
poly = Polynome(liste_coefs) # création de l'objet Polynome basé sur la liste
return poly # renvoie le polynôme résultat de la multiplication
def __pow__(self, n): # méthode permettant de redéfinir l'opérateur de puissance : self ** n
# on crée l'objet poly à partir d'une liste contenant un seul élément 1, élément neutre pour la multiplication des polynômes
poly = Polynome()
for i in range(n): # on multiplie n fois poly par self à l'aide de l'opérateur *
poly = poly*self # équivalent à : poly = poly.__mul__(self)
return poly # renvoie le polynôme résultat de l'opération (self ** n)
def __truediv__(self, other): # méthode permettant de redéfinir l'opérateur « / » pour 2 polynômes
# si le degré de self est inférieur au degré de other
if self.degre()
return (Polynome(), self) # sortie de la fonction
# polynôme self représentant au départ le reste r
r = Polynome(self.coefs)
# degré du polynôme représentant le quotient q
degre = r.degre() - other.degre()
# initialisation du polynôme q : [0, 0, 1] -> ... + X^2
q = Polynome(*degre + )
# tant que le degré mini des termes du polynôme q est supérieur ou égal à 0, et que r n'est pas égal à 0.
while (degre>=0) and (r.coefs[-1]!=0):
# coefficient du nouveau terme du polynôme q
coef = r.coefs[-1] / other.coefs[-1]
# affectation du coefficient au terme
q.coefs = coef
# on multiplie le polynôme other par le polynôme coef*(x^degre)
p = other * (coef, degre)
# soustraction des polynômes r et p
r = r - p
# degré du nouveau terme du polynôme q
degre = r.degre() - other.degre()
# renvoi le couple (q, r) représentant le quotient et le reste de la division
return (q, r)
def __eq__(poly1, other): # méthode permettant de redéfinir l'opérateur « == » pour 2 polynômes
return (poly1.coefs==other.coefs) # renvoie True si les 2 listes de coefficients sont égales
def eval(self,x): # méthode permettant d'évaluer le polynôme en fonction de x
# intialisation des variables
valeur_polynome = self.coefs # valeur_polynome = a0
power=1
for coef in self.coefs[1:]: # parcours des coefficients du polynôme à partir de a1 : a1, a2, ..., an
power = power*x # calcul de la puissance de x pour ai : power = x^i
valeur_polynome += coef*power # valeur_polynome = valeur_polynome + ai*x^i
return valeur_polynome # renvoie la valeur du polynôme
def eval_horner(self,x): # méthode permettant d'évaluer le polynôme en fonction de x
# intialisation de la variable
valeur_polynome = self.coefs[-1] # valeur_polynome = an
for coef in reversed(self.coefs[:-1]): # parcours des coefficients du polynôme à partir de an-1 : an-1, ..., a1, a0
valeur_polynome = valeur_polynome*x + coef # valeur_polynome = valeur_polynome*x + ai
return valeur_polynome # renvoie la valeur du polynôme
def matrice_polynome(mat):
# création de la matrice du polynôme caractéristique
# parcours des indices des lignes de la matrice
for i in range(len(mat)):
# parcours des indices des colonnes de la matrice
for j in range(len(mat)):
if i==j: # si le coefficient est sur la diagonale
# On copie à cet emplacement le polynôme P(X) = X - mat
mat = Polynome([-mat, 1])
else: # sinon le polynôme P(X) = - mat
mat = Polynome([-mat])
# renvoi la matrice du polynôme caractéristique
return mat
def determinant(mat):
# développement du déterminant de la matrice mat par rapport la ligne i
# si la matrice est d'ordre 1
if len(mat)==1:
# on renvoie l'unique élément de la matrice
return mat
else: # sinon
# création du polynôme nul
d = Polynome()
# parcours des indices des colonnes de la matrice
for j, element in enumerate(mat):
# suppression de la 1re ligne de la matrice : mat[1:]
# + suppression de la colonne j dans la matrice mat
comat= [ligne[:j] + ligne[j+1:] for ligne in mat[1:]]
# det(M) = (-1)**(j)*a(1,j)*(com M)(0,j)
d += Polynome([pow(-1,j)])*element*determinant(comat)
# on renvoie le polynôme caractéristique
return d
print("I. Polynôme carcatéristique d'une matrice")
print()
# matrice exemple
m = [[2, 1], [-1, 0]]
print("m = " + str(m))
print()
# création de la matrice du polynôme caractéristique
mp = matrice_polynome(m)
# détermination du polynôme caractéristique associé à la matrice m
p = determinant(mp)
# affiche le polynôme caractéristique de m
print("Pm(X) = " + str(p))
print()
print("II. Polynôme caractéristique associé à une suite récurrente linéaire")
print()
# matrice compagnon associée à la suite de Fibonacci
m = [[0, 1], [1, 1]]
print("m = " + str(m))
print()
# création de la matrice du polynôme caractéristique
mp = matrice_polynome(m)
# détermination du polynôme caractéristique associé à la matrice m
p = determinant(mp)
# affiche le polynôme caractéristique
print("Pm(X) = " + str(p))
IV. Conclusion
Après avoir montré comment obtenir le polynôme caractéristique associé à une matrice carrée, nous avons pu proposer une implémentation en Python.
Enfin, nous avons mieux compris l'intérêt de ces polynômes caractéristiques à l'aide d'un exemple simple permettant de faire le lien entre la suite de Fibonacci et le nombre d'or.
Sources :
https://fr.wikipedia.org/wiki/Polyn%C3%B4me_caract%C3%A9ristique
https://fr.wikipedia.org/wiki/D%C3%A9terminant_(math%C3%A9matiques)
https://fr.wikipedia.org/wiki/Matrice_(math%C3%A9matiques)
https://fr.wikipedia.org/wiki/Matrice_identit%C3%A9
https://fr.wikipedia.org/wiki/Comatrice
https://en.wikipedia.org/wiki/Laplace_expansion
https://fr.wikipedia.org/wiki/Suite_r%C3%A9currente_lin%C3%A9aire
Soutenez le club developpez.com en souscrivant un abonnement pour que nous puissions continuer à vous proposer des publications.