Généralités sur les systèmes linéaires
Un système linéaire est un ensemble d’équations linéaires, c’est-à-dire d’équations où les inconnues apparaissent à la puissance 1 et ne sont pas multipliées entre elles. Un système de m équations à n inconnues peut s’écrire sous la forme : \begin{equation} \begin{cases} a_{11}x_1 + a_{12}x_2 + \dots + a_{1n}x_n = b_1 \\ a_{21}x_1 + a_{22}x_2 + \dots + a_{2n}x_n = b_2 \\ \vdots \\ a_{m1}x_1 + a_{m2}x_2 + \dots + a_{mn}x_n = b_m \end{cases} \end{equation} où les $x_i$ sont les inconnues, les $a_{ij}$ sont les coefficients du système, et les $b_i$ sont les termes constants. On peut représenter un système linéaire sous forme matricielle : \begin{equation} AX = B \end{equation} où : $A = \begin{pmatrix} a_{11} & a_{12} & \dots & a_{1n} \\ a_{21} & a_{22} & \dots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \dots & a_{mn} \end{pmatrix}$ est la matrice des coefficients. $X = \begin{pmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{pmatrix}$ est le vecteur des inconnues. $B = \begin{pmatrix} b_1 \\ b_2 \\ \vdots \\ b_m \end{pmatrix}$ est le vecteur des termes constants. Un système linéaire peut avoir : Une solution unique : dans ce cas, les équations sont indépendantes et se coupent en un seul point. Une infinité de solutions : dans ce cas, certaines équations sont des combinaisons linéaires des autres, et le système décrit une droite, un plan, ou un hyperplan. Aucune solution : dans ce cas, les équations sont incompatibles et ne se coupent pas. On dit alors que le système est incompatible. Résoudre un système linéaire consiste à trouver les valeurs des inconnues qui satisfont toutes les équations simultanément.
L’algorithme du pivot de Gauss
L’algorithme du pivot de Gauss est une méthode systématique pour résoudre un système d’équations linéaires. Il consiste à transformer le système initial en un système équivalent (c’est-à-dire ayant les mêmes solutions) mais plus simple à résoudre, en utilisant des opérations élémentaires sur les lignes. Les opérations élémentaires sur les lignes sont : 1. Échanger deux lignes : $L_i \leftrightarrow L_j$ 2. Multiplier une ligne par un scalaire non nul : $L_i \leftarrow kL_i$ avec $k \neq 0$ 3. Ajouter à une ligne un multiple d’une autre ligne : $L_i \leftarrow L_i + kL_j$ L’algorithme se déroule en deux phases : Phase 1 : Élimination (ou triangulation) Cette phase consiste à transformer la matrice augmentée $(A|B)$ en une matrice échelonnée réduite par rapport aux lignes. La matrice augmentée est obtenue en ajoutant le vecteur $B$ comme dernière colonne à la matrice $A$. On procède de la manière suivante : Étape 1 : On choisit le premier élément non nul de la première colonne comme pivot. Si le premier élément est nul, on échange la première ligne avec une ligne où le premier élément est non nul. Étape 2 : On annule tous les éléments sous le pivot en utilisant l’opération $L_i \leftarrow L_i – \frac{a_{i1}}{a_{11}}L_1$ pour $i > 1$. Étape 3 : On répète les étapes 1 et 2 pour la sous-matrice obtenue en supprimant la première ligne et la première colonne, et ainsi de suite jusqu’à obtenir une matrice échelonnée. Phase 2 : Remontée (ou substitution) Une fois la matrice échelonnée obtenue, on peut résoudre le système en partant de la dernière ligne et en remontant. La dernière équation de la matrice échelonnée donne directement la valeur d’une inconnue (ou une relation entre plusieurs inconnues). On substitue cette valeur dans l’équation précédente pour trouver la valeur d’une autre inconnue. On continue ainsi jusqu’à la première équation. Exemple : Considérons le système suivant : \begin{equation} \begin{cases} 2x + y – z = 8 \\ -3x – y + 2z = -11 \\ -2x + y + 2z = -3 \end{cases} \end{equation} La matrice augmentée est : \begin{equation} \begin{pmatrix} 2 & 1 & -1 & 8 \\ -3 & -1 & 2 & -11 \\ -2 & 1 & 2 & -3 \end{pmatrix} \end{equation} Phase 1 : Élimination $L_2 \leftarrow L_2 + \frac{3}{2}L_1$ et $L_3 \leftarrow L_3 + L_1$ : \begin{equation} \begin{pmatrix} 2 & 1 & -1 & 8 \\ 0 & \frac{1}{2} & \frac{1}{2} & 1 \\ 0 & 2 & 1 & 5 \end{pmatrix} \end{equation} $L_3 \leftarrow L_3 – 4L_2$ : \begin{equation} \begin{pmatrix} 2 & 1 & -1 & 8 \\ 0 & \frac{1}{2} & \frac{1}{2} & 1 \\ 0 & 0 & -1 & 1 \end{pmatrix} \end{equation} Phase 2 : Remontée $L_3$ donne $-z = 1$, donc $z = -1$. $L_2$ donne $\frac{1}{2}y + \frac{1}{2}(-1) = 1$, donc $y = 3$. $L_1$ donne $2x + 3 – (-1) = 8$, donc $x = 2$. La solution du système est donc $x = 2$, $y = 3$, et $z = -1$. Remarques : L’algorithme du pivot de Gauss peut être utilisé pour calculer l’inverse d’une matrice et déterminer son rang. Il existe des variantes de l’algorithme du pivot de Gauss, comme l’algorithme de Gauss-Jordan, qui transforme la matrice en une matrice échelonnée réduite par rapport aux lignes.