Choleského dekompozice

Z Wikipedie, otevřené encyklopedie

Choleského dekompozice (také Choleského rozklad) je metoda rozložení 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 transpozicí matice druhé.

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

Obsah

[editovat] Využití

[editovat] Výpočet inverzní matice

Inverzní matici A-1 lze vypočítat z inverzní matice L-1 podle následujícího vztahu.

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

Samotný výpočet inverzní matice L-1 není příliš obtížný, neboť to je také dolní trojúhelníková matice a lze ji vypočítat užitím vztahu 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}

[editovat] Ř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é.

[editovat] 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_{kk} - \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];
  }
}