C++ Bc. 33: Porovnání verzí
m + link |
mBez shrnutí editace |
||
| (Není zobrazeno 10 mezilehlých verzí od 2 dalších uživatelů.) | |||
| Řádek 1: | Řádek 1: | ||
;[http://en.wikipedia.org/wiki/Cholesky_decomposition Choleskyho rozklad] | |||
Napište funkci, která počítá | Napište funkci, která počítá ''Choleskyho rozklad'' pozitivně semidefinitní matice. | ||
pozitivně semidefinitní matice | |||
Matice <math>\mathbf A</math> je pozitivně definitní, pokud pro každý nenulový vektor <math>\mathbf x</math> platí <math>\mathbf x^t \mathbf A \mathbf x > 0 | Matice <math>\mathbf A</math> je pozitivně definitní, pokud pro každý nenulový vektor <math>\mathbf x</math> platí <math>\mathbf x^t \mathbf A \mathbf x > 0</math>. Pro každou pozitivně definitní matici existuje jednoznačný symetrický rozklad (Choleskyho rozklad) <math>\mathbf A = \mathbf L \mathbf L^t,</math> kde <math>\mathbf L</math> je dolní trojúhelníková matice. Například | ||
<math>\begin{pmatrix} | <math>\begin{pmatrix} | ||
| Řádek 29: | Řádek 26: | ||
0 & 0 & 0 & 0 & 1 | 0 & 0 & 0 & 0 & 1 | ||
\end{pmatrix} | \end{pmatrix} | ||
</math> | </math> | ||
| Řádek 36: | Řádek 32: | ||
<math> | <math> | ||
\mathbf A = \mathbf A^{(1)} = \begin{pmatrix} | \mathbf A = \mathbf A^{(1)} = \begin{pmatrix} | ||
a_{11} & a_{*1}^t \\ | a_{11} & \mathbf a_{*1}^t \\ | ||
a_{*1} & A^{(2)} | \mathbf a_{*1} & \mathbf A^{(2)} | ||
\end{pmatrix} | \end{pmatrix} | ||
\longrightarrow | \longrightarrow | ||
\begin{pmatrix} | \begin{pmatrix} | ||
\sqrt{a_{11}} & 0 \\ | \sqrt{a_{11}} & \mathbf 0 \\ | ||
b_{*1} | \mathbf b_{*1} & \mathbf B^{(2)} | ||
\end{pmatrix},</math> | \end{pmatrix},</math> | ||
kde <math>b_{*1} = {1\over \sqrt{a_{11}}} a_{*1}</math> (tj. prvky pod diagonálou vydělíme odmocninou z | kde <math>\mathbf b_{*1} = {1\over \sqrt{a_{11}}} \mathbf a_{*1}</math> (tj. prvky pod diagonálou vydělíme odmocninou z diagonálního prvku) a | ||
<math>\mathbf B^{(2)} = \mathbf A^{(2)} - b_{*1}b_{*1}^t</math>. V našem příkladu tedy | <math>\mathbf B^{(2)} = \mathbf A^{(2)} - \mathbf b_{*1} \mathbf b_{*1}^t</math>. V našem příkladu tedy | ||
<math>\mathbf B^{(2)} = | <math>\mathbf B^{(2)} = | ||
\begin{pmatrix} | \begin{pmatrix} | ||
169 & 143 & 104 & 52 \\ | |||
\ | 143 & 221 & 158 & 74 \\ | ||
104 & 158 & 149 & 65 \\ | |||
52 & 74 & 65 & 30 | |||
\ | \end{pmatrix} = | ||
\end{pmatrix} | \begin{pmatrix} | ||
</math> | 365 & 311 & 230 & 122 \\ | ||
311 & 365 & 266 & 134 \\ | |||
230 & 266 & 230 & 110 \\ | |||
122 & 134 & 110 & 55 | |||
\end{pmatrix} - | |||
\begin{pmatrix} | |||
14\times14 & 14\times12 & 14\times9 & 14\times5 \\ | |||
12\times14 & 12\times12 & 12\times9 & 12\times5 \\ | |||
9\times14 & 9\times12 & 9\times9 & 9\times5 \\ | |||
5\times14 & 5\times12 & 5\times9 & 5\times5 | |||
\end{pmatrix}. | |||
</math> | |||
Submatice <math>\mathbf B^{(2)}</math> je také pozitivně definitní a stejným způsobem můžeme vypočítat druhý sloupec Choleskyho rozkladu a obdobně i zbývající sloupce. | |||
Explicitní vzorce pro výpočet koeficentů matice <math>\mathbf L</math> Choleskyho rozkladu jsou | |||
<math> l_{i,j} = \frac{1}{l_{j,j}} \left( a_{i,j} - \sum_{k=1}^{j-1} l_{i,k} l_{j,k} \right), \qquad\mbox{pro } i>j. </math> | |||
<math> l_{i,i} = \sqrt{ a_{i,i} - \sum_{k=1}^{i-1} l_{i,k}^2 }. </math> | |||
Aktuální verze z 15. 1. 2009, 16:09
Napište funkci, která počítá Choleskyho rozklad pozitivně semidefinitní matice.
Matice je pozitivně definitní, pokud pro každý nenulový vektor platí . Pro každou pozitivně definitní matici existuje jednoznačný symetrický rozklad (Choleskyho rozklad) kde je dolní trojúhelníková matice. Například
První sloupec Choleskyho rozkladu můžeme vypočítat jako
kde (tj. prvky pod diagonálou vydělíme odmocninou z diagonálního prvku) a . V našem příkladu tedy
Submatice je také pozitivně definitní a stejným způsobem můžeme vypočítat druhý sloupec Choleskyho rozkladu a obdobně i zbývající sloupce.
Explicitní vzorce pro výpočet koeficentů matice Choleskyho rozkladu jsou
