Complessità algoritmo decomposizione LU

[raff5184]

non ho capito il seguente passaggio:
"il problema del calcolo della matrice inversa.
$A*X=I$, I matrice identità
Trovare X. Decomponendo X come vettore riga di n vettori ottengo un sistema di n sistemi di equazioni del tipo $A*x=b$ per cui essendo la complessità di un singolo problema pari a $n^3$ avendo n sistemi ho una complessità di $n^4$, fin qui ok!

Ma x ciascun problema sfrutto la decomposizione LU riducendo la complessità da $n^4$ a $n^3$. [Ora inizia a diventare poco chiaro.] Con la decomposizione LU un sistema $A*x=b$ diventa un sistema dl tipo:
$y=U*x$
$L*y=e$ [ok]
questo sistema ha complessità n [? non mi convince per quanto dice dopo]
Sfruttando la decomposizione LU abbiamo un sistema che si risolve per sostituzione, allora per trovare la matr inversa X dobbiamo fare $n^2$ operazioni; [dovrebbe essere l'n di prima per gli n sistemi...? e quindi $n^2]
continuando: la decomposizione LU ha complessità $n^3$ [ma non era n (punto interrogativo precedente.) Ma poi se la decomposizione LU ha complessità $n^3$ questa non va moltiplicata per n, ed ottengo di nuovo $n^4$?] e il calcolo dell'inversa ha complessità $n^2$. il termine $n^3$ domina, quindi complessità $n^3$ [ok]

[Nidhogg]

Basta vedere l'algoritmo di LU-Decomposition per capire che ha un tempo di esecuzione pari a $Theta(n^3)$. Infatti l'algoritmo contiene tre livelli di annidamento, tre cicli for che iterano fino ad $n$.

Saluti, Ermanno.