Choleského dekompozice

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

$\bold A = \bold L \cdot \bold L^H\qquad \bold A = \bold L \cdot \bold L^T$

Dolní trojúhelníková matice L z tohoto rozkladu se nazývá Choleského trojúhelník matice A. Modifikací lze dosáhnout toho, že se touto metodou mohou vypočítávat silně regulární symetrické matice, pouze se musí ve vedlejším poli zaznamenávat, které řádky matice jsou imaginární.

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.

$\bold L \bold y = \bold b$

$\bold L^T \bold x = \bold 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^-1 užitím vztahu

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

Inverzní matice L^-1 je to dolní trojúhelníková matice a lze ji vypočítat například Gaussovou eliminací L^-1 L = E, kde E je jednotková matice.

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

$l_{kk}^{-1} l_{kk} = 1 \ \longrightarrow \ l_{kk}^{-1} = 1 / l_{kk}$

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

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

Je-li matice A tak velká, že ji při výpočtu v počtí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^-1 a A^-1 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í.

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

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

$\ \vdots$

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

Pro druhý sloupec platí:

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

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

$\ \vdots$

$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.

$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.

$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í.