Élimination de Gauss-Jordan
De Wikipedia, l'encyclopédie encyclopedia
Pour les articles homonymes, voir Pivot.
En mathématiques, plus précisément en algèbre linéaire, l'élimination de Gauss-Jordan, aussi appelée méthode du pivot de Gauss, nommée en hommage à Carl Friedrich Gauss et Wilhelm Jordan, est un algorithme pour déterminer les solutions d'un système d'équations linéaires, pour déterminer le rang d'une matrice ou pour calculer l'inverse d'une matrice (carrée) inversible. Lorsqu'on applique l'élimination de Gauss à une matrice, on obtient sa forme échelonnée réduite.
Cette méthode est connue des mathématiciens chinois depuis au moins le Ier siècle de notre ère. Elle est référencée dans le livre chinois Jiuzhang suanshu (Les Neuf Chapitres sur l'art mathématique), dont elle constitue le huitième chapitre, sous le titre « Fang cheng » (la disposition rectangulaire). La méthode est présentée au moyen de dix-huit exercices. Dans son commentaire daté de 263, Liu Hui en attribue la paternité à Chang Ts'ang, chancelier de l'empereur de Chine au IIe siècle avant notre ère.
En Europe, cette méthode a été découverte et présentée sous forme moderne au XIXe siècle. En 1810, Carl Friedrich Gauss présente sa méthode des moindres carrés dans un livre étudiant le mouvement de l'astéroïde Pallas[1]. Dans l'article 13 de ce livre, il décrit une méthode générale de résolution de système d'équations linéaires qui constitue l'essentiel de la méthode du pivot. En 1888, Wilhelm Jordan publie un livre de géodésie précisant comment utiliser cette méthode et adoptant une notation un peu différente[2]. C'est grâce à ce dernier livre que cette méthode se diffusa dans tout l'Occident[3]. Elle est aujourd'hui connue sous le nom d'élimination de Gauss-Jordan ou méthode du pivot de Gauss.
Opérations
L'algorithme de Gauss-Jordan produit la matrice échelonnée réduite d'une matrice à l'aide d'opérations élémentaires sur les lignes. Trois types d'opérations élémentaires sont utilisées :
- Échange de deux lignes ;
- Multiplication d'une ligne par un scalaire non nul ;
- Ajout du multiple d'une ligne à une autre ligne.
Pseudocode
Soit une matrice A de dimensions n × m ;
L'algorithme de Gauss-Jordan est le suivant[4] :
Gauss-Jordan r = 0 (r est l'indice de ligne du dernier pivot trouvé) Pour j de 1 jusqu'à m (j décrit tous les indices de colonnes) | Rechercher max(|A[i,j]|, r+1 ≤ i ≤ n). Noter k l'indice de ligne du maximum | (A[k,j] est le pivot) | Si A[k,j]≠0 alors (A[k,j] désigne la valeur de la ligne k et de la colonne j) | | r=r+1 (r désigne l'indice de la future ligne servant de pivot) | | Diviser la ligne k par A[k,j] (On normalise la ligne de pivot de façon que le pivot prenne la valeur 1) | | Si k≠r alors | | | Échanger les lignes k et r (On place la ligne du pivot en position r) | | Fin Si | | Pour i de 1 jusqu'à n (On simplifie les autres lignes) | | | Si i≠r alors | | | | Soustraire à la ligne i la ligne r multipliée par A[i,j] (de façon à annuler A[i,j]) | | | Fin Si | | Fin Pour | Fin Si Fin Pour Fin Gauss-Jordan
Exemple.
On part de la matrice
Il s'agit d'une matrice réelle, donc le module d'un coefficient est sa valeur absolue.
- Première itération, j = 1 (et r = 0) :
- étape 1.1 : on cherche dans la première colonne de la matrice la valeur maximale des valeurs absolues des coefficients. Elle vaut 2, située en (1, 1), de sorte que k = 1,
- étape 1.2.1 : r = 1,
- étape 1.2.2 : r = k, il n'y a pas d'échange,
- étape 1.2.3 : on divise la ligne 1 par A(1, 1) = 2, soit ,
- étape 1.2.4 :
- ligne i = 2, on a A(2, 1) = -1 ; on calcule
, - ligne i = 3, on a A(3, 1) = 0, la ligne n'est donc pas modifiée,
- ligne i = 2, on a A(2, 1) = -1 ; on calcule
- la matrice est alors
;
- deuxième itération, j = 2 (et r = 1) :
- étape 2.1 : on cherche dans les lignes 2 à 3 de la deuxième colonne la valeur maximale en valeur absolue. Il s'agit de 3/2, situé en (2, 2),
- étape 2.2.1 : r = 2,
- étape 2.2.2 : r = k, il n'y a pas d'échange.
- étape 2.2.3 : on divise la ligne 2 par A'(2, 2) = 3/2, soit ,
- étape 2.2.4 :
- ligne i = 1, on a A'(1, 2) = -1/2 ; on calcule
, - ligne i = 3, on a A'(3, 2) = -1 ; on calcule
,
- ligne i = 1, on a A'(1, 2) = -1/2 ; on calcule
- la matrice est alors
;
- troisième itération, j = 3 (et r = 2) :
- étape 3.1 : le pivot de la troisième colonne, troisième ligne est 4/3. Donc k = 3
- étape 3.2.1 : r = k,
- étape 3.2.2 : il n'y a aucune ligne à permuter,
- étape 3.2.3 : on divise la ligne 3 par A''(3, 3) = 4/3, elle devient
- étape 3.2.4 :
- ligne i = 1, on a A''(1, 3) = -1/3. La dernière étape annule ce coefficient.
- ligne i = 2, on a A''(2, 3) = -2/3. La dernière étape annule ce coefficient.
- la matrice est alors
qui est réduite échelonnée.
Stabilité numérique
La première section de l'algorithme, soit l'échange de ligne avec la valeur de pivot la plus grande, a pour but d'améliorer la stabilité numérique de l'algorithme. Cette étape tente de minimiser les erreurs d'arrondis cumulatives causant de l'instabilité numérique. Cette stratégie permet en général de remédier à cette instabilité, même si on peut donner des contre-exemples[5].
Complexité algorithmique
La complexité algorithmique asymptotique de l'élimination de Gauss est O(n3) (notations de Landau) : n×n est la taille de la matrice et le nombre d'instructions à réaliser est proportionnel à n3. Cet algorithme peut être utilisé sur un ordinateur pour des systèmes avec des milliers d'inconnues et d'équations[réf. nécessaire]. Cependant, l'algorithme de Strassen, qui est en O(n2,807) a une meilleure complexité algorithmique asymptotique.
La complexité algorithmique du pivot de Gauss reste O(n3) quand la matrice est creuse. En effet, prenons une matrice n×n dont seulement k n entrées sont non nulles mais dont les entrées sont régulièrement réparties sur les lignes et les colonnes, alors au cours de l'algorithme du pivot de Gauss le nombre moyen de valeurs non nulles sur une ligne passera de k à 2k puis 3k jusqu'à n. On trouve donc que le nombre d'instructions est de l'ordre de n n (n-1)/2.
L'élimination de Gauss-Jordan peut être utilisée pour inverser une matrice carrée si celle-ci est inversible. Pour cela, on crée une matrice à n lignes et 2n colonnes en bordant la matrice A par la matrice identité In, ce qui génère une matrice augmentée (en) notée [ A | I ]. Si la matrice d'entrée est inversible, on applique l'algorithme de Gauss-Jordan à la matrice augmentée. La matrice finale est de la forme [ I | A−1 ] et contient l'inverse de la matrice initiale dans sa section de droite.
Exemple
Admettons la matrice suivante:
Pour trouver l'inverse de cette matrice, il faut générer la matrice augmentée [ A | I ] comme suit:
En appliquant l'algorithme de Gauss-Jordan, on obtient la matrice augmentée sous sa forme échelonnée réduite suivante:
Comme précédemment, le premier pivot est sur la première ligne. À l'étape 2.2.3, la première ligne devient
L'étape 2.2.4 devient :
- ligne i = 2, on a A(2, 1) = -1 ; on calcule
; - ligne i = 3, on a A(3, 1) = 0, la ligne n'est pas modifiée.
On a donc
Pour la deuxième itération, on permute les lignes 2 et 3, et on divise la nouvelle ligne 2 par 2, soit à l'étape 2.2.3 :
À l'étape 2.2.4 :
- ligne i = 1, on a A(1, 3) = 0, la ligne n'est pas modifiée ;
- ligne i = 3, on a A(3, 3) = -1 ; on calcule
;
On a donc
Pour la troisième itération, on divise la ligne 3 par 1, la matrice est inchangée à l'étape 2.2.3.
À l'étape 2.2.4 :
- ligne i = 1, on a A(1, 2) = -1/2 ; on calcule
; - ligne i = 2, on a A(2, 2) = -1/2 ; on calcule
;
On a donc
- .
Une dernière permutation des lignes 2 et 3 nous donne
- .
La section gauche de la matrice est la matrice identité, ce qui démontre que A est inversible. La section 3x3 de droite, soit la matrice B, est l'inverse de A.
Cas général
Effectuer une opération élémentaire O sur les n lignes d'une matrice revient à la multiplier à gauche par la matrice élémentaire (inversible) Gs := O(In).
En notant O1, …, Os les opérations élémentaires que l'on effectue sur A, et Gs = Os(In) les matrices élémentaires associées, on aboutit donc, dans la section de gauche, à la matrice
et dans celle de droite, à la matrice
Ainsi, B est inversible et BA = In, donc B−1 = A et A−1 = B.