Conditionnement des systèmes linéaires

Objectifs d'apprentissage

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

• Calculer le nombre de condition d'une matrice
• Interpréter le conditionnement comme facteur d'amplification d'erreur
• Appliquer les théorèmes de perturbation
• Utiliser le raffinement itératif pour améliorer la précision
• Reconnaître un système mal conditionné

Prérequis

• Normes vectorielles et matricielles
• Factorisation LU

Qu'est-ce que le conditionnement ?

Motivation

Considérons le système $A \cdot x = b$. En pratique :

• Les coefficients de $A$ et $b$ sont connus avec une précision limitée
• Les calculs introduisent des erreurs d'arrondi
• La solution calculée $x^*$ diffère de la solution exacte $x$

Question fondamentale : De petites erreurs sur les données produisent-elles de petites ou de grandes erreurs sur la solution ?

Exemple introductif : deux systèmes très différents

Considérons deux systèmes 2×2 et voyons comment ils réagissent à une perturbation de 5% sur le second membre.

Système 1 — Bien conditionné (matrice identité) :

Solution exacte : $x = (2, 3)^T$.

Perturbons $b$ de 5% : $b' = (2{,}1, 3{,}15)^T$ (on ajoute 5% à chaque composante).

Nouvelle solution : $x' = (2{,}1, 3{,}15)^T$.

L'erreur sur $x$ est exactement 5%. Le système est parfaitement stable.

Système 2 — Mal conditionné :

Solution exacte : $x = (1, 1)^T$.

Perturbons $b$ de 5% : $b' = (2{,}1, 2{,}1105)^T$.

Résolvons le système perturbé :

• Ligne 2 - Ligne 1 : $0{,}01 \cdot x_2 = 0{,}0105$, donc $x_2 = 1{,}05$
• De la ligne 1 : $x_1 = 2{,}1 - 1{,}05 = 1{,}05$

Nouvelle solution : $x' = (1{,}05, 1{,}05)^T$.

Ici aussi l'erreur est de 5%, mais si on perturbe différemment (par exemple $b' = (2{,}1, 2{,}01)^T$), on obtient $x' = (11{,}1, -9)^T$ — une erreur énorme ! Le système est très sensible à la direction de la perturbation.

Système bien conditionné vs mal conditionné

Interprétation géométrique : Dans la visualisation ci-dessus, les lignes représentent les équations du système. Pour un système bien conditionné, les lignes se croisent à angle droit (ou proche). Pour un système mal conditionné, les lignes sont presque parallèles — un petit déplacement d'une ligne déplace beaucoup le point d'intersection.

Le nombre de condition

Définition

Le nombre de condition d'une matrice inversible $A$ est :

Il dépend du choix de la norme. On note $\kappa_p(A)$ pour la norme $p$.

Calcul détaillé : système bien conditionné

Reprenons le Système 1 avec $A = I = \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}$ (matrice identité).

Étape 1 : Calculer $\|A\|_\infty$ (max des sommes de lignes)

• Ligne 1 : $|1| + |0| = 1$
• Ligne 2 : $|0| + |1| = 1$
• $\|A\|_\infty = \max(1, 1) = 1$

Étape 2 : Calculer $A^{-1}$

Pour la matrice identité, l'inverse est elle-même :

Étape 3 : Calculer $\|A^{-1}\|_\infty$

• Ligne 1 : $|1| + |0| = 1$
• Ligne 2 : $|0| + |1| = 1$
• $\|A^{-1}\|_\infty = 1$

Étape 4 : Calculer $\kappa_\infty(A)$

Calcul détaillé : système mal conditionné

Reprenons le Système 2 avec $A = \begin{pmatrix} 1 & 1 \\ 1 & 1{,}01 \end{pmatrix}$.

Étape 1 : Calculer $\|A\|_\infty$

• Ligne 1 : $|1| + |1| = 2$
• Ligne 2 : $|1| + |1{,}01| = 2{,}01$
• $\|A\|_\infty = 2{,}01$

Étape 2 : Calculer $A^{-1}$

Pour une matrice 2×2, on utilise la formule :

Calculons le déterminant :

Donc :

Étape 3 : Calculer $\|A^{-1}\|_\infty$

• Ligne 1 : $|101| + |-100| = 201$
• Ligne 2 : $|-100| + |100| = 200$
• $\|A^{-1}\|_\infty = 201$

Étape 4 : Calculer $\kappa_\infty(A)$

Propriétés du nombre de condition

Théorèmes de perturbation

Perturbation du second membre

Si on résout $A \cdot x = b$ avec $b$ perturbé en $b + \delta b$, la solution perturbée est $x + \delta x$.

Démonstration

De $A(x + \delta x) = b + \delta b$ et $Ax = b$, on déduit $A \cdot \delta x = \delta b$.

Donc $\delta x = A^{-1} \delta b$, ce qui donne :

De plus, $\|b\| = \|Ax\| \leq \|A\| \cdot \|x\|$, donc $\|x\| \geq \|b\| / \|A\|$.

