Pivotage et normalisation

Objectifs d'apprentissage

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

Identifier les situations où un pivot pose problème (nul ou trop petit)
Appliquer le pivotage partiel pour améliorer la stabilité numérique
Comprendre le principe du pivotage complet
Utiliser la normalisation (scaling) pour équilibrer un système
Implémenter l'élimination de Gauss avec pivotage partiel

Prérequis

Élimination de Gauss
Notion d'erreurs d'arrondi en arithmétique flottante

Pourquoi le pivotage est-il nécessaire ?

Le problème des petits pivots

Dans l'élimination de Gauss, nous divisons par le pivot pour calculer les multiplicateurs :

m_{ik} = \frac{a_{ik}^{(k)}}{a_{kk}^{(k)}}

Deux situations problématiques peuvent survenir :

🚨

Problèmes avec les pivots

Pivot nul : La division est impossible, l'algorithme échoue.
Pivot très petit : La division amplifie les erreurs d'arrondi, produisant des résultats incorrects.

Exemple d'instabilité numérique

Considérons le système suivant avec $\epsilon = 10^{-20}$ :

\begin{cases} \epsilon \cdot x_1 + x_2 = 1 \\ x_1 + x_2 = 2 \end{cases}

La solution exacte est approximativement $x_1 \approx 1$ et $x_2 \approx 1$ .

Sans pivotage (pivot = $\epsilon$ ) :

Le multiplicateur est $m = 1/\epsilon = 10^{20}$ , un nombre énorme !

Après élimination : $(1 - 10^{20}) x_2 = 2 - 10^{20}$

En arithmétique flottante avec précision limitée, $1 - 10^{20} \approx -10^{20}$ et $2 - 10^{20} \approx -10^{20}$ , donc $x_2 \approx 1$ .

Puis $x_1 = (1 - x_2)/\epsilon = 0/\epsilon = 0$ . Erreur catastrophique !

Avec pivotage (on échange les lignes, pivot = 1) :

\begin{cases} x_1 + x_2 = 2 \\ \epsilon \cdot x_1 + x_2 = 1 \end{cases}

Le multiplicateur est $m = \epsilon$ , un petit nombre.

Après élimination : $(1 - \epsilon) x_2 = 1 - 2\epsilon \approx 1$ , donc $x_2 \approx 1$ .

Puis $x_1 = 2 - x_2 = 1$ . Résultat correct !

Pivotage partiel (par lignes)

Principe

À chaque étape $k$ de l'élimination, avant de diviser par le pivot, on cherche l'élément de plus grande valeur absolue dans la colonne $k$ , parmi les lignes $k, k+1, \ldots, n$ .

p = \arg\max_{i \geq k} |a_{ik}^{(k)}|

Si $p \neq k$ , on permute les lignes $k$ et $p$ .

Algorithme

pivotage_partiel.pypython

import numpy as np

