Choleského dekompozice

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

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 faktor matice A.

Využití[editovat | editovat zdroj]

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

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[editovat | editovat zdroj]

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í soustavy L X = I, kde I je jednotková matice, pak X = L-1.

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

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

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

 \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č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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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