En combinant :

Application numérique avec ε = 0,05 (5%)

Système bien conditionné ($\kappa = 1$) :

Si l'erreur relative sur $b$ est $\varepsilon = 0{,}05$ (5%), alors :

Système mal conditionné ($\kappa = 400$) :

Avec la même erreur $\varepsilon = 0{,}05$ sur $b$ :

Vérification sur notre exemple

Reprenons le système mal conditionné avec la perturbation défavorable $b' = (2{,}1, 2{,}01)^T$.

Calcul de l'erreur relative sur $b$ :

Calcul de l'erreur relative sur $x$ :

Solution exacte : $x = (1, 1)^T$, solution perturbée : $x' = (11{,}1, -9)^T$ (calculé plus haut).

Vérification de la borne :

L'erreur réelle (1010%) est bien inférieure à la borne (2020%), mais reste énorme !

Perturbation de la matrice

Si $A$ est perturbée en $A + \delta A$ :

La même règle s'applique : le nombre de condition amplifie les erreurs relatives.

Perturbation combinée (CSE)

En pratique, on a souvent des erreurs sur $A$ et sur $b$ simultanément. Le Componentwise Sensitivity Estimate (CSE) donne :

Application numérique

Si les données ont une erreur de mesure de 5% à la fois sur $A$ et sur $b$ :

Système bien conditionné ($\kappa = 1$) :

Système mal conditionné ($\kappa = 400$) :

Résidu et erreur

Le résidu mesure « à quel point la solution approchée satisfait l'équation » :

où $x^*$ est notre solution calculée.

La relation entre résidu et erreur est :

Interprétation avec ε = 0,05

Supposons qu'on calcule une solution avec un résidu relatif de 5% : $\|r\|/\|b\| = 0{,}05$.

Système bien conditionné ($\kappa = 1$) :

L'erreur relative est exactement 5%. Résidu et erreur sont équivalents.

Système mal conditionné ($\kappa = 400$) :

L'erreur peut être κ fois plus grande ou κ fois plus petite que le résidu relatif, soit un écart de κ² = 160 000 entre les bornes !

Exemples de matrices mal conditionnées

Matrice de Hilbert

import numpy as np

def nombre_condition(A, p=2):
  """
  Calcule le nombre de condition de A.
  """
  if p == 2:
      s = np.linalg.svd(A, compute_uv=False)
      return s[0] / s[-1]
  else:
      return np.linalg.norm(A, p) * np.linalg.norm(np.linalg.inv(A), p)

# Matrices de Hilbert
for n in [3, 5, 10]:
  H = np.array([[1/(i+j+1) for j in range(n)] for i in range(n)])
  kappa = nombre_condition(H)
  print(f"κ(H_{n}) = {kappa:.2e}")

Perte de chiffres significatifs

Règle pratique

Démonstration

Supposons que les données soient connues avec une précision de $p$ chiffres significatifs. Cela correspond à une erreur relative de l'ordre de $10^{-p}$ (l'epsilon machine pour la précision $p$).

D'après le théorème de perturbation, l'erreur relative sur la solution est bornée par :

Si $\kappa(A) = 10^k$, alors :

Une erreur relative de $10^{-(p-k)}$ signifie que seuls $p - k$ chiffres sont fiables. On a donc perdu $k = \log_{10}(\kappa)$ chiffres à cause du conditionnement.

Application à notre exemple

Pour le système mal conditionné avec $\kappa \approx 400$ :

On perd environ 2 à 3 chiffres significatifs.

Vérification numérique :

Supposons qu'on travaille avec des données à 3 chiffres significatifs (erreur relative $\sim 10^{-3}$).

L'erreur sur la solution peut atteindre :

Une erreur relative de $10^{-0{,}4} \approx 0{,}4$ signifie qu'on n'a plus que $3 - 2{,}6 \approx 0{,}4$ chiffre fiable — presque aucun !

Dans notre exemple concret, avec 5% d'erreur sur $b$, on a observé jusqu'à 1010% d'erreur sur $x$. La borne théorique était $\kappa \times 5\% = 400 \times 5\% = 2000\%$. L'erreur réelle (1010%) est inférieure à la borne, ce qui est cohérent.

Tableau récapitulatif

Avec une précision double (≈ 16 chiffres) :

Que faire face à un mauvais conditionnement ?

Résumé

Le nombre de condition $\kappa(A) = \|A\| \cdot \|A^{-1}\|$ mesure la sensibilité du système aux perturbations.

Points clés :

• L'erreur relative peut être amplifiée par $\kappa(A)$
• Un petit résidu ne garantit pas une petite erreur
• On perd environ $\log_{10}(\kappa)$ chiffres significatifs

Pour aller plus loin

La prochaine leçon présentera le raffinement itératif, une technique élégante pour récupérer la précision perdue à cause du conditionnement, en réutilisant la factorisation LU déjà calculée.