def gauss_pivotage_partiel(A, b):
  """
  Élimination de Gauss avec pivotage partiel.

  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 avec pivotage partiel
  for k in range(n - 1):
      # Recherche du pivot maximal dans la colonne k
      max_idx = k + np.argmax(np.abs(Aug[k:, k]))

      # Permutation des lignes si nécessaire
      if max_idx != k:
          Aug[[k, max_idx]] = Aug[[max_idx, k]]
          print(f"Étape {k+1}: Permutation L{k+1} <-> L{max_idx+1}")

      # Vérifier que le pivot n'est pas nul
      if abs(Aug[k, k]) < 1e-12:
          raise ValueError("Matrice singulière détectée")

      # Élimination standard
      for i in range(k + 1, n):
          m = Aug[i, k] / Aug[k, 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):
      x[i] = (Aug[i, n] - np.dot(Aug[i, i+1:n], x[i+1:n])) / Aug[i, i]

  return x

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

x = gauss_pivotage_partiel(A, b)
print(f"Solution : x = {x}")

Coût supplémentaire

Le pivotage partiel ajoute un coût négligeable :

Recherche du maximum : $O(n-k)$ comparaisons à l'étape $k$
Permutation : $O(n)$ opérations

Le coût total reste $O(n^3/3)$ .

Pivotage complet (par lignes et colonnes)

Principe

On cherche l'élément de plus grande valeur absolue dans toute la sous-matrice restante :

(p, q) = \arg\max_{i,j \geq k} |a_{ij}^{(k)}|

On permute ensuite :

Les lignes $k$ et $p$
Les colonnes $k$ et $q$

⚠️

Suivi des inconnues

La permutation des colonnes change l'ordre des inconnues ! Il faut garder trace de ces permutations pour réordonner la solution finale.

Avantages et inconvénients

Aspect	Pivotage partiel	Pivotage complet
Recherche du pivot	$O(n-k)$	$O((n-k)^2)$
Coût total	$O(n^2)$ de plus	$O(n^3/3)$ de plus
Stabilité	Excellente en pratique	Optimale théoriquement
Usage	Standard (recommandé)	Rare (cas spéciaux)

💡

Recommandation pratique

Le pivotage partiel est suffisant dans la grande majorité des cas et est le choix par défaut dans les bibliothèques numériques (NumPy, LAPACK, etc.). Le pivotage complet n'est utilisé que dans des situations très spécifiques.

Normalisation (Scaling)

Le problème des échelles différentes

Considérons un système où les coefficients d'une même ligne ont des ordres de grandeur très différents :

\begin{pmatrix} 2 & 100000 \\ 1 & 1 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \end{pmatrix} = \begin{pmatrix} 100002 \\ 2 \end{pmatrix}

Le pivotage partiel conserverait la première ligne comme pivot ( $|2| > |1|$ ), alors que ce 2 n'est « grand » qu'en apparence : rapporté à l'échelle de sa propre ligne ( $10^5$ ), c'est un pivot minuscule.

Pivotage partiel avec normalisation

L'idée est de normaliser chaque ligne avant de comparer les pivots potentiels :

s_i = \max_{j} |a_{ij}|

On choisit le pivot qui maximise :

p = \arg\max_{i \geq k} \frac{|a_{ik}^{(k)}|}{s_i}

pivotage_normalise.pypython

import numpy as np

def gauss_pivotage_normalise(A, b):
  """
  Élimination de Gauss avec pivotage partiel normalisé.
  """
  n = len(b)
  Aug = np.column_stack([A.astype(float), b.astype(float)])

  # Calculer les facteurs d'échelle (max de chaque ligne)
  s = np.max(np.abs(Aug[:, :n]), axis=1)

  # Vérifier qu'aucune ligne n'est nulle
  if np.any(s == 0):
      raise ValueError("Ligne nulle détectée")

  for k in range(n - 1):
      # Pivot normalisé : |a_ik| / s_i
      ratios = np.abs(Aug[k:, k]) / s[k:]
      max_idx = k + np.argmax(ratios)

      if max_idx != k:
          Aug[[k, max_idx]] = Aug[[max_idx, k]]
          s[k], s[max_idx] = s[max_idx], s[k]

      if abs(Aug[k, k]) < 1e-12 * s[k]:
          raise ValueError("Matrice singulière")

      for i in range(k + 1, n):
          m = Aug[i, k] / Aug[k, k]
          Aug[i, k:] -= m * Aug[k, k:]

  # Substitution arrière
  x = np.zeros(n)
  for i in range(n - 1, -1, -1):
      x[i] = (Aug[i, n] - np.dot(Aug[i, i+1:n], x[i+1:n])) / Aug[i, i]

  return x

Détection des matrices singulières

Le pivotage permet aussi de détecter les matrices singulières :

🚨

Matrice singulière

Si, après la recherche du pivot maximal, le meilleur candidat est nul (ou très proche de zéro par rapport à la précision machine), alors la matrice est singulière et le système n'a pas de solution unique.

En pratique, on utilise un seuil de tolérance :

detection_singularite.pypython

# Tolérance relative
tol = 1e-12

# Après pivotage, vérifier le pivot
if abs(Aug[k, k]) < tol * s[k]:
  raise ValueError(f"Matrice singulière ou quasi-singulière à l'étape {k}")

Résumé

Le pivotage est une technique essentielle pour assurer la stabilité numérique de l'élimination de Gauss :

Pivotage partiel : Permute les lignes pour maximiser le pivot. Coût négligeable, très efficace en pratique. C'est le choix standard.
Pivotage complet : Permute lignes et colonnes. Plus coûteux, rarement nécessaire.
Normalisation : Équilibre les lignes avant de comparer les pivots. Utile quand les échelles varient beaucoup.
Détection de singularité : Un pivot nul après pivotage indique une matrice singulière.

Situation	Solution
Pivot exactement nul	Pivotage obligatoire
Pivot très petit	Pivotage pour stabilité
Échelles très différentes	Normalisation + pivotage
Matrice singulière	Détection via pivot nul

Pour aller plus loin

La prochaine leçon introduira la factorisation LU, une méthode qui permet de « mémoriser » le travail d'élimination de Gauss pour résoudre efficacement plusieurs systèmes avec la même matrice.