Synthèse

Vue d’ensemble

La synthèse est organisée par grands thèmes plutôt que par CM. La structure reste volontairement flexible : les chapitres pourront être ajoutés, fusionnés, déplacés ou retirés à mesure que le cours 2026–2027 se précise.

1. Systèmes linéaires et méthodes directes

Élimination de Gauss

Le problème de départ est la résolution d’un système

$$Ax=b.$$

L’élimination de Gauss transforme progressivement $A$ en une matrice triangulaire supérieure $U$ en annulant les coefficients sous les pivots. Les opérations sur les lignes peuvent être représentées par des matrices élémentaires.

À l’étape $k$, une transformation de Gauss s’écrit

$$G_k=I-w_ke_k^T,$$

où $w_k$ contient les multiplicateurs utilisés pour éliminer les coefficients sous le pivot.

L’idée importante n’est pas seulement de trianguler $A$ : les transformations successives expliquent directement la factorisation LU.

Factorisation LU

Si tous les pivots nécessaires sont non nuls,

$$G_{n-1}\cdots G_2G_1A=U.$$

En inversant les transformations,

$$A=F_1F_2\cdots F_{n-1}U=LU, \qquad F_k=G_k^{-1}.$$

$L$ est triangulaire inférieure à diagonale unité et contient les multiplicateurs de l’élimination ; $U$ est triangulaire supérieure.

En pratique, la factorisation peut être stockée in-place : la partie strictement inférieure de la matrice contient les coefficients de $L$, tandis que la diagonale et la partie supérieure contiennent $U$. La diagonale unité de $L$ n’est pas stockée.

Pivotage et permutations

Une matrice inversible peut avoir un pivot nul pendant l’élimination. L’inversibilité de $A$ ne suffit donc pas à garantir que LU sans permutation fonctionne.

Le pivotage partiel choisit à l’étape $k$

$$p=\arg\max_{i=k,\ldots,n}|a_{ik}|$$

puis échange les lignes $k$ et $p$.

On obtient alors

$$PA=LU.$$

Le pivotage partiel garantit également que les multiplicateurs satisfont

$$|\ell_{ik}|\le 1.$$

Cette propriété limite la croissance provoquée par l’élimination et joue un rôle central dans sa stabilité numérique.

Méthode — construire $LU$ avec Gauss et pivotage partiel

À chaque colonne $k$, on applique toujours la même procédure :

1. Choisir le pivot dans la colonne $k$ :

$$p=\arg\max_{i=k,\ldots,n}|a_{ik}|.$$

Si $p\neq k$, échanger les lignes $k$ et $p$. Les échanges successifs sont enregistrés dans $P$.

2. Calculer un multiplicateur pour chaque ligne sous le pivot :

$$\ell_{ik}=\frac{a_{ik}}{a_{kk}},\qquad i>k.$$

3. Éliminer le coefficient sous le pivot :

$$R_i\leftarrow R_i-\ell_{ik}R_k.$$

4. Ne pas jeter les multiplicateurs. Une fois la colonne $k$ éliminée, ranger chaque $\ell_{ik}$ à la position $(i,k)$ de $L$. On fait cela colonne après colonne. La diagonale de $L$ vaut $1$ :

$$L= \begin{pmatrix} 1&0&\cdots&0\\ \ell_{21}&1&&\vdots\\ \ell_{31}&\ell_{32}&\ddots&0\\ \vdots&\vdots&\ddots&1 \end{pmatrix}.$$

La matrice obtenue après les éliminations est $U$.

Avec pivotage, le résultat est

$$PA=LU.$$

Le point essentiel est donc : LU = élimination de Gauss + conservation des multiplicateurs. En stockage in-place, on ne construit même pas deux matrices séparées : les $\ell_{ik}$ remplacent les coefficients éliminés sous la diagonale, tandis que la diagonale et la partie supérieure contiennent $U$.

Lors d’un échange de lignes à une étape ultérieure, les multiplicateurs déjà stockés dans les colonnes précédentes doivent suivre les lignes échangées.

Code C — LU in-place avec pivotage partiel

Le code du cours traduit directement la méthode précédente : recherche du pivot, échange des lignes, calcul de $\ell_{ik}$, puis élimination.

#include <math.h>

int LU_DecompositionPartialPivoting(FullMatrix *A) {
    if (A == NULL || A->m != A->n || A->n <= 0)
        return -1;

    const int n = A->n;

    for (int k = 0; k < n - 1; ++k) {
        int p = k;
        double maxPivot = fabs(FM(A, k, k));

        for (int i = k + 1; i < n; ++i) {
            const double candidate = fabs(FM(A, i, k));
            if (candidate > maxPivot) {
                maxPivot = candidate;
                p = i;
            }
        }

        if (maxPivot == 0.0) return -1;

        swapRows(A, k, p);

        const double akk = FM(A, k, k);

        for (int i = k + 1; i < n; ++i) {
            FM(A, i, k) /= akk;  // stocke l_ik

            for (int j = k + 1; j < n; ++j)
                FM(A, i, j) -= FM(A, i, k) * FM(A, k, j);
        }
    }

    return FM(A, n - 1, n - 1) == 0.0 ? -1 : 0;
}

