Choleského dekompozice

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

Dolní trojúhelníková matice L z tohoto rozkladu se nazývá Choleského faktor matice A. Dekompozice je pojmenována po francouzském matematikovi André-Louisovi Choleském (1875–1918).

VyužitíEditovat

Řešení soustavy lineárních rovnicEditovat

Soustavu lineárních rovnic Ax = b lze řešit převodem na dvě soustavy rovnic.

 
 

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

Je-li matice A malá, lze pomocí Choleského rozkladu spočítat inverzní matici A−1 užitím vztahu

 

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.

 

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

 

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

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

 
 
 
 

Pro druhý sloupec platí:

 
 
 
 

Pro prvky na diagonále lze, vzhledem ke znalosti celého řádku vlevo od prvku, odvodit následující vzorec.

 

Pro prvky pod diagonálou lze odvodit následující vztah.

 

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é vlastnostiEditovat

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