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).
Sia
A
{\displaystyle A}
matrice quadrata , hermitiana e definita positiva su campo
K
{\displaystyle K}
A
{\displaystyle A}
A
=
L
L
+
(
A
∈
K
m
×
m
)
{\displaystyle \mathbf {A} =\mathbf {L} \mathbf {L} ^{+}\qquad (\mathbf {A} \in \mathbb {K} ^{m\times m})}
con
L
{\displaystyle L}
matrice triangolare inferiore con elementi diagonali positivi e
L
+
{\displaystyle L^{+}}
coniugata trasposta di
L
{\displaystyle L}
Se la matrice
A
{\displaystyle A}
simmetrica , la coniugata trasposta di
L
{\displaystyle L}
trasposta e la decomposizione si semplifica:
A
=
L
L
T
(
A
∈
R
n
×
n
)
{\displaystyle \mathbf {A} =\mathbf {L} \mathbf {L} ^{T}\qquad (\mathbf {A} \in \mathbb {R} ^{n\times n})}
L'algoritmo di Cholesky , usato per calcolare la matrice di decomposizione
L
{\displaystyle L}
algoritmo di Gauss .
L'algoritmo ricorsivo inizia con il considerare:
A
(
1
)
:=
A
{\displaystyle \mathbf {A} ^{(1)}:=\mathbf {A} }
A
(
i
)
:=
(
a
i
,
i
b
i
∗
b
i
B
(
i
)
)
{\displaystyle \mathbf {A} ^{(i)}:={\begin{pmatrix}a_{i,i}&\mathbf {b} _{i}^{*}\\\mathbf {b} _{i}&\mathbf {B} ^{(i)}\end{pmatrix}}}
L
i
:=
(
1
a
i
,
i
0
−
1
a
i
,
i
b
i
I
)
{\displaystyle \mathbf {L} _{i}:={\begin{pmatrix}{\frac {1}{\sqrt {a_{i,i}}}}&0\\-{\frac {1}{a_{i,i}}}\mathbf {b} _{i}&\mathbf {I} \end{pmatrix}}}
A
(
i
)
:=
L
i
−
1
(
1
0
0
B
(
i
)
−
1
a
i
,
i
b
i
b
i
∗
)
(
L
i
−
1
)
∗
{\displaystyle \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:
A
(
i
+
1
)
:=
B
(
i
)
−
1
a
i
,
i
b
i
b
i
∗
{\displaystyle \mathbf {A} ^{(i+1)}:=\mathbf {B} ^{(i)}-{\frac {1}{a_{i,i}}}\mathbf {b} _{i}\mathbf {b} _{i}^{*}}
in modo che:
A
(
i
)
=
L
i
−
1
(
1
0
0
A
(
i
+
1
)
)
(
L
i
−
1
)
∗
{\displaystyle \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
{\displaystyle A^{(n)}=1}
L
{\displaystyle L}
L
:=
L
1
L
2
…
L
n
{\displaystyle \mathbf {L} :=\mathbf {L} _{1}\mathbf {L} _{2}\dots \mathbf {L} _{n}}
L'algoritmo di Cholesky Banachiewicz dà una formula per calcolare direttamente le entrate della matrice triangolare inferiore
L
{\displaystyle L}
L
{\displaystyle L}
∀
i
=
1
,
…
,
m
{\displaystyle \forall i=1,\dots ,m}
∀
j
=
1
,
…
,
(
i
−
1
)
{\displaystyle \forall j=1,\dots ,(i-1)}
l
i
,
j
=
1
l
j
,
j
(
a
i
,
j
−
∑
ι
=
1
j
−
1
l
i
,
ι
l
j
,
ι
)
{\displaystyle 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
=
a
i
,
i
−
∑
k
=
1
i
−
1
l
i
,
k
2
.
{\displaystyle l_{i,i}={\sqrt {a_{i,i}-\sum _{k=1}^{i-1}l_{i,k}^{2}}}.}
L'algoritmo di Cholesky-Crout fornisce un procedimento un po' differente per calcolare le entrate della matrice triangolare inferiore
L
{\displaystyle L}
L
{\displaystyle L}
∀
i
=
1
,
…
,
m
{\displaystyle \forall i=1,\dots ,m}
l
i
,
i
=
a
i
,
i
−
∑
k
=
1
i
−
1
l
i
,
k
2
.
{\displaystyle l_{i,i}={\sqrt {a_{i,i}-\sum _{k=1}^{i-1}l_{i,k}^{2}}}.}
∀
j
=
(
i
+
1
)
,
…
,
m
{\displaystyle \forall j=(i+1),\dots ,m}
l
j
,
i
=
1
l
i
,
i
(
a
j
,
i
−
∑
ι
=
1
i
−
1
l
j
,
ι
l
i
,
ι
)
{\displaystyle l_{j,i}={\frac {1}{l_{i,i}}}\left(a_{j,i}-\sum _{\iota =1}^{i-1}l_{j,\iota }l_{i,\iota }\right)}
(EN A General Method for Approximating Nonlinear Transformations of ProbabilityDistributions .
(EN 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.
