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

\[m_{i 1}=\frac{a_{i 1}^{(1)}}{a_{11}^{(1)}}, \quad i=2,3, \ldots, n,\]

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

\[\begin{aligned} & a_{i j}^{(2)}=a_{i j}^{(1)}-m_{i 1} a_{1 j}^{(1)}, \quad i, j=2, \ldots, n, \\ & b_i^{(2)}=b_i^{(1)}-m_{i 1} b_1^{(1)}, \quad i=2, \ldots, n, \end{aligned}\]

où les \(b_i^{(1)}\) sont les composantes de \(\mathbf{b}^{(1)}\) et on obtient un nouveau système de la forme

\[\left[\begin{array}{cccc} a_{11}^{(1)} & a_{12}^{(1)} & \ldots & a_{1 n}^{(1)} \\ 0 & a_{22}^{(2)} & \ldots & a_{2 n}^{(2)} \\ \vdots & \vdots & & \vdots \\ 0 & a_{n 2}^{(2)} & \ldots & a_{n n}^{(2)} \end{array}\right] \quad\left[\begin{array}{c} x_1 \\ x_2 \\ \vdots \\ x_n \end{array}\right]=\left[\begin{array}{c} b_1^{(1)} \\ b_2^{(2)} \\ \vdots \\ b_n^{(2)} \end{array}\right]\]

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

\[\mathrm{A}^{(k)} \mathbf{x}=\mathbf{b}^{(k)}, \quad 1 \leq k \leq n,\]

où, pour \(k \geq 2\), la matrice \(\mathrm{A}^{(k)}\) est de la forme suivante

\[\mathrm{A}^{(k)}=\left[\begin{array}{cccccc} a_{11}^{(1)} & a_{12}^{(1)} & \ldots & \ldots & \ldots & a_{1 n}^{(1)} \\ 0 & a_{22}^{(2)} & & & & a_{2 n}^{(2)} \\ \vdots & & \ddots & & & \vdots \\ 0 & \ldots & 0 & a_{k k}^{(k)} & \ldots & a_{k n}^{(k)} \\ \vdots & & \vdots & \vdots & & \vdots \\ 0 & \ldots & 0 & a_{n k}^{(k)} & \ldots & a_{n n}^{(k)} \end{array}\right]\]

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

\[\left[\begin{array}{ccccc} a_{11}^{(1)} & a_{12}^{(1)} & \ldots & \ldots & a_{1 n}^{(1)} \\ 0 & a_{22}^{(2)} & & & a_{2 n}^{(2)} \\ \vdots & & \ddots & & \vdots \\ 0 & & & \ddots & \vdots \\ 0 & & & & a_{n n}^{(n)} \end{array}\right] \quad\left[\begin{array}{c} x_1 \\ x_2 \\ \vdots \\ \vdots \\ x_n \end{array}\right]=\left[\begin{array}{c} b_1^{(1)} \\ b_2^{(2)} \\ \vdots \\ \vdots \\ b_n^{(n)} \end{array}\right]\]

Pour être consistant avec les notations introduites précédemment, on note \(U\) la matrice triangulaire supérieure \(\mathrm{A}^{(n)}\).

Définition: Pivots

Les termes \(a_{k k}^{(k)}\) sont appelés pivots et doivent être évidemment non nuls pour \(k=1, \ldots, n-1\).

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}\]
Remarque: coût de la méthode de Gauss

En utilisant les formules élémentaires

\[\sum_{i=1}^n i=\frac{n(n+1)}{2} \quad \text { et } \quad \sum_{i=1}^n i^2=\frac{n(n+1)(2 n+1)}{6},\]

on peut vérifier que pour effectuer l’élimination de Gauss, \(2(n-1) n(n+1) / 3+n(n-1)\) flops sont nécessaires, auxquels il faut ajouter \(n^2\) flops pour la résolution par "remontée" du système triangulaire \(U \mathbf{x}=\mathbf{b}^{(n)}\). Ainsi, environ \(\left(2 n^3 / 3+2 n^2\right)\) flops sont nécessaires pour résoudre le système linéaire en utilisant la méthode de Gauss. En ne conservant que le terme dominant, on peut dire que le procédé d’élimination de Gauss a un coût de \(2 n^3 / 3\) flops.

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

Par exemple, la matrice \(A\) ci-dessous est inversible et ses termes diagonaux sont non nuls

\[\mathrm{A}=\left[\begin{array}{lll} 1 & 2 & 3 \\ 2 & 4 & 5 \\ 7 & 8 & 9 \end{array}\right], \quad \mathrm{A}^{(2)}=\left[\begin{array}{ccc} 1 & 2 & 3 \\ 0 & 0 & -1 \\ 0 & -6 & -12 \end{array}\right]\]

Pourtant, on doit interrompre la méthode de Gauss à la seconde étape car \(a_{22}^{(2)}=0\).

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 :

  1. les matrices à diagonale dominante par ligne;

  2. les matrices à diagonale dominante par colonne;

  3. les matrices symétriques définies positives voir Théorème pour la factorisation de Cholesky de ces matrices.