Dans cet exercice, on vous demandera de compléter quelques lignes de codes pour implémenter l'algorithme 1.1 du cours, qui à une matrice $A \in K^{n \times n}$, $Char(K) \neq 2$, trouve une matrice inversible $P$ tel que $P^T \cdot A \cdot P$ est diagonale.
Le langage de programmation utilisé ici est le Python, qui est très simple d'utilisation et se lit facilement. Vous remarquerez que contrairement au C++, on ne met pas de ';' à la fin de chaque instruction, il n'y a pas besoin d'indiquer le type de la variable lors de sa déclaration ou de la définition d'une fonction, et les accolades sont en quelque sorte remplacées par des ':'.
Tout d'abord, quelques commandes de bases utiles à Python et à l'algèbre linéaire :
(Remarque : Vous devrez lancer chaque portion de code d'instructions un à un, dans l'ordre, en cliquant sur le l'option >| en haut permettant de lancer le code, afin que les importations et définitions des fonctions faites dans ces blocs soient toutes prises en compte.)
from sympy import *
"""Affichage de base :"""
print("Hello World") # Affiche le message Hello World. Permet aussi d'afficher des variables. Par exemple :
annee = 1 # Déclaration d'une variable annee, qui est un entier (on n'indique pas le type de annee !)
print("Je suis en", annee, "ère année Bachelor")
"""Quelques types de matrices :"""
n, m = 2, 3
# Syntaxe permettant d'assigner plusieurs variables à la fois. Aussi utilisée ...
# ... lorsque une fonction renvoie plusieurs variables.
A = Matrix([[1, 2, 3], [0, 4, 5], [0, 0, 6]]) # Définition standard d'une matrice 3x3. Chaque ligne est indiquée entre [].
I = eye(n) # Définition d'une matrice identité nxn.
O = ones(n, m) # Définition d'une matrice de taille nxm avec que des 1.
Z = zeros(n, m) # Définition d'une matrice de taille nxm avec que des 0.
D = diag(1, 6, 8, 10, 11) # Définition d'une matrice diagonale avec (1, 6, 8, 10, 11) comme diagonale.
"""Accès aux éléments de la matrice :"""
i, j = 1, 2
# Les entrées d'une matrice, comme en C++, sont indexées depuis le 0.
A[i, j] # Renvoie l'élément de la ligne i+1, colonne j+1 de A, i.e. A_{i+1, j+1}.
"""Opérations sur les matrices :"""
B = A.copy() # Copie d'une matrice (ATTENTION : Ne faites pas B = A. Vous aurez des surprises comme avec les pointeurs C++.).
A+B # Addition de deux matrices. Valable aussi avec le -.
A*B # Multiplication de deux matrices.
A**n # Puissance d'une matrice.
n*A # Multiplication par un scalaire.
"""Quelques méthodes de matrices :"""
x, y = A.shape # Dimensions de A (x = nb. lignes, y = nb. colonnes). Si on en veut qu'une, on utilise :
x = A.rows # Nb. de lignes de A
y = A.cols # Nb. de colonnes de A
A.det() # Déterminant.
B = A.inv() # Inverse (la commande ne modifie pas A).
T = A.T # Transposée (la commande ne modifie pas A).
"""Affichage de matrices :"""
print(A, ", blabla", "\n") # Affiche A en ligne de texte, suivi d'autre chose si vous voulez (\n permet de faire un saut de ligne).
pprint(A) # Affiche A sous forme de matrice.
"""Boucle for :"""
n = 10
# En C++, une boucle for de base sur les valeurs {0, 1, 2, ..., n-1} s'écrit sous la forme : for (int i(0); i < n; ++i) { code }.
# Voici l'équivalent en Python :
for i in range(n): # 0 est inclu, n est exclu.
print(i)
"""Conditions if :"""
# En C++, une condition if s'écrit sous la forme : if (i > 10 or i < - 10) { code }.
# En Python, c'est pareil, mais on ne délimite généralement pas l'instruction avec des parenthèses (ce n'est cependant pas faux)
# et on délimite avec des parenthèses les conditions groupées lorsqu'on a plusieurs "or", "and", ... dans une même instruction.
if n > 9:
print(true)
if (n > 9 and m > 9) or x == 1:
print(true)
else:
print(false)
Effectuez l'exercice en tapant des lignes de codes dans le bloc vide ci-dessous. Vous pouvez ensuite l'éxecuter en cliquant sur le bloc pour le sélectionner, puis en cliquant sur le l'option >| en haut permettant de lancer le code.
"""Attention, l'indexation dans les fonctions définies dans nos exercices commencent toujours à 0 !"""
def SwapCol(A, i, j):
""" B = SwapCol(A, i, j) échange les colonnes i et j de A (avec l'indexation commençant à 0)."""
C = A.copy() # Les matrices sont des objets dits "Mutable" : ils peuvent être modifiés lors de la fonction.
# On en fait donc une copie.
for k in range(C.rows): # On itère sur les lignes.
element_k_i = C[k, i] # On copie les éléments des colonnes i et j et on les échange, un par un.
element_k_j = C[k, j]
C[k, j] = element_k_i
C[k, i] = element_k_j
""" Remarque :
Python permet d'échanger les valeurs de deux variables de manière plus compacte en utilisant la syntaxe :
n, m = m, n
Vous pouvez ajouter toute sorte de méthodes/fonctions/opérations sur vos éléments du côté droit de l'égalité ! """
return C
def SwapCol_Matrix(size, i, j):
""" P = SwapCol_Matrix(n, i, j) retourne la matrice élémentaire de taille 'size'x'size' échangeant les colonnes i et j
d'une matrice A en faisant A*P."""
P = eye(size)
P = SwapCol(P, i, j)
return P
def AddColtoCol(A, i, j, scalar):
""" B = AddColtoCol(A, i, j, scalar) ajoute 'scalar' (par défaut 1) fois la colonne i à la colonne j de A."""
C = A.copy()
##### COMPLETER LE CORPS DE LA FONCTION ##### (Utilisez C et non A !!)
return C
def AddColtoCol_Matrix(size, i, j, scalar):
""" P = AddColtoCol_Matrix(size, i, j, scalar) retourne la matrice élémentaire de taille 'size'x'size' additionnant 'scalar'
fois la colonne i à la colonne j d'une matrice A en faisant A*P."""
P = eye(size)
P = AddColtoCol(P, i, j, scalar)
return P
###################################################
# On définit les même fonctions sur les lignes en utilisant la transposée et les fonctions déjà définies.
def SwapRow(A, i, j):
""" B = SwapRow(A, i, j) échange les lignes i et j de A (avec l'indexation commençant à 0)."""
C = A.T
C = SwapCol(C, i, j) # On échange les colonnes i et j de C = A^T.
C = C.T # On retranspose et on retourne la matrice.
return C
def AddRowtoRow(A, i, j, scalar):
""" B = AddRowtoRow(A, i, j, scalar) ajoute 'scalar' fois la ligne i à la ligne j de A."""
C = A.T
C = AddColtoCol(C, i, j, scalar)
C = C.T
return C
Vous pouvez tester les fonctions dans le bloc vide ci-dessous.
Pour conclure, on définit encore une ou deux fonctions et on passe à l'algorithme 1.1. Ici, vous devrez compléter (dans la fonction diagonalize) trois ou quatre lignes en utilisant les fonctions définies dans l'exercice 2.
def is_row_zero(A, i):
"""b = is_row_zero(A, i) retourne vrai (true) si la ligne i (indexation commençant à 0) de A est zéro et faux (false) sinon."""
for k in range(A.cols): # On itère sur les colonnes.
if A[i, k] != 0: # Si on trouve un élément différent de 0 sur la ligne i, on retourne faux.
return false
return true
def find_non_zero_el_in_row(A, i, j = 0):
"""k = find_non_zero_el_in_row(A, i, j) retourne le plus petit k t.q. A_{i, k} =/= 0 et k>=j
(i.e. retourne l'indice de la première colonne, en partant de j, avec un élément différent de 0 sur la ligne i).
La fonction retourne le nombre de colonnes de A si k n'existe pas."""
for k in range(j, A.cols): # On itère sur les colonnes j, j+1, ...
if A[i, k] != 0: # Si on trouve un élément non nul, on renvoie l'indice de sa colonne.
return k
return A.cols # Sinon, on renvoie le nombre de colonnes de A.
"""Ici, on suppose que A est une matrice symétrique carrée."""
def diagonalize(A):
""" D = diagonalize(A)[0] retourne la matrice A sous forme diagonalisée par l'algorithme 1.1,
P = diagonalize(A)[1] retourne la matrice P telle que P^T A P est diagonale,
D, P = diagonalize(A) retourne les deux."""
D = A.copy()
size = A.rows
P = eye(size)
for i in range(size-1): # On itère sur la taille de A - 1 (il n'y aura pas besoin de toucher à la dernière ligne/colonne)
if is_row_zero(D, i) == true: # Si la ligne i est zéro ...
continue # ... passer à l'étape i+1
if D[i, i] == 0: # Si l'élément diagonal est 0,
k = find_non_zero_el_in_row(D, i, i) # On cherche le prochain élément non nul de la ligne,
if D[k, k] != 0: # Si l'élément diagonal correspondant à l'indice k de cette colonne est non nul, on ?
##### COMPLETER LES TROIS LIGNES DE CODES MANQUANTES en vous inspirant de la suite. #####
else: # Sinon, on additionne une fois la colonne k sur la colonne i (de même pour les lignes).
D = AddColtoCol(D, k, i)
D = AddRowtoRow(D, k, i)
P = P*AddColtoCol_Matrix(size, k, i)
for j in range(i+1, size): # Pour chaque colonne i+1, i+2, ...
##### COMPLETER LA LIGNE DE CODE MANQUANTE #####
D = AddColtoCol(D, i, j, coeff) # On additionne "coeff" fois la colonne i sur la colonne j.
D = AddRowtoRow(D, i, j, coeff) # De même sur les lignes.
P = P*AddColtoCol_Matrix(size, i, j, coeff)
return D, P
Vous pouvez tester les fonctions dans le bloc vide ci-dessous. Des matrices sont déjà prêtes pour le test.
M1 = Matrix([[1, 0, 2], [0, 3, 4], [2, 4, 0]]) # Exemple 1.6 du cours
M2 = Matrix([[2, 4, 6], [4, 4, 3], [6, 3, 1]]) # Exemple 1.7 du cours
M3 = ones(5)