Choleského dekompozice

Choleského dekompozice (také Choleského rozklad) je metoda rozložení hermitovské (tj. v reálných číslech symetrické) pozitivně definitní čtvercové matice A na součin dolní a horní trojúhelníkové matice, přičemž jedna trojúhelníková matice je hermitovsky sdružená k matici druhé (v reálných číslech transponovaná).

${\displaystyle \mathbf {A} =\mathbf {L} \cdot \mathbf {L} ^{H}\qquad \mathbf {A} =\mathbf {L} \cdot \mathbf {L} ^{T}}$

Dolní trojúhelníková matice L z tohoto rozkladu se nazývá Choleského faktor matice A. Dekompozice je pojmenována po francouzském matematikovi André-Louisovi Choleském (1875–1918).

Využití

Řešení soustavy lineárních rovnic

Soustavu lineárních rovnic Ax = b lze řešit převodem na dvě soustavy rovnic.

${\displaystyle \mathbf {L} \mathbf {y} =\mathbf {b} }$

${\displaystyle \mathbf {L} ^{T}\mathbf {x} =\mathbf {y} }$

Vzhledem k tomu, že matice soustavy jsou trojúhelníkové, je řešení uvedených rovnic zpětným dosazením velmi snadné.

Výpočet inverzní matice

Je-li matice A malá, lze pomocí Choleského rozkladu spočítat inverzní matici A⁻¹ užitím vztahu

${\displaystyle \mathbf {A} ^{-1}={\left(\mathbf {L} ^{-1}\right)}^{T}\cdot \mathbf {L} ^{-1}.}$

Inverzní matice L⁻¹ je to dolní trojúhelníková matice a lze ji vypočítat například Gaussovou eliminací soustavy L X = I, kde I je jednotková matice, pak X = L⁻¹.

Pro prvky na hlavní diagonále lze odvodit následující vztah.

${\displaystyle x_{kk}l_{kk}=1\ \longrightarrow \ x_{kk}=1/l_{kk}}$

Prvky pod diagonálou lze počítat postupně zprava doleva následovně.

${\displaystyle \sum _{i=c}^{r}x_{ri}l_{ic}=0\ \longrightarrow \ x_{rc}=-1/l_{cc}\cdot \sum _{i=c+1}^{r}x_{ri}l_{ic}}$

Je-li matice A tak velká, že ji při výpočtu v počítači musíme ukládat v řídkém formátu, pak tento postup použít nelze. Je-li matice A rozumně řídká, pak i Choleského faktor L je řídký, matice L⁻¹ a A⁻¹ jsou zpravidla husté.

Algoritmus rozkladu

Prvky matice L je možné počítat po sloupcích zleva a v každém sloupci odshora dolů.

Pro první sloupec platí následující.

${\displaystyle a_{11}=l_{11}l_{11}\ \longrightarrow \ l_{11}={\sqrt {a_{11}}}}$

${\displaystyle a_{21}=l_{21}l_{11}\ \longrightarrow \ l_{21}=a_{21}/l_{11}}$

${\displaystyle \ \vdots }$

${\displaystyle a_{n1}=l_{n1}l_{11}\ \longrightarrow \ l_{n1}=a_{n1}/l_{11}}$

Pro druhý sloupec platí:

${\displaystyle a_{22}=l_{21}l_{21}+l_{22}l_{22}\ \longrightarrow \ l_{22}={\sqrt {a_{22}-l_{21}^{2}}}}$

${\displaystyle a_{32}=l_{31}l_{21}+l_{32}l_{22}\ \longrightarrow \ l_{32}=\left(a_{32}-l_{31}l_{21}\right)/l_{22}}$

${\displaystyle \ \vdots }$

${\displaystyle a_{n2}=l_{n1}l_{21}+l_{n2}l_{22}\ \longrightarrow \ l_{n2}=\left(a_{n2}-l_{n1}l_{21}\right)/l_{22}}$

Pro prvky na diagonále lze, vzhledem ke znalosti celého řádku vlevo od prvku, odvodit následující vzorec.

${\displaystyle a_{kk}=\sum _{i=1}^{k}l_{ki}^{2}\ \longrightarrow \ l_{kk}={\sqrt {a_{kk}-\sum _{i=1}^{k-1}l_{ki}^{2}}}}$

Pro prvky pod diagonálou lze odvodit následující vztah.

${\displaystyle a_{rc}=\sum _{i=1}^{c}l_{ri}l_{ci}\ \longrightarrow \ l_{rc}=\left(a_{rc}-\sum _{i=1}^{c-1}l_{ri}l_{ci}\right)/l_{cc}}$

V jazyku C lze uvedený postup zapsat následovně.

for (c=0; c<n; c++) {
  for (sum=0, i=c-1; i>=0; i--)
    sum += sqr(L[c][i]);
  L[c][c] = sqrt(A[c][c] - sum);
  for (r=c+1; r<n; r++) {
    for (sum=0, i=c-1; i>=0; i--)
      sum += L[r][i]*L[c][i];
    L[r][c] = (A[r][c] - sum) / L[c][c];
  }
}

Numerické vlastnosti

Choleského rozklad je bezpodmínečně zpětně stabilní.

Zdroj