Algorithme du pivot de Gauss

---

import numpy as np

Toutes les matrices considérées ici seront inversibles (et par conséquent des matrices carrées !)

Préambule : permutation de lignes

• Construire une fonction permute(M,L1,L2) qui échange la ligne L1 et la ligne L2 d'une matrice M.

Exemple :

M = np.array([[1,1,2,-1],[1,0,-1,2],[2,1,3,2],[-1,-2,0,4]])
M

array([[ 1,  1,  2, -1],
       [ 1,  0, -1,  2],
       [ 2,  1,  3,  2],
       [-1, -2,  0,  4]])

permute(M,2,3)

array([[ 1,  1,  2, -1],
       [ 1,  0, -1,  2],
       [-1, -2,  0,  4],
       [ 2,  1,  3,  2]])

1. Matrice échelonnée triangulaire

L'objectif de cette première partie est de transformer une matrice inversible quelconque en matrice triangulaire supérieure.
Afin de simplifier la réalisation de cet objectif, le problème va être découpé en plusieurs exercices, modifiant pas à pas une colonne j donnée en paramètre d'une matrice M.

1.1 Exercice : recherche du pivot

• Construire une fonction recherchepivot(M,j) qui pour une matrice M donnée et sa colonne j :

  • recherche le pivot de la colonne j, à savoir le premier coefficient non nul de la colonne j, situé à partir de la diagonale.
  • permute ce pivot, ainsi que toute sa ligne, avec la ligne j.
  • renvoie la matrice ainsi transformée.

Exemple :

M = np.array([[1,1,2,-1],[1,0,-1,2],[2,1,3,2],[-1,-2,0,4]])
M

array([[ 1,  1,  2, -1],
       [ 1,  0, -1,  2],
       [ 2,  1,  3,  2],
       [-1, -2,  0,  4]])

recherchepivot(M,1)

array([[ 1,  1,  2, -1],
       [ 2,  1,  3,  2],
       [ 1,  0, -1,  2],
       [-1, -2,  0,  4]])

1.2 Exercice : annulation des coefficients

• Créer une fonction annulcoeff(M,j) qui pour une matrice M donnée et sa colonne j :

  • applique la fonction précédente.
  • annule les coefficients situés sous le pivot de la colonne j, en utilisant des opérations sur les lignes.

Rappel : une ligne $L_{i}$ est remplacée par : $M[j,j] \times L_{i} - M[i,j] \times L_{j}$

Exemple :

annulcoeff(M,1)

array([[ 1,  1,  2, -1],
       [ 2,  1,  3,  2],
       [ 1,  0, -1,  2],
       [ 3,  0,  6,  8]])

1.3 Exercice : pivot de Gauss

• Construire une fonction gauss(M) qui transforme une matrice inversible M en matrice triangulaire supérieure, en utilisant l'algorithme du pivot de Gauss.

Exemple :

G = gauss(M)
G

array([[ 1,  1,  2, -1],
       [ 0, -1, -3,  3],
       [ 0,  0, -2, -1],
       [ 0,  0,  0, -5]])

2. Matrice échelonnée diagonale

2.1 Exercice : remontée de l'algorithme de Gauss

• Construire une fonction remonte(G) qui transforme une matrice inversible triangulaire supérieure G en matrice diagonale, en utilisant la remontée de l'algorithme du pivot de Gauss.

Exemple :

remonte(G)

array([[-2500,     0,     0,     0],
       [    0,    50,     0,     0],
       [    0,     0,    10,     0],
       [    0,     0,     0,    -5]])

• Construire une fonction diagonale(M) qui transforme une matrice inversible M en matrice diagonale, en utilisant les programmes précédents.

Exemple :

diagonale(M)

array([[-2500,     0,     0,     0],
       [    0,    50,     0,     0],
       [    0,     0,    10,     0],
       [    0,     0,     0,    -5]])

2.2 Bonus : inversion d'une matrice

• Construire une fonction inverse(M) qui calcule l'inverse d'une matrice inversible M, en utilisant la matrice identité et la méthode vue en TD.

Exemple :

inverse(M)

array([[ 4. ,  2. , -2. ,  1. ],
       [-5.6, -2.2,  3. , -1.8],
       [ 0.4, -0.2,  0. ,  0.2],
       [-1.8, -0.6,  1. , -0.4]])