Esercizi Metodi numerici

0.1 Complessità Computazionale

Calcolare il costo computazionale del seguente sistema:

 b(1)

x(1) =



 a(1, 1)

 i−1

P

− a(i, k)x(k)

b(i) k=1

x(i) =





 a(i, i)  b

 x = 1

a x = b 1

11 1 1 a

 11



 −a

b x

−→ x = 2 21 1

a x + a x = b (1)

2

21 1 22 2 2 a

22

−a

b x +a x

a x + a x + a x = b 

 x = 3 31 1 32 2

31 1 32 2 33 3 3  3 a

33

Quindi 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:

5

ˆ 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 ci

n(n + 1)

saranno . Si può considerare:

2 n n−1 2

−

n(n 1) n n

X X

− −

i 1= i = =

2 2 2

i=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+1

P

− a(i, k)x(k)

b(i)

x(i) =





 a(i, i)  b

 x = 3

a x + a x + a x = b 3

11 1 12 2 13 3 1 a

 33

  −a

b x

−→ x = 2 23 3

a x + a x = b (2)

2

22 1 223 2 2 a

22

−a

b x +a x

a x = b

 

x = 1 12 2 13 3

33 3 3  1 a

11

− −

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 n

X

X − − − − − − = +

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

i=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:

1

f o r j =1 t o m

x ( 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 2

m(m + 1) m m

X X

− − − − − −

m j = 0 + (m (m 1)) + (m (m 2)) + ... + m 1 = j = = +

2 2 2

j=1 j=1

2

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

||AA ||

1. k(A) = −1

||A|| ||A ||

2. k(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

la matrice è stabile

il processo per il calcolo dell’indice di condizionamento è stabile

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) 1

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

2

Esercizio: 3×3

∈

Fornire un esempio di matrice A R che non sia la matrice identità tale che:

−1

||A|| ||A ||

k(A) = = 1

1 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 −1

0 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 −1

0 0 1 0 0 0 0 0 0 n

3

Fattorizzazione LU 

 

 

 a a a ... ... a

1 0 0 ... ... 0

a a a ... ... a 11 12 13 1n

11 12 13 1n 0 u u ... ... u

l 1 0 ... ... 0

a a a ... ... a 22 23 2n

21

21 22 23 2n 

 

 

 

 

 

 0 0 u ... ... u

l l 1 ... ... a

a a a ... ... a 33 3n

31 32 3n

31 32 33 3n 

 

 

 

 

 

 . .. .. .. ..

.. .. .. .. ..

. .. .. .. .. ..

..

.. = .

.. 

 

 

 .

.

. . . . . .

. . . . .

. . . . 

 

 

 

 

 

 .. .. .. .. ..

.. .. .. .. ..

.. .. .. .. .. ..

..

.. 

 

 

 .

.

. . . . . .

. . . . .

. . . . . 

 

 

 0 0 0 ... ... u

l l l ... ... 1

a a a ... ... a nn

n1 n2 n3

n1 n2 n3 nn (4)

Fattorizzare in forma LU la matrice  

−7

10 0

−3 2 6

A =  

−1

5 5

a −0,

l = = 3

21

21 u

11 − −0,

u = a l u = 1

22 22 21 12 → −

a = l u + l u = l u + u u = a l u = 6

23 21 13 22 23 21 13 23 23 23 21 13

−

u = a (l u + l u )

33 33 31 13 32 23

a

l = = 0, 5

31

31 u

11 −l

a u

→

a = l u + l u l = 32 31 12

32 31 12 32 22 32 u

22 −155

Sostituendo nella formula, si ottiene che u =

33

Quindi si avrà:    

−7

1 0 0 10 0

−0, −0,

3 1 0 0 1 6

L = U =

   

−25 −155

0, 5 1 0 0

Esercizio:

Data la matrice A = E + αe e

1 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 norma

T

e = 1, 0, 0, ..., 0 e = 0, 0, 0, ..., 1

1 n

   

0 0 ... 1 0 0 ... α

0 0 ... 0 0 0 ... 0

   

αe e = α = (5)

 

 

. .

1 n .. ..

 

 

0 0 0 0

0 0

   

0 0 ... 0 0 0 ... 0

     

1 1 ... 1 0 0 ... α 1