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:

$𝐀=𝐋{𝐋}^{*}(𝐀\in {𝕂}^{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:

$𝐀=𝐋{𝐋}^T(𝐀\in {ℝ}^{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:

${𝐀}^{(1)}:=𝐀$

${𝐀}^{(i)}:=\left(\begin{array}{cc}{a}_{i,i}& {𝐛}_i^{*}\\ {𝐛}_i& {𝐁}^{(i)}\end{array}\right)$

${𝐋}_i:=\left(\begin{array}{cc}\frac{1}{\sqrt{a_{i,i}}}& 0\\ -\frac{1}{a_{i,i}}{𝐛}_i& 𝐈\end{array}\right)$

${𝐀}^{(i)}:={𝐋}_i^{-1}\left(\begin{array}{cc}1& 0\\ 0& {𝐁}^{(i)}-\frac{1}{a_{i,i}}{𝐛}_i{𝐛}_i^{*}\end{array}\right)({𝐋}_i^{-1}{)}^{*}$

Si definisce per i successivi $i$:

${𝐀}^{(i+1)}:={𝐁}^{(i)}-\frac{1}{a_{i,i}}{𝐛}_i{𝐛}_i^{*}$

in modo che:

${𝐀}^{(i)}={𝐋}_i^{-1}\left(\begin{array}{cc}1& 0\\ 0& {𝐀}^{(i+1)}\end{array}\right)({𝐋}_i^{-1}{)}^{*}$

La ricorsione termina dopo n passi dove $A^{(n)}=1$. Si vede che la matrice triangolare inferiore $L$ è calcolata come:

$𝐋:={𝐋}_1{𝐋}_2\dots {𝐋}_n$

Algoritmo di Cholesky Banachiewicz

LTemplate:'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:

$\mathrm{\forall }i=1,\dots ,m$
    $\mathrm{\forall }j=1,\dots ,(i-1)$
      $l_{i,j}=\frac{1}{l_{j,j}}(a_{i,j}-\sum _{\iota =1}^{j-1}{l}_{i,\iota }{l}_{j,\iota })$
    $l_{i,i}=\sqrt{a_{i,i}-\sum _{k=1}^{i-1}{l}_{i,k}^2}.$

Algoritmo di Cholesky-Crout

LTemplate:'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:

 $\mathrm{\forall }i=1,\dots ,m$
   $l_{i,i}=\sqrt{a_{i,i}-\sum _{k=1}^{i-1}{l}_{i,k}^2}.$
   $\mathrm{\forall }j=(i+1),\dots ,m$
     $l_{j,i}=\frac{1}{l_{i,i}}(a_{j,i}-\sum _{\iota =1}^{i-1}{l}_{j,\iota }{l}_{i,\iota })$

Esempio

Un esempio pratico per una decomposizione di Cholesky di una matrice 2x2:

$A=\left[\begin{array}{cc}a& b\\ b& d\end{array}\right]$

$A=P{P}^{\prime }$

$P=\left[\begin{array}{cc}\sqrt{a}& 0\\ \frac{b}{\sqrt{a}}& \sqrt{d-\frac{b^2}{a}}\end{array}\right]$

Bibliografia

• Template:En S. J. Julier and J. K. Uhlmann. A General Method for Approximating Nonlinear Transformations of ProbabilityDistributions.
• Template: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