Sistemi lineari
1. Quante moltiplicazioni e divisioni esegue approssimativamente l'algoritmo di Gauss nel risolvere il sistema $Ax=b$ con A matrice 100x100?
2. Se la matrice A ha numero di condizionamento $μ=10$, qual è il numero di condizionamento della matrice -5A. Giustifica la risposta?
3. Dare la fattorizzazione $A= LU$ o $PA=LU$ della matrice$ || ( 2 , 3 ),( 0 , 1 ) ||$
2)Trovo il numero di condizionamento della matrice calcolando $||A^(1-)||*||A||$ quindi $||5 A^(1-)||*||5A|$ ,
$|1/5|*||A^(1-)||*|5|*||A||$, $||A^(1-)||*|25|*||A||$ tendo presente che $||A^(1-)||*||A||=10$
$||A^(1-)||*||A||=5*10$
1)Per l'algoritmo di gauss per un sistema 100x100
$a_(1,1)x_(1,1)+..+a_(1,100)x_(1,100)=b_1$
$....$
$ a_(100,1)x_(100,1)+..+a_(100,100)x_(100,100)=b_100 $
per la prima riga
$x_(1,1)=(b_1-(a_(1,2)x_(1,2)+..+a_(1,100)x_(1,100)))/a_(1,1)$
che poi sostituisco nelle successive con una moltiplicazione, ad esempio per la seconda
$a_(2,1)*(b_1-(a_(1,2)x_(1,2)+..+a_(1,100)x_(1,100)))/a_(1,1)+...=b_2$
le moltiplicazioni e le divisioni dovrebbero essere qualcosa come $100^2+100^2$
Per il terzo ho letto in che cosa consiste la fattorizzazione però non so come procedere.
2. Se la matrice A ha numero di condizionamento $μ=10$, qual è il numero di condizionamento della matrice -5A. Giustifica la risposta?
3. Dare la fattorizzazione $A= LU$ o $PA=LU$ della matrice$ || ( 2 , 3 ),( 0 , 1 ) ||$
2)Trovo il numero di condizionamento della matrice calcolando $||A^(1-)||*||A||$ quindi $||5 A^(1-)||*||5A|$ ,
$|1/5|*||A^(1-)||*|5|*||A||$, $||A^(1-)||*|25|*||A||$ tendo presente che $||A^(1-)||*||A||=10$
$||A^(1-)||*||A||=5*10$
1)Per l'algoritmo di gauss per un sistema 100x100
$a_(1,1)x_(1,1)+..+a_(1,100)x_(1,100)=b_1$
$....$
$ a_(100,1)x_(100,1)+..+a_(100,100)x_(100,100)=b_100 $
per la prima riga
$x_(1,1)=(b_1-(a_(1,2)x_(1,2)+..+a_(1,100)x_(1,100)))/a_(1,1)$
che poi sostituisco nelle successive con una moltiplicazione, ad esempio per la seconda
$a_(2,1)*(b_1-(a_(1,2)x_(1,2)+..+a_(1,100)x_(1,100)))/a_(1,1)+...=b_2$
le moltiplicazioni e le divisioni dovrebbero essere qualcosa come $100^2+100^2$
Per il terzo ho letto in che cosa consiste la fattorizzazione però non so come procedere.
Risposte
UP
Per il 3:
la tua matrice mi sembra già una triangolare superiore, comunque se proprio vogliamo scriverla come prodotto $LU$ direi che la si scrive in questa forma $((1,0),(0,1))((2,3),(0,1))$.
Ovviamente la matrice diagonale è sia tr.sup. che tr.inf.
Per il metodo di Gauss direi che richiede $n^2$ operazioni siccome ogni elemento richiede di essere eliminato, lasciando solo la diagonale, per cui una fomula più esatta sarebbe $n(n-1)$ moltiplicazione e somme.
la tua matrice mi sembra già una triangolare superiore, comunque se proprio vogliamo scriverla come prodotto $LU$ direi che la si scrive in questa forma $((1,0),(0,1))((2,3),(0,1))$.
Ovviamente la matrice diagonale è sia tr.sup. che tr.inf.
Per il metodo di Gauss direi che richiede $n^2$ operazioni siccome ogni elemento richiede di essere eliminato, lasciando solo la diagonale, per cui una fomula più esatta sarebbe $n(n-1)$ moltiplicazione e somme.
per la 1) oltre l'osservazione di Quinzio, considera che l'algoritmo di risoluzione di Gauss, utilizzando la fattorizzazione LUP (per rimanere in tema), ha complessità $O(n^2)$. Perciò direi che le moltiplicazioni/divisioni siano $O(100^2)$ con costante nascosta dell'ordine di $c>=4$.
L'algoritmo LU ha complessità O(n^3)... Per l'esattezza qualcosa tipo \(\displaystyle \frac23n^3 + O(n^2)\)
La complessità teorica è invece più bassa nel senso che si dimostra che è uguale a quella della moltiplicazione matriciale. Il limite inferiore non si è ancora trovato o comunque non è stato dimostrato che è l'inferiore.
Detto questo vediamo di fare il calcolo.
Si fanno \(\displaystyle n-1 \) passaggi.
Per ogni passaggio \(\displaystyle i \) si fanno \(\displaystyle n-i \) divisioni. Quindi si fanno \(\displaystyle n-i \) operazioni del tipo \(\displaystyle \mathbf{v} = \mathbf{v} +\alpha\mathbf{w}\) dove la dimensione dei vettori è \(\displaystyle n-i +1\).
In formule risulta quindi che per ogni step ci sono in totale:
\(\displaystyle (n-i)+(n-i)(n-i+1) = (n-i)(n-i+2)\) moltiplicazioni/divisioni
\(\displaystyle (n-i)(n-i+1)\) addizioni/sottrazioni.
Ora tenenedo conto che \(\displaystyle \sum_{i=1}^{n-1}1 = n-1 \), \(\displaystyle \sum_{i=1}^{n-1}i = \frac{n(n-1)}{2} = \frac{n^2 - n}{2} \) e \(\displaystyle \sum_{i=1}^{n-1}i^2 = \frac{(n-1)n(2n-1)}{6} = \frac{2n^3-3n^2+n}{6}\)
Vediamo pertanto di fare i calcoli:
\(\displaystyle \begin{align}\text{mul_ops} &= \sum_{i=1}^{n-1} (n-i)(n-i+2) \\
&= \sum_{i=1}^{n-1} \Bigl(n^2 - 2ni +2n +i^2 -2i\Bigr) \\
&= (n^2 + 2n)(n-1) -2(n+1)\sum_{i=1}^{n-1}i + \sum_{i=1}^{n-1}i^2 \\
&= (n^3 + n^2 - 2n) - (n+1)(n^2 - n) + \frac{2n^3-3n^2+n}{6} \\
&= (n^3 + n^2 - 2n) - (n^3-n) + \frac{2n^3-3n^2+n}{6} \\
&= n^2 - n + \frac{2n^3-3n^2+n}{6} \\
&= \frac{6n^2 - 6n +2n^3 -3n^2 + n}{6} \\
&= \frac{2n^3 +3n^2 -5n}{6} \\
&= \frac13n^3 +\frac12n^2 -\frac56n
\end{align}\)
similmente...
\(\displaystyle \begin{align}\text{add_ops} &= \sum_{i=1}^{n-1} (n-i)(n-i+1) \\
&= \sum_{i=1}^{n-1} \Bigl(n^2 - 2ni +n +i^2 -i\Bigr) \\
&= (n^2 + n)(n-1) -(2n+1)\sum_{i=1}^{n-1}i + \sum_{i=1}^{n-1}i^2 \\
&= (n^3 - n) - \frac{(2n+1)(n^2 - n)}{2} + \frac{2n^3-3n^2+n}{6} \\
&= (n^3 -n) - \frac{2n^3-n^2-n}{2} + \frac{2n^3-3n^2+n}{6} \\
&= - n + \frac{n^2+n}{2} + \frac{2n^3-3n^2+n}{6}\\
&= \frac{-6n +3n^2 +3n +2n^3 -3n^2 + n}{6} \\
&= \frac{2n^3 +4n}{6} \\
&= \frac13n^3 +\frac23n
\end{align}\)
In conclusione:
\(\displaystyle \begin{align}\text{ops} &= \text{mul_ops} + \text{add_ops} \\
&= \frac13n^3 +\frac12n^2 -\frac56n + \frac13n^3 +\frac23n\\
&= \frac23n^3 +\frac12n^2 -\frac16n
\end{align}\)
----------------------------------------------
Nel caso di n=100 risulta pertanto:
\(\displaystyle \text{ops}(100) = \frac23 100^3 +\frac12 100^2 -\frac16 100 \approx 671650 \gg 100^2 + 100^2 = 20000\)
La complessità teorica è invece più bassa nel senso che si dimostra che è uguale a quella della moltiplicazione matriciale. Il limite inferiore non si è ancora trovato o comunque non è stato dimostrato che è l'inferiore.
Detto questo vediamo di fare il calcolo.
Si fanno \(\displaystyle n-1 \) passaggi.
Per ogni passaggio \(\displaystyle i \) si fanno \(\displaystyle n-i \) divisioni. Quindi si fanno \(\displaystyle n-i \) operazioni del tipo \(\displaystyle \mathbf{v} = \mathbf{v} +\alpha\mathbf{w}\) dove la dimensione dei vettori è \(\displaystyle n-i +1\).
In formule risulta quindi che per ogni step ci sono in totale:
\(\displaystyle (n-i)+(n-i)(n-i+1) = (n-i)(n-i+2)\) moltiplicazioni/divisioni
\(\displaystyle (n-i)(n-i+1)\) addizioni/sottrazioni.
Ora tenenedo conto che \(\displaystyle \sum_{i=1}^{n-1}1 = n-1 \), \(\displaystyle \sum_{i=1}^{n-1}i = \frac{n(n-1)}{2} = \frac{n^2 - n}{2} \) e \(\displaystyle \sum_{i=1}^{n-1}i^2 = \frac{(n-1)n(2n-1)}{6} = \frac{2n^3-3n^2+n}{6}\)
Vediamo pertanto di fare i calcoli:
\(\displaystyle \begin{align}\text{mul_ops} &= \sum_{i=1}^{n-1} (n-i)(n-i+2) \\
&= \sum_{i=1}^{n-1} \Bigl(n^2 - 2ni +2n +i^2 -2i\Bigr) \\
&= (n^2 + 2n)(n-1) -2(n+1)\sum_{i=1}^{n-1}i + \sum_{i=1}^{n-1}i^2 \\
&= (n^3 + n^2 - 2n) - (n+1)(n^2 - n) + \frac{2n^3-3n^2+n}{6} \\
&= (n^3 + n^2 - 2n) - (n^3-n) + \frac{2n^3-3n^2+n}{6} \\
&= n^2 - n + \frac{2n^3-3n^2+n}{6} \\
&= \frac{6n^2 - 6n +2n^3 -3n^2 + n}{6} \\
&= \frac{2n^3 +3n^2 -5n}{6} \\
&= \frac13n^3 +\frac12n^2 -\frac56n
\end{align}\)
similmente...
\(\displaystyle \begin{align}\text{add_ops} &= \sum_{i=1}^{n-1} (n-i)(n-i+1) \\
&= \sum_{i=1}^{n-1} \Bigl(n^2 - 2ni +n +i^2 -i\Bigr) \\
&= (n^2 + n)(n-1) -(2n+1)\sum_{i=1}^{n-1}i + \sum_{i=1}^{n-1}i^2 \\
&= (n^3 - n) - \frac{(2n+1)(n^2 - n)}{2} + \frac{2n^3-3n^2+n}{6} \\
&= (n^3 -n) - \frac{2n^3-n^2-n}{2} + \frac{2n^3-3n^2+n}{6} \\
&= - n + \frac{n^2+n}{2} + \frac{2n^3-3n^2+n}{6}\\
&= \frac{-6n +3n^2 +3n +2n^3 -3n^2 + n}{6} \\
&= \frac{2n^3 +4n}{6} \\
&= \frac13n^3 +\frac23n
\end{align}\)
In conclusione:
\(\displaystyle \begin{align}\text{ops} &= \text{mul_ops} + \text{add_ops} \\
&= \frac13n^3 +\frac12n^2 -\frac56n + \frac13n^3 +\frac23n\\
&= \frac23n^3 +\frac12n^2 -\frac16n
\end{align}\)
----------------------------------------------
Nel caso di n=100 risulta pertanto:
\(\displaystyle \text{ops}(100) = \frac23 100^3 +\frac12 100^2 -\frac16 100 \approx 671650 \gg 100^2 + 100^2 = 20000\)
"vict85":
L'algoritmo LU ha complessità O(n^3)... Per l'esattezza qualcosa tipo \(\displaystyle \frac23n^3 + O(n^2)\)
Sì certo la fattorizzazione (decomposizione) LUP di una matrice è $O(n^3)$. Io mi riferivo ad un fatto secondario, che utilizzando le matrici date L, U, P si può risolvere un sistema di equazioni con le "mosse di Gauss" con un algoritmo di complessità $O(n^2)$. Per legarsi con il punto 1) si può pensare, visto che L ed U sono matrici triangolari, la somma totale e le mosse totali hanno stesso numero approssimativo totale.
Ma calcolarlo direttamente, come hai fatto te, forse è più chiaro e corretto
"hamming_burst":
[quote="vict85"]L'algoritmo LU ha complessità O(n^3)... Per l'esattezza qualcosa tipo \(\displaystyle \frac23n^3 + O(n^2)\)
Sì certo la fattorizzazione (decomposizione) LUP di una matrice è $O(n^3)$. Io mi riferivo ad un fatto secondario, che utilizzando le matrici date L, U, P si può risolvere un sistema di equazioni con le "mosse di Gauss" con un algoritmo di complessità $O(n^2)$. Per legarsi con il punto 1) si può pensare, visto che L ed U sono matrici triangolari, la somma totale e le mosse totali hanno stesso numero approssimativo totale.
Ma calcolarlo direttamente, come hai fatto te, forse è più chiaro e corretto
[/quote]Ti riferisci alla “sostituzione”? Dopo un semplice controllo sul libro (non avevo voglia di fare i calcoli) quello risulta essere formato da \(\displaystyle \frac{n^2+n}{2} \) moltiplicazioni/divisioni e \(\displaystyle \frac{n^2-n}{2} \) addizioni/sottrazioni (il calcolo è abbastanza semplice). Il tutto due volte più una componente \(\displaystyle O(1) \) (la permutazione che diventa \(\displaystyle O(n) \) se gli scambi vengono fatti).
Comunque il pivoting non l'ho messo nel calcolo. Per il partial pivoting si aggiungono \(\displaystyle \frac{n(n-1)}{2} \) confronti (più eventuali scambi se li metti nel conto). Il complete pivoting invece aggiunge \(\displaystyle O(n^3) \) operazioni quindi risulta particolarmente pesante. Per il root pivoting non so. Il calcolo di altri metodi li lascio a chi ne ha voglia.
Rileggendo però mi sa che ho fatto il calcolo con il metodo di Gauss (quello che non genera L o meglio che la cancella). Il metodo LU ripensandoci ha \(\displaystyle (n-i)(n-i+1) \) moltiplicazioni/divisioni e \(\displaystyle (n-i)(n-i) \) addizioni sottrazioni per ogni passaggio. L'aggiunstamento non è comunque significativo.
allora penso che per algoritmo di gauss, si intenda
for k=1 to n-1
for i=k+1 to n
$m_(ik)=(a^(k)_(ik))/(a^(k)_(kk))$
for j=k+1 to n+1
$a^(k+1)_(ij)=a^(k)_(ij)-m_(ik)a^(k)_(kj)$
end
end
end
quindi avrei $100^2$ divisioni e 100 moltiplicazioni
for k=1 to n-1
for i=k+1 to n
$m_(ik)=(a^(k)_(ik))/(a^(k)_(kk))$
for j=k+1 to n+1
$a^(k+1)_(ij)=a^(k)_(ij)-m_(ik)a^(k)_(kj)$
end
end
end
quindi avrei $100^2$ divisioni e 100 moltiplicazioni
per quanto riguarda la matrice $| ( 2 , 3 ),( 0 , 1 ) |$
se $U=A*(m_1*m_2)$
dove $m_1$ e $m_2$ sono uguali $m_1,m_2=| ( 1 , 0 ),( 0 , 1 ) |$
$U= | ( 2 , 3 ),( 0 , 1 ) |$
ed $L=(m_1*m_2)^-1$ quindi $L=| ( 1 , 0 ),( 0 , 1 ) |$
se $U=A*(m_1*m_2)$
dove $m_1$ e $m_2$ sono uguali $m_1,m_2=| ( 1 , 0 ),( 0 , 1 ) |$
$U= | ( 2 , 3 ),( 0 , 1 ) |$
ed $L=(m_1*m_2)^-1$ quindi $L=| ( 1 , 0 ),( 0 , 1 ) |$
"BHK":
allora penso che per algoritmo di gauss, si intenda
for k=1 to n-1
for i=k+1 to n
$m_(ik)=(a^(k)_(ik))/(a^(k)_(kk))$
for j=k+1 to n+1
$a^(k+1)_(ij)=a^(k)_(ij)-m_(ik)a^(k)_(kj)$
end
end
end
quindi avrei $100^2$ divisioni e 100 moltiplicazioni
Ti assicuro che il metodo di eliminazione di Gauss ha più di \(\displaystyle \frac{4n^3+3n^2-n}{6} = \frac{n(n+1)(4n-1)}{6} \) operazioni più quelle per la risoluzione del sistema triangolare (che sono \(\displaystyle n^2 \) operazioni circa) e ho ampiamento mostrato il calcolo per arrivarci. Ho anche ricontrollato su un libro se avevo fatto i calcoli giusti.
Cosa non hai capito della mia ampia risposta?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo