RICHIAMI DI ALGEBRA LINEARE E NORME DI

RICHIAMI DI ALGEBRA LINEARE E NORME DI MATRICI E
VETTORI
LUCIA GASTALDI
1. Matrici. Operazioni fondamentali.
Una matrice A è un insieme di m × n numeri reali (o complessi) ordinati, rappresentato
nella tabella rettangolare seguente:

a11 a12
 a21 a22
A=
 ··· ···
am1 am2

· · · a1n
· · · a2n 
.
··· ··· 
· · · amn
Osserviamo che aij indica l’elemento di A che si trova sulla i-esima riga e sulla j-esima
colonna. La notazione A ∈ Rm×n significa che la matrice A ha m righe ed n colonne di
elementi reali. Nel caso in cui m = n la matrice si dice quadrata di ordine n. Se n = 1
abbiamo un vettore colonna che indicheremo con x ∈ Rm , le cui componenti sono indicate
con xi .
Date due matrici della stessa dimensione A ∈ Rm×n e B ∈ Rm×n , la matrice C ∈ Rm×n di
elementi cij = aij + bij per i = 1, · · · , m e j = 1, · · · , n è la matrice somma delle matrici
A e B. La matrice che ha tutti gli elementi nulli, indicata con 0, è l’elemento neutro rispetto
alla somma di matrici. La matrice B di elementi bij = −aij sommata ad A dà la matrice
nulla.
Dato un numero reale α, il prodotto di A per lo scalare α è dato dalla matrice C ∈ R m×n
di elementi cij = αaij .
Pertanto l’insieme delle matrici in Rm×n gode della struttura di spazio lineare.
Date due matrici A ∈ Rm×p e B ∈ Rp×n , la matrice prodotto C ha dimensione m × n
ed i suoi elementi si ottengono mediante la seguente relazione
cij =
p
X
aik bkj .
k=1
Quindi per moltiplicare tra loro due matrici devono essere ”compatibili”, nel senso che la
prima deve avere un numero di colonne pari al numero delle righe della seconda. Si può
dimostrare che il prodotto di matrici gode della proprietà associativa e distributiva rispetto
alla somma, ma non della proprietà commutativa.
1
2
LUCIA GASTALDI
Il prodotto di due matrici quadrate di ordine n è ancora una matrice quadrata di ordine
n, quindi in Rn×n l’operazione prodotto è ben definita. La matrice identità data da


1 0 ··· ··· 0
 0 1
0 ··· 0 


... ... ...

I=


 0 ··· 0
1 0 
0 ··· ··· 0 1
è l’elemento neutro rispetto al prodotto in Rn×n . Ossia se A ∈ Rn×n , allora AI = IA = A.
Definizione 1. Data una matrice A ∈ Rm×n , chiamiamo trasposta di A la matrice AT ∈
Rn×m che si ottiene scambiando tra loro le righe e le colonne di A.
Valgono le seguenti proprietà:
a.
b.
c.
d.
(AT )T = A;
(A + B)T = AT + B T ;
(AB)T = B T AT ;
(αA)T = αAT per ogni α ∈ R.
Definizione 2. Una matrice A ∈ Rn×n si dice simmetrica se A = AT .
Se vale che AT A = AAT = I allora la matrice si dice ortogonale.
Definizione 3. Sia A ∈ Cm×n , la matrice B = AH ∈ Cn×m è detta matrice coniugata
trasposta o aggiunta di A se vale bij = āji essendo āji il numero complesso couniugato di
Aji .
Valgono le seguenti proprietà:
a.
b.
c.
d.
(AH )H = A;
(A + B)H = AH + B H ;
(AB)H = B H AH ;
(αA)H = ᾱAH per ogni α ∈ C.
Definizione 4. Una matrice A ∈ Cn×n si dice hermitiana se A = AH .
Se vale che AH A = AAH = I allora la matrice si dice unitaria.
2. Matrice inversa
Definizione 5. Data una matrice A ∈ Rn×n , se esiste una matrice X ∈ Rn×n tale che
AX = XA = I, allora A si dice invertibile e la matrice X viene detta matrice inversa di
A e viene indicata con A−1 . Una matrice non invertibile viene detta singolare.
Se A è invertibile anche la sua inversa A−1 lo è, e vale (A−1 )−1 = A. Inoltre anche la
trasposta di A è invertibile e vale (AT )−1 = (A−1 )T = A−T . Infine se A e B sono due matrici
quadrate di ordine n invertibili, anche il prodotto AB è invertibile e vale (AB) −1 = B −1 A−1 .
3
3. Determinante di una matrice
Definizione 6. Dicesi determinante di una matrice quadrata A di ordine n il numero
X
det(A) =
sign(π)a1π1 a2π2 · · · anπn ,
π∈P
dove P = {π = (π1 , · · · , πn )T } è l’insieme degli n! vettori ottenuti permutando il vettore
i = (1, 2, · · · , n)T dei primi n interi e sign(π) è uguale a 1 (rispettivamente -1) se π si ottiene
da i mediante un numero pari (rispettivamente dispari) di scambi.
Valgono le seguenti proprietà:
a. det(AT ) = det(A);
b. det(AB) = det(A) det(B);
c. det(A−1 ) = 1/ det(A);
d. det(αA) = αn det(A), per ogni α ∈ R.
Indichiamo con Aij la matrice di ordine n − 1 ottenuta sopprimendo la i-esima riga e la jesima colonna, e diciamo minore complementare associato all’elemento aij il determinante
della matrice Aij . Chiamiamo minore principale k-esimo di A, il determinante della
sottomatrice principale Ak di ordine k che si ottiene sopprimendo le ultime n − k righe e
colonne di A. Posto ∆ij = (−1)i+j det(Aij ), il cofattore dell’elemento aij , il determinante
può essere ottenuto con la seguente relazione ricorsiva:

