6. Factorisation LU : Pivotage

Objectifs

Modifier la factorisation LU pour prendre en compte le pivot

Principe

Lors du calcul de la factorisation $LU$, le pivot, c’est-à-dire le premier coefficient de la sous-matrice (complément de Schur) $S_{k,k}(0,0)$ peut être nul. Pour obtenir une factorisation LU, une méthode consiste à chercher un coefficient non nul dans cette sous-matrice et à pivoter les lignes et colonnes pour lui donner le rôle de pivot.

Pivotage partiel

Nous faisons ici le choix de chercher le remplaçant du pivot parmi tous les coefficients de la sous-colonne uniquement. Ce nouveau pivot est le coefficient le plus grand (en terme de valeur absolue) et, en cas d’égalité, celui de plus petit indice ligne (i.e le “premier rencontré”). Le pivot n’est recherché que dans la première colonne c’est pourquoi nous parlons de pivotage partiel. Quand le pivot est cherché dans toutes la sous-matrices, nous parlons alors de pivotage complet.

Exemple

Prenons le système linéaire suivant :

$$ \underbrace{\begin{pmatrix} 2&4&1&-3\\\
-1& -2& 2 & 4\\\
4& 2& -3& 5\\\
5& -4& -3& 1 \end{pmatrix}}_{A} X = \underbrace{\begin{pmatrix} 1\\\ 2\\\ 3\\\ 4 \end{pmatrix}}_{b} $$

Effectuons maintenant la factorisation LU de $A$ sur place :

Implémentation

Permutation de lignes : Vecteur et Matrice

Dans les classes Vecteur et Matrice, ajoutez deux méthodes permettant de pivoter intégralement deux lignes de prototype suivant :

void Vecteur::permute(int i, int j);
void Matrice::permute(int i, int j);

LU avec pivot

Implémentez maintenant la factorisation LU avec pivot dont le prototype peut être sous forme :

• D’une méthode de la classe Matrice :

void Matrice::lu_pivot(Vecteur &b);

• D’une fonction hors classe :

void lu_pivot(Matrice &A, Vecteur &b);

L’algorithme ressemble alors au suivant :

Avant chaque factorisation partielle :
  - Vérifier si le pivot est nul (ou proche de zéro !)
    - Si oui :
      - Chercher le pivot (max de la sous-colonne) : sa valeur et son indice ligne
      - Pivoter les deux lignes dans la `Matrice` et dans le `Vecteur` membre de droite
    - Continuer la factorisation (comme précédemment)

if( abs(pivot) < 1e-14)   //Pivot considéré comme nulle