Decomposizione di Cholesky

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

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} \mathbf{L}^{T} \qquad (\mathbf{A} \in \mathbb{R}^{n \times n})$

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^{(n)} =1$. Si vede che la matrice triangolare inferiore $L$ è calcolata come:

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

Algoritmo di Cholesky Banachiewicz

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

$\forall i = 1,\dots,m$
    $\forall j = 1,\dots,(i - 1)$
      $l_{i,j} = \frac{1}{l_{j,j}} \left(a_{i,j} - \sum_{\iota = 1}^{j-1} l_{i,\iota} l_{j,\iota}\right)$
    $l_{i,i} = \sqrt{ a_{i,i} - \sum_{k=1}^{i-1} l_{i,k}^2 }.$

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:

 $\forall i = 1,\dots,m$
   $l_{i,i} = \sqrt{ a_{i,i} - \sum_{k=1}^{i-1} l_{i,k}^2 }.$
   $\forall j = (i+1),\dots,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)$

Bibliografia

• (EN) S. J. Julier and J. K. Uhlmann. A General Method for Approximating Nonlinear Transformations of ProbabilityDistributions.
• (EN) S. J. Julier and J.K. Uhlmann, A new extension of the Kalman filter to nonlinear systems, in Proc. AeroSense: 11th Int. Symp. Aerospace/Defence Sensing, Simulation and Controls, 1997, pp. 182–193.

Voci correlate

• Decomposizione LU
• Decomposizione di una matrice
• Decomposizione QR
• Matrice hermitiana
• Matrice quadrata
• Matrice simmetrica
• Matrice trasposta coniugata
• Matrice triangolare