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$$A$ una matrice quadrata, hermitiana e definita positiva su campo $K$$K$; tale $A$$A$ può essere decomposta come:

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

con $L$$L$ matrice triangolare inferiore con elementi diagonali positivi e $L^{+}$$L^{+}$ la matrice coniugata trasposta di $L$$L$.

Se la matrice $A$$A$ è reale e simmetrica, la coniugata trasposta di $L$$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})$${\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$$L$, è una versione modificata dell'algoritmo di Gauss.

L'algoritmo ricorsivo inizia con il considerare:

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

$\mathbf {L} :=\mathbf {L} _{1}\mathbf {L} _{2}\dots \mathbf {L} _{n}$${\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$$L$. Esso inizia formando l'angolo superiore sinistro della matrice $L$$L$ e procede a calcolare la matrice riga per riga:

$\forall i=1,\dots ,m$$\forall i=1,\dots ,m$
    $\forall j=1,\dots ,(i-1)$$\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,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}}}.$$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$$L$. Inizia formando l'angolo superiore sinistro della matrice $L$$L$ e procede a calcolare la matrice colonna per colonna:

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