1.5 Matrices et algorithme de Gauss

On comprend que la méthode illustrée sur l'exemple précédent, appelée algorithme de Gauss, s'applique à des systèmes de tailles quelconques. Il consiste à utiliser des opérations élémentaires qui font progressivement apparaître des zéros dans la partie inférieure gauche de la matrice.

Nous verrons d'autres exemples plus loin, mais arrêtons-nous un instant pour introduire une certaine simplification d'écriture.

Matrices associées à un système

Les opérations élémentaires que l'on effectue sur un système général du type \[ (*) \left\{ \begin{array}{ccccccccc} a_{11}x_1&+&a_{12}x_2&+&\cdots&+&a_{1n}x_n&=&b_1\\ a_{21}x_1&+&a_{22}x_2&+&\cdots&+&a_{2n}x_n&=&b_2\\ \vdots&&&&&&&\vdots&\\ a_{m1}x_1&+&a_{m2}x_2&+&\cdots&+&a_{mn}x_n&=&b_m \end{array} \right. \,, \] agissent sur les coefficients \(a_{ij}\), et sur les termes du second membre, les \(b_i\). Dans ces opérations, le nom que l'on donne aux variables (jusqu'à présent: \(x_1,\dots,x_n\)) n'a pas d'importance. Il est donc utile de simplifier la manipulation des systèmes en ne gardant que la structure numérique des coefficients et du second membre.

Soit \((*)\) le système ci-dessus.
  1. La matrice associée à \((*)\) est le tableau de \(m\times n\) nombres défini par \[ \begin{pmatrix} a_{11}&a_{12}&\cdots&a_{1n}\\ a_{21}&a_{22}&\cdots&a_{2n}\\ \vdots&\vdots&&\vdots\\ a_{m1}&a_{m2}&\cdots&a_{mn} \end{pmatrix} \]
  2. La matrice augmentée associée à \((*)\) est le tableau de \(m\times (n+1)\) nombres défini par \[ \left( \begin{array}{cccc|c} a_{11}&a_{12}&\cdots&a_{1n}&b_1\\ a_{21}&a_{22}&\cdots&a_{2n}&b_2\\ \vdots&\vdots&&\vdots &\vdots \\ a_{m1}&a_{m2}&\cdots&a_{mn}&b_m \end{array} \right) \] (La ligne verticale, qui sépare les \(a_{kn}\) des \(b_k\), est là pour rappeler que la dernière colonne doit être interprétée comme le second membre dans \((*)\).)

Exemple: La matrice augmentée du système \[ \left\{ \begin{array}{ccccccccc} -x_1 &+& x_2 && &+& x_4 &=& \alpha\\ x_1 && &+& x_3 &+& 7x_4 &=& \beta\\ && x_2 &-& x_3 &+& x_4 &=& \gamma \end{array} \right. \] est donnée par \[ \left( \begin{array}{cccc|c} -1&1&0&1&\alpha\\ 1&0&1&7&\beta\\ 0&1&-1&1&\gamma \end{array} \right) \]

Opérations élémentaires sur les matrices

Il est clair que les opérations élémentaires (de Type I,II,III) que l'on effectue sur un système se traduisent naturellement en des opérations sur les lignes de la matrice et de la matrice augmentée associée.

De manière générale, on peut effectuer des opérations élémentaires sur une matrice sans se référer au système dont elle est issue. On peut donc définir deux matrices comme étant équivalentes selon les lignes (ou ligne-équivalentes) si l'une peut s'obtenir à partir de l'autre par un nombre fini d'opérations élémentaires.

Matrices échelonnées

L'algorithme de Gauss mène, en général, à une matrice qui est ce que nous appelions ''aussi triangulaire que possible''; définissons ce terme précisément.

Pour une matrice \(m\times n\) quelconque,
  1. Le coefficient principal de la \(i\)-ème ligne est, s'il y en a un, le premier coefficient non-nul trouvé, en partant de la gauche.
  2. Une matrice est échelonnée si les deux conditions suivantes sont satisfaites:
    • Si elle possède des lignes nulles (c'est-à-dire ne contenant que des coefficients nuls), alors celles-ci sont toutes dans la partie inférieure de la matrice.
    • Si elle possède des lignes non-nulles, alors le coefficient principal de chacune de ces lignes se trouve strictement à droite du coefficient principal de la ligne du dessus.

Exemple: La matrice \[ \left( \begin{array}{cccc|c} {\color{blue}3}&1&2&0&7\\ 0&0&{\color{blue}4}&3&-1\\ 0&0&0&{\color{blue}-\frac12}&0\\ 0&0&0&0&0 \end{array} \right) \] est échelonnée. En effet, la seule ligne ne contenant que des zéros est tout en bas, et sur chacune des autres lignes, le coefficient principal est strictement à droite du coefficient principal de la ligne du dessus: \({\color{blue}-\frac12}\) (coefficient principal de la troisième ligne) est à droite de \({\color{blue}4}\) (coefficient principal de la deuxième ligne), qui est lui-même à droite de \({\color{blue}3}\) (coefficient principal de la première ligne).

Exemple: La matrice \[ \begin{pmatrix} 1&2&3&4\\ 0&0&1&2\\ 0&0&-1&0 \end{pmatrix} \] n'est pas échelonnée, car le coefficient principal de la troisième ligne est juste sous le (et non strictement à droite du) coefficient principal de la deuxième ligne.

Théorème: Toute matrice peut être transformée, à l'aide d'un nombre fini de transformations élémentaires, en une matrice échelonnée. (En d'autres termes: toute matrice est équivalente selon les lignes à une matrice échelonnée.)

La méthode utilisée dans les exemples traités plus haut se généralise sans difficulté à n'importe quelle matrice.

Exemple: Considérons la matrice augmentée du système vu plus haut: \[ \left( \begin{array}{ccc|c} 3&5&4&1\\ 6&12&6&0\\ -2&-2&-7&5 \end{array} \right). \] En appliquant successivement les opérations élémentaires \[ L_2\leftarrow \tfrac16 L_2 \,,\quad L_1\leftrightarrow L_2 \,,\quad L_2\leftarrow L_2-3 L_1 \,,\\ L_3\leftarrow L_3+2L_1 \,,\quad L_3\leftarrow L_3+2L_2\,, \] on obtient comme on a vu la matrice \[ \left( \begin{array}{ccc|c} 1&2&1&0\\ 0&-1&1&1\\ 0&0&-3&7 \end{array} \right)\,, \] qui est échelonnée.

Remarque: La matrice échelonnée obtenue dépend du choix des opérations élémentaires faites en chemin! Par exemple, en partant de \[ \begin{pmatrix} 1&1&1\\ 1&1&3 \end{pmatrix}\,, \] alors en faisant \(L_2\leftarrow L_2-L_1\) on obtient une première échelonnée \[ \begin{pmatrix} {\color{blue}1}&1&1\\ 0&0&{\color{blue}2} \end{pmatrix}\,, \] mais en faisant \(L_1\leftrightarrow L_2\) suivie de \(L_2\leftarrow L_2-L_1\) on obtient \[ \begin{pmatrix} {\color{blue}1}&1&3\\ 0&0&{\color{blue}-2} \end{pmatrix}\,, \] qui est une autre forme échelonnée. Donc une matrice peut posséder plusieurs formes échelonnées.

Concrètement, dans la transformation d'un système à l'aide d'opérations élémentaires, c'est une fois que la matrice obtenue est échelonnée que l'on peut déjà savoir si le système est compatible, si oui identifier les variables libres, et exprimer l'ensemble des solutions. Voyons un exemple assez complet:

Exemple: Supposons que l'on parte du système \[ (*) \left\{ \begin{array}{ccccccccc} 3x_1 &+& x_2 &+& 2x_3 && &=&7 \\ 6x_1 &+& 2x_2 &+& 12x_3 &+& 7x_4 &=&12 \\ 6x_1 &+& 2x_2 &+& 8x_3 &+& 4x_4 &=&13 \\ 3x_1 &+& x_2 &+& 6x_3 &+& 4x_4 &=&6 \end{array} \right.\,, \] dont la matrice augmentée est \[ \left( \begin{array}{cccc|c} 3&1&2&0&7\\ 6&2&12&7&12\\ 6&2&8&4&13\\ 3&1&6&4&6 \end{array} \right) \] Faisons d'abord apparaître des zéros dans la première colonne, en appliquant successivement \(L_2\leftarrow L_2-2L_1\), \(L_3\leftarrow L_3-2L_1\), \(L_4\leftarrow L_4-L_1\): \[ \left( \begin{array}{cccc|c} 3&1&2&0&7\\ 0&0&8&7&-2\\ 0&0&4&4&-1\\ 0&0&4&4&-1 \end{array} \right) \] Comme les deux dernières lignes sont égales, on peut faire \(L_4\leftarrow L_4-L_3\): \[ \left( \begin{array}{cccc|c} 3&1&2&0&7\\ 0&0&8&7&-2\\ 0&0&4&4&-1\\ 0&0&0&0&0 \end{array} \right) \] Ensuite, \(L_2\leftarrow L_2-2L_3\), suivie de \(L_2\leftrightarrow L_3\), nous donne une version échelonnée: \[ \left( \begin{array}{cccc|c} {\color{blue}3}&1&2&0&7\\ 0&0&{\color{blue}4}&4&-1\\ 0&0&0&{\color{blue}-1}&0\\ 0&0&0&0&0 \end{array} \right) \] Comment poursuivre, pour obtenir \(S_{(*)}\)? Pour y voir plus clair, revenons au système correspondant à cette dernière matrice augmentée: \[ (*)' \left\{ \begin{array}{ccccccccc} 3x_1 &+& x_2 &+& 2x_3 &+&{\color{red}0x_4} &=&7 \\ {\color{red}0x_1} &+& {\color{red}0x_2} &+& 4x_3 &+& 4x_4 &=&-1\\ {\color{red}0x_1} &+& {\color{red}0x_2} &+&{\color{red}0x_3} &-& x_4 &=&0 \\ {\color{red}0x_1} &+& {\color{red}0x_2} &+&{\color{red}0x_3} &+&{\color{red}0x_4} &=&0 \end{array} \right.\,, \] que l'on peut écrire plus simplement comme \[ (*)' \left\{ \begin{array}{cccccccccc} 3x_1 &+& x_2 &+& 2x_3 && &=&7 \\ && && 4x_3 &+& 4x_4 &=&-1\\ && && &-& x_4 &=&0 \end{array} \right.\,. \] On a supprimé la dernière ligne ''\({\color{red}0x_1} + {\color{red}0x_2} +{\color{red}0x_3} +{\color{red}0x_4} =0\)''. En effet, cette contrainte n'en est pas une, puisqu'elle est satisfaite par n'importe quel quadruplet \((x_1,x_2,x_3,x_4)\).

On observe maintenant que la variable \(x_2=t\) est libre, puisqu'on peut la passer du côté droit pour obtenir un système triangulaire en \((x_1,x_3,x_4)\), qui sont les variables de base: \[ (*)' \left\{ \begin{array}{cccccccc} 3x_1 &+& 2x_3 && &=&7-t \\ && 4x_3 &+& 4x_4 &=&-1\\ && &-& x_4 &=&0 \end{array} \right.\,. \] Maintenant, en procédant ''de bas en haut'', on obtient \[ x_4=0\,,\qquad x_3=-\tfrac{1}{4}\,, \qquad x_1=\frac{15-2t}{6}\,, \] et donc: \[ S_{(*)}=S_{(*)'}=\bigl\{ (\tfrac{15-2t}{6},t,-\tfrac14,0)\,:\,t\in\mathbb{R} \bigr\} \] Le système est donc compatible, et possède une infinité de solutions.

Exemple: Considérons le système \[ (*) \left\{ \begin{array}{ccccccc} x_1 &+& x_2 &-& x_3 &=&5 \\ 3x_1 &+& 4x_2 && &=&4 \\ 4x_1 &+& 5x_2 &-& x_3 &=&7 \end{array} \right. \] Après échelonnage, sa matrice devient \[ \left( \begin{array}{ccc|c} 1&1&-1&5\\ 0&1&3&-11\\ 0&0&0&-3 \end{array} \right). \] Le système correspondant est \[ (*)' \left\{ \begin{array}{ccccccc} x_1 &+& x_2 &-& x_3 &=&5 \\ {\color{red}0x_1} &+ & x_2 &+& 3x_3 &=&-11 \\ {\color{red}0x_1} &+& {\color{red}0x_2} &+& {\color{red}0x_3} &=&-3 \end{array} \right.\,, \] qui est incompatible, puisque la dernière contrainte ne peut jamais être satisfaite, quel que soit \((x_1,x_2,x_3)\). Donc \((*)\) est aussi incompatible.

La réduite de Gauss
Une matrice est échelonnée réduite si elle est échelonnée et si, de plus, Les coefficients principaux d'une matrice échelonnée réduite sont appelés pivots.

Exemple: La matrice \[ \begin{pmatrix} 0&{\color{blue}1}&{\color{magenta}0}&3&8&{\color{magenta}0}&1&{\color{magenta}0}&2\\ 0&{\color{magenta}0}&{\color{blue}1}&5&9&{\color{magenta}0}&2&{\color{magenta}0}&1\\ 0&{\color{magenta}0}&{\color{magenta}0}&0&0&{\color{blue}1}&3&{\color{magenta}0}&6\\ 0&{\color{magenta}0}&{\color{magenta}0}&0&0&{\color{magenta}0}&0&{\color{blue}1}&5\\ 0&{\color{magenta}0}&{\color{magenta}0}&0&0&{\color{magenta}0}&0&{\color{magenta}0}&{0} \end{pmatrix} \] est échelonnée réduite (les pivots sont indiqués en bleu).

Voyons comment obtenir une échelonnée réduite d'une matrice. Une fois encore, la méthode présentée dans cet exemple particulier montre comment procéder en général:

Exemple: Considérons encore une fois la matrice du premier exemple de cette section: \[ \left( \begin{array}{ccc|c} 3&5&4&1\\ 6&12&6&0\\ -2&-2&-7&5 \end{array} \right)\,. \] Pour obtenir sa réduite, on commence par l'échelonner, comme vu plus haut: \[ \left( \begin{array}{ccc|c} 1&2&1&0\\ {\color{magenta}0}&-1&1&1\\ {\color{magenta}0}&{\color{magenta}0}&-3&7 \end{array} \right)\,. \] On poursuit en rendant tous les coefficients principaux égaux à \(1\), à l'aide de \(L_2\leftarrow (-1)L_2\) et \(L_3\leftarrow \frac{1}{-3}L_3\): \[ \left( \begin{array}{ccc|c} {\color{blue}1}&2&1&0\\ {\color{magenta}0}&{\color{blue}1}&-1&-1\\ {\color{magenta}0}&{\color{magenta}0}&{\color{blue}1}&-7/3 \end{array} \right)\,, \] Remarquons que maintenant, lorsqu'on additionne un multiple d'une ligne \(L_i\) à une ligne \(L_j\) située au-dessus, la présence de zéros fait qu'on ne modifie pas les coefficients de \(L_j\) situés à droite du coefficient principal de \(L_i\).

On procède donc ''du bas vers le haut'' pour faire apparaître des zéros au-dessus des ''\({\color{blue}1}\)''. D'abord, on utilise \(L_2\leftarrow L_2+L_3\) pour faire partir le ''\(-1\)'' de la troisième colonne, ce qui donne \[ \left( \begin{array}{ccc|c} {\color{blue}1}&2&1&0\\ {\color{magenta}0}&{\color{blue}1}&{\color{magenta}0}&-10/3\\ {\color{magenta}0}&{\color{magenta}0}&{\color{blue}1}&-7/3 \end{array} \right)\,. \] Ensuite, on peut faire disparaître le ''\(2\)'' de la deuxième colonne en faisant \(L_1\leftarrow L_1-2L_2\), \[ \left( \begin{array}{ccc|c} {\color{blue}1}&{\color{magenta}0}&1&20/3\\ {\color{magenta}0}&{\color{blue}1}&{\color{magenta}0}&-10/3\\ {\color{magenta}0}&{\color{magenta}0}&{\color{blue}1}&-7/3 \end{array} \right)\,, \] puis le ''\(1\)'' de la troisième colonne en faisant \(L_1\leftarrow L_1-L_3\): \[ \left( \begin{array}{ccc|c} {\color{blue}1}&{\color{magenta}0}&{\color{magenta}0}&27/3\\ {\color{magenta}0}&{\color{blue}1}&{\color{magenta}0}&-10/3\\ {\color{magenta}0}&{\color{magenta}0}&{\color{blue}1}&-7/3 \end{array} \right)\,, \] qui est la forme échelonnée réduite de la matrice de départ. On remarque que cette matrice correspond au système \[ \left\{ \begin{array}{ccccccc} x_1 && && &=&27/3 \\ && x_2 && &=&-10/3 \\ && && x_3 &=&-7/3 \end{array} \right.\,, \] pour lequel on a la solution ''sous les yeux'': \((x_1,x_2,x_3)=(\frac{27}{3},\frac{-10}{3},\frac{-7}{3})\).

On l'a mentionné plus haut, une matrice peut être échelonnée d'une infinité de façons différentes. Pour la réduite, c'est différent:

Théorème: Toute matrice \(A\) peut être transformée, à l'aide d'un nombre fini de transformations élémentaires, en une matrice échelonnée réduite. De plus, cette échelonnée réduite est unique et ne dépend pas des opérations élémentaires avec lesquelles elle a été obtenue; on l'appelle la réduite de Gauss de \(A\).

(Omise pour l'instant.)

Dans la résolution d'un système, on n'a pas besoin d'aller jusqu'à la réduite pour obtenir la solution; n'importe quelle échelonnée suffit. Mais puisque la réduite est unique, comme l'affirme le théorème ci-dessus, elle fournit des informations importantes sur la matrice de départ, que nous exploiterons dans les chapitres suivants, en particulier dans l'étude des applications linéaires. D'un point de vue pratique, elle nous permet toujours d'identifier les variables de base et les variables libres, et donc de résoudre complètement le système.

Quiz 1.5-1 : Soit \((*)\) un système linéaire \(m\times n\). Vrai ou faux?
  1. Si \(m\gt n\), alors \((*)\) ne possède aucune solution.
  2. Si \(m=n\), alors \((*)\) possède exactement une solution.
  3. Si \(m\lt n\), alors \((*)\) possède une infinité de solution.

Dernière compilation: 2023-08-30 (14:16:45)

Sauf indication contraire, le contenu de ce document est soumis à une licence Creative Commons internationale, Attribution: Pas d'Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 (CC BY-NC-SA 4.0)