da Lory314 » 14/06/2013, 17:12
L'algoritmo di Cholesky consente di decomporre una matrice $A$ simmetrica e definita positiva nel prodotto $LL^T$, con $L$ matrice triangolare inferiore. Qual è il vantaggio di tale decomposizione?
Supponiamo che devi risolvere il sistema lineare $Ax=b$; bene, sostituiamo ad $A$ la sua decomposizione e otteniamo
\[
LL^Tx=b
\]
Ora denotiamo con $y=L^Tx$. Otteniamo due sistemi:
\[
Ly=b \\
L^Tx=y
\].
Il primo ha come termine noto $b$, incognita $y$ e matrice dei coefficienti $L$; risolvendo questo sistema trovi $y$ che sarà il termine noto del secondo sistema, da cui poi ricavi $x$ che coincide con la soluzione del tuo sistema originale. Il vantaggio sta nel fatto che questi due sistemi si risolvono molto rapidamente con gli algoritmi di sostituzione in avanti o indietro dato che le matrici sono triangolare.
La matrice $L$ si costruisce procedendo per righe con le formule:
\[
L_{j,j} = \sqrt{A_{j,j} - \sum_{k=1}^{j-1}{L_{j,k}^2}} \\
L_{i,j} = \frac{1}{L_{j,j}}(A_{i,j} - \sum_{k=1}^{j-1}{L_{i,k}L_{j,k}})
\]
Nel tuo esempio, applicando le formule che ti ho scritto dovresti ottenere che
$
L = (( 1 , 0 , 0 ),( 1 , 1 , 0 ),( 1 , 2 , 1 ) )
$
Da qui poi risolvi i sistemi come prima ti ho detto.