Matrici(array multidimensionali)
array
Matrici
• In matematica, in particolare in algebra lineare, una matrice è una tabella ordinata di elementi
• Ad esempio, la seguente è una matrice intera:
− 201
531
• In generale
=
nmnn
m
m
aaa
aaa
aaa
A
L
LLLL
L
L
10
11110
00100
array
Algebra delle matrici
• Sulle matrici si possono definire numerose operazioni: due matrici (aventi dei numeri opportuni di righe e colonne) possono essere sommate, sottratte, moltiplicate fra loro, e moltiplicate per un numero (detto scalare)
• Somma ( ) ijijij BABA +≡+
• Esempio
=
+++
+++
+++
≡
+
333
058
731
121221
005071
520301
112
057
500
221
001
231
array
Algebra delle matrici
• Sulle matrici si possono definire numerose operazioni: due matrici (aventi dei numeri opportuni di righe e colonne) possono essere sommate, sottratte, moltiplicate fra loro, e moltiplicate per un numero (detto scalare)
• Moltiplicazione per uno scalare
( ) ijij cAcA ≡
• Esempio
=
⋅⋅⋅
⋅⋅⋅
⋅⋅⋅
≡
⋅
10105
005
10155
252515
050515
253515
221
001
231
5
array
Array multidimensionali
Dichiarazione di array multidimensionali
tipo-elementi nome-array[lung-1][lung-2]· · ·[lung-n]
Esempio: int marketing[10][5][12]
� (indici potrebbero rappresentare: prodotti, venditori, mesi dell’anno)
Esempio: int mat[3][4];
⇒ matrice 3 × 4
� Per ogni dimensione i l’indiceva da 0 a lung-i − 1.
array
Accesso agli elementiEsempio:
Int ele, mat[3][4];
...
ele = mat[0][0]; elemento di riga 0 e colonna 0 (primo elemento)
mat[2][3] = 28; elemento di riga 2 e colonna 3 (ultimo elemento)
mat[2][1] = mat[0][0] * mat[1][3];
� Come per i vettori, l’unica operazione possibile sulle matrici è l’accesso agli elementi tramite l’operatore []
Inizializzazione di matrici
Esempio:
int mat[2][3] = {{1,2,3}, {4,5,6}};
int mat[2][3] = {1,2,3,4,5,6};
int mat[2][3] = {{1,2,3}};
int mat[2][3] = {1,2,3};
int mat[2][3] = {{1}, {2,3}};
array
Esempio
� Esempio:Lettura estampa diuna matrice
#include <stdio.h>
#define RIG 2
#define COL 3
main()
{
int mat[RIG][COL];
int i, j;
/* lettura matrice */
printf("Lettura matrice %d x %d;\n", RIG, COL);
for (i = 0; i < RIG; i++)
for (j = 0; j < COL; j++)
scanf("%d", &mat[i][j]);
/* stampa matrice */
printf("La matrice e’:\n");
for (i = 0; i < RIG; i++) {
for (j = 0; j < COL; j++)
printf("%d\t", mat[i][j]);
printf("\n");
}
}
Esercizi
• Scrivere un programma che
– Acquisisce due matrici 3x4, chiamandole A e B
– effettua la somma A+B registrando il risultato in una
terza matrice C
o Stampa il contenuto di C
– Richiede un valore scalare c
o Effettua il prodotto di A per lo scalare c, cA, e registra il risultato in C
– Stampa il contenuto delle matrici A, B e C
vettori 8
array
Algebra delle matrici
• Moltiplicazione di due matrici
• La moltiplicazione tra due matrici A e B è un'operazione più complicata delle precedenti– La definizione di moltiplicazione è motivata dal fatto che una
matrice modellizza una applicazione lineare: il prodotto di matrici corrisponde alla composizione di applicazioni lineari
• Esempio
++++
++++=
211211110110201210110010
210211010100200210010000
babababababa
babababababa
=
⋅
2120
1110
0100
121110
020100
bb
bb
bb
aaa
aaa
array
Algebra delle matrici
• Moltiplicazione di due matrici
#define M 3#define P 4#define N 2
int a[M][P], b[P][N], c[M][N];.../* calcolo prodotto */for (i = 0; i < M; i++)
for (j = 0; j < N; j++) {c[i][j] = 0;for (k = 0; k < P; k++)
c[i][j] = c[i][j] + a[i][k] * b[k][j];}
• La moltiplicazione tra due matrici A e B è un'operazione più complicata delle precedenti– La definizione di moltiplicazione è motivata dal fatto che una
matrice modellizza una applicazione lineare: il prodotto di matrici corrisponde alla composizione di applicazioni lineari
array
Matrici e sistemi lineari
• Grazie alle regole finora date, le matrici sono utili anche nella rappresentazione di sistemi di equazioni lineari
=+++
=+++
=+++
mnmnmm
nn
nn
bxaxaxa
bxaxaxa
bxaxaxa
L
L
L
L
1100
11111010
00101000
=
⋅
mmmnmm
n
n
b
b
b
x
x
x
aaa
aaa
aaa
LL
L
LLLL
L
L
1
0
1
0
10
11110
00100
array
Esercizi
Esercizio: Leggere due matrici A(MxN) e B(MxN) - l’utente scegliela dimensione (comune) delle matrici (MAX 50*50)
Il programma deve poter:
1. stampare la matrice somma
2. stampare la matrice prodotto (se possibile)
3 . stampare le matrici
4 . uscire dal programma
array
Esercizi
Esercizio: Programma che legge una matrice A(MxN) (le dimensioni sono ascelta dell’utente – dimensioni massime 50*50) e
1. stampa l’elemento massimo con i suoi indici di riga e di colonna
2. costruisce il vettore degli elementi massimi di ogni riga, e lo stampa
3. costruisce il vettore degli elementi massimi di ogni colonna, e lo stampa
4. calcola la matrice T(NxM) trasposta di A, e la stampa
(il generico elemento Tij della trasposta T di A è pari ad Aji)
array
Rango di una matrice
• Nell'algebra lineare, il rango o caratteristica di una matrice A è il massimo numero di colonne (o righe) linearmente indipendenti in A
• Il modo più semplice per calcolare il rango di una matrice A è dato dall'algoritmo di Gauss. L'algoritmo trasforma la matrice in una matrice a gradini con lo stesso rango, dato dal numero di righe non nulle, o equivalentemente di pivot
• Esempio con rango(A)=2
−−=
5263
2200
0121
3142
A
=
0000
0000
1100
15.021
aA
array
Algoritmo di Gauss
• L'algoritmo, attraverso l'applicazione di operazioni elementari dette mosse di Gauss, riduce la matrice in una forma detta a gradini– La matrice così ridotta permette il calcolo del rango della matrice
nonché la risoluzione del sistema lineare ad essa associato
• Le mosse di Gauss sono operazioni che modificano una matrice in uno dei modi seguenti:
• scambiando due righe;
• moltiplicando una riga per un numero diverso da zero;
• sommando una riga ad un multiplo di un'altra riga.
• scambiare l'ordine di scrittura di due equazioni;
• moltiplicare entrambi i membri di un'equazione per un numero diverso da zero;
• sommare ad ogni membro di un'equazione la stessa quantità a sinistra e a destra.
In un sistema di equazioni lineari, le mosse corrispondono a:
array
Algoritmo di Gauss
• L'algoritmo, attraverso l'applicazione di operazioni elementari dette mosse di Gauss, riduce la matrice in una forma detta a gradini– La matrice così ridotta permette il calcolo del rango della matrice
nonché la risoluzione del sistema lineare ad essa associato
• Le mosse di Gauss sono operazioni che modificano una matrice in uno dei modi seguenti:
• scambiando due righe;
• moltiplicando una riga per un numero diverso da zero;
• sommando una riga ad un multiplo di un'altra riga.
• scambiare l'ordine di scrittura di due equazioni;
• moltiplicare entrambi i membri di un'equazione per un numero diverso da zero;
• sommare ad ogni membro di un'equazione la stessa quantità a sinistra e a destra.
E’ comodo –vedremo perché – limitarsi a due tipi di mosse
array
Algoritmo di Gauss
1. Se la prima riga (riga «0») ha il primo elemento nullo, scambiala con una riga che ha il primo elemento non nullo. Se tutte le righe hanno il primo elemento nullo, passa al punto 3
3. Adesso sulla prima colonna tutte le cifre, eccetto forse la prima, sono nulle. A questo punto ritorna al punto 1 considerando la sottomatrice che ottieni cancellando la prima riga e la prima colonna
2. Per ogni riga Ri (eccetto la prima � i>0) cerca il primo elemento non nullo (colonna k), moltiplica la prima riga per un coefficiente scelto in maniera tale che la somma tra la prima riga e Ri abbia l’elemento k-esimo nullo (coefficiente=- aik/ a0k). Sostituisci Ri con la somma appena ricavata
−=
5263
2201
0120
3140
A
−=
5263
3140
0120
2201
aA
0
0
Ra
aRR
k
ikii −←
=
nmnn
m
m
aaa
aaa
aaa
A
L
LLLL
L
L
10
11110
00100
array
Esempio (I)
−
−
−
=
3463
2242
0321
A
0111
2RRR −←
0221
3RRR −←
Non ci sono elementi diversi da zero, passo alla colonna successiva
1224
5RRR −←
1
2
3
−
=
3500
2400
0321
aA
−
=
3500
2400
0321
aA
−
=
3500
2400
0321
bA
−
=
3500
2400
0321
bA
−
=
5.0000
2400
0321
cA
array
Esempio (II)
−−=
5263
2200
0121
3142
A
=
5.05.000
2200
5.15.100
3142
aA
=
5.05.000
2200
5.15.100
3142
aA
0112
1RRR
−−←
0332
3RRR −←
Non ci sono elementi diversi da zero, passo alla colonna successiva
=
0000
0000
5.15.100
3142
cA
=
5.05.000
2200
5.15.100
3142
bA
=
5.05.000
2200
5.15.100
3142
bA
1225.1
2RRR −←
1335.1
5.0RRR −←
1
2
3
array
Una possibile implementazione1. Leggo la matrice
2. Per ogni riga (e dalla prima all’ultima di esse)2.1 devo controllare che la riga che alla colonna "colonna" abbia un elemento diverso da zero (se la colonna è l’ultima, termino il punto (2.1))
2.1.1 se ha zero, devo cercare una riga successiva che alla colonna "colonna" abbia un elemento diverso da zero
– Se c’è, la porto «in cima» alle righe, scambiandola di posto con l’attuale
– altrimenti, passo alla prossima colonna, e torno al punto (2.1)
2.2 se ho ottenuto una riga con alla colonna "colonna" un elemento diverso da zero
2.2.1 in tutte le righe successive effettuo la sostituzione «alla Gauss»
3. Calcolo il rango(numero delle righe contenenti elementi diversi da zero)
4. Calcolo il determinante(produttoria dei termini diagonali – attenzione al numero di scambi in (2))
array
Algebra delle matrici quadrate
• Fra le matrici, occupano un posto di rilievo le matrici quadrate, cioè le matrici n*n – matrici che hanno lo stesso numero n di righe e di colonne
• Elemento neutro per la moltiplicazione:
=
100
010
001
L
LLLL
L
L
I
• Moltiplicando fra loro due matrici quadrate n*n, si ottiene un’altra matrice quadrata n*n – Di una matrice A è quindi possibile calcolare A*A, A*A*A, …
o Fare la potenza di una matrice A, A2, A3, … Am
array
Algebra delle matrici quadrate
• Fra le matrici, occupano un posto di rilievo le matrici quadrate, cioè le matrici n*n – matrici che hanno lo stesso numero n di righe e di colonne
• In matrici quadrate il procedimento di Gauss induce una forma particolare, in cui il «triangolo inferiore» della matrice è composto da soli zeri – Triangolarizzazione di una matrice
– Nota: nel processo possono comparire degli zeri anche in altre posizioni – caso particolare: sulla diagonale
=
004
010
321
A
−
=
1200
010
321
bA
array
Determinante delle matrici quadrate
• In algebra lineare, il determinante è una funzione che associa ad ogni matrice quadrata A uno scalare che ne sintetizza alcune proprietà algebriche
• Il determinante è uno strumento usato in vari settori della matematica:– nello studio dei sistemi di equazioni lineari
– nel calcolo infinitesimale a più dimensioni (p.e. Jacobiano)
– nel calcolo tensoriale,
– nella geometria differenziale
– …
array
Determinante delle matrici quadrate
• In algebra lineare, il determinante è una funzione che associa ad ogni matrice quadrata A uno scalare che ne sintetizza alcune proprietà algebriche
• Il significato geometrico principale si ottiene interpretando la matrice quadrata A di ordine n come trasformazione lineare di uno spazio vettoriale a n dimensioni: – il valore assoluto di det(A) è il fattore con cui vengono modificati i
volumi degli oggetti contenuti nello spazio
– se è diverso da zero, il segno del determinante indica inoltre se la trasformazione A preserva o cambia l'orientazione dello spazio rispetto agli assi di riferimento.
array
Calcolo del determinante…
• … di matrici quadrate (limitiamoci a questi casi).
• Si utilizza lo sviluppo di Laplace
=
1110
0100
aa
aaA ( ) 01101100det aaaaA −≡
=
222120
121110
020100
aaa
aaa
aaa
A
( ) ( )
( )
( )
−+
+
−+
+
−≡
+
+
+
1211
0201
20
02
2221
0201
10
01
2221
1211
00
00
det1
det1
det1det
aa
aaa
aa
aaa
aa
aaaA
• Se A è 2*2:
• Se A è 3*3:
array
Calcolo del determinante…
• … di matrici quadrate (limitiamoci a questi casi).
• Si utilizza lo sviluppo di Laplace
=
1110
0100
aa
aaA ( ) 01101100det aaaaA −≡• Se A è 2*2:
• Se A è n*n: • Ci si riconduce al calcolo di n determinati di matrici (n-1)*(n-1)
• Complicato e dispendioso
array
Calcolo del determinante…
• … di matrici quadrate (limitiamoci a questi casi).
• Si utilizza lo sviluppo di Laplace
• Se però A fosse in forma triangolare…:
=
22
1211
020100
00
0
a
aa
aaa
A
( ) ( )
( )
( )
⋅⋅−+
+
⋅⋅−+
+
−≡
+
+
+
1211
020102
22
020101
22
1211
00
00
det01
0det01
0det1det
aa
aa
a
aa
a
aaaA
array
Calcolo del determinante…
• … di matrici quadrate (limitiamoci a questi casi).
• Si utilizza lo sviluppo di Laplace
• Se però A fosse in forma triangolare…:
=
22
1211
020100
00
0
a
aa
aaa
A
( ) ( )
( )
221100
12221100
22
1211
00
00
0
0det1det
aaa
aaaa
a
aaaA
=
=⋅−=
=
−=
+
• … il determinante sarebbe il semplice prodotto dei termini sulla diagonale
array
Calcolo del determinante…
• … di matrici quadrate (limitiamoci a questi casi).
• Si utilizza lo sviluppo di Laplace
• Le mosse di Gauss (limitate ai due tipi precedentemente evidenziati) mantengono invariato il valore del determinate– Cambia solo il segno ad ogni scambio di righe
• Il procedimento diventa quindi semplice:– Si triangolarizza la matrice (contando quanti scambi di riga sono
stati effettuati – sia «numero_di _scambi» il valore)
– Si effettua il prodotto dei termini sulla diagonale
– Si moltiplica il prodotto così ottenuto per (-1)^(numero_di _scambi)
array
Esercizi (II)
Esercizio: Programma che legge una matrice A(NxN) e
1. verifica se la matrice è diagonale
(una matrice si dice diagonale se Aij≠0 solo quando i =j;
2. verifica se la matrice è simmetrica
(una matrice si dice simmetrica se Aij =Aji per ogni coppia di indici i e j);
3. calcola il rango della matrice
4. calcola il determinante della matrice
array
Esempi
−
−=
152
324
321
A
−=
135
322
102
A
−−
−=
531
323
102
A
−=
314
423
001
A
Det(A)=79 Det(A)=-5
Det(A)=18 Det(A)=10
−−
−−
−−
−−
=
8532
3742
5825
4523
A
Det(A)=-54
Applicazione: regola di Cramer
• Sistema da risolvere
• Se è uguale a zero il metodo di Cramer non è applicabile ed il sistema è impossibile o indeterminato
• Matrice dei coefficienti
array
array
Applicazione: regola di Cramer
• Sistema da risolvere
• Soluzioni
• Matrice dei coefficienti
array
Applicazione: regola di Cramer
• Nota: il calcolo del determinante implica moltissime somme e moltiplicazioni (divisioni)– è quindi instabile
– è pratico solo per sistemi di piccole dimensioni
– è comunque importante, perché indica una via generale di soluzione