Décomposition de Cholesky et de Crout
La décomposition de Cholesky est notamment utilisée pour résoudre des systèmes linéaires. Plutôt que de résoudre $Ax=y$, on résout les deux systèmes triangulaires $Lz=y$ et $L^Tx=z$.
Algorithme de calcul : Écrivons $A=(a_{i,j})$ et $L=(l_{i,j})$. De l'égalité $A=LL^T$, on déduit que $$a_{i,j}=\sum_{k=1}^n l_{i,k}l_{j,k}=\sum_{k=1}^{\min(i,j)}l_{i,k}l_{j,k}$$ puisque $L$ est triangulaire inférieure. Pour $i=1$, on détermine la première colonne de $L$ en commençant par le coefficient diagonal :
- $j=1$, $a_{1,1}=l_{1,1}l_{1,1}$ d'où $l_{1,1}=\sqrt{a_{1,1}}.$
- $j=2$, $a_{1,2}=l_{1,1}l_{2,1}$ d'où $l_{2,1}=a_{1,2}/l_{1,1}.$
- ...
Si on a déterminé les $i-1$ ières colonnes de $L$, on peut déterminer la $i$-ème en commençant la aussi par le coefficient diagonal :
- $j=i$, $a_{i,i}=l_{i,1}l_{i,1}+l_{i,2}l_{i,2}+\cdots+l_{i,i}l_{i,i},$ d'où $l_{i,i}=\sqrt{a_{i,i}-l_{i,1}^2-\cdots-l_{i,i-1}^2}.$
- $j=i+1$, $a_{i,i+1}=l_{i,1}l_{i+1,1}+\cdots+l_{i,i}l_{i+1,i}$ d'où $$l_{i+1,i}=\frac{a_{i,i+1}-l_{i,1}l_{i+1,1}-\cdots-l_{i,i-1}l_{i+1,i-1}}{l_{i,i}}.$$
- ...
L'inconvénient de la méthode précédente est l'utilisation des racines carrées dans les calculs des coefficients diagonaux de $L,$ qui est source potentielle d'erreurs de calculs numériques. C'est pourquoi on préfère parfois la décomposition de Cholesky alternative ou décomposition de Crout qui consiste à écrire toute matrice symétrique $A$ sous la forme $A=LDL^T$ où $L$ est triangulaire inférieure avec des $1$ sur la diagonale et $D$ est diagonale. Les coefficients sont cette fois calculés par les formules $$d_{i,i}=a_{i,i}-\sum_{k=1}^{i-1}l_{i,k}^2d_{k,k}$$ $$l_{i,j}=\frac{1}{d_{j,j}}\left(a_{i,j}-\sum_{k=1}^{j-1}l_{i,k}l_{j,k}d_{k,k}\right),\ \textrm{pour }i> j.$$