Choleského dekompozice

Technology

12 hours ago

Author

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á).

:\mathbf A = \mathbf L \cdot \mathbf L^H\qquad \mathbf A = \mathbf L \cdot \mathbf L^T

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í

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

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

:\mathbf L \mathbf y = \mathbf b :\mathbf L^T \mathbf x = \mathbf 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

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

:\mathbf A^{-1} = {\left(\mathbf L^{-1}\right)}^T \cdot \mathbf 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čí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í.

: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=0; i--) sum += sqr(L[c][i]); L[c][c] = sqrt(A[c][c] - sum); for (r=c+1; r=0; i--) sum += L[r][i]*L[c][i]; L[r][c] = (A[r][c] - sum) / L[c][c]; } }