Exercice de Programmation : L'algorithme 1.1¶

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)

Hello World
Je suis en 1 ère année Bachelor
Matrix([[1, 2, 3], [0, 4, 5], [0, 0, 6]]) , blabla 

⎡1  2  3⎤
⎢       ⎥
⎢0  4  5⎥
⎢       ⎥
⎣0  0  6⎦
0
1
2
3
4
5
6
7
8
9
True
False

Exercice 1 (Entraînement rapide aux commandes)¶

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.

Définissez une matrice quelconque.
Affichez-là sous forme matricielle.
Calculez son déterminant.
Affichez l'élément qui est dans le coin inférieur droit de votre matrice.
Parcourez les éléments de la première ligne de votre matrice et affichez-les.

Exercice 2 (Opérations élémentaires sur les colonnes)¶

"""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.

Exercice 3 (Algorithme 1.1)¶

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)