Costo computazionale

Vediamo adesso il costo di questo algoritmo, analizzando le righe significative per la complessità:

$(1)$ viene eseguito un prodotto scalare di dimensione $j-1$, quindi $2(j-1)$ flops;

$(2)$ si esegue una somma ed un prodotto scalare di dimensione $j-1$, quindi ancora $2(j-1)$ flops;

$(3)$ vi sono una somma ed una divisione, due operazioni trascurabili, ma viene anche eseguito un prodotto matrice-vettore di dimensioni $n-j \times j-1$, quindi $2(n-j)(j-1)$.

Sommando il costo del prodotto matrice-vettore (che è predominante sul costo dei prodotti scalari) su $j$ si perviene a:

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

un costo proporzionale al cubo della dimensione significativa, un costo sicuramente importante ma la metà di quello necessario alla fattorizzazione $LU$: il fatto di avere una matrice simmetrica ci consente di ridurre di un fattore $\frac{1}{2}$ il costo della fattorizzazione.