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

1 Využití
- 1.1 Výpočet inverzní matice
- 1.2 Řešení soustavy lineárních rovnic
2 Algoritmus rozkladu

[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];
  }
}

Citováno z „http://cs.wikipedia.org../../../c/h/o/Cholesk%C3%A9ho_dekompozice.html“

Kategorie: Numerická matematika