Matrici (array multidimensionali) - ISGroup• Sulle matrici si possono definire numerose...

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


• 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


• 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


• 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




=

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




• 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




• 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




• 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


• Sistema da risolvere

• Soluzioni

• Matrice dei coefficienti

array


• 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

Matrici (array multidimensionali) - ISGroup• Sulle matrici si possono definire numerose...

Documents

Transcript of Matrici (array multidimensionali) - ISGroup• Sulle matrici si possono definire numerose...