Decomposizione di Choleski

Da Wikipedia, l'enciclopedia libera.

In algebra lineare la decomposizione di Cholesky è la fattorizzazione di una matrice hermitiana e definita positiva in una matrice triangolare inferiore e nella sua trasposta coniugata. Essa si può considerare come un caso speciale della più generale decomposizione LU. Il nome di questa decomposizione ricorda il matematico francese André-Louis Cholesky (1875-1918).

[modifica] Definizione

Sia A una matrice quadrata, hermitiana e definita positiva su campo K; tale A può essere decomposta come

$\mathbf{A} = \mathbf{L} \mathbf{L}^+ \qquad (\mathbf{A} \in \mathbb{K}^{m \times m})$

con L matrice triangolare inferiore con elementi diagonali positivi e L⁺ la matrice coniugata trasposta di L.

Se la matrice A è reale e simmetrica, la coniugata trasposta di L coincide con la trasposta e la decomposizione si semplifica

$\mathbf{A} = \mathbf{L}^{T} \mathbf{L} \qquad (\mathbf{A} \in \mathbb{R}^{n \times n})$

[modifica] Algoritmo di Cholesky

L'algoritmo di Cholesky , usato per calcolare la matrice di decomposizione L, è una versione modificata dell'algoritmo di Gauss.

L'algoritmo ricorsivo inizia con il considerare

$\mathbf{A}^{(1)} := \mathbf{A}$

$\mathbf{A}^{(i)} = \begin{pmatrix} a_{i,i} & \mathbf{b}_{i}^{*} \\ \mathbf{b}_{i} & \mathbf{B}^{(i)} \end{pmatrix}$

$\mathbf{L}_{i} := \begin{pmatrix} \frac{1}{\sqrt{a_{i,i}}} & 0 \\ - \frac{1}{a_{i,i}} \mathbf{b}_{i} & \mathbf{I} \end{pmatrix}$

$\mathbf{A}^{(i)} := \mathbf{L}_{i}^{-1} \begin{pmatrix} 1 & 0 \\ 0 & \mathbf{B}^{(i)} - \frac{1}{a_{i,i}} \mathbf{b}_{i} \mathbf{b}_{i}^{*} \end{pmatrix} (\mathbf{L}_{i}^{-1})^{*}$

Si definisce per i successivi i:

$\mathbf{A}^{(i + 1)} := \mathbf{B}^{(i)} - \frac{1}{a_{i,i}} \mathbf{b}_{i} \mathbf{b}_{i}^{*}$

in modo che

$\mathbf{A}^{(i)} = \mathbf{L}_{i}^{-1} \begin{pmatrix} 1 & 0 \\ 0 & \mathbf{A}^{(i+1)} \end{pmatrix} (\mathbf{L}_{i}^{-1})^{*}$

La ricorsione termina dopo n passi dove A⁽ⁿ⁾ = 1. Si vede che la matrice triangolare inferiore L è calcolata come

$\mathbf{L} := \mathbf{L}_{1} \mathbf{L}_{2} \dots \mathbf{L}_{n}$

[modifica] Algoritmo di Cholesky Banachiewicz

L'algoritmo di Cholesky Banachiewicz dà una formula per calcolare direttamente le entrate della matrice triagolare inferiore L. Esso inizia formando l'angolo superiore sinistro della matrice L e procede a calcolare la matrice riga per riga.

per i = 1,...,m

per j = 1,...,i

$l_{i,j} = \frac{1}{l_{j,j}} \left(a_{i,j} - \sum_{\iota = 1}^{j-1} l_{i,\iota} l_{j,\iota}\right)$

[modifica] Algoritmo di Cholesky-Crout

L' algoritmo di Cholesky-Crout fornisce un procedimento un po' differente per calcolare le entrate della matrice triangolare inferiore L. Inizia formando l'angolo superiore sinistro della matrice L e procede a calcolare la matrice colonna per colonna.

per i = 1,...,m

per j = i,...,m

$l_{j,i} = \frac{1}{l_{i,i}} \left(a_{j,i} - \sum_{\iota = 1}^{i-1} l_{j,\iota} l_{i,\iota}\right)$