Sistemi triangolari e fattorizzazione LU: costo computazionale

Salve a tutti, sto studiando metodi numerici sul libro Quarteroni e sono alle prese con fattorizzazione LU e sistemi triangolari.

Riporto formule e parole del testo :

Metodo delle sostituzioni in avanti :

$ x_1= b_1 /a_11 $


$ x_i=1 /a_{ii } [b_i -sum_{j=i+1}^{i-1} a_{ij} x_j] $ con $ i=2,3...,n $ .

Mi viene detto che il costo computazionale del metodo è pari a $ n^2 $ flops.

Facendo letteralmente una prova, con una generica matrice $ 2 x 2 $ ho contato 5 diverse operazioni, e pertanto sono perplesso. Inoltre in una nota del libro viene specificato che :"Assumeremo che un flop corrispoda ad una qualsiasi operazione di somma, sottrazione, moltiplicazione o divisione. Altri autori assumono che un flop corrisponde ad una somma e ad una moltiplicazione." Quindi in poche parole mi sta dicendo che il costo computazionale non è un "qualcosa" univocamente definito? Ci sono varie interpretazioni e ognuno sceglie la sua preferita?


Idem per la fattorizzazione LU ( il cui costo dovrebbe essere di $ 2/3 n^3 $ flops). Qualcuno può spiegarmi come dimostrare questi risultati ( magari usando qualche serie ) o piuttosto trattasi di risultati che vanno presi per veri a prescindere?

Graazie a chiunque mi risponderà XD

Il costo computazionale della sostituzione in avanti non è \(n^2\) ma \(O(n^2)\), il che esprime l'ordine di grandezza del costo, che potrebbe essere in realtà \(n^2 + n\) o qualcos'altro di simile, ma ovviamente l'unica cosa che importa è l'ordine dominante.
Per quanto riguarda la definizione di flop, è univoca ed è l'esecuzione di una operazione in virgola mobile da parte di un processore; tuttavia un processore non necessita dello stesso numero di operazioni per fare somma, sottrazione, moltiplicazione e divisione di due numeri. Questo esula dall'analisi numerica, ma anticamente per un processore era molto più costoso fare una divisione che una somma, necessitando anche dieci volte il numero di istruzioni; col miglioramento della tecnologia dei processori il divario va assottigliandosi e oggi una moltiplicazione costa quasi come una somma e poco meno di una divisione [ma potrei sbagliarmi]. Questi sono dettagli di informatica e sono irrilevanti per l'analisi numerica.

Per dimostrare questi risultati semplicemente fai i conti e poi tieni l'ordine di grandezza dominante.