Aller au contenu
ELECTRONICS ENGINEERINGelectronics-engineering.com
Géométrie et algèbre

Systèmes linéaires et élimination de Gauss

Forme matricielle, signification géométrique, opérations élémentaires, forme échelonnée, systèmes incompatibles et sous-déterminés, Gauss-Jordan et coût de l'algorithme.

https://www.electronics-engineering.com/fr/systemes-lineaires-elimination-de-gauss/

Pas encore de vote : soyez le premier à noter cette page.

Résoudre un système d’équations linéaires est le problème le plus courant des mathématiques appliquées : les courants d’un réseau électrique, les forces dans une structure en treillis, l’interpolation de données, la simulation d’un circuit avec SPICE s’y ramènent tous. Dans cette leçon, nous voyons comment écrire un système sous forme matricielle, ce qu’il signifie géométriquement et comment le résoudre par l’élimination de Gauss, qui est aussi l’algorithme utilisé par les ordinateurs.

Systèmes linéaires et forme matricielle

Un système de m équations linéaires à n inconnues s’écrit

    \[ \begin{cases} a_{11}x_1 + a_{12}x_2 + \dots + a_{1n}x_n = b_1\\ \quad\vdots\\ a_{m1}x_1 + a_{m2}x_2 + \dots + a_{mn}x_n = b_m \end{cases} \qquad\Longleftrightarrow\qquad A\,\mathbf x = \mathbf b \]

où A est la matrice des coefficients (m lignes, n colonnes), \mathbf x le vecteur des inconnues et \mathbf b le second membre. En plaçant \mathbf b à côté de A, on obtient la matrice augmentée (A\,|\,\mathbf b). Si \mathbf b = \mathbf 0, le système est homogène et admet toujours au moins la solution nulle.

La signification géométrique

Avec deux inconnues, chaque équation est une droite du plan, et résoudre le système revient à trouver les points communs. Il n’y a que trois possibilités.

Les trois possibilités pour un système de deux équations à deux inconnues
Deux droites du plan : elles se coupent en un point (une seule solution), elles sont parallèles et distinctes (aucune solution), elles sont confondues (une infinité de solutions, dépendant d’un paramètre).

Il en va de même en général : un système linéaire a une solution, aucune ou une infinité. Il ne peut pas en avoir exactement deux, car si \mathbf x_1 et \mathbf x_2 sont solutions, chaque point de la droite qui les joint l’est aussi, \mathbf x_1 + t(\mathbf x_2 - \mathbf x_1) : en effet A\big(\mathbf x_1 + t(\mathbf x_2 - \mathbf x_1)\big) = \mathbf b + t(\mathbf b - \mathbf b) = \mathbf b. Avec trois inconnues, chaque équation est un plan, et les solutions sont un point, une droite, un plan ou rien.

Opérations élémentaires

Les solutions d’un système ne changent pas si l’on applique ces opérations élémentaires à ses équations (c’est-à-dire aux lignes de la matrice augmentée) :

  1. échanger deux lignes ;
  2. multiplier une ligne par un nombre non nul ;
  3. ajouter un multiple d’une ligne à une autre ligne.

Chaque opération est inversible (elle s’annule par une opération du même type), donc toute solution du nouveau système résout l’ancien et réciproquement.

L’élimination de Gauss

L’idée est d’utiliser les opérations élémentaires pour amener la matrice augmentée à la forme échelonnée : chaque ligne commence par plus de zéros que celle du dessus. Le premier coefficient non nul de chaque ligne s’appelle le pivot. Ensuite, on résout le système de bas en haut, par substitution remontante.

Exemple.

    \[ \begin{cases} x + 2y + z = 4\\ 2x + 5y + 3z = 11\\ -x + y + 4z = 9 \end{cases} \]

    \[ \left(\begin{array}{ccc|c} 1 & 2 & 1 & 4\\ 2 & 5 & 3 & 11\\ -1 & 1 & 4 & 9 \end{array}\right) \xrightarrow[R_3 + R_1]{R_2 - 2R_1} \left(\begin{array}{ccc|c} 1 & 2 & 1 & 4\\ 0 & 1 & 1 & 3\\ 0 & 3 & 5 & 13 \end{array}\right) \xrightarrow{R_3 - 3R_2} \left(\begin{array}{ccc|c} 1 & 2 & 1 & 4\\ 0 & 1 & 1 & 3\\ 0 & 0 & 2 & 4 \end{array}\right) \]

De la dernière ligne 2z = 4, donc z = 2. De la deuxième, y = 3 - z = 1. De la première, x = 4 - 2y - z = 0. Solution : (0, 1, 2). Il vaut toujours la peine de la vérifier dans la troisième équation d’origine : 0 + 1 + 8 = 9. Correct.

Systèmes incompatibles et sous-déterminés

La forme échelonnée dit tout de suite ce qui se passe.

  • Si une ligne (0\ 0\ \dots\ 0\,|\,c) avec c \ne 0 apparaît, c’est l’équation 0 = c, le système est incompatible.
  • Sinon, il est résoluble. On calcule les inconnues correspondant aux pivots ; les autres sont des paramètres libres. Avec n inconnues et r pivots, les solutions dépendent de n - r paramètres.

Exemple. x + y - z = 1, 2x + 3y + z = 5, 3x + 4y = 6. Avec R_2 - 2R_1 et R_3 - 3R_1, on obtient les lignes (0\ 1\ 3\,|\,3) et (0\ 1\ 3\,|\,3) ; avec R_3 - R_2, la dernière devient entièrement nulle. Il reste deux pivots et trois inconnues : z = t libre, y = 3 - 3t, x = 1 - y + z = -2 + 4t. Les solutions forment la droite (x, y, z) = (-2, 3, 0) + t\,(4, -3, 1).

Si la dernière ligne avait été (0\ 0\ 0\,|\,1) (par exemple avec 7 au lieu de 6 à droite de la troisième équation), le système aurait été incompatible : les trois plans n’auraient eu aucun point commun.

L’élimination de Gauss-Jordan

En poursuivant l’élimination aussi vers le haut et en divisant chaque ligne par son pivot, on obtient la forme échelonnée réduite : pivots égaux à 1 et zéros au-dessus et au-dessous de chaque pivot. Les solutions se lisent directement, sans substitution. La même procédure, appliquée à la matrice (A\,|\,I), calcule la matrice inverse (voir la leçon sur les matrices).

Combien ça coûte

Pour un système n\times n, l’élimination demande environ \tfrac23 n^3 opérations. Avec n = 1000, c’est un peu moins d’un milliard, une fraction de seconde pour un ordinateur. Les bibliothèques numériques (LAPACK, utilisée par MATLAB et NumPy) emploient exactement l’élimination de Gauss, sous la forme appelée factorisation LU, avec pivot partiel : à chaque étape, on choisit comme pivot le coefficient de plus grande valeur absolue de la colonne, pour ne pas diviser par de très petits nombres et limiter les erreurs d’arrondi.

Une note pour les électroniciens

Avec l’analyse nodale, chaque nœud d’un circuit linéaire donne une équation linéaire en les tensions des nœuds (loi des courants de Kirchhoff). Un circuit de 500 nœuds est un système 500\times 500, et un simulateur comme SPICE, à chaque pas de temps, ne fait rien d’autre que le construire et le résoudre par élimination de Gauss, en profitant du fait que la matrice est presque entièrement nulle.

S’abonner
Notifier de
guest
1 commentaire
Le plus ancien
Plus récent Les plus votés
1
0
Vous avez apprécié cet article ? Merci de laisser un commentaire.x