Esercizi Metodi numerici

Complessità computazionale

Calcolare il costo computazionale del seguente sistema

 b(1)x(1) = a(1, 1) i−1P− a(i, k)x(k)b(i) k=1x(i) = a(i, i)  b x = 1a x = b 111 1 1 a 11 −ab x−→ x = 2 21 1a x + a x = b (1)221 1 22 2 2 a22−ab x +a xa x + a x + a x = b  x = 3 31 1 32 231 1 32 2 33 3 3  3 a33Quindi in generale si avranno le formule (1).

Come vanno gli indici della sommatoria? Indice riga della matrice A uguale all’elemento che si sta calcolando, mentre l’indice di colonna varia fino all’indice precedente della x che si sta calcolando (cioè fino ad i-1).

Quindi, ad esempio, se si sta calcolando x, si avrà la somma di 4 prodotti. In generale si hanno:

• N divisioni (n-1 sotto, e una sopra)
• I-1 prodotti
• I-1 somme

Siccome i va da 1 ad n, si può considerare come la somma dei primi m interi. Quindi, si avrà che cin(n + 1) saranno.

Si può considerare:

2 n n−1 2−n(n 1) n nX X− −i 1= i = =2 2 2i=1 i=1 2

Questo vale sia per prodotti che somme. In definitiva si avrà che il costo computazionale è O(n )

Calcolare il costo computazionale del seguente sistema

 b(n)x(n) = a(n, n) nk=i+1P− a(i, k)x(k)b(i)x(i) = a(i, i)  b x = 3a x + a x + a x = b 311 1 12 2 13 3 1 a 33  −ab x−→ x = 2 23 3a x + a x = b (2)222 1 223 2 2 a22−ab x +a xa x = b x = 1 12 2 13 333 3 3  1 a11− −

In questo caso i decrementa i = n 1, n 2, ..., 1, e si avranno:

• N divisioni (n-1 sotto, e una sopra)
• N-i prodotti
• N-i somme

Quindi:

1 n−1 2−(n 1)n n nXX − − − − − − = +n i = 0 + (n (n 1)) + (n (n 2)) + ... + n 1 = i = 2 2 2i=n i=1

Poiché si possono riordinare i termini e si ottiene la stessa del caso spiegato sopra.

Calcolare il costo computazionale del seguente algoritmo

1f o r j =1 t o mx ( j ) = b( j )/ l ( j , j )f o r i=j +1 t o m = *b( i ) = b( i ) l ( i , j ) x ( j )

Per ogni j = 1, ..., m si avrà:

• Una divisione
• M-j moltiplicazioni
• M-j somme

Quindi si può dire che:

m m 2m(m + 1) m mX X− − − − − −m j = 0 + (m (m 1)) + (m (m 2)) + ... + m 1 = j = = +2 2 2j=1 j=12 m

Quindi il costo computazionale è O 2.

Esercizio

Data una matrice A, non singolare, dire quali delle seguenti affermazioni sono vere e motivare le risposte:

• 1. k(A) =  -1||AA ||
• 2. k(A) =  -1||A|| ||A ||
• 3. k(A) permette di calcolare il condizionamento di un sistema lineare
• 4. k(A) < 0.5
• 5. Se k(A) = 5000 il sistema è ben condizionato e la matrice è malcondizionata
• 6. La matrice è stabile
• 7. Il processo per il calcolo dell’indice di condizionamento è stabile
• 8. Il processo per il calcolo dell’indice di condizionamento è malcondizionato

1) Falso, perché k(A) è il prodotto delle due norme, non la norma del prodotto. Anche perché,1 ||1||AA = 1 e = 1.

2) Falso. Le norme devono essere uguali. L’uguaglianza non è valida se si usano due tipi di norma.

3) Vero, perché è proprio l’indice di condizionamento.

4) Falso, non può essere perché già k(I)

5.1) Falso. Se la matrice è mal condizionata lo è anche il sistema

5.2) Falso. La stabilità dipende dall’algoritmo e k(A) e non da informazioni sull’algoritmo

5.3) Falso. Dipende dall’algoritmo che si sceglie per calcolare l’indice di condizionamento che sarà stabile o meno

5.4) Falso. Il processo per il calcolo dell’indice di condizionamento è un algoritmo e quindi può essere stabile o instabile, non c’entra il malcondizionamento che non è legato all’algoritmo

Esercizio

Fornire un esempio di matrice A in R^3×3 che non sia la matrice identità tale che:

•  -1||A|| ||A ||k(A) = = 11 1

Sapendo che l’inversa di una matrice diagonale è ancora una matrice diagonale, ma gli elementi della diagonale sono i reciproci. Quindi per semplicità, siccome non ci sono specifiche sulla struttura della matrice, si sceglie una matrice diagonale. Basta prendere la matrice identità e cambiare il segno oppure una matrice con tutti 1 sulla anti-diagonale        −1 −10 0 0 0 1 0 0 n 0 0−1 ∈0 1 0 0 1 0 0 0 0 n 0 n R (3)       −1 −10 0 1 0 0 0 0 0 0 n

Fattorizzazione LU

   a a a ... ... a1 0 0 ... ... 0a a a ... ... a 11 12 13 1n11 12 13 1n 0 u u ... ... ul 1 0 ... ... 0a a a ... ... a 22 23 2n2121 22 23 2n       0 0 u ... ... ul l 1 ... ... aa a a ... ... a 33 3n31 32 3n31 32 33 3n       . .. .. .. .... .. .. .. ... .. .. .. .. ...... = ...    ... . . . . .. . . . .. . . .       .. .. .. .. .... .. .. .. .... .. .. .. .. ......    ... . . . . .. . . . .. . . . .    0 0 0 ... ... ul l l ... ... 1a a a ... ... a nnn1 n2 n3n1 n2 n3 nn (4)

Fattorizzare in forma LU la matrice  −710 0−3 2 6A =  −15 5a −0,l = = 32121 u11 − −0,u = a l u = 122 22 21 12 → −a = l u + l u = l u + u u = a l u = 623 21 13 22 23 21 13 23 23 23 21 13−u = a (l u + l u )33 33 31 13 32 23al = = 0, 53131 u11 −la u→a = l u + l u l = 32 31 1232 31 12 32 22 32 u22 −155Sostituendo nella formula, si ottiene che u =33

Quindi si avrà:    −71 0 0 10 0−0, −0,3 1 0 0 1 6L = U =   −25 −1550, 5 1 0 0

Esercizio

Data la matrice A = E + αe e₁ n

Dove:

• E è una matrice avente 1 sulla diagonale principale e sulla prima riga e zero altrove
• e ed e sono i vettori di ordine n formati da zero tranne nell’elemento indicato dal pedice.

1 n ∞Calcolare l’indice di condizionamento di A in normaT e = 1, 0, 0, ..., 0 e = 0, 0, 0, ..., 11 n   0 0 ... 1 0 0 ... α0 0 ... 0 0 0 ... 0   αe e = α = (5)  . .1 n .. ..  0 0 0 00 0   0 0 ... 0 0 0 ... 0     1 1 ... 1 0 0 ... α 1