Annexe B — Exemples détaillés de pivotage

Cette annexe présente deux exemples complets de pivotage : le pivotage complet (lignes et colonnes) et le pivotage partiel (lignes seulement). Ces exemples illustrent l'importance du pivotage pour la stabilité numérique.

Exemple 1 : Pivotage complet

Le pivotage complet consiste à échanger à la fois des lignes et des colonnes pour placer le plus grand élément (en valeur absolue) de la sous-matrice restante en position de pivot.

Système initial

Considérons le système $Ax = b$ avec :

A = \begin{pmatrix} 4 & 1 & -32 \\ 0 & 4 & 3 \\ 6 & 3 & 7 \end{pmatrix}, \quad b = \begin{pmatrix} 3 \\ 1 \\ 2 \end{pmatrix}

Matrice augmentée initiale :

\left( \begin{array}{ccc|c} 4 & 1 & -32 & 3 \\ 0 & 4 & 3 & 1 \\ 6 & 3 & 7 & 2 \end{array} \right)

Étape 1 : Recherche du pivot maximal

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

Élément	Valeur absolue
$a_{13} = -32$	$32$ ← maximum
$a_{31} = 6$	$6$
$a_{11} = 4$	$4$

Le maximum est $|{-32}| = 32$ en position $(1, 3)$ .

Pour amener cet élément en position $(1, 1)$ , on effectue :

Échange de lignes : $R_1 \leftrightarrow R_1$ (pas nécessaire, déjà en ligne 1)
Échange de colonnes : $C_1 \leftrightarrow C_3$

⚠️

Attention : ordre des inconnues

L'échange de colonnes modifie l'ordre des inconnues. Il faut garder trace de cet ordre pour reconstruire la solution finale. Initialement : $(x_1, x_2, x_3)$ . Après $C_1 \leftrightarrow C_3$ : $(x_3, x_2, x_1)$ .

Après l'échange $C_1 \leftrightarrow C_3$ :

\left( \begin{array}{ccc|c} -32 & 1 & 4 & 3 \\ 3 & 4 & 0 & 1 \\ 7 & 3 & 6 & 2 \end{array} \right)

Ordre des inconnues : $O = (x_3, x_2, x_1)$

Étape 2 : Élimination sous le pivot

Maintenant on élimine les éléments sous le pivot $-32$ :

Multiplicateurs :

m_{21} = \frac{a_{21}}{a_{11}} = \frac{3}{-32} = -\frac{3}{32}

m_{31} = \frac{a_{31}}{a_{11}} = \frac{7}{-32} = -\frac{7}{32}

Opérations :

$R_2 \leftarrow R_2 - m_{21} \cdot R_1 = R_2 + \frac{3}{32} R_1$
$R_3 \leftarrow R_3 - m_{31} \cdot R_1 = R_3 + \frac{7}{32} R_1$

Après élimination (première colonne) :

\left( \begin{array}{ccc|c} -32 & 1 & 4 & 3 \\ 0 & 4{,}094 & 0{,}375 & 1{,}281 \\ 0 & 3{,}219 & 6{,}875 & 2{,}656 \end{array} \right)

Étape 3 : Deuxième pivot

On cherche le maximum dans la sous-matrice $2 \times 2$ restante (lignes 2-3, colonnes 2-3) :

Élément	Valeur absolue
$a_{33} = 6{,}875$	$6{,}875$ ← maximum
$a_{22} = 4{,}094$	$4{,}094$

Pour amener $6{,}875$ en position $(2, 2)$ :

Échange de lignes : $R_2 \leftrightarrow R_3$
Échange de colonnes : $C_2 \leftrightarrow C_3$

Après les échanges :

\left( \begin{array}{ccc|c} -32 & 4 & 1 & 3 \\ 0 & 6{,}875 & 3{,}219 & 2{,}656 \\ 0 & 0{,}375 & 4{,}094 & 1{,}281 \end{array} \right)

Ordre des inconnues : $O = (x_3, x_1, x_2)$

Étape 4 : Dernière élimination

Multiplicateur :

m_{32} = \frac{0{,}375}{6{,}875} \approx 0{,}0545

Opération : $R_3 \leftarrow R_3 - m_{32} \cdot R_2$

Matrice triangulaire finale :

