Feuille d’exercices 8

Feuille d’exercices 8#

Objectifs

  • Polynômes

  • Réduction matricielle

Exercice 1 : Manipulation de polynômes#

Question 1 : Effectuer les opérations suivantes :

  1. Créer l’anneau de polynômes \(\mathbb{Q}[X]\) et nommer X la variable correspondante

  2. Créer les polynômes \(P(X) = 2X^4 - \frac{1}{2}X - \frac{3}{2}\) et \(Q(X) = X^2 - 3X + 2\).

  3. Calculer \(S(X) = -2 P(X) + Q(2X^2+1)\).

  4. Calculer \(R(X) = {\rm pgcd}(P(X), Q(X))\).

  5. Vérifier que \(P(X)\) est bien divisible par \(R(X)\), et calculer le quotient correspondant.

POLY.<X> = PolynomialRing(QQ, "X")
P = 2*X**4 - (1/2)*X -(3/2)
Q = X**2 - 3*X + 2
print("P =", P)
print("Q =", Q)
S = -2 * P(X) + Q(X**2+1)
print("S =", S)
R = gcd(P, Q)
print("R =", R)
print(P % R == 0)
print("quotient =", P // R)

P = 2*X^4 - 1/2*X - 3/2
Q = X^2 - 3*X + 2
S = -3*X^4 - X^2 + X + 3
R = X - 1
True
quotient = 2*X^3 + 2*X^2 + 2*X + 3/2

Question 2 : Dérivées successives d’un polynôme aléatoire.

  1. En utilisant la méthode .random_element() de l’anneau de polynômes, construire un polynôme aléatoire \(P(X)\) à coefficients entiers.

  2. Obtenir le degré \(d\) de \(P(X)\).

  3. Vérifier, à l’aide d’une boucle, que la dérivée \(d\)-ème de \(P(X)\) est égale au polynôme constant \((d!) \times a\), où \(a\) est le coefficient dominant du polynôme \(P(X)\).

POLY_ZZ.<X> = PolynomialRing(ZZ, "X")
P = POLY_ZZ.random_element(6)
print("P =", P)

d = P.degree()
print("d =", d)

Q = P
for i in range(d):
    Q = Q.derivative()
print(Q)
c = factorial(d) * P.constant_coefficient()
print(c)
print(Q == factorial(d) * P.constant_coefficient())

P = -X^6 - X^5 + X^4 - 14*X^3 - 2*X^2 + 1
d = 6
-720
720
False

Exercice 2 : autour du polynôme caractéristique d’une matrice#

Question 1 : Construire la matrice \({\bf M}\) suivante, puis calculer son polynôme caractéristique \(P(X)\).

\[\begin{split} {\bf M} = \left(\begin{array}{rrr} -1 & 0 & 0 \\ -2 & 1 & 4 \\ -8 & 0 & 3 \end{array}\right) \end{split}\]
M = matrix(QQ, [[-1, 0, 0], [-2, 1, 4], [-8, 0, 3]])
P = M.characteristic_polynomial()

Question 2 : Calculer les valeurs propres de la matrice \({\bf M}\) (avec la méthode eigenvalues), puis vérifier que le polynôme caractéristique s’annule sur ces valeurs propres.

valeurs_propres = M.eigenvalues()
print(all(P(s) == 0 for s in valeurs_propres))

True

Question 3 : Vérifier que, si \(\lambda\) est une des valeurs propres de \({\bf M}\), alors le rang de \({\bf M} - \lambda {\bf I_3}\) est \(2\), où \({\bf I_3}\) est la matrice identité.

I3 = matrix.identity(QQ, 3)
for s in valeurs_propres:
    print( (M - s*I3).rank() )

2
2
2

Question 4 : Vérifier que \(P({\bf M}) = {\bf 0}\). Autrement dit, vérifier que si \(P(X)\) s’écrit \(a_2 X^2 + a_1 X + a_0\), alors la matrice \(a_2 {\bf M}^2 + a_1 {\bf M} + a_0 {\bf I_3}\) est égale à la matrice nulle.

Remarque . On dit alors que \(P\) est un polynôme annulateur de la matrice \({\bf M}\). Le polynôme caractéristique est toujours un polynôme annulateur de sa matrice : c’est l’objet du théorème de Cayley–Hamilton.

print(P(M))

[0 0 0]
[0 0 0]
[0 0 0]

Exercice 3 : racines de polynômes#

Question 1 : Construire le polynôme

\[ P(X) = 2X^{6} - 3X^{5} - 13X^{4} + 29X^{3} - 27X^{2} + 32X - 12 \]

en tant que polynôme à coefficients entiers.

R = PolynomialRing(ZZ, "X")
X = R.gen()
P = 2*X**6 - 3*X**5 - 13*X**4 + 29*X**3 - 27*X**2 + 32*X - 12

On peut obtenir les racines d’un polynôme dans une structure algébrique autre que celle de ses coefficients, en spécifiant la structure en paramètre de la méthode roots. Par exemple, P.roots(RR) donne les racines de P dans le corps de nombres flottants.

Question 2 : Quelles sont les racines de \(P\) dans :

  • l’anneau des entiers ?

  • le corps des rationnels ?

  • le anneau des éléments « symboliques » (qui contient le nombre complexe \(i\)), représenté par la variable SR ?

racines_ZZ = P.roots(ZZ)
print("Dans Z :", racines_ZZ)

racines_QQ = P.roots(QQ)
print("Dans Q :", racines_QQ)

racines_SR = P.roots(SR)
print("Dans SR :", racines_SR)

Dans Z : [(-3, 1), (2, 2)]
Dans Q : [(1/2, 1), (-3, 1), (2, 2)]

Dans SR : [(-3, 1), (1/2, 1), (-I, 1), (I, 1), (2, 2)]

Question 3 : Vérifier que \(P(X) = \alpha \prod_{i=1}^k (X - x_i)^{m_i}\), où :

  • \(\alpha\) est le coefficient dominant de \(P\),

  • les \((x_i)\) sont les racines de \(P\) dans le corps des nombres complexes CC,

  • les \((m_i)\) sont les multiplicités de ces racines.

Q = 1
racines_SR = P.roots(CC)
for i in range(len(racines_SR)):
    racine = racines_SR[i]
    facteur = (X - racine[0])**racine[1]
    Q *= facteur
Q = P.leading_coefficient() * Q
print(Q == P)

True

Exercice 4 : interpolation de Lagrange#

Soient \(x_0, x_1, \dots, x_{n-1}\) des éléments \(2\) à \(2\) distincts d’un corps (rationnels ou complexes par exemple), et \(y_0, y_1, \dots, y_{n-1}\) d’autres éléments de ce même corps (cette fois, pas nécessairement distincts). Le problème de l’interpolation consiste à calculer un polynôme \(P(X)\) de degré \(\le n-1\) tel que

\[ P(x_i) = y_i, \quad \forall i \in \{0, \dots, n-1 \}. \]

Pour cela, il existe plusieurs méthodes, la plus connue étant la méthode de Lagrange.

Pour \(0 \le i \le n-1\), on définit le \(i\)-ème polynôme de Lagrange associé au vecteur \(\mathbf{x} = (x_0, \dots, x_{n-1})\) comme le polynôme :

\[ L_i(X) = \prod_{j \in \{0, \dots, n-1\} \setminus \{ i \}} \frac{X - x_j}{x_i - x_j}. \]

Question 1 : Écrire une fonction polynome_lagrange(R, vec_x, i) qui prend en entrée un anneau de polynômes R, une liste de points d’évaluation vec_x de longueur \(n\) et un entier i entre \(0\) et \(n-1\), et qui calcule \(L_i(X)\).

def polynome_lagrange(R, vec_x, i):
    X = R.gen()
    res = R.one()
    n = len(vec_x)
    for j in range(n):
        if j != i:
            res = res * (X - vec_x[j])/(vec_x[i] - vec_x[j])
    return res

Les polynômes \(L_i(X)\) ainsi construits forment une base d’interpolation. On peut ainsi calculer le polynôme interpolateur \(P\) des \((x_i, y_i)\) grâce à la formule :

\[ P(X) = \sum_{i=0}^{n-1} y_i L_i(X) \]

Question 2 : Écrire une fonction polynome_interpolateur(R, vec_x, vec_y) qui retourne le polynôme interpolateur dans l’anneau de polynômes R, associé aux listes de points d’évaluation vec_x (les valeurs \(x_0, \dots, x_{n-1}\)) et de valeurs d’évaluation vec_y (les valeurs \(y_0, \dots, y_{n-1}\)).

def polynome_interpolateur(R, vec_x, vec_y):
    n = len(vec_x)
    res = R.zero()
    for i in range(n):
        res += vec_y[i] * polynome_lagrange(R, vec_x, i)
    return res

Question 3 : Afficher dans un même graphique :

  1. une liste de \(8\) points du plan de la forme \((x_i, y_i)\) où \(x_i = i\) et \(y_i\) est un entier tiré aléatoirement entre \(-20\) et \(20\),

  2. le polynôme interpolateur des \((x_i)\) et \((y_i)\).

On vérifiera que le tracé du polynôme passe bien par les points du plan qui on été tirés.

def teste_et_affiche():
    n = 8
    R = PolynomialRing(QQ, "X")
    
    # on crée les vecteurs x et y 
    vec_x = [ i for i in range(n) ]
    vec_y = [ randint(-20, 20) for i in range(n) ]
    
    # on calcule le polynome interpolateur de Lagrange
    P = polynome_interpolateur(R, vec_x, vec_y)
    print(P)
    
    # on affiche les points et le polynome sur un même graphique
    pl = points([[vec_x[i], vec_y[i]] for i in range(n)], color="red", size=40)
    pl += plot(P, 0, n-1)
    pl.show()

teste_et_affiche()

-59/336*X^7 + 1529/360*X^6 - 2429/60*X^5 + 1733/9*X^4 - 22831/48*X^3 + 205451/360*X^2 - 55481/210*X + 18
../_images/f97506a50205811ffd629c82004f0d37b034ac7a4e482f0ae4f982b69ddb9191.png
Contenu