Résolution triangulaire

Une fois $A=LU$ connue, résoudre

$$Ax=b$$

revient à effectuer deux résolutions triangulaires :

$$Ly=b, \qquad Ux=y.$$

La première utilise une substitution avant et la seconde une substitution arrière.

Avec pivotage, $PA=LU$, donc le second membre doit lui aussi être permuté :

$$Ly=Pb,\qquad Ux=y.$$

Coût des méthodes directes

Pour une matrice dense $n\times n$, la factorisation LU demande

$$N_{\mathrm{flop}} =\frac{n(n-1)(4n+1)}{6} =\frac23n^3+O(n^2).$$

Chaque résolution triangulaire coûte $O(n^2)$. Ainsi, si plusieurs systèmes possèdent la même matrice $A$ mais des seconds membres différents, on factorise $A$ une seule fois puis on réutilise $L$ et $U$.

2. Arithmétique flottante, conditionnement et stabilité

Représentation en virgule flottante

En IEEE 754 binary64 (double), un nombre normalisé possède 53 bits de précision significative. L’espacement immédiatement au-dessus de 1 vaut

$$\varepsilon=2^{-52}\approx2.22\times10^{-16},$$

tandis que l’unit roundoff pour l’arrondi au plus proche est

$$u=2^{-53}\approx1.11\times10^{-16}.$$

Modèle d’erreur d’arrondi

Pour une opération élémentaire et en l’absence d’overflow ou d’underflow,

$$\operatorname{fl}(a\circ b)=(a\circ b)(1+\delta), \qquad |\delta|\le u.$$

Une élimination correcte en arithmétique exacte peut donc se comporter différemment en machine. En particulier, un pivot très petit peut produire un multiplicateur énorme et amplifier les effets des arrondis.

Conditionnement d’un système linéaire

Pour $Ax=b$, en gardant $b$ fixe et en perturbant $A$ de $\Delta A$, l’analyse au premier ordre donne

$$\Delta x\approx-A^{-1}\Delta A\,x.$$

D’où

$$\frac{\|\Delta x\|}{\|x\|} \lesssim \kappa(A) \frac{\|\Delta A\|}{\|A\|},$$

avec

$$\boxed{\kappa(A)=\|A\|\,\|A^{-1}\|}.$$

Attention :

$$AA^{-1}=I,$$

mais le nombre de condition utilise le produit des normes

$$\|A\|\,\|A^{-1}\|,$$

et non la norme du produit $\|AA^{-1}\|$. En général,

$$\|AA^{-1}\|\le \|A\|\,\|A^{-1}\|,$$

donc, pour les normes matricielles usuelles, $\kappa(A)\ge 1$.

Le conditionnement est une propriété du problème : un grand $\kappa(A)$ signifie qu’une petite perturbation des données peut provoquer une grande variation de la solution.

Erreur backward et erreur forward

En arithmétique flottante, les facteurs calculés par LU vérifient

$$\widehat L\widehat U=PA+\Delta A.$$

Le backward error mesure donc la perturbation $\Delta A$ nécessaire pour interpréter le résultat calculé comme la solution exacte d’un problème voisin.

L’erreur forward mesure directement l’écart entre la solution calculée $\widehat x$ et la solution exacte $x$.

Schématiquement,

$$\text{forward error} \approx \text{conditionnement} \times \text{backward error}.$$

Ainsi, un algorithme peut être numériquement stable tout en donnant une solution peu précise si le problème lui-même est mal conditionné.

Stabilité de l’élimination de Gauss

Sans pivotage, un petit pivot peut créer des multiplicateurs très grands et conduire à une forte perte de précision.

Avec pivotage partiel, $|\ell_{ik}|\le1$. La croissance des coefficients de $U$ est mesurée par le growth factor

$$\rho=\frac{\|\widehat U\|_{\max}}{\|A\|_{\max}}.$$

Le backward error dépend notamment de ce facteur. Le cours donne la borne de Wilkinson

$$\rho\le2^{n-1},$$

qui peut être atteinte dans le pire cas. Cette borne est pessimiste mais montre que le pivotage partiel ne donne pas une garantie absolue contre toute croissance.

3. Matrices creuses

Sparsité et structure

Bande d’une matrice

Formats COO et CSR

Stockage et coût

4. Factorisations creuses et réordonnancement

Fill-in

Interprétation par graphe

Factorisation symbolique et numérique

Réordonnancement

5. Factorisations pour matrices structurées

Cholesky et LDLT

6. Moindres carrés et factorisation QR

Problème des moindres carrés

Factorisation QR

7. Valeurs propres

8. SVD et approximation de rang faible

Décomposition en valeurs singulières

Approximation de rang faible

Définitions et résultats essentiels

Méthodes et pièges fréquents