Algebra lineare - Applicazioni
Antonino Polimeno
Dipartimento di Scienze Chimiche
Università degli Studi di Padova
Sistemi lineari - 1
– Sistema sottodeterminato (n>m), sovradeterminato (n<m)
2
11 1 1 1 1
21 1 2 2 2
1 1
1 1
j j n n
j j n n
i ij j in n i
m mj j mn n m
a x a x a x b
a x a x a x b
a x a x a x b
a x a x a x b
Ax b
– Teorema di Rouchè-Capelli: il sistema ammette soluzioni se
e solo se il rango della matrice associata è uguale al rango
della matrice dei coefficienti.
Sistemi lineari - 2
– La matrice associata (A|b) è
– Il rango rk(A) di una matrice generica A è il numero massimo di righe (o colonne) linearmente indipendenti della matrice; il rango è evidentemente minore o uguale al minimo tra il numero di righe e colonne
11 1 1
21 2 2
1
|
n n
m mj mn
a a b
a a b
a a a
A b
Sistemi lineari - 3
– Un sistema lineare omogeneo (b=0) ammette sempre almeno una soluzione
– Lo spazio delle soluzioni ha dimensione n-rk(A); p.es. n-rk(A)=2 significa che lo spazio vettoriale di tutte le soluzioni è formato da (infinite) n-uple di numeri combinazioni lineari di due n-uple
specifiche etc.
– se il sistema è sovradeterminato (n<m, più equazioni che
incognite), se esistono soluzioni, possiamo avere una soluzione (e quindi possiamo costruire n equazioni indipendenti a partire dalle m date) o infinite soluzioni
– se n=m (n. equazioni = n. incognite), se esistono soluzioni, possiamo avere una soluzione o infinite soluzioni
– se il sistema è sottodeterminato (n>m, più incognite che equazioni), se esistono soluzioni, sono infinite
4
Sistemi lineari - 4
– Il caso di maggiore interesse è dato da n=m:
– se rk(A)=n esiste una sola soluzione, si pùo dimostrare che A è invertibile e la soluzione si può scrivere come x=A-1b (se b=0 il sistema è omogeneo e la soluzione è triviale, x=0, altrimenti è il caso del sistema lineare non omogeneo con un’unica soluzione)
– se rk(A)<n, si pùo dimostrare che A non è invertibile ed esistono infinite soluzioni; il caso più comune è quello del sistema omogeneo con soluzione non triviale
n=m; sistema omogeneo?
sì rk(A)=n, quindi det(A) 0 - soluzione triviale
rk(A)<n, quindi det(A) = 0 - soluzione non triviale
no
rk(A)=n, quindi det(A) 0 - soluzione unica rk(A)<n, quindi det(A) = 0 - infinite soluzioni
Bilanciamento di una reazione chimica
6
1 C H O 6 12 6 2 O 2 3 CO 2 4 H O 2
x x x x
1 2 3 4
1 2 3 4
1 2 3 4
1 2 3 4
6 0 1 0 0
12 0 0 2 0
6 2 2
C 6 0 0
H 12 0 0 3
O 6 2
1 0
2
x x x x
x x x x
x
x x x
x x x
x
A x b
Il sistema è sottodeterminato (3 equazioni e 4 incognite); il teorema RC e verificato con rango di A pari a 3; sono quindi date
1 soluzioni
Soluzioni di sistemi lineari
– Algoritmo di Gauss Jordan – Decomposizione LU
– Decomposizione SVD
– Algoritmi iterativi per grandi sistemi con matrici sparse (gradiente coniugato)
→ metodi diretti: la soluzione si ottiene con un numero fintito di operazioni
→ algoritmi iterativi: la soluzione è costruita come limite di una successione infinita
Sistema triangolare
8
11
12 22
1 2
1
1
0 0
0
for 1, :
n n
i j
nn
j
j ij
i jj
x x
a
a a
a a a
j n
b a
a
A
matrice triangolare (superiore) 2
O n
Metodo di Cramer
1 2 3
3 2 1 39 2 1 3 39 1 3 2 39
2 3 1 34 3 1 2 34 1 2 3 34
1 2 3 25 2 3 37 1 25 3 17 1 2 25 11
, ,
det 4 det 4 det 4
39 34 26
x x x
A
A A A
b
!
O n
per n=20, per 1 ns per operazione, circa 150 anni
Metodo di eliminazione
10
1 2 3
1 2 3
1 2 3
3 2 1 39
| 2 3 1 34
1 2 3 26
3 2 39
2 3 34
2 3 34
x x x
x x x
x x x
A b
per -2/3, sommata alla seconda equazione
3
O n
Metodo di eliminazione
1 2 3
1 2 3
1 2 3
3 2 1 39
| 0 5 / 3 1 / 3 8
1 2 3 26
3 2 39
5 1
0 8
3 3
2 3 34
x x x
x x x
x x x
A b
per -1/3, sommata alla terza equazione
Metodo di eliminazione
12
1 2 3
1 2 3
1 2 3
3 2 1 39
| 0 5 / 3 1 / 3 8 0 4 / 3 8 / 3 13
3 2 39
5 1
0 8
3 3
4 8
0 13
3 3
x x x
x x x
x x x
A b
per -4/5, sommata alla terza equazione
Metodo di eliminazione
1 2 3
1 2 3
1 2 3
3 2 1 39
| 0 5 / 3 1 / 3 8 0 0 12 / 5 33 / 5
3 2 39
5 1
0 8
3 3
12 33
0 0
5 5
x x x
x x x
x x x
A b
sistema triangolare
2
O n
Trasformazione di Gauss
14
11 1
1
1 11 1
1 11
1 0 0
1 0
0
0 1
n
n nn
i
n
a a
a a
a L a
a a
A
1 1
11 12 1 1
2 2 2
22 2 2
2 2 1 1 1
2 2 2
2
| |
| | 0
0
n
n
n nn n
a a a b
a a b
a a b
A b A b
A b L A b
Trasformazione di Gauss
1
1 0 0 0
0 0 0 0
con :
0 1 0
0 0 1
k ik
ik k k
k k ik
nk
m a
a m
m
