Méthode d’élimination de Gauss
La méthode d’élimination de Gauss (MEG) a pour but de transformer le système \(A \mathbf{x}=\mathbf{b}\) en un système équivalent (c’est-à-dire ayant la même solution) de la forme \(U \mathbf{x}=\widehat{b}\), où \(U\) est une matrice triangulaire supérieure et \(\widehat{b}\) est un second membre convenablement modifié. Ce dernier système peut être alors résolu par une méthode de substitution rétrograde.
Au cours de la transformation, on utilise essentiellement la propriété selon laquelle on ne change pas la solution du système quand on ajoute à une équation donnée une combinaison linéaire des autres équations.
Considérons une matrice inversible \(\mathrm{A} \in \mathbb{R}^{n \times n}\) dont le terme diagonal \(a_{11}\) est supposé non nul. On pose \(\mathrm{A}^{(1)}=\mathrm{A}\) et \(\mathbf{b}^{(1)}=\mathbf{b}\). On introduit le multiplicateur
où les \(a_{i j}^{(1)}\) désignent les éléments de \(\mathrm{A}^{(1)}\). On peut éliminer l’inconnue \(x_1\) des lignes \(i=2, \ldots, n\) en leur retranchant \(m_{i 1}\) fois la première ligne et en faisant de même pour le membre de droite. On définit alors
où les \(b_i^{(1)}\) sont les composantes de \(\mathbf{b}^{(1)}\) et on obtient un nouveau système de la forme
que l’on note \(\mathrm{A}^{(2)} \mathbf{x}=\mathbf{b}^{(2)}\) et qui est équivalent au système de départ.
On peut à nouveau transformer ce système de façon à éliminer l’inconnue \(x_2\) des lignes \(3, \ldots, n\). En poursuivant ainsi, on obtient une suite finie de systèmes
où, pour \(k \geq 2\), la matrice \(\mathrm{A}^{(k)}\) est de la forme suivante
où on a supposé \(a_{i i}^{(i)} \neq 0\) pour \(i=1, \ldots, k-1\). Il est clair que pour \(k=n\) on obtient alors le système triangulaire supérieur \(\mathrm{A}^{(n)} \mathbf{X}=\mathbf{b}^{(n)}\) suivant
Pour être consistant avec les notations introduites précédemment, on note \(U\) la matrice triangulaire supérieure \(\mathrm{A}^{(n)}\).
- Explicitons les formules de la MEG permettant de passer du \(k\)-ième système au \(k+1\)-ième
-
pour \(k=1, \ldots, n-1\), on suppose que \(a_{k k}^{(k)} \neq 0\) et on définit le multiplicateur
\[m_{i k}=\frac{a_{i k}^{(k)}}{a_{k k}^{(k)}}, \quad i=k+1, \ldots, n .\]On pose ensuite
\[\begin{array}{ll} a_{i j}^{(k+1)}=a_{i j}^{(k)}-m_{i k} a_{k j}^{(k)}, & i, j=k+1, \ldots, n, \\ b_i^{(k+1)}=b_i^{(k)}-m_{i k} b_k^{(k)}, & i=k+1, \ldots, n . \end{array}\]
Comme indiqué précédemment, la méthode de Gauss n’est correctement définie que si les pivots \(a_{k k}^{(k)}\) sont différents de zéro pour \(k=1, \ldots, n-1\).
Malheureusement, le fait que les termes diagonaux de \(A\) soient non nuls ne suffit pas à empêcher l’apparition de pivots nuls durant la phase d’élimination.
Exemple
Des conditions plus restrictives sur \(A\) sont donc nécessaires pour assurer que la méthode s’applique bien. |
Nous verrons à la Section que si les mineurs principaux \(d_i\) de A sont non nuls pour \(i=1, \ldots, n-1\) alors les pivots correspondants \(a_{i i}^{(i)}\) sont également non nuls (rappelons que \(d_i\) est le déterminant de la \(i\)-ième sous-matrice principale \(\mathrm{A}_i\), i.e. la sous-matrice constituée des \(i\) premières lignes et colonnes de A). La matrice de l’exemple précédent ne satisfait pas cette condition puisque \(d_1=1\) et \(d_2=0\). |
Il existe des catégories de matrices pour lesquelles la méthode de Gauss peut être utilisée sans risque dans sa forme de base. Parmi ces matrices, citons les suivantes :
-
les matrices à diagonale dominante par ligne;
-
les matrices à diagonale dominante par colonne;
-
les matrices symétriques définies positives voir Théorème pour la factorisation de Cholesky de ces matrices.