IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Voir le flux RSS

User

[Actualité] Calcul formel avec Python (suite) : relations entre coefficients et racines d'un polynôme

Noter ce billet
par , 18/09/2023 à 12h26 (6998 Affichages)
I. Introduction

Dans un précédent billet, on a pu s'initier au calcul formel avec Python en comparant deux expressions mathématiques. On souhaite maintenant aller plus loin en déterminant les relations qui relient les coefficients et les racines d'un polynôme.

Note : les définitions données par la suite sont toutes issues de la page Wikipedia Relations entre coefficients et racines.



II. Définitions mathématiques


II-A. Rappel sur les polynômes

Un polynôme 𝑃 de degré 𝑛 s'écrit sous sa forme la plus générale :

Nom : polynome1.png
Affichages : 945
Taille : 2,4 Ko

𝑎i est appelé coefficient de Xi.

On peut aussi le définir grâce à ses racines, c'est-à-dire l'ensemble des valeurs de X qui annulent 𝑃. Ainsi, le théorème de d'Alembert-Gauss garantit que tout polynôme de degré 𝑛 à coefficients complexes admet exactement 𝑛 racines sur , éventuellement multiples. Il en résulte qu'un polynôme 𝑃 à coefficients complexes peut se réécrire :

Nom : polynome2.png
Affichages : 939
Taille : 3,0 Ko

avec 𝑥i les racines de 𝑃, éventuellement multiples.


II-B. Polynômes symétriques

On définit le k-ième polynôme symétrique à 𝑛 indéterminées, noté σk, comme la somme de tous les produits à k facteurs de ses indéterminées (il y a autant de produits possibles à k facteurs que de combinaisons de k éléments parmi 𝑛).

Par exemple, les polynômes symétriques associés aux indéterminées 𝑥1, 𝑥2, 𝑥3 et 𝑥4 sont :

Nom : formules1.png
Affichages : 1045
Taille : 8,6 Ko

Plus généralement, en considérant les polynômes symétriques σ0, σ1, ..., σn à 𝑛 indéterminées :

Nom : formules2.png
Affichages : 830
Taille : 14,0 Ko


II-C. Relations entre coefficients et racines

On donne maintenant les formules qui relient les coefficients et les racines d'un polynôme 𝑃 :

Nom : relations.png
Affichages : 925
Taille : 5,7 Ko

Ces relations s'obtiennent en développant le produit 𝑃 = 𝑎n(X − x1) (X − x2)⋯(X − xn), et en identifiant les coefficients du développement (qui s'expriment à partir des polynômes symétriques des racines) avec les coefficients de 𝑃 = 𝑎nXn + 𝑎n−1Xn−1 + ⋯ + a0.

Note : Les relations entre les coefficients et les racines portent le nom de François Viète, le premier à les avoir énoncées dans le cas de racines positives.



III. Implémentation en Python

Pour représenter en Python ces polynômes et pouvoir réaliser des opérations entre eux, on utilise à nouveau notre classe Polynome :

Nom : classe_polynome.png
Affichages : 829
Taille : 12,3 Ko

On peut ainsi écrire une fonction qui va nous permettre de développer le produit 𝑃 = an(X − x1) (X − x2)⋯(X − xn), puis d'identifier les coefficients du polynôme obtenu avec ceux de 𝑃 = 𝑎nXn + 𝑎n−1Xn−1 + ⋯ + a0 :

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
def coefficients_polynome(poly):
 
    # initialisation de la liste des coefficients
    liste_coefficients = []
    liste_termes=[]
 
    # parcours des termes du polynôme passé en argument
    for terme in poly.liste_termes:
        # création de la liste de variable sans le 'X' : ('xi','x2')
        liste_vars = tuple([t for t in terme[1] if t!='X'])
 
        # ajout du tuple (coef,vars) à la liste
        liste_termes.append((terme[0],liste_vars))
 
    # détermination du nombre de coefficients du polynôme : ('a3','x1','x2','x3') -> 4
    nombre_coefficients = max([len(t[1]) for t in liste_termes])
 
    # parcours des indices des coefficients : 0 -> nombre_coefficients-1
    for indice_coefficient in range(nombre_coefficients):
 
        # création de la liste des termes du polynôme associés aux coefficients, avec comme formule des coefs : a(n-k) = (-1)^k*an*σk(x1,...,xn)
        termes_polynome =[terme for terme in liste_termes if len(terme[1])==(nombre_coefficients-indice_coefficient)]
 
        # ajout du polynôme à la liste
        liste_coefficients.append(Polynome(termes_polynome))
 
    # renvoie la liste des polynômes associés aux coefficients    
    return liste_coefficients

