$$\newcommand{\mtn}{\mathbb{N}}\newcommand{\mtns}{\mathbb{N}^*}\newcommand{\mtz}{\mathbb{Z}}\newcommand{\mtr}{\mathbb{R}}\newcommand{\mtk}{\mathbb{K}}\newcommand{\mtq}{\mathbb{Q}}\newcommand{\mtc}{\mathbb{C}}\newcommand{\mch}{\mathcal{H}}\newcommand{\mcp}{\mathcal{P}}\newcommand{\mcb}{\mathcal{B}}\newcommand{\mcl}{\mathcal{L}} \newcommand{\mcm}{\mathcal{M}}\newcommand{\mcc}{\mathcal{C}} \newcommand{\mcmn}{\mathcal{M}}\newcommand{\mcmnr}{\mathcal{M}_n(\mtr)} \newcommand{\mcmnk}{\mathcal{M}_n(\mtk)}\newcommand{\mcsn}{\mathcal{S}_n} \newcommand{\mcs}{\mathcal{S}}\newcommand{\mcd}{\mathcal{D}} \newcommand{\mcsns}{\mathcal{S}_n^{++}}\newcommand{\glnk}{GL_n(\mtk)} \newcommand{\mnr}{\mathcal{M}_n(\mtr)}\DeclareMathOperator{\ch}{ch} \DeclareMathOperator{\sh}{sh}\DeclareMathOperator{\th}{th} \DeclareMathOperator{\vect}{vect}\DeclareMathOperator{\card}{card} \DeclareMathOperator{\comat}{comat}\DeclareMathOperator{\imv}{Im} \DeclareMathOperator{\rang}{rg}\DeclareMathOperator{\Fr}{Fr} \DeclareMathOperator{\diam}{diam}\DeclareMathOperator{\supp}{supp} \newcommand{\veps}{\varepsilon}\newcommand{\mcu}{\mathcal{U}} \newcommand{\mcun}{\mcu_n}\newcommand{\dis}{\displaystyle} \newcommand{\croouv}{[\![}\newcommand{\crofer}{]\!]} \newcommand{\rab}{\mathcal{R}(a,b)}\newcommand{\pss}[2]{\langle #1,#2\rangle} $$
Bibm@th

Décomposition de Cholesky et de Crout

Théorème (décomposition de Cholesky) : Soit $A$ une matrice symétrique définie positive. Alors il existe une matrice triangulaire inférieure $L$ telle que $A=LL^T$. De plus, si on impose aux coefficients diagonaux de $L$ d'être strictement positifs, cette factorisation est unique.

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.$$

Consulter aussi...
Recherche alphabétique
Recherche thématique