Élimination de Gauss

Objectifs d'apprentissage

À la fin de cette leçon, vous serez en mesure de :

• Appliquer l'algorithme d'élimination de Gauss pour résoudre un système linéaire
• Identifier et utiliser les pivots lors de l'élimination
• Transformer un système quelconque en système triangulaire supérieur
• Évaluer la complexité algorithmique de la méthode
• Comparer l'élimination de Gauss avec la méthode de Gauss-Jordan

Prérequis

• Notions de base en algèbre linéaire (matrices, vecteurs)
• Opérations élémentaires sur les lignes d'une matrice
• Résolution de systèmes triangulaires par substitution

Principe de la méthode

L'élimination de Gauss (aussi appelée méthode de Gauss ou réduction de Gauss) est l'une des méthodes les plus fondamentales pour résoudre les systèmes d'équations linéaires. Son principe est simple et élégant :

La méthode se décompose en deux étapes :

1. Phase d'élimination : Utiliser les opérations élémentaires pour créer des zéros sous la diagonale, transformant ainsi la matrice $A$ en une matrice triangulaire supérieure $U$.

2. Phase de substitution : Résoudre le système triangulaire $U \cdot x = y$ par substitution arrière.

Exemple détaillé pas à pas

Résolvons le système suivant :

Avant de détailler les calculs, explorez le processus de manière interactive :

Étape initiale : écrire la matrice augmentée

Phase d'élimination

Premier pivot : $a_{11} = 3$

Le pivot est l'élément diagonal utilisé pour éliminer les éléments situés en dessous de lui dans la même colonne. Ici, le premier pivot est $a_{11} = 3$.

Objectif : Créer des zéros en positions (2,1) et (3,1).

Pour éliminer $a_{21} = 1$, on effectue : $R_2 \leftarrow R_2 - \frac{1}{3}R_1$

Pour éliminer $a_{31} = 2$, on effectue : $R_3 \leftarrow R_3 - \frac{2}{3}R_1$

Détaillons le calcul pour $R_2$ :

Et pour $R_3$ :

La matrice devient :

Second pivot : $a_{22} = \frac{7}{3}$

Objectif : Créer un zéro en position (3,2).

On effectue : $R_3 \leftarrow R_3 - \frac{-4/3}{7/3}R_2 = R_3 + \frac{4}{7}R_2$

La matrice triangulaire supérieure obtenue est :

Phase de substitution arrière

On résout en remontant de la dernière équation à la première :

Étape 1 : De la troisième équation :

Étape 2 : De la deuxième équation :

Étape 3 : De la première équation :

Solution finale : $x_1 = 3$, $x_2 = 1$, $x_3 = 2$.

La notion de pivot

Définition

Le pivot à l'étape $k$ est l'élément diagonal $a_{kk}^{(k)}$ utilisé pour éliminer tous les éléments situés en dessous de lui dans la colonne $k$.

Rôle du pivot

À chaque étape, on divise par le pivot pour calculer les multiplicateurs :

Puis on effectue l'élimination : $R_i \leftarrow R_i - m_{ik} R_k$

Algorithme général

Voici l'algorithme d'élimination de Gauss pour un système de $n$ équations à $n$ inconnues :

import numpy as np

def elimination_gauss(A, b):
  """
  Résout le système A.x = b par élimination de Gauss.

  Paramètres:
      A : matrice des coefficients (n x n)
      b : vecteur des seconds membres (n,)

  Retourne:
      x : vecteur solution (n,)
  """
  n = len(b)

  # Créer la matrice augmentée
  Aug = np.column_stack([A.astype(float), b.astype(float)])

  # Phase d'élimination (triangularisation)
  for k in range(n - 1):  # Pour chaque pivot
      pivot = Aug[k, k]

      if abs(pivot) < 1e-12:
          raise ValueError(f"Pivot nul à l'étape {k}")

      for i in range(k + 1, n):  # Pour chaque ligne sous le pivot
          # Calculer le multiplicateur
          m = Aug[i, k] / pivot
          # Éliminer
          Aug[i, k:] = Aug[i, k:] - m * Aug[k, k:]

  # Phase de substitution arrière
  x = np.zeros(n)
  for i in range(n - 1, -1, -1):
      somme = sum(Aug[i, j] * x[j] for j in range(i + 1, n))
      x[i] = (Aug[i, n] - somme) / Aug[i, i]

  return x

# Exemple d'utilisation
A = np.array([[3, -1, 2],
            [1,  2, 3],
            [2, -2, -1]], dtype=float)
b = np.array([12, 11, 2], dtype=float)

x = elimination_gauss(A, b)
print(f"Solution : x = {x}")
# Affiche : Solution : x = [3. 1. 2.]

Complexité algorithmique

Analyse du coût

L'élimination de Gauss nécessite deux types d'opérations :

1. Phase d'élimination :

• À l'étape $k$, on effectue environ $(n-k)$ divisions et $(n-k)^2$ multiplications-soustractions.
• Le coût total est de l'ordre de :

2. Phase de substitution arrière :

• Coût de l'ordre de $\frac{n^2}{2}$ opérations.

Comparaison avec d'autres méthodes

Temps de calcul pratique

Pour donner une idée concrète, voici les temps approximatifs pour différentes tailles de systèmes sur un ordinateur moderne :

Méthode de Gauss-Jordan

La méthode de Gauss-Jordan est une variante qui élimine les éléments à la fois au-dessus et en dessous de la diagonale, transformant la matrice en matrice identité.

Principe

Au lieu d'obtenir une matrice triangulaire supérieure, on obtient directement :

Avantages et inconvénients

Visualisation du processus

Le tableau suivant résume les étapes de l'élimination pour notre exemple :

La visualisation suivante montre la méthode de Gauss-Jordan appliquée au même système, pour comparaison avec l'élimination de Gauss :

Résumé

L'élimination de Gauss est une méthode fondamentale pour résoudre les systèmes linéaires :

• Principe : Transformer le système en un système triangulaire supérieur équivalent, puis résoudre par substitution arrière.
• Pivot : Élément diagonal utilisé pour éliminer les éléments en dessous. Un pivot nul pose problème (solution : pivotage).
• Complexité : $O(n^3/3)$ flops, ce qui est bien meilleur que la méthode de Cramer ($O(n!)$).
• Gauss-Jordan : Variante qui évite la substitution arrière mais est 50% plus coûteuse — déconseillée pour la résolution simple.
• L'algorithme se programme facilement et constitue la base de nombreuses bibliothèques numériques.

Pour aller plus loin

La prochaine leçon abordera le pivotage, une technique essentielle pour :

• Éviter les divisions par zéro (pivot nul)
• Améliorer la stabilité numérique de l'algorithme
• Réduire les erreurs d'arrondi lors des calculs

Nous verrons le pivotage partiel et le pivotage complet, ainsi que la technique de normalisation (scaling).