User

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é p_M(X), est le polynôme défini par :



où det est le déterminant des matrices, I_n 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 ;
• A_i,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.I_n - M :

Code Python :

Sélectionner tout - Visualiser dans une fenêtre à part

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 - Visualiser dans une fenêtre à part

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 - Visualiser dans une fenêtre à part

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 𝜑ⁿ, on obtient:

𝜑ⁿ⁺² = 𝜑ⁿ⁺¹ + 𝜑ⁿ

Donc la suite (𝜑ⁿ) est une suite de Fibonacci.


Mise en œuvre en Python :

Code Python :

Sélectionner tout - Visualiser dans une fenêtre à part

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 - Visualiser dans une fenêtre à part

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