\left( \begin{array}{ccc|c} -32 & 4 & 1 & 3 \\ 0 & 6{,}875 & 3{,}219 & 2{,}656 \\ 0 & 0 & 3{,}918 & 1{,}136 \end{array} \right)

Étape 5 : Substitution arrière

On résout le système triangulaire :

x_2 = \frac{1{,}136}{3{,}918} \approx 0{,}290

x_1 = \frac{2{,}656 - 3{,}219 \times 0{,}290}{6{,}875} \approx 0{,}250

x_3 = \frac{3 - 4 \times 0{,}250 - 1 \times 0{,}290}{-32} \approx -0{,}053

Rappel : L'ordre des inconnues est $(x_3, x_1, x_2)$ , donc :

La première composante calculée est $x_2$
La deuxième est $x_1$
La troisième est $x_3$

Solution finale (remise dans l'ordre original $(x_1, x_2, x_3)$ ) :

x = \begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix} \approx \begin{pmatrix} 0{,}250 \\ 0{,}290 \\ -0{,}053 \end{pmatrix}

Exemple 2 : Impact du pivotage sur la précision

Cet exemple montre comment le pivotage partiel améliore drastiquement la précision des calculs en arithmétique à précision finie.

Contexte

Considérons un système flottant avec base $b = 10$ et $s = 4$ chiffres significatifs. À chaque opération, le résultat est arrondi à 4 chiffres.

Système initial

A = \begin{pmatrix} -0{,}002 & 4{,}000 & 4{,}000 \\ -2{,}000 & 2{,}906 & -5{,}387 \\ 3{,}000 & -4{,}031 & -3{,}112 \end{pmatrix}, \quad b = \begin{pmatrix} 7{,}998 \\ -4{,}481 \\ -4{,}143 \end{pmatrix}

La solution exacte est $x^* = (1, 1, 1)^T$ .

Méthode 1 : Sans pivotage

On utilise directement $a_{11} = -0{,}002$ comme premier pivot.

Problème : Ce pivot est très petit ! Les multiplicateurs seront énormes :

m_{21} = \frac{-2{,}000}{-0{,}002} = 1000

m_{31} = \frac{3{,}000}{-0{,}002} = -1500

Élimination (avec arrondi à 4 chiffres) :

$R_2 \leftarrow R_2 - 1000 \cdot R_1$ :

$a_{22}' = 2{,}906 - 1000 \times 4{,}000 = 2{,}906 - 4000 = -3997$ → arrondi : $-3{,}997 \times 10^3$
$a_{23}' = -5{,}387 - 1000 \times 4{,}000 = -4005$ → arrondi : $-4{,}005 \times 10^3$
$b_2' = -4{,}481 - 1000 \times 7{,}998 = -8002$ → arrondi : $-8{,}002 \times 10^3$

Matrice triangulaire (après arrondi) :

\left( \begin{array}{ccc|c} -0{,}002 & 4{,}000 & 4{,}000 & 7{,}998 \\ 0 & -3{,}997 & -4{,}005 & -8{,}002 \\ 0 & 0 & -10{,}00 & 0{,}000 \end{array} \right) \times 10^3 \text{ (lignes 2-3)}

Substitution arrière :

x_3 = \frac{0{,}000}{-10{,}00} = 0{,}000

x_2 = \frac{-8002 - (-4005) \times 0}{-3997} = \frac{-8002}{-3997} \approx 2{,}002

x_1 = \frac{7{,}998 - 4 \times 2{,}002 - 4 \times 0}{-0{,}002} = \frac{-0{,}010}{-0{,}002} = 5{,}000

Solution sans pivotage : $x \approx (5{,}000, 2{,}002, 0{,}000)^T$

🚨

Résultat catastrophique !

La solution obtenue $(5{,}000, 2{,}002, 0{,}000)$ est complètement fausse ! La solution exacte est $(1, 1, 1)$ . L'erreur relative sur $x_1$ est de 400% !

Méthode 2 : Avec pivotage partiel

On cherche le plus grand élément (en valeur absolue) dans la première colonne :

Ligne	Élément	Valeur absolue
1	$-0{,}002$	$0{,}002$
2	$-2{,}000$	$2{,}000$
3	$3{,}000$	$3{,}000$ ← maximum

Échange : $R_1 \leftrightarrow R_3$

Après échange :

