La fattorizzazione di Cholesky decompone una matrice simmetrica definita positiva A come prodotto A = LL^T, dove L è una matrice triangolare inferiore con elementi diagonali positivi. È il metodo diretto più efficiente per questa classe di matrici.
Vedi anche: Decomposizione LU, Legge di Inerzia di Sylvester, Numero di Condizionamento.
Enunciato
Teorema: una matrice A \in M_n(\mathbb{R}) è simmetrica e definita positiva se e solo se esiste un’unica matrice triangolare inferiore L con elementi diagonali positivi tale che:
A = LL^T
La matrice L si chiama fattore di Cholesky di A.
Algoritmo
Gli elementi di L si calcolano colonna per colonna:
L_{ii} = \sqrt{A_{ii} - \sum_{k=1}^{i-1} L_{ik}^2}
L_{ji} = \frac{1}{L_{ii}}\left(A_{ji} - \sum_{k=1}^{i-1} L_{ik} L_{jk}\right) \quad (j > i)
Se in qualsiasi passo si ottiene A_{ii} - \sum_k L_{ik}^2 < 0, la matrice non è definita positiva e la fattorizzazione fallisce — questo è anche un test di definitezza positiva computazionalmente efficiente.
Costo Computazionale
La fattorizzazione di Cholesky richiede circa \frac{n^3}{3} operazioni — metà del costo dell’eliminazione di Gauss (\frac{2n^3}{3}) — e usa solo la parte triangolare della matrice, risparmiando anche memoria.
Per risolvere A\vec{x} = \vec{b} una volta nota L:
- Risolvere L\vec{y} = \vec{b} (sostituzione in avanti): O(n^2)
- Risolvere L^T\vec{x} = \vec{y} (sostituzione all’indietro): O(n^2)
Stabilità Numerica
La fattorizzazione di Cholesky è incondizionatamente stabile per matrici simmetriche definite positive: non richiede pivoting (a differenza dell’eliminazione di Gauss) e gli errori di arrotondamento non si amplificano. Vedi: Virgola Mobile.
Varianti
- Fattorizzazione LDL^T: A = LDL^T con L triangolare inferiore a diagonale unitaria e D diagonale. Applicabile a matrici simmetriche non necessariamente definite positive; evita radici quadrate.
- Fattorizzazione di Cholesky incompleta: usata come precondizionatore per metodi iterativi (IC-CG). Vedi: Gradiente Coniugato.
Applicazioni ingegneristiche
- FEM e analisi strutturale: le matrici di rigidezza globale sono simmetriche definite positive (struttura ben vincolata); Cholesky è il solutore diretto standard nei codici FEM (NASTRAN, Abaqus, Code_Aster).
- Filtro di Kalman: la matrice di covarianza dell’errore è simmetrica definita positiva; la fattorizzazione di Cholesky garantisce stabilità numerica nell’aggiornamento della covarianza (square-root Kalman filter).
- Statistica e machine learning: la generazione di campioni da distribuzioni normali multivariate usa Cholesky: \vec{x} = L\vec{z} con \vec{z} \sim \mathcal{N}(0, I) produce \vec{x} \sim \mathcal{N}(0, \Sigma) con \Sigma = LL^T.
- Ottimizzazione: nei metodi del secondo ordine (Newton), la matrice hessiana è simmetrica; Cholesky verifica la definitezza positiva e risolve il sistema lineare per la direzione di Newton.