Decomposizione di Cholesky

Da Wikipedia, l'enciclopedia libera.
(Reindirizzamento da Fattorizzazione 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[modifica | modifica wikitesto]

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[modifica | modifica wikitesto]

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[modifica | modifica wikitesto]

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[modifica | modifica wikitesto]

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[modifica | modifica wikitesto]

  • (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[modifica | modifica wikitesto]

matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica