Riassunto esame Calcolo Numerico, Prof. Bellanca Nicolò, libro consigliato Elementi di calcolo numerico: metodi e algoritmi, M.G. Gasparo, R. Morandi

B∥ A, B R n∗n

∥A ∗ ≤ ∥A∥ ∗ ∥B∥ ∀ ∈

B∥ A, B

Norma 2 Norma 1 Norma ∞

n n

∥A∥ = max ∣λ ( T ∑ ∑

A A)∣

2 i ∣a ∣ ∣a ∣

∥A∥ = max ∥A∥ = max

​ ​ ​ ​ 1 ∞

i=1...n ij ij

​ ​ ​ ​ ​ ​ ​ ​

j=1...n i=1...n

i=1 j=1

Proprietà di norme matriciali indotte

Ad una norma vettoriale “corrisponde” una norma matriciale

∥A ∗ x∥ R

∈ n

∥A∥ = sup x

∥x∥ ​

∥•∥ , ∥•∥ , ∥•∥

2 1 ∞

​ ​ ​

Sono norme matriciali indotte dalle corrispondenti norme vettoriali, soddisfano:

R R

n∗n n

∥Ax∥ ≤ ∥A∥ ∗ ∣x∣ ∈ , ∈

A x

R n

∥I∥ = 1 ∈ matrice identit

aˋ

I

Condizionamento di A R R

n∗n n

∈ , ∈

A x

=

Ax b −1

= 0 → ∃



det(A) A

Indice di condizionamento 1

Appunti Completi 4

−1

= ∥A∥ ∗ ∥A∥

K(A)

Perturbazione solo su b

Sia  la perturbazione di 

δb b = → + = +

Ax b A(x δx) b δb

+ = +

Ax Aδx b δb

=

Aδx δb

=

Ax b

∥b∥ = ∥Ax∥ ≤ ∥A∥ ∗ ∥x∥

∥b∥

∥x∥ ≥ ∥A∥ ​

=

Aδx δb

−1

=

δx A δb

−1

∥δb∥ ≤ ∥A ∥ ∗ ∥δb∥

∥δx∥ ∥δb∥

≤ ∗

K(A)

∥x∥ ∥b∥

​ ​ ​ ​ ​ ​ ​ ​

Ind. di cond.

Err. rel. dati Err. rel. ris.

Perturbazione anche su A

Siano  e  le perturbazioni su  e su 

δA δb A b

∥δx∥ ∥δb∥ ∥δA∥

( )

≤ +

∗

K(A)

∥x∥ ∥b∥ ∥A∥

​ ​ ​ ​ ​ ​ ​

Ind. di cond.

Err. rel. dati Err. rel. ris.

Osservazioni su K(A) −1 −1

= ∥A∥ ∗ ∥A∥ ≥ ∥A ∗ ∥ = ∥I∥ = 1

K(A) A

Non ci sono relazioni tra l’ordine del sistema  e 

n K(A)

Non ci sono relazioni tra  e 

det(A) K(A)

Esempi 1 −1 −1 −1 ... −1

0 1 −1 −1 ... −1

0 0 1 −1 ... −1 →

= ∥A∥ =

A n

∞

⋮ ⋱ ⋮

​ ​ ​ ​ ​ ​ ​ ​

⋮ ⋱ ⋮

0 ... ... ... ... 1

1 1 2 4 ... 2 n−2

0 1 1 2 ... 2 n−3

0 0 1 1 ... 2 n−4

−1 −1

→ n−1

= ∥A ∥ = 2

A ∞

⋮ ⋱ ⋮

​ ​ ​ ​ ​ ​ ​ ​ ​

⋮ ⋱ ⋮

0 ... ... ... ... 1

n−2

∑ i n−1

2 =

1 + 1 + (2 − 1)

​

i=0

Nelle matrici diagonali il numero di condizionamento è sempre uguale a 1

Appunti Completi 5

1 1 1

1 0 ... 0 , , ..., )

=

10 diag(

A

​ 1 10 10 10

0 ... 0 ​ ​ ​

1

10 ​

= −1

A ∥A ∥ =

∞

​ ​ ​ ​ ​ ​

⋮ ⋱ ⋮ 10

​ ​

1

0 0 ... 10 ​ −1

10 0 ... 0 = 10, ..., 10)