On teste maintenant notre fonction pour un polynôme de degré 3 possédant 3 racines 𝑥1, x2 et x3 :

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
# recherche des coefficients du polynôme :
# P = a3X^3 + a2x^2 + a1X + a0
 
# Il possède 3 racines x1, x2, x3, on peut donc l'écrire sous sa forme factorisée :
# P = a3*(X-x1)*(X-x2)*(X-x3)
 
# création des objets représentant le coefficient a3, l'indéterminé X et les racines du polynôme
𝑎3 = Polynome('a3') # création d'un 1er objet Polynome représentant le coefficient a3 
X =  Polynome('X') # création d'un 2e objet représentant la variable X
x1 = Polynome('x1') # création d'un 3e objet représentant la racine x1
x2 = Polynome('x2') # création d'un 4e objet représentant la racine x2
x3 = Polynome('x3') # création d'un 5e objet représentant la racine x3
 
# création d'un objet Polynome à partir de l'expression a3*(X-x1)*(X-x2)*(X-x3)
P = a3*(X-x1)*(X-x2)*(X-x3)
 
# détermination des coefficients du polynôme en fonction de ses racines
coefs_polynome = coefficients_polynome(P)
 
# nombre de racines
n=3
 
print("Coefficients du polynôme exprimés en fonction de ses racines :")
 
# parcours des coefficients du polynôme de an à a0, avec comme formule des coef. : a(n-k) = (-1)^k*an*σk(x1,...,xn)
for k,p in enumerate(reversed(coefs_polynome)):
    if k>0: # on choisit de ne pas afficher an = an
        # affiche a(n-k) = ...
        print('a{0} = '.format(n-k) + p.__str__())

Le code affiche :

Nom : resultat1.png
Affichages : 922
Taille : 8,0 Ko

Qui peut également s'écrire :

Nom : resultat2.png
Affichages : 921
Taille : 4,9 Ko

En posant a3=1, et connaissant les racines du polynôme, on peut ainsi évaluer ses autres coefficients et donc identifier l'équation correspondante.

Vous pouvez également vérifier ce résultat par exemple avec l'outil de calcul bien connu Wolfram|Alpha.
.


IV. Module complet

