Analisi del codice e costo computazionale

Cerchiamo adesso di dare una spiegazione del codice appena visto. Come si vede dall'introduzione teorica, durante il passo j-esimo sia per il calcolo di $d_j$ che degli $l_{ij}$ $(i>j)$ viene utilizzata la quantità $l_{jk}d_k$ all'interno di una sommatoria per $k=1, \cdots, j-1$; risulta perciò utile memorizzare questi valori in una forma comoda per il calcolo della sommatoria, e questa forma ci viene fornita dall'algebra lineare: se si memorizzasse, per esempio per il calcolo di $d_j$, gli elementi $l_{jk}$ in un vettore riga e il fattore $l_{jk}d_k$ in un vettore colonna (chiamato da qui in avanti $v$), e se ne facesse il prodotto scalare quello che si otterrebbe sarebbe proprio la sommatoria da sottrarre ad $a_{ij}$:

$$d_j = a_{jj}-\sum_{k=1}^{j-1} (l_{jk})(l_{jk}d_k)$$

$$(l_{j1}, \cdots , l_{jk}) \left( \begin{array}{c} l_{j1}d... ...\cdots + l_{jk}l_{jk}d_k = \sum_{k=1}^{j-1} {(l_{jk})}^2d_k$$

proprio quello che stavamo cercando. Ma come costruire $v$? Gli elementi $l_{jk}$ sono gli elementi $a_{jk}$ e quindi $A(j,1:j-1)$, mentre gli elementi $d_k$ sono la diagonale della matrice $A(1:j-1, 1:j-1)$, facendo il prodotto di queste due quantità si ottiene un vettore riga, facendone il trasposto otteniamo il vettore che cercavamo; quanto descritto viene eseguito nella riga $(1)$. Ora che abbiamo ottenuto il vettore $v$ possiamo calcolare l'elemento $d_j$ tramite la riga $(2)$:

$$d_j \equiv A(j,j)=A(j,j)-\underbrace{A(j,1:j-1)*v}_{\sum_{k=1}^{j-1} {(l_{jk})}^2d_k}\mbox{.}$$

Per il calcolo della j-esima colonna di $L$ seguiamo le indicazioni che ci vengono della teoria che tradotte in codice portano alla riga $(3)$:

$$A(j+1:n,j)=(\underbrace{A(j+1:n,j)}_{a_{ij}}-\overbrace{\unde... ... {\sum_{k=1}^{j-1} l_{ik}l_{jk}d_k})/\underbrace{A(j,j)}_{d_j}$$