C++ Bc. 33

Choleskyho rozklad

Napište funkci, která počítá choleskyho rozklad pozitivně semidefinitní matice.

Matice $\mathbf {A}$ je pozitivně definitní, pokud pro každý nenulový vektor $\mathbf {x}$ platí $\mathbf {x} ^{t}\mathbf {A} \mathbf {x} >0.$ Pro každou pozitivně definitní matici existuje jednoznačný symetrický rozklad (Choleskyho rozklad) $\mathbf {A} =\mathbf {L} \mathbf {L} ^{t},$ kde $\mathbf {L}$ je dolní trojúhelníková matice. Například

${\begin{pmatrix}225&210&180&135&75\\210&365&311&230&122\\180&311&365&266&134\\135&230&266&230&110\\75&122&134&110&55\\\end{pmatrix}}={\begin{pmatrix}15&0&0&0&0\\14&13&0&0&0\\12&11&10&0&0\\9&8&7&6&0\\5&4&3&2&1\end{pmatrix}}{\begin{pmatrix}15&14&12&9&5\\0&13&11&8&4\\0&0&10&7&3\\0&0&0&6&2\\0&0&0&0&1\end{pmatrix}}$

První sloupec Choleskyho rozkladu můžeme vypočítat jako

$\mathbf {A} =\mathbf {A} ^{(1)}={\begin{pmatrix}a_{11}&a_{*1}^{t}\\a_{*1}&A^{(2)}\end{pmatrix}}\longrightarrow {\begin{pmatrix}{\sqrt {a_{11}}}&0\\b_{*1}&B^{(2)}\end{pmatrix}},$

kde $b_{*1}={1 \over {\sqrt {a_{11}}}}a_{*1}$ (tj. prvky pod diagonálou vydělíme odmocninou z diagonálnho prvku) a $\mathbf {B} ^{(2)}=\mathbf {A} ^{(2)}-b_{*1}b_{*1}^{t}$. V našem příkladu tedy

$\mathbf {B} ^{(2)}={\begin{pmatrix}15&0&0&0&0\\{\underline {14}}&365&311&230&122\\{\underline {12}}&311&365&266&134\\{\underline {9}}&230&266&230&110\\{\underline {5}}&122&134&110&55\\\end{pmatrix}},$ prvky vektoru $b_{*1}$ jsou podtrženy. Submatice $B^{(2)}$ je také pozitivně definitní a stejným způsobem můžeme vypočítat druhý sloupec choleskyho rozkladu a obdobně i zbývající sloupce.

[ Zpět | C++ | Další ]