se n = 1

 an11
X
det(A) =
∆ij aij per n > 1,


j=1
detta formula di sviluppo del determinante secondo la i-esima riga e la j-esima colonna o
regola di Laplace.
Data una matrice A ∈ Rm×n , consideriamo le sottomatrici quadrate di ordine q che si
ottengono sopprimendo in modo qualunque m − q righe ed n − q colonne. Il corrispondente
determinante si dice minore di ordine q.
Definizione 7. Dicesi rango di una matrice l’ordine massimo dei minori non nulli della
matrice. Esso viene indicato con rank(A). La matrice ha rango massimo o pieno se rank(A) =
min(m, n).
Il rango esprime il massimo numero di vettori colonna linearmente indipendenti di A.
Dato un vettore x ∈ Rn , il vettore prodotto y = Ax ∈ Rm ha componenti date dalla
formula
n
X
aij xj , per i = 1, · · · , m.
yi =
j=1
Osserviamo che, in questa formula, la componente j-esima del vettore x moltiplica gli elementi di A che si trovano sulla j-esima colonna. Indichiamo con aj ∈ Rm il vettore colonna
dato dalla j-esima colonna di A. Allora il vettore y = Ax può essere ottenuto come combinazione lineare dei vettori colonna di A come segue:
n
X
(1)
y = Ax =
xj a j .
j=1
4
LUCIA GASTALDI
Consideriamo lo spazio immagine o range di A
(2)
range(A) = {y ∈ Rm : y = Ax per x ∈ Rn }.
Da (1) si ricava che lo spazio immagine di A coincide con lo spazio vettoriale formato da
tutte le combinazioni lineari delle colonne di A ossia
range(A) = span{a1 , a2 , · · · , an }.
Di conseguenza si ha rank(A) = dim(range(A)).
L’insieme
(3)
si dice nucleo di A.
Valgono le seguenti relazioni:
ker(A) = {x ∈ Rn : Ax = 0}
(4)
rank(A) = rank(AT )
(5)
rank(A) + dim(ker(A)) = n.
In particolare, se m = n ed A è non singolare, si ha che det(A) 6= 0, rank(A) = n e
ker(A)) = {0}.
Un caso che si presenta abbastanza frequentemente nelle applicazioni è quello delle matrici
simmetriche e definite positive.
Definizione 8. Data una matrice A ∈ Rn×n simmetrica essa è definita positiva se
(6)
xT Ax > 0 per ogni x ∈ Rn con x 6= 0.
Teorema 1. (criterio di Sylvester) Una matrice simmetrica A di ordine n è definita positiva
se e solo se
det(Ak ) > 0, per k = 1, 2, · · · , n,
essendo Ak il minore principale di ordine k.
4. Sistemi lineari
Dati una matrice A ∈ Rm×n e un vettore b ∈ Rm , il vettore x ∈ Rn si dice soluzione del
sistema lineare di matrice dei coefficienti A e termine noto b se vale
(7)
Ax = b.
Dalla relazione (1) si vede che la condizione affinché esista x ∈ Rn soluzione di (7) è che
(8)
b ∈ range(A),
ossia che b sia combinazione lineare delle colonne di A. Questo può essere espresso in altri
termini dicendo che la matrice A e la matrice aumentata [A, b] hanno lo stesso rango, cioè
rank(A) = rank([A, b]) (teorema di Rouchè-Capelli).
Quindi se la condizione (8) è soddisfatta esiste almeno un x ∈ R soluzione di (7). Per
quanto riguarda l’unicità della soluzione si osserva che se x1 ∈ Rn e x2 ∈ Rn sono due
soluzioni di (7) allora vale che
Ax1 = b,
e
Ax2 = b.
Sottraendo membro a membro si ottiene Ax1 − Ax2 = A(x1 − x2 ) = 0, quindi la differenza
x1 − x2 è soluzione del sistema omogeneo Ax = 0 ed appartiene al nucleo di A. Quindi
5
si ha unicità della soluzione se ker(A) = {0}. Dalla relazione fondamentale (5) si ha che
ker(A) = {0} equivale a rank(A) = n; se invece rank(A) = r < n allora il sistema omogeneo
ha infinite soluzioni. Più precisamente, ci sono n − r soluzioni linearmente indipendenti, ogni
altra soluzione si ottiene come combinazione lineare di esse.
In conclusione, se vale (8) e se si ha che rank(A) = r < n, allora la soluzione del sistema
lineare Ax = b è data da x = y + x0 essendo y ∈ Rn una qualunque soluzione del sistema
non omogeneo (Ay = b) e x0 ∈ ker(A).
Nel caso in cui A sia un matrice quadrata di ordine n, la condizione rank(A) = n garantisce
che la condizione (8) sia sempre verificata e la relazione (5) implica che la soluzione del
sistema lineare è unica. In questo caso, quindi, la condizione rank(A) = n è equivalente a
det(A) 6= 0. Di conseguenza, la matrice A risulta invertibile e la soluzione del sistema lineare
è espressa da x = A−1 b.
5. Autovalori ed autovettori
Definizione 9. Sia A una matrice quadrata di ordine n a coefficienti reali o complessi, il
numero λ ∈ C si dice autovalore di A se esiste un vettore x ∈ Cn non nullo (x 6= 0) tale
che
(9)
Ax = λx.
Il vettore x è detto autovettore associato all’autovalore λ.
L’insieme degli autovalori della matrice A si chiama spettro di A e si indica con il simbolo
σ(A).
Dicesi raggio spettrale della matrice A il numero ρ(A) dato dal massimo modulo degli
autovalori e si pone
ρ(A) = max |λ|.
λ∈σ(A)
Cerchiamo ora di caratterizzare gli autovalori di A. Dalla relazione (9) si ricava (A−λI)x =
0. Quindi x è autovettore di A associato all’autovalore λ se appartiene al ker(A − λI).
Affinché ker(A − λI) non sia ridotto al solo elemento nullo, la matrice A − λI deve essere
singolare. Concludendo λ ∈ C è autovalore di A se vale
det(A − λI) = 0.
Quindi λ è autovalore della matrice A se e solo se è radice del polinomio caratteristico
p(λ) = det(A − λI). Dal teorema fondamentale dell’algebra segue che esistono esattamente
n autovalori della matrice A se vengono contati tenendo conto della loro molteplicità. In
particolare λ si dice autovalore semplice di A se λ è una radice semplice del polinomio
caratteristico, inoltre si dice che λ ha molteplicità ν se λ è radice di molteplicità ν del
polinomio caratteristico.
Osserviamo che se x è un autovettore di A associato all’autovalore λ anche αx, con α ∈ C,
è autovettore di A associato all’autovalore λ, infatti vale:
A(αx) = αAx = αλx = λ(αx).
Inoltre uno stesso autovettore non può essere associato a due autovalori distinti. Infatti se
Ax = λ1 x e Ax = λ2 x con λ1 6= λ2 , allora (λ1 − λ2 )x = 0 e quindi necessariamente x = 0.
6
LUCIA GASTALDI
Si definisce autospazio associato all’autovalore λ lo spazio lineare
V (λ) = {x ∈ Cn : Ax − λx = 0}.
Si ha che la dimensione di V (λ) è minore o uguale alla molteplicità ν(λ).
Definizione 10. Date due matrici A ∈ Cn×n e S ∈ Cn×n , con det(S) 6= 0, si consideri la
matrice B ∈ Cn×n data da B = S −1 AS. Si dice allora che A e B sono matrici simili e la
trasformazione da A a B si dice trasformazione per similitudine.
Due matrici simili hanno lo stesso spettro e lo stesso polinomio caratteristico, infatti se λ
è un autovalore di A e x è un autovettore associato, vale Ax = λx. Moltiplicando a sinistra
per la matrice S −1 si ricava
S −1 Ax = λS −1 x, da cui segue S −1 ASS −1 x = BS −1 x = λS −1 x,
quindi λ è autovalore di B e S −1 x è l’autovettore associato.
Definizione 11. Data A ∈ Cn×n , se esiste una matrice X ∈ Cn×n invertibile tale che la
matrice Λ = X −1 AX è diagonale, allora la matrice A si dice diagonalizzabile e la matrice
Λ contiene sulla sua diagonale tutti gli autovalori di A.
Se A è diagonalizzabile vale che X −1 AX = Λ e moltiplicando a sinistra per X si ottiene
AX = XΛ. Denotando con xi la i-esima colonna di X, si ricava che Axi = λi xi . Quindi le
colonne di X sono gli autovettori di A. Poiché X ha rango pieno tutte le sue colonne sono
linearmente indipendenti, ne consegue che gli autovettori di una matrice diagonalizzabile
formano una base per Cn .
Il caso della matrice A ∈ Rn×n simmetrica è particolarmente importante. Infatti se A è
simmetrica allora ha autovalori reali ed autovettori a due a due ortogonali. Se inoltre la
matrice è anche definita positiva allora tutti gli autovalori sono positivi.
Allo scopo di calcolare numericamente gli autovalori è utile avere un’indicazione sulle
regioni del piano complesso che li contengono.
Teorema 2. (Teorema di Gershgorin) Sia A una matrice quadrata di ordine n. Per ogni
i = 1, 2, · · · , n consideriamo i dischi Ri e Ci del piano complesso costruiti come segue:
Ri = {z ∈ C : |z − aii | ≤
Ci = {z ∈ C : |z − aii | ≤
n
X
j=1,j6=i
n
X
j=1,j6=i
|aij |}
|aji |}.
Allora gli autovalori di A appartengono sia all’unione dei dischi R i che a quella dei Ci ossia
λ∈
n
³[
i=1
Ri
n
´\³[
i=1
´
Ci .
7
6. Norme di vettore e di matrice
L’insieme dei vettori x ∈ Rn e l’insieme delle matrici quadrate di ordine n formano due
spazi vettoriali, in quanto in essi è definita l’operazione di somma e il prodotto per uno
scalare reale. Introduciamo ora il nuovo concetto di norma che servirà a determinare la
distanza fra elementi dello spazio lineare, la convergenza di successioni a valori nello spazio
lineare e la grandezza delle quantità di interesse.
Ad esempio, se si considerano le soluzioni x e x̃ dei due sistemi lineari seguenti:
Ax = b,
Ax̃ = b + δb
ci si può chiedere quale influenza ha la perturbazione del termine noto δb sull’errore x − x̃.
In questo caso vorremmo stabilire se l’errore è piccolo ogni qual volta δb è piccolo.
Per misurare la grandezza di un elemento in uno spazio vettoriale usiamo le norme.
Definizione 12. Sia V uno spazio vettoriale di elementi x. Dicesi norma un’applicazione
k · k : V → R che gode delle seguenti proprietà:
1. kxk ≥ 0 per ogni x ∈ V ;
2. kxk = 0 se e solo se x = 0;
3. kαxk = |α|kxk, per ogni x ∈ V e α ∈ R;
4. kx + yk ≤ kxk + kyk (disuguaglianza triangolare).
Sia V uno spazio vettoriale e k · k una norma definita su esso. Dati x0 ∈ V ed r > 0, si
dice sfera centrata in x0 di raggio r l’insieme
(10)
B(x0 , r) = {x ∈ V : kx − x0 k < r}.
Iniziamo ad introdurre oltre alla ben nota norma euclidea di vettore, altre due norme
che potranno essere utili in seguito: dato x ∈ Rn si pone
kxk1 =
(11)
kxk2 =
n
X
i=1
Ã
|xi |;
n
X
i=1
|xi |2
!1/2
;
kxk∞ = max |xi |.
1≤i≤n
Nella Fig. 1 sono disegnati gli intorni di raggio unitario nelle norme sopra introdotte. Le
norme definite in (11) sono tra loro equivalenti nel senso che
√
kxk2 ≤ kxk1 ≤ √nkxk2 ;
(12)
kxk∞ ≤ kxk2 ≤ nkxk∞ .
La definizione di norma di matrice è un po’ più complessa in quanto si vuole che sia compatibile con una norma di vettore. Più precisamente data una norma di vettore ad essa si
associa una norma di matrice in modo tale che valga la seguente relazione
kAxk ≤ kAkkxk.
Per ottenere la disuguaglianza desiderata si può definire una norma di matrice, detta norma
di matrice naturale associata alla norma di vettore k · k, come segue: per ogni matrice
8
LUCIA GASTALDI
1
Intorno unitario
|| . ||
2
1
1
Intorno unitario
Intorno unitario
|| . ||
|| . ||
OO
1
Figure 1. Intorni unitari nelle norme k · k2 , k · k∞ e k · k1 .
A ∈ Rn×n
(13)
kAk =
kAxk
.
x6=0 kxk
sup
x∈Rn ,
Ne segue che la norma cosı̀ definita gode anche della proprietà submoltiplicativa:
(14)
kABk ≤ kAkkBk.
Si noti che kIk = 1 per ogni norma naturale di matrice associata ad una norma di vettore.
Ad esempio la seguente norma di Frobenius
!1/2
à n n
XX
kAkF =
a2ij
i=1 j=1
√
non è una norma naturale di matrice come si verifica facilmente poiché kIkF = n.
Le norme naturali di matrice associate alle norme di vettore definite in (11) sono date da:
kAk1 = max
1≤i≤n
(15)
n
X
|aij |,
j=1
n
X
|aij |,
kAk∞ = max
1≤j≤n
i=1
p
kAk2 = ρ(AT A).
Valgono le seguenti disuguaglianze:
√
1
√ kAk1 ≤ kAk2 ≤ nkAk1 ,
n
√
1
√ kAk2 ≤ kAk∞ ≤ nkAk2 ,
n
√
kAk2 ≤ kAkF ≤ nkAk2 ,
kAxk2 ≤ kAkF kxk2 .
Le definizioni delle norme e le conseguenti disuguaglianze valgono anche nel caso di matrici
rettangolari A ∈ Rm×n .
9
7. Numero di condizionamento di una matrice
Dati A ∈ Rn×n e b ∈ Rn con A non singolare, sia x ∈ Rn la soluzione del sistema lineare
Ax = b. Considerata poi una perturbazione δb ∈ Rn del vettore b, indichiamo con x̃ ∈ Rn
la soluzione del sistema Ax̃ = b − δb. Cerchiamo delle relazioni tra la differenza x − x̃ e la
perturbazione sul dato δb. Introduciamo le seguenti quantità:
kx − x̃k errore assoluto,
kx − x̃k
kxk
errore relativo.
Sottraendo membro a membro le due relazioni Ax = b e Ax̃ = b − δb si ricava
Ax − Ax̃ = δb da cui A(x − x̃) = δb.
Essendo A non singolare, si ha
Passando alle norme si ottiene
x − x̃ = A−1 δb.
kx − x̃k = kA−1 δbk ≤ kA−1 k kδbk.
Per valutare l’errore relativo, osserviamo che
kbk = kAxk ≤ kAk kxk da cui
quindi
(16)
Definizione 13. Il numero
(17)
kAk
1
≤
,
kxk
kbk
kδbk
kx − x̃k
≤ kAk kA−1 k
.
kxk
kbk
K(A) = kAk kA−1 k
viene detto numero di condizionamento della matrice A.
Se I è la matrice identità, allora K(I) = 1 e da (14) segue che per ogni matrice A si ha
che K(A) ≥ 1. Se il numero di condizionamento è molto grande allora la matrice si dice
malcondizionata e dalla relazione (16) si vede che anche se la perturbazione sul dato è piccola
si può avere che l’errore relativo sulla soluzione può essere molto grande. Questo risultato
è di grande rilievo nella risoluzione dei sistemi lineari, infatti a causa del procedimento di
calcolo della soluzione si generano errori di arrotondamento che danno luogo ad una soluzione
approssimata x̃. Si dice residuo del sistema il vettore r = b − Ax̃. Allora x̃ può essere visto
come la soluzione relativa al dato b + r e quindi applicando (16) si ha
kx − x̃k
krk
≤ K(A)
.
kxk
kbk
Nel caso in cui si consideri un sistema perturbato della forma:
(A + δA)x̃ = b + δb,
essendo δA una matrice di perturbazione, vale il seguente risultato più generale:
µ
¶
kx − x̃k
kδAk kδbk
K(A)
≤
+
.
kxk
1 − K(A)kδAk/kAk kAk
kbk
10
LUCIA GASTALDI
Dipartimento di Matematica, Università di Brescia, Italy
E-mail address: [email protected]
URL: http://dm.ing.unibs.it/gastaldi/