Analisi dell'algoritmo e costo computazionale

Come si vede nel codice sopra abbiamo introdotto la quantità $\beta$ per un fatto di efficienza: infatti quello che vogliamo rappresentare è

\begin{displaymath}\frac{2}{v^Tv}\end{displaymath}

che sappiamo essere uno scalare. Tramite alcuni passi algebrici si giunge al risultato che

\begin{displaymath}\beta = \frac{2}{v^Tv} = \frac{\vert x_1\vert + \vert\alpha\vert}{\vert\alpha\vert}
\rightarrow \frac{s*v_1}{\alpha}\end{displaymath}

e l'aver introdotto questo fattore ci consente di spezzare il calcolo del prodotto tra la matrice di Householder e la matrice $A$ in modo da ridurre la complessità: infatti calcolando esplicitamente $vv^T$ avremmo ottenuto una matrice, che moltiplicata per $A$ avrebbe aumentato considerevolmente la complessità dell'algoritmo; in questo modo riusciamo a calcolarci $\beta v$ e successivamente $v^TA$ che è un vettore e quindi vanno a moltiplicarsi due vettori, un costo decisamente minore del prodotto matrice-matrice.

Per quanto riguarda il costo computazionale dividiamo il calcolo per le righe significative:

(1) si calcola una norma su un vettore di lunghezza $m-i+1$ che prevede il quadrato di ogni componente, la loro somma ed infine estrarne la radice quadrata: un totale di $2(m-i+1)+1$ flops;
(2) si eseguono $m-i$ divisioni;
(3) la parte più corposa dell'algoritmo si trova qua dentro, infatti vengono eseguite circa $4(m-i)(n-i)$ flops, metà per il calcolo di $v^TA$ e le altre per l'aggiornamento della matrice.

Allora, sommando su $i$ il costo della riga $(3)$ si ottiene

\begin{displaymath}\sum_{i=1}^n 4(m-i)(n-i) \approx \frac{4}{3} (n^3+
\frac{3}{2}n^2(m-n))\end{displaymath}

che nel caso quadrato $m=n$ diventa un costo proporzionale a $\frac{4}{3} n^3$, non proprio l'ideale per risolvere sistemi lineari.

Morpheus 2004-01-04