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 :
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 :
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 :
- A'i,j est la matrice carrée de taille n déduite de A en remplaçant la j-ème colonne par une colonne constituée uniquement de zéros, sauf un 1 sur la i-ème ligne ;
- Ai,j est la sous-matrice carrée de taille n–1 déduite de A en supprimant la i-ème ligne et la j-ème colonne (son déterminant fait donc partie des mineurs de A).
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 :
Prenons comme exemple la matrice :
Son développement nous donne :
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 :
| Code Python : | Sélectionner tout |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | 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[i][i] mat[i][i] = Polynome([-mat[i][i], 1]) else: # sinon le polynôme P(X) = - mat[i][i] mat[i][j] = Polynome([-mat[i][j]]) # 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é :
| Code Python : | Sélectionner tout |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | 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[0][0] else: # sinon # création du polynôme nul d = Polynome([0]) # parcours des indices des colonnes de la matrice for j, element in enumerate(mat[0]): # 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 :
| Code Python : | Sélectionner tout |
1 2 3 4 5 6 7 8 9 10 11 | # 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 :
Sa matrice compagnon est alors de la forme :
Si on considère maintenant la suite de Fibonacci et sa relation de récurrence :
On peut alors obtenir sa matrice compagnon :
D'où l'on déduit son polynôme caractéristique :
On voit tout de suite le lien avec le nombre d'or 𝜑 qui est racine de l'équation caractéristique :
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 :
| Code Python : | Sélectionner tout |
1 2 3 4 5 6 7 8 9 10 11 | # 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 :
| Code Python : | Sélectionner tout |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 | class Polynome: def __init__(self, liste_coefs=[0]): # 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[0]) else: # sinon if self.coefs[0]!=0: s=str(self.coefs[0]) + " + " for i in range(1, len(self.coefs)): # parcours des indices des coefficients du polynôme : [a1, a2, ..., an] if self.coefs[i]!=0: # si le coefficient de degré i n'est pas nul if self.coefs[i]!=1: # si le coefficient de degré i est différent de 1 s+="{}.X^{} + ".format(self.coefs[i],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[i] = self.coefs[i] + other.coefs[i] # 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[i] = self.coefs[i] - other.coefs[i] # 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[i] = round(self.coefs[i],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[0]; degre = other[1] liste_coefs = [0]*degre + self.coefs for i in range(degre, len(liste_coefs)): liste_coefs[i] = liste_coefs[i]*coef else: # initialisation de la liste des coefficients qu'avec des zéros liste_coefs=[0]*(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[i1]*other.coefs[i2] 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([1]) 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()<other.degre(): # on renvoie (0, self) : q=0, r=self return (Polynome([0]), 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([0]*degre + [1]) # 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[degre] = 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[0] # 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[i][i] mat[i][i] = Polynome([-mat[i][i], 1]) else: # sinon le polynôme P(X) = - mat[i][i] mat[i][j] = Polynome([-mat[i][j]]) # 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[0][0] else: # sinon # création du polynôme nul d = Polynome([0]) # parcours des indices des colonnes de la matrice for j, element in enumerate(mat[0]): # 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%A9ristique
https://fr.wikipedia.org/wiki/D%C3%A...C3%A9matiques)
https://fr.wikipedia.org/wiki/Matric...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_..._lin%C3%A9aire