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 :

Deux situations problématiques peuvent survenir :

Exemple d'instabilité numérique

Considérons le système suivant avec :

La solution exacte est approximativement et .

Sans pivotage (pivot = ) :

Le multiplicateur est , un nombre énorme !

Après élimination :

En arithmétique flottante avec précision limitée, et , donc .

Puis . Erreur catastrophique !

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

Le multiplicateur est , un petit nombre.

Après élimination : , donc .

Puis . Résultat correct !

Pivotage partiel (par lignes)

Principe

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

Si , on permute les lignes et .

Algorithme

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 : comparaisons à l'étape
• Permutation : opérations

Le coût total reste .

Pivotage complet (par lignes et colonnes)

Principe

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

On permute ensuite :

• Les lignes et
• Les colonnes et

Avantages et inconvénients

Normalisation (Scaling)

Le problème des échelles différentes

Considérons un système où les coefficients ont des ordres de grandeur très différents :

Le pivotage partiel choisirait la deuxième ligne (pivot = 1), mais la première ligne a un élément bien plus grand en valeur absolue (le 1 de la première ligne vs le ).

Pivotage partiel avec normalisation

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

On choisit le pivot qui maximise :

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 :

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

# 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.

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.