TP 3: Calcul matriciel

Environnement de travail

Ouvrir EduPython pour utiliser les modules numpy et numpy.linalg (pour linear algebra) de Python, pour utiliser Python comme assistant de calcul matriciel

Se familiariser avec numpy

Nous allons faire l'exercice suivant avec numpy : On cherche un polynôme qui annule la matrice $T$ définie par

La matrice $T = \begin{pmatrix} 1 & 1 &1\\ 0& 1 & 1\\ 0 & 0 &1 \end{pmatrix}$ est une liste de listes (ligne par ligne)

Recopier le code suivant et l'exécuter


import numpy as np

T = np.array([[1,1,1],[0,1,1],[0,0,1]])
#I est la matrice identité d'ordre 3
I = np.eye(3)
S = T - I
print(S)

Maintenant il s'agit de calculer $S^3$ et de vérifier que l'on obtient la matrice nulle. Une façon de faire est :

Recopier le code suivant et l'exécuter


import numpy as np

T = np.array([[1,1,1],[0,1,1],[0,0,1]])
#I est la matrice identité d'ordre 3
I = np.eye(3)
S = T - I
S2 = S.dot(S)
S3 = S2.dot(S)
#on peut faire aussi S3 = S.dot(S).dot(S)
print(S3)

Une autre façon est d'utiliser le module numpy.linalg


import numpy as np
import numpy.linalg as alg

T = np.array([[1,1,1],[0,1,1],[0,0,1]])
#I est la matrice identité d'ordre 3
I = np.eye(3)
S = T - I
S3 = alg.matrix_power(S,3)
print(S3)

Exercices

  1. Comme $S^3 = T^3 - 3T^2 +3T -I$ on a trouvé un polynôme qui annule $T$, ce qui nous permet ici de trouver l'inverse de $T$ le module numpy.linalg permet lorsqu'une matrice est inversible de calculer son inverse, en écrivant T' = alg.inv(T)
  2. Vérifier que $T' = T^2 -3T +3I$
  3. Soit $A = \begin{pmatrix} 0.625 & 0.375 \\ 0.375& 0.625 \end{pmatrix}$ et $U = \begin{pmatrix} -1 & 1 \\ 1& 1 \end{pmatrix}$ Vérifier que $AU = DU$ où $U = \begin{pmatrix} 0.25 & 0 \\ 0& 1 \end{pmatrix}$

Algorithme d'Euclide étendu

On peut regarder l'algorithme d'Euclide étendu d'un point de vue matriciel où il s'agit de répéter le processus suivant : $ \begin{pmatrix} a\\ b \end{pmatrix} \to \begin{pmatrix} 0 & 1\\ 1& -(a//b) \end{pmatrix}\begin{pmatrix} a\\ b \end{pmatrix}$ où $a//b$ donne le quotient de la division euclidienne de $a$ par $b$

Exercices

  1. Ecrire une fonction euclide_etendu(a,b), sous forme vectorisée qui retourne sous forme de liste en premier le pgcd $d$ puis $u$ et $v$ tel que $au+bv = d$
  2. Test: a = 1292 et b = 798 on doit obtenir d = 38, u = -8 et v = 13
  3. Utiliser la fonction précédente pour résoudre toute équation du type $ax \equiv b \ [n]$

    La fonction doit afficher les deux possibilités suivantes:

    1. "Une solution entre 0 et n-1:--> ...."
    2. "Pas de solution"
  4. Test: 34 et 235 sont premiers entre eux et on a $1 = 11 \times 235 -76 \times 34$ donc 159 est l'unique solution entre 0 et 234 de $34x \equiv 1 \ [235]$