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.



Morpheus 2004-01-04