A diag(10,

−1

0 10 ... 0 ∥A ∥ = 10

∞

−1 ​

=

A ​ ​ ​ ​ ​ ​

⋮ ⋱ ⋮

0 0 ... 10 1

−1

= ∥A∥ ∗ ∥A ∥ = 10 = 1

∗

K(A) 10 ​

3. Sistemi Lineari =

Il Problema è determinare la soluzione (se esiste) di 

Ax b

R R

n∗n n

∈ ∈

A b, x

Regola di Cramer (noto) )

det(A

i

= 1, ...,

=

​

x n

i

i ​ ​

det(A)

 è la matrice ottenuta da  sostituendo alla i-esima colonna il vettore 

A A b

i ​

I determinanti possono essere calcolati con la regola di Laplace

n

∑ i+j

(−1) ∗

= ∗ )

det(A) a det(A

1j 1j

​ ​ ​

j=1

− 1

Dove  rappresenta la matrice di ordine  ottenuta da  eliminando la prima riga e la j-esima colonna

A n A

1j ​

Problema (n + 1)!

Il numero di operazioni supera  6

10! ≅ 3.6 ∗ 10

18

20! ≅ 2.4 ∗ 10

64

50! ≅ 3 ∗ 10

Metodi numerici

I metodi diretti costituiscono una soluzione esatta, in assenza di errori di arrotondamento, in un numero finito di

operazioni

Per matrici “dense” e di ordine non elevato

I metodi iterativi costituiscono una successione di vettori convergente, sotto opportune condizioni, alla soluzione.

Necessitano criteri di arresto

Per matrici “sparse” e di ordine elevato

Casi facilmente risolubili



diagonale

A

Appunti Completi 6

= /

x b a

i i ii

​ ​ ​ ⟺

= 1, ..., =0 ∀i



i n a

ii

​ ​

= 0



det(A)



triangolare

A

Algoritmo basato su sostituzione in avanti (inferiore) o all’indietro (superiore)

Triangolare inferiore A b

a x b

11 1 1

​ ​ ​

a a x b

21 22 2 2

​ ​ ​ ​

a a a x b

=

21 22 23 3 3

​ ​ ​ ​ ​

​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​

⋮ ⋱ ⋮ ⋮

... ...

a a a x b

n1 a2 nn n n

​ ​ ​ ​ ​

= /

x b a

1 1 11

​ ​ ​

− ∗

b a x

2 21 1

= ​ ​ ​

x

2 ​ ​

a

22 ​

...

i−1

− ∗

∑

b x x

i ik k

k=1

= 3, ...,

=

​ ​ ​ ​

a n

i

i ​ ​

a

ii ​

= 0 ⟺ = 0 ∀i

 

det(A) a

ii ​

Algoritmo di risoluzione in avanti

R R

∈ ∈

n×n n

1. Leggi  triangolare inferiore invertibile e 

A b

= / 1

2. Calcola 

x b a

1 1 1

​ ​ ​ i−1

− ∗x

∑

b a

= 2, … , = i

Ripeti per  → 

3. ik k

i n a k=1

​ ​ ​ ​

i a

​ ​

ii ​

4. Stampa 

x

5. Stop

Triangolare superiore A b

... ...

a a a x b

11 12 1n 1 1

​ ​ ​ ​ ​

a a x b

22 2n 2 2

​ ​ ​ ​

x b

=

3 3

⋱ ⋮ ​ ​

​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​

⋮ ⋮

a a

n−1∗n−1 n−1∗n

​ ​

a x b

nn n n

​ ​ ​

= /

x b a

n n nn

​ ​ ​

− ∗

b a x

n−1 n−1∗n n

= ​ ​ ​

x

n−1 ​ ​

a

n−1∗n−1 ​

...

n

− ∗

∑

b a x

i ik k

k=i+1

= − 1, − 2, ..., 1

=

​ ​ ​ ​

x n n

i

i ​ ​

a

ii ​ = 0 ⟺ =0 ∀i

 

det(A) a

ii ​

Algoritmo di risoluzione in avanti

R R

∈ ∈

n×n n

1. Leggi  triangolare superiore invertibile e 

A b

= /

2. Calcola 

x b a

n n nn

​ ​ ​ − ∗

n

∑

b a x

= − 1, … , 1 = i ik k

Ripeti per  → 

3. k=i+1

i n x ​ ​ ​ ​

i a

​ ​

ii ​

4. Stampa 

x

Appunti Completi 7

5. Stop

Metodo di Gauss

=

Dato il sistema 

Ax b ⎧a + + ... + =

x a x a x b

11 1 12 2 1n 1

n

​ ​ ​ ​ ​ ​ ​

+ + ... + =

⎨

a x a x a x b

21 1 22 2 2n 2

n

​ ​ ​ ​ ​ ​ ​

​ ​

⎩

⋮ + + ... + =

a x a x a x b

1 2

n1 n2 nn n n

​ ​ ​ ​ ​ ​ ​

...

a a a b

11 12 1n 1

​ ​ ​ ​

...

a a a b

21 22 2n 2

​ ​ ​ ​

...

a a a b

= =

31 32 3n 3

A b

​ ​ ​ ​

​ ​ ​ ​ ​ ​ ​ ​

⋮ ⋮

...

a a a b

n1 n2 nn n

​ ​ ​ ​

1. Primo pivot a

= (a −

Con l’elemento , costruiamo il moltiplicatore , e poi sostituiamo le righe successive con

a m i1

11 ​

i1 i1

a

​ ​ ​ ​

11 ​

)x + (a − )x + ... = − 

m a m a b m b

11 1 12 2 1

i1 i2 i1 i i1

​ ​ ​ ​ ​ ​ ​ ​ ​ ​

A(i,:)=A(i,:)-m*A(1,:);

b(i)=b(i)-m*b(1);

2. Pivot successivi

Utilizzando la nuova matrice ottenuta si procede allo stesso modo, utilizzando il primo elemento diverso da zero

della riga successiva (k−1)

a

ik

= ​

m ik (k−1)

​ ​

a

kk ​

(k−1) (k−1) (k−1) (k−1) (k−1) (k−1)

... =

(a − )x + (a − )x + −

m a m a b m b

ik k ik k+1 ik

ik kk i3 i k

k(k+1)

​ ​ ​ ​ ​ ​ ​ ​ ​ ​ ​

A(i,:)=A(i,:)-m*A(k,:);

b(i)=b(i)-m*b(k);

− 1

Dopo  passaggi otteniamo la matrice triangolare superiore U, algoritmo di risoluzione all’indietro per risolvere

n =

il sistema 

Ux b ... ...

a a a b

11 12 1n 1

​ ​ ​ ​

(1) (1) (1)

0 ... ...

a a b

22 2n 2

​ ​ ​

(2) (2) (2)

0 0 ...

a a b

= =

U d

33 3n 3

​ ​ ​

​ ​ ​ ​ ​ ​ ​ ​ ​

⋮ ⋮

(n−1) (n−1)

0 0 0 ... a b

nn n

​ ​

(k) = 0 −

Il metodo di Gauss è applicabile se , ovvero se tutte le matrici  minori principali di  fino all’ordine



a A A n

k

kk ​ ​

1 ) = 0

 hanno 



det(A

k ​

Teorema

R

∈ ) = 0, = 1 … − 1

n+n

Sia  tale che (  minore principale di ordine k) allora il metodo di gauss è



A det(a k n A

k k

​ ​

applicabile.

Algoritmo

Appunti Completi 8

for k=1:n-1

if A(k)(k)==0

break

M(i)(k)=A(i)(k)/A(k)(k);

for j=k+1:n

A(i)(j)=A(i)(j)-M(i)(k)*A(k)(j);

end

b(i)=b(i)-M(i)(k)*b(k)

A(i)(k)=0;

end

if A(n,n) != 0

x(n)=b(n)/A(n)(n);

for i=n-1:1

sum=0;

for k=i+1:n

sum = sum + a(i)(k)*x(k);

end

x(i)=1/a(i)(i)*(b(i)-sum;

end

end

Difetti

Non è applicabile a tutte le matrici invertibili

Si interrompe su pivot nullo

È potenzialmente instabile

Scambio di righe opportuno

Esempio 1 1+ 1

[ ] [ ] [ ]

ε ε

= =

= →

A x

b

1 0.5 1.5 1

​ ​ ​

−3 −3

= 0.3 ∗ 10 , = 10, = 3 = 5.0 ∗ 10