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á).
Dolní trojúhelníková matice L z tohoto rozkladu se nazývá Choleského faktor matice A.
Využití
Řešení soustavy lineárních rovnic
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í matice
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č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
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é vlastnosti
Choleského rozklad je bezpodmínečně zpětně stabilní.