\left( \begin{array}{ccc|c} 3{,}000 & -4{,}031 & -3{,}112 & -4{,}143 \\ -0{,}002 & 4{,}000 & 4{,}000 & 7{,}998 \\ -2{,}000 & 2{,}906 & -5{,}387 & -4{,}481 \end{array} \right)

Multiplicateurs (maintenant raisonnables) :

m_{21} = \frac{-0{,}002}{3{,}000} \approx -0{,}0007

m_{31} = \frac{-2{,}000}{3{,}000} \approx -0{,}6667

Élimination (première colonne) :

Après élimination et arrondi à 4 chiffres :

\left( \begin{array}{ccc|c} 3{,}000 & -4{,}031 & -3{,}112 & -4{,}143 \\ 0 & 3{,}997 & 3{,}998 & 7{,}995 \\ 0 & 0{,}218 & -7{,}462 & -7{,}243 \end{array} \right)

Deuxième pivot : On cherche le max dans la colonne 2 (lignes 2-3) :

Ligne 2 : $|3{,}997| = 3{,}997$ ← maximum
Ligne 3 : $|0{,}218| = 0{,}218$

Pas d'échange nécessaire.

Élimination (deuxième colonne) :

m_{32} = \frac{0{,}218}{3{,}997} \approx 0{,}0545

Matrice triangulaire finale :

\left( \begin{array}{ccc|c} 3{,}000 & -4{,}031 & -3{,}112 & -4{,}143 \\ 0 & 3{,}997 & 3{,}998 & 7{,}995 \\ 0 & 0 & -7{,}681 & -7{,}681 \end{array} \right)

Substitution arrière :

x_3 = \frac{-7{,}681}{-7{,}681} = 1{,}000

x_2 = \frac{7{,}995 - 3{,}998 \times 1{,}000}{3{,}997} = \frac{3{,}997}{3{,}997} = 1{,}000

x_1 = \frac{-4{,}143 - (-4{,}031) \times 1{,}000 - (-3{,}112) \times 1{,}000}{3{,}000} = \frac{3{,}000}{3{,}000} = 1{,}000

Solution avec pivotage : $x = (1{,}000, 1{,}000, 1{,}000)^T$

✅

Résultat correct !

Avec le pivotage partiel, on obtient la solution exacte $(1, 1, 1)$ malgré l'arithmétique à 4 chiffres !

Comparaison des résultats

Méthode	Solution obtenue	Solution exacte	Erreur relative max
Sans pivotage	$(5{,}000, 2{,}002, 0{,}000)$	$(1, 1, 1)$	400%
Avec pivotage partiel	$(1{,}000, 1{,}000, 1{,}000)$	$(1, 1, 1)$	0%

Pourquoi le pivotage fonctionne-t-il ?

Le problème des petits pivots

Quand le pivot est très petit par rapport aux autres éléments :

Multiplicateurs énormes : $m_{ij} = a_{ij}/a_{kk}$ devient très grand
Amplification des erreurs d'arrondi : Multiplier par un grand nombre amplifie les erreurs
Perte de chiffres significatifs : Les petites quantités sont « absorbées » par les grandes

La solution du pivotage

En choisissant le plus grand pivot possible :

Multiplicateurs bornés : $|m_{ij}| \leq 1$ avec le pivotage partiel
Erreurs contrôlées : Les erreurs d'arrondi ne sont pas amplifiées
Stabilité numérique : Le conditionnement effectif reste raisonnable

💡

Règle pratique

Pivotage partiel : À chaque étape $k$ , chercher le maximum $|a_{ik}|$ pour $i \geq k$ et échanger les lignes. Coût négligeable, gain en stabilité énorme.

Pivotage complet : Chercher le maximum dans toute la sous-matrice restante. Plus coûteux mais parfois nécessaire pour des matrices très mal conditionnées.

Résumé

Type de pivotage	Recherche du pivot	Coût	Usage
Aucun	Utilise $a_{kk}$ directement	$0$	Jamais en pratique
Partiel	Max dans la colonne $k$	$O(n^2)$	Standard (défaut)
Complet	Max dans la sous-matrice	$O(n^3)$	Matrices très mal conditionnées

À retenir : Le pivotage partiel est toujours utilisé en pratique. Son coût est négligeable par rapport au gain en stabilité numérique. Les bibliothèques comme NumPy (np.linalg.solve) et LAPACK l'utilisent systématiquement.