Dubbi su algoritmo di Gauss e fattorizzazione LU
Salve a tutti, sto studiando per l'esame di calcolo numerico e ho riscontrato un paio di problemi, per cui chiedo il vostro aiuto. Sto studiando dal libro "Matematica numerica: metodi, algoritmi e software" di Almerico Murli; ecco le cose che non mi sono chiare finora:
1) Quando valuta la complessità computazionale dell'algoritmo di Gauss, il libro dice:
Non capisco perché dice che servono 2n(n-1) flop per modificare la sottomatrice e il vettore dei termini noti... Il mio ragionamento è: per calcolare \(\displaystyle a_{ij} \) effettuiamo 2(n-1) flop (abbiamo n-1 moltiplicazioni e n-1 sottrazioni), ma anche per calcolare \(\displaystyle b_i \) per i=2,...,n abbiamo 2(n-1) flop (anche qui n-1 moltiplicazioni e n-1 sottrazioni)... dov'è che sbaglio?
2) Per spiegare la fattorizzazione LU, il libro fa riferimento a una matrice \(\displaystyle M_k \) detta triangolare unitaria elementare inferiore di indice k, ma non ho per niente capito la definizione:
"Dato un vettore m del tipo \(\displaystyle m_T = (0,0,...m_{k+1},...,m_n) \) la matrice \(\displaystyle M_k \) di ordine n, definita come \(\displaystyle M_k = I - me_{kT} \), dove \(\displaystyle e_{kT} \) è il k-esimo vettore unitario, è detta matrice triangolare unitaria elementare inferiore di indice k."
Ma se moltiplico m per il k-esimo vettore unitario non ottengo il vettore nullo???
Grazie a chi mi aiuterà!
1) Quando valuta la complessità computazionale dell'algoritmo di Gauss, il libro dice:
Non capisco perché dice che servono 2n(n-1) flop per modificare la sottomatrice e il vettore dei termini noti... Il mio ragionamento è: per calcolare \(\displaystyle a_{ij} \) effettuiamo 2(n-1) flop (abbiamo n-1 moltiplicazioni e n-1 sottrazioni), ma anche per calcolare \(\displaystyle b_i \) per i=2,...,n abbiamo 2(n-1) flop (anche qui n-1 moltiplicazioni e n-1 sottrazioni)... dov'è che sbaglio?
2) Per spiegare la fattorizzazione LU, il libro fa riferimento a una matrice \(\displaystyle M_k \) detta triangolare unitaria elementare inferiore di indice k, ma non ho per niente capito la definizione:
"Dato un vettore m del tipo \(\displaystyle m_T = (0,0,...m_{k+1},...,m_n) \) la matrice \(\displaystyle M_k \) di ordine n, definita come \(\displaystyle M_k = I - me_{kT} \), dove \(\displaystyle e_{kT} \) è il k-esimo vettore unitario, è detta matrice triangolare unitaria elementare inferiore di indice k."
Ma se moltiplico m per il k-esimo vettore unitario non ottengo il vettore nullo???
Grazie a chi mi aiuterà!
Risposte
Ti rispondo al primo quesito:
Supponiamo che tu debba fare k passi. Avendo bene in mente il pseudo codice dell'algoritmo di Gauss, sai che devi eseguire:
(n-k) volte l'operazione di moltiplicazione,
(n-k) l'operazione di sottrazione,
1 volta la divisione per il calcolo del moltiplicatore.
Tutto questo lo devi eseguire in totale (n-k) volte. Per il termine noto, lo stesso devi eseguire (n-k) volte sottrazioni ed (n-k) volte moltiplicazioni (0 divisioni poichè l'hai già eseguita prima).
In totale avrai \(\displaystyle (n-k)[(n-k)+1+(n-k)]+2(n-k) \), cioè: \(\displaystyle 2(n-k)^2 +3(n-k) \).
Ora non ti resta che scrivere: \(\displaystyle \sum_{k=1}^{n-1} 2(n-k)^2 +3(n-k) \). Dopo bisogna proseguire con i calcoli (usando note formule dell'analisi) per ottenere che la complessità del metodo di Gauss si riduce a \(\displaystyle \frac{1}{3} n^3\).
Supponiamo che tu debba fare k passi. Avendo bene in mente il pseudo codice dell'algoritmo di Gauss, sai che devi eseguire:
(n-k) volte l'operazione di moltiplicazione,
(n-k) l'operazione di sottrazione,
1 volta la divisione per il calcolo del moltiplicatore.
Tutto questo lo devi eseguire in totale (n-k) volte. Per il termine noto, lo stesso devi eseguire (n-k) volte sottrazioni ed (n-k) volte moltiplicazioni (0 divisioni poichè l'hai già eseguita prima).
In totale avrai \(\displaystyle (n-k)[(n-k)+1+(n-k)]+2(n-k) \), cioè: \(\displaystyle 2(n-k)^2 +3(n-k) \).
Ora non ti resta che scrivere: \(\displaystyle \sum_{k=1}^{n-1} 2(n-k)^2 +3(n-k) \). Dopo bisogna proseguire con i calcoli (usando note formule dell'analisi) per ottenere che la complessità del metodo di Gauss si riduce a \(\displaystyle \frac{1}{3} n^3\).
"Rosy1993":
2) Per spiegare la fattorizzazione LU, il libro fa riferimento a una matrice \(\displaystyle M_k \) detta triangolare unitaria elementare inferiore di indice k, ma non ho per niente capito la definizione:
"Dato un vettore m del tipo \(\displaystyle m_T = (0,0,...m_{k+1},...,m_n) \) la matrice \(\displaystyle M_k \) di ordine n, definita come \(\displaystyle M_k = I - me_{kT} \), dove \(\displaystyle e_{kT} \) è il k-esimo vettore unitario, è detta matrice triangolare unitaria elementare inferiore di indice k."
Ma se moltiplico m per il k-esimo vettore unitario non ottengo il vettore nullo???
Grazie a chi mi aiuterà!
Direi che, per \(\displaystyle k=1\) e \(n=3 \) intenda questo:
\(\displaystyle \begin{pmatrix}0 \\ m_2 \\ m_3 \end{pmatrix}
\begin{pmatrix}1 \\ 0 \\ 0 \end{pmatrix}^{\intercal} =
\begin{pmatrix}0 \\ m_2 \\ m_3 \end{pmatrix}
\begin{pmatrix}1 & 0 & 0 \end{pmatrix} =
\begin{pmatrix}0 & 0 & 0 \\ m_2 & 0 & 0 \\ m_3 & 0 & 0 \end{pmatrix} \)
perciò \(M_1\) è la seguente matrice:
\(\displaystyle \begin{pmatrix}1 & 0 & 0 \\ -m_2 & 1 & 0 \\ -m_3 & 0 & 1 \end{pmatrix} \)
Grazie mille a entrambi per la risposta! 
Vict85, in effetti sono stata troppo impulsiva e ho trasformato quello che doveva essere un prodotto colonna per riga in un prodotto riga per colonna
Adesso è chiaro! 
wolframio32, ci ho messo un po' ma credo di aver capito anche la tua risposta, oggi faccio i calcoli e vedrò di scovare questa fantomatica complessità
Se dovessi avere altri problemi faccio affidamento su di voi!!!
Vict85, in effetti sono stata troppo impulsiva e ho trasformato quello che doveva essere un prodotto colonna per riga in un prodotto riga per colonna
Adesso è chiaro! wolframio32, ci ho messo un po' ma credo di aver capito anche la tua risposta, oggi faccio i calcoli e vedrò di scovare questa fantomatica complessità
Se dovessi avere altri problemi faccio affidamento su di voi!!!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo