Fattorizzazione di Cholesky — ingegnerismo.it

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.