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

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_{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];
  }
}

Choleského dekompozice

Z Wikipedie, otevřené encyklopedie

Obsah

[editovat] Využití

[editovat] Výpočet inverzní matice

[editovat] Řešení soustavy lineárních rovnic

[editovat] Algoritmus rozkladu

Zobrazení

Osobní nástroje

Hledání

Navigace

Nástroje

V jiných jazycích