3.8 Élimination de Gauss-Jordan
À la section précédente, nous avons vu comment caractériser les solutions de\(\mathbf{A}\mathbf{x} = \mathbf{b}\) si \(\mathbf{A}\) est sous FER. En transformant un systèmegénéral d’équations linéaires en un système équivalent ayant la FER, leproblème est résolu. L’élimination de Gauss-Jordan est un algorithme detransformation menant à un système équivalent d’équations linéaires \(\mathbf{R} \mathbf{x} = \mathbf{d}\), où \(\mathbf{R}\) est sous FER, qui n’utilise que des opérationsélémentaires sur les lignes. En langage courant, on dit que la transformationd’une matrice en FER est une réduction.
Rappelons les trois types d’opérations élémentaires permises:
\(L_i \leftarrow \alpha L_i\) (on remplace la \(i\)-ième lignepar le produit de la \(i\)-ième ligne par \(\alpha\), où \(\alpha \neq 0\))
\(L_i \leftarrow L_i + \alpha L_j\) (on remplace la \(i\)-ième ligne parla somme de la \(i\)-ième ligne et du produit de la \(j\)-ième ligne par\(\alpha\), où \(\alpha \neq 0\) et \(i \neq j\))
\(L_i \leftrightarrow L_j\) (on échange ligne \(i\) et ligne\(j\), où \(i \neq j\)).
Soit \(\mathbf{A} = \begin{bmatrix} 1 & -1 & 2 & 1\\ 2 & -2 & 0 & 2 \\ -1 & 3 & 0 & 1 \end{bmatrix}\),\(\mathbf{x} = \begin{bmatrix} x_1\\x_2\\x_3\\x_4\end{bmatrix}\),et \(\mathbf{b} = \begin{bmatrix} 3\\ 1\\ 1\end{bmatrix}\).
La matrice augmentée associée au système \(\mathbf{A}\mathbf{x} = \mathbf{b}\) est\(\left[\begin{array}{cccc|c} 1 & -1 & 2 & 1 & 3 \\ 2 & -2 & 0 & 2 & 1\\ -1 & 3 & 0 & 1 & 1 \end{array}\right].\)Nous la transformons maintenant en matrice sous FER enutilisant les opérations élémentaires sur les lignes.
L’élément de la première ligne se retrouvant dans la première colonne est le pivot de cette ligne. Nous devons donc nousassurer que tout les éléments sous ce pivot soient nuls en utilisant lesopérations élémentaires sur les lignes. Ceci peut être accomplit en appliquant\(L_2 \leftarrow L_2 + (-2)\times L_1\) et\(L_3 \leftarrow L_3 + L_1\). La matrice résultante est\[\left[\begin{array}{cccc|c}1 & -1 & 2 & 1 & 3 \\ 0 & 0 & -4 & 0 & -5\\ 0 & 2 & 2 & 2 & 4\end{array}\right].\]
Notons que l’élément non nul le plus à gauche des deuxième ettroisième lignes sont distincts de \(1\). Nous pouvons obtenir les valeursrequises en appliquant \(L_2 \leftarrow -\frac{1}{4} L_2\) et\(L_3 \leftarrow \frac{1}{2} L_3\). La matrice résultante est\[\left[\begin{array}{cccc|c}1 & -1 & 2 & 1 & 3 \\ 0 & 0 & 1 & 0 & \frac{5}{4}\\ 0 & 1 & 1 & 1 & 2\end{array}\right].\]
Le pivot de la troisième ligne se retrouve à la gauche de celui de la secondeligne. Nous échangerons alors les deux lignes en appliquant \(L_2 \leftrightarrow L_3\)afin d’obtenir\[\left[\begin{array}{cccc|c}1 & -1 & 2 & 1 & 3 \\ 0 & 1 & 1 & 1 & 2 \\ 0 & 0 & 1 & 0 & \frac{5}{4}\end{array}\right].\]
On transforme l’élément au-dessus du pivot de la deuxième ligne en appliquant\(L_1 \leftarrow L_1 + L_2\) afin d’obtenir\[\left[\begin{array}{cccc|c}1 & 0 & 3 & 2 & 5 \\ 0 & 1 & 1 & 1 & 2 \\ 0 & 0 & 1 & 0 & \frac{5}{4}\end{array}\right].\]
Il ne reste qu’à transformer les éléments au-dessus du pivot de la troisièmeligne en appliquant \(L_1 \leftarrow L_1 + (-3)\times L_3\) et \(L_2 \leftarrow L_2 + (-1)\times L_3\) afin d’obtenir\[\left[\begin{array}{cccc|c}1 & 0 & 0 & 2 & \frac{5}{4} \\ 0 & 1 & 0 & 1 & \frac{3}{4}\\ 0 & 0 & 1 & 0 & \frac{5}{4}\end{array}\right].\]Cette matrice est sous FER. Les variables correspondantes aux trois premièrescolonnes sont des variables pivots. Une des solutions de \(\mathbf{A}\mathbf{x} = \mathbf{b}\) est alors donnée par \(\mathbf{x} = \begin{bmatrix} 5/4 \\ 3/4 \\ 5/4 \\ 0\end{bmatrix}\).On obtient toutes les solutions en posant \(x_4 = s\) (la seule variable libre)et en résolvant ensuite pour les variables pivots \(x_1,x_2,x_3\) en terme duparamètre \(s\). Les solutions prennent alors la forme\(\mathbf{x} = \begin{bmatrix} \frac{5}{4} - 2s\\ \frac{3}{4} - s \\ \frac{5}{4} \\ s\end{bmatrix}\), pour \(s \in \mathbb{R}\).
Remarque: La FER d’une matrice est unique. Indépendamment de la séquencedes opérations élémentaires utilisées, le résultat final est toujours le même.
3.8.1 Pseudo-code
II est possible de codifier la procédure. Voici le pseudo-code pourl’implémentation de la réduction d’une matrice \(\mathbf{A}\) de dimension \(m \times n\) :
- poser \(p = 1\)
pour \(k = 1,\ldots, n\), alors
s’il existe \(i \in \{p,\ldots,m\}\) tel que \(a_{ik} \neq 0,\)alors
- si \(i \neq p\), échanger la \(p\)-ième ligne et la \(i\)-ième ligne
- appliquer \(L_p \leftarrow \alpha^{-1} L_p\), où\(\alpha\) est l’élément de la colonne \(k\) de la ligne \(p\)
- appliquer \(L_q \leftarrow L_q - \alpha_{q}L_R\) pour tout\(q \neq p\), où \(\alpha_q\) est l’élément de la colonne \(k\)de la \(q\)-ième ligne
- \(p = p+1\)
- arrêter lorsque \(p > m\)
Exercices
Transformer chacune des matrices suivantes en FER en utilisant lesopérations élémentaires sur les lignes.
\(\begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0\end{bmatrix}\)
\(\begin{bmatrix} 0 & 2 & 2 & 0 \\ 0 & -1 & 0 & 1 \\ 0 & 1 & 2 & 1 \end{bmatrix}\)
Déterminez tous les nombres réels \(x, y, z\) satisfaisant au systèmed’équations linéaires\[\begin{align*}3 x - 2y - z & = 1 \\2z + x - y & = 5 \end{align*}\]
Soit \(\mathbf{A}\in \mathbb{K}^{m\times n}\), \(\mathbb{K}\) un corps.Démontrez l’unicité de la FER de \(\mathbf{A}\).
Solutions
Notons que\[\begin{align*}& \begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0\end{bmatrix} \\\xrightarrow{L_1 \leftrightarrow L_3}~ &\begin{bmatrix} 1 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0\end{bmatrix} \\\xrightarrow{L_2 \leftrightarrow L_3}~&\begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1\end{bmatrix} \\\end{align*}\]
Notons que\[\begin{eqnarray*} & \begin{bmatrix} 0 & 2 & 2 & 0 \\ 0 & -1 & 0 & 1 \\ 0 & 1 & 2 & 1 \end{bmatrix} \\\xrightarrow{L_1 \leftrightarrow L_3}~& \begin{bmatrix} 0 & 1 & 2 & 1 \\ 0 & -1 & 0 & 1 \\0 & 2 & 2 & 0 \end{bmatrix} \\\xrightarrow{L_2 \leftarrow L_2 + L_1}~& \begin{bmatrix} 0 & 1 & 2 & 1 \\ 0 & 0 & 2 & 2 \\0 & 2 & 2 & 0 \end{bmatrix} \\\xrightarrow{L_3 \leftarrow L_3 - 2L_1}~& \begin{bmatrix} 0 & 1 & 2 & 1 \\ 0 & 0 & 2 & 2 \\0 & 0 & -2 & -2 \end{bmatrix} \\\xrightarrow{L_3 \leftarrow L_3 + L_2}~& \begin{bmatrix} 0 & 1 & 2 & 1 \\ 0 & 0 & 2 & 2 \\0 & 0 & 0 & 0 \end{bmatrix} \\\xrightarrow{L_2 \leftarrow \frac{1}{2}L_2}~& \begin{bmatrix} 0 & 1 & 2 & 1 \\ 0 & 0 & 1 & 1 \\0 & 0 & 0 & 0 \end{bmatrix} \\\xrightarrow{L_1 \leftarrow L_1 -2 L_2}~& \begin{bmatrix} 0 & 1 & 0 & -1 \\ 0 & 0 & 1 & 1 \\0 & 0 & 0 & 0 \end{bmatrix} \\\end{eqnarray*}\]
Ce système peut s’écrire sous la forme\(\begin{bmatrix} 3 & -2 & -1 \\ 1 & -1 & 2 \end{bmatrix} \begin{bmatrix} x\\ y\\ z \end{bmatrix} = \begin{bmatrix} 1\\ 5 \end{bmatrix}.\) (Faites attention. Lesvariables de la deuxième équation sont données de façon désordonnée dans laquestion.) La matrice augmentée du système est\[\left[\begin{array}{rrr|r}3 & -2 & -1 & 1\\1 & -1 & 2 & 5\end{array}.\right]\]
L’application de \(L_1 \leftrightarrow L_2\) donne\[\left[\begin{array}{rrr|r}1 & -1 & 2 & 5 \\3 & -2 & -1 & 1 \end{array}\right].\]
L’application de \(L_2 \leftarrow L_2 - 3 L_1\) donne\[\left[\begin{array}{rrr|r}1 & -1 & 2 & 5 \\0 & 1 & -7 & -14\end{array}\right].\]
L’application de \(L_1 \leftarrow L_1 + L_2\) donne\[\left[\begin{array}{rrr|r}1 & 0 & -5 & -9 \\0 & 1 & -7 & -14\end{array}\right].\]
Ainsi, \(z\) est la seule variable libre.En prenant \(z = s\), la deuxième ligne devient \(y - 7s = -14\)et la première ligne devient \(x - 5s = -9\).Donc, les solutions sont \(\begin{bmatrix} x\\y\\z \end{bmatrix} = \begin{bmatrix} -9 + 5s \\ -14 + 7s \\ s\end{bmatrix}\)pour \(s \in \mathbb{R}\).
Ce résultat signifie que l’on peut parler de la forme échelonnée réduitede \(\mathbf{A}\).
Supposons que \(\mathbf{A}\) puisse être transformée en deux matrices en FER\(\mathbf{B}\) et \(\mathbf{C}\) en appliquant différentes suites d’opérationsélémentaires sur les lignes. Nous voulons montrer que \(\mathbf{B} = \mathbf{C}\).
Premièrement, notons que les systèmes \(\mathbf{B}\mathbf{x} = \mathbf{0}\)et \(\mathbf{C}\mathbf{x} = \mathbf{0}\) doivent avoir les mêmes solutions que\(\mathbf{A}\mathbf{x} = \mathbf{0}\).
Soit \(i\) le plus petit indice tel que \(\mathbf{B}\) et \(\mathbf{C}\)diffèrent à la \(i\)-ième colonne.Parce que \(\mathbf{B}\) et \(\mathbf{C}\) sont en FER,\(\mathbf{B}_i\) (colonne \(i\) de \(\mathbf{B}\)) et \(\mathbf{C}_i\) ne peuvent être tous lesdeux des colonnes pivots. Sans perte de généralité, on suppose que\(\mathbf{C}_i\) n’est pas une colonne pivot.Donc, \(x_i\) est une variable libre pour \(\mathbf{C}\mathbf{x} = \mathbf{0}\).En résolvant pour \(\mathbf{x}\) dans \(\mathbf{C}\mathbf{x} = \mathbf{0}\) (après avoirfixé \(x_i = 1\)) et toutes les autres variables libres par \(0\),on obtient une solution \(\mathbf{x}'\) telle que \(x'_i = 1\) et \(x'_j = 0\)pour tout \(j > i\).Puisque \(\mathbf{C}\mathbf{x}' = \mathbf{0}\) et \(\mathbf{B}_j = \mathbf{C}_j\)pour \(j = 1,\ldots,i-1\), on obtient\[\begin{align*}\mathbf{B}\mathbf{x}' & = \mathbf{B}\mathbf{x}' - \mathbf{C}\mathbf{x}' \\& = \sum_{j=1}^n \mathbf{B}_jx'_j-\sum_{j=1}^n \mathbf{C}_jx'_j \\& = \sum_{j=1}^n (\mathbf{B}_j-\mathbf{C}_j)x'_j \\& = \sum_{j=1}^i (\mathbf{B}_j-\mathbf{C}_j)x'_j \\& = (\mathbf{B}_i - \mathbf{C}_i)x'_i \\& = \mathbf{B}_i - \mathbf{C}_i \neq \mathbf{0}.\end{align*}\]Ainsi, \(\mathbf{x}'\) n’est pas une solution de \(\mathbf{B}\mathbf{x} = \mathbf{0}\),ce qui contredit que \(\mathbf{B}\mathbf{x} = \mathbf{0}\) et \(\mathbf{C}\mathbf{x} = \mathbf{0}\)ont les mêmes solutions.
