Analisi dell'algoritmo e costo computazionale

La riga $(1)$ divide gli elementi sottodiagonali per $a_{ii}^{(i)}$, mentre la riga $(2)$ necessita di maggiori chiarimenti. Tale riga modifica gli elementi che si trovano sotto la riga i-esima e a destra della colonna i-esima escluse; vediamo cosa succede nel caso $i=1$: moltiplichiamo $L_1$ ad $A\equiv A^{(1)}$

$$L_1A^{(1)}=(I-g_1e_1^T)A^{(1)}=A^{(1)}-g_1e_1^TA^{(1)}=A^{(1)}-g_1(e_1^TA^{(1)})$$

si nota che $(e_1^TA^{(1)})$ altri non è che la prima riga di $A$, $a^1$, e quindi scriviamo

$$L_1A^{(1)}=A^{(1)}-g_1a^1\mbox{.}$$

Concentriamoci adesso su $g_1a^1$: la matrice che otteniamo dal prodotto ha la prima riga composta di elementi uguali a zero (la prima componente di $g_1$ è nulla) e quindi possiamo considerare $g_1$ dal primo elemento non nullo in poi; inoltre la prima colonna di $g_1a^1$ risulta essere uguale ad $a_1$ dal secondo elemento in poi (il primo è zero): se la matrice così fatta fosse sottratta direttamente ad $A^{(1)}$ teoricamente andrebbe ad azzerare gli elementi sottodiagonali della prima colonna, ma proprio in quelle posizioni abbiamo memorizzato gli elementi non nulli del vettore $g_1$ che quindi verrebbero modificati; possiamo allora limitarci alla porzione suddetta.

Passiamo adesso al costo computazionale: durante il passo i-esimo vengono eseguite:

1. $(n-i)$ operazioni nella riga $(1)$, le divisioni;
   
2. ${(n-i)}^2$ moltiplicazioni ed altrettante sottrazioni per la riga $(2)$ per un totale di $2{(n-i)}^2$ operazioni.

Sommando tra $1$ ed $n-1$ otteniamo

$$\begin{eqnarray*} \sum_{i=1}^{n-1} ((n-i)+2{(n-i)}^2) & = & \sum_{i=1}^{n-1} ... ...+\frac{n(n-1)(2n-1)}{3} \\ \\ & \approx & \frac{2}{3} n^3 \end{eqnarray*}$$

La fattorizzazione ha un costo proporzionale al cubo della dimensione significativa; per risolvere il sistema lineare associato ci sarà anche un costo proporzionale ad $n^2$.