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

In [1]:

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.

In [0]:

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

Dans cet exercice, on définit des fonctions permettant de faire des opérations élémentaires sur les colonnes et les lignes d'une matrice.
Le corps de la fonction AddColtoCol qui additionne x fois la colonne i à la colonne j est manquant (il manque deux, voire trois, lignes). C'est à vous de le compléter.

In [0]:

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

In [0]:

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.

In [0]:

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.

In [2]:

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)

In [0]: