4. Factorisation de Cholesky

Objectifs

1. Calculer la factorisation de Cholesky d’une matrice symétrique définie positive
2. Résoudre le système linéaire une fois la factorisation effectuée

Factorisation de Cholesky

Si $A$ est symétrique définie positive, une alternative à la décomposition $LU$, qui utilise à son avantage les propriétés de $A$ est la décomposition de Cholesky : $$A=L{L}^T,$$ où $L$ est une matrice triangulaire inférieure. Contrairement à la $LU$, la diagonale de la matrice $L$ n’est pas a priori composée uniquement de 1 et, de plus, nous avons $\text{diag}(L)=\text{diag}(U)$.

Pseudo-code

Une version naïve est la suivante. Elle peut être améliorée car certains calculs sont doublées et rendu inutiles du fait que le complément de Schur est lui aussi symétrique et défini positif.

L = 0;
Lt = 0;
S = A;
for k =0:N-1
  // Pivot
  pivot = sqrt(S(k,k))
  // Colonne de L
  L(k,k) = pivot;
  for i = k+1:N-1
    L(i,k) = S(i,k) / pivot;
  // Ligne de Lt
  Lt(k,k) = L(k,k);
  for j = k+1:N-1
    Lt(k,j) = L(j,k);
  // Complément de Schur
  for i = k+1:N-1
    for j = k+1:N-1
      S(i,j) = S(i,j) - L(i,k)*Lt(k,j);

Implémentation

Définissez la fonction suivante qui modifie la matrice $A$ en y stockant les matrices $L$ et $L^T$ (la diagonale étant la même pour les deux) :

void Matrice::decomp_Cholesky();

Validation

Pour la matrice $A$ suivante : $$A=\left(\begin{array}{ccccc}2& -1& 0& 0& 0\\ -1& 2& -1& 0& 0\\ 0& -1& 2& -1& 0\\ 0& 0& -1& 2& -1\\ 0& 0& 0& -1& 2\\ \end{array}\right)$$ La matrice $L$ de la décomposition de Cholesky est donnée par : $$L=\left(\begin{array}{ccccc}1.4142& 0& 0.& 0.& 0\\ -0.7071& 1.2247& 0& 0& 0\\ 0& -0.8165& 1.1547& 0& 0\\ 0& 0& -0.8660& 1.1180& 0\\ 0& 0& 0& -0.8944& 1.0954\end{array}\right)$$