On donne pour finir le code complet du module pour effectuer les tests :

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
244
245
246
247
248
249
250
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[1] 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[0] for t in liste_termes if t[1]==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 = [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[indice] = (1,(terme,))
            elif len(terme)<=1 or not isinstance(terme[0], (int, float)): # ou si le terme est un tuple à un seul élément : ('a',)
                termes[indice] = (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[0][1]==():
            return str(self.liste_termes[0][0]) # 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[1]))
 
            if liste_vars==[]: # si c'est un nombre
                chaine_terme=str(terme[0])
            else: # sinon
                # si le coefficient du terme vaut 1 : (1,'a')
                if terme[0]==1:
                    chaine_terme='' # on part d'une chaîne vide
                else: # sinon
                    chaine_terme=str(terme[0]) + '*' # 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[1] 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].replace(" + -1*"," - ").replace("-1*","-")
 
 
    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 __sub__(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',)), (1,('b',))] + [(1,('a','a')), (1,('b',))] = [(1,('a',)), (1,('b',)), (1,('a','a')), (1,('b',))]
 
        # tri et regroupement des termes identiques en utilisant les règles R4 et R5 :
        # R5 : a + b - a*a - b -> a - a*a + b - b   (tri)
        # R4 : a - a*a + b - b -> a - a*a   (regroupement)
        # [(1,('a',)), (1,('b',)), (-1,('a','a')), (-1,('b',))] -> [(1,('a',)), (-1,('a','a'))]
 
        # met un signe - devant les coefficients de la liste des termes de other
        other_liste_termes=[(-terme[0],terme[1]) for terme in other.liste_termes]
 
        # 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 la soustraction 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[0],terme[1]) 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[0]*terme_gauche[0]
                var = terme_droite[1] + terme_gauche[1]
 
                # 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)
 
 
def coefficients_polynome(poly):
 
    # initialisation de la liste des coefficients
    liste_coefficients = []
    liste_termes=[]
 
    # parcours des termes du polynôme passé en argument
    for terme in poly.liste_termes:
        # création de la liste de variables sans le 'X' : ('x1','x2')
        liste_vars = tuple([t for t in terme[1] if t!='X'])
 
        # ajout du tuple (coef,vars) à la liste
        liste_termes.append((terme[0],liste_vars))
 
    # détermination du nombre de coefficients du polynôme : ('a3','x1','x2','x3') -> 4
    nombre_coefficients = max([len(t[1]) for t in liste_termes])
 
    # parcours des indices des coefficients : 0 -> nombre_coefficients-1
    for indice_coefficient in range(nombre_coefficients):
 
        # création de la liste des termes du polynôme associés aux coefficients, avec comme formule des coefs : a(n-k) = (-1)^k*an*σk(x1,...,xn)
        termes_polynome =[terme for terme in liste_termes if len(terme[1])==(nombre_coefficients-indice_coefficient)]
 
        # ajout du polynôme à la liste
        liste_coefficients.append(Polynome(termes_polynome))
 
    # renvoie la liste des polynômes associés aux coefficients    
    return liste_coefficients
 
# recherche des coefficients du polynôme :
# P = a3X^3 + a2x^2 + a1X + a0
 
# Il possède 3 racines x1, x2, x3, on peut donc l'écrire sous sa forme factorisée :
# P = a3*(X-x1)*(X-x2)*(X-x3)
 
# création des objets représentant le coefficient a3, l'indéterminé X et les racines du polynôme
𝑎3 = Polynome('a3') # création d'un 1er objet Polynome représentant le coefficient a3 
X =  Polynome('X') # création d'un 2e objet représentant la variable X
x1 = Polynome('x1') # création d'un 3e objet représentant la racine x1
x2 = Polynome('x2') # création d'un 4e objet représentant la racine x2
x3 = Polynome('x3') # création d'un 5e objet représentant la racine x3
 
# création d'un objet Polynome à partir de l'expression a3*(X-x1)*(X-x2)*(X-x3)
P = a3*(X-x1)*(X-x2)*(X-x3)
 
# détermination des coefficients du polynôme en fonction de ses racines
coefs_polynome = coefficients_polynome(P)
 
# nombre de racines
n=3
 
print("Coefficients du polynôme exprimés en fonction de ses racines :")
 
# parcours des coefficients du polynôme de an à a0, avec comme formule des coef. : a(n-k) = (-1)^k*an*σk(x1,...,xn)
for k,p in enumerate(reversed(coefs_polynome)):
    if k>0: # on choisit de ne pas afficher an = an
        # affiche a(n-k) = ...
        print('a{0} = '.format(n-k) + p.__str__())


V. Conclusion

Le calcul symbolique nous a donc permis cette fois d'obtenir les relations qui relient les coefficients et les racines d'un polynôme. Pour cela, on a simplement développé sa forme factorisée en utilisant les règles qui régissent les opérations arithmétiques, puis on a identifié les coefficients de ce développement avec ceux du polynôme exprimé sous sa forme générale.

Comme le calcul numérique sur ordinateur permet d'évaluer rapidement une expression numérique, le calcul formel peut donc être très utile pour vérifier facilement certaines identités ou relations mathématiques.


Sources :
https://fr.wikipedia.org/wiki/Calcul_formel
https://fr.wikipedia.org/wiki/Polyn%C3%B4me
https://fr.wikipedia.org/wiki/Relati...nts_et_racines
https://fr.wikipedia.org/wiki/Combin...9p%C3%A9tition
https://fr.wikipedia.org/wiki/Ensemb...%27un_ensemble

Envoyer le billet « Calcul formel avec Python (suite) : relations entre coefficients et racines d'un polynôme » dans le blog Viadeo Envoyer le billet « Calcul formel avec Python (suite) : relations entre coefficients et racines d'un polynôme » dans le blog Twitter Envoyer le billet « Calcul formel avec Python (suite) : relations entre coefficients et racines d'un polynôme » dans le blog Google Envoyer le billet « Calcul formel avec Python (suite) : relations entre coefficients et racines d'un polynôme » dans le blog Facebook Envoyer le billet « Calcul formel avec Python (suite) : relations entre coefficients et racines d'un polynôme » dans le blog Digg Envoyer le billet « Calcul formel avec Python (suite) : relations entre coefficients et racines d'un polynôme » dans le blog Delicious Envoyer le billet « Calcul formel avec Python (suite) : relations entre coefficients et racines d'un polynôme » dans le blog MySpace Envoyer le billet « Calcul formel avec Python (suite) : relations entre coefficients et racines d'un polynôme » dans le blog Yahoo

Commentaires