12. Matrici Sistemi Trasformazioni - copernico.bo.it · Definizione: Minore complementare di un ......

Appunti java Capitolo 12 pag. 1

12. Matrici Sistemi Trasformazioni 12.0 Matrici: definizioni e proprietà. Definizione: Matrice Si dice Matrice reale A del tipo m x n l’insieme di m·n numeri reali disposti su m righe ed n colonne come segue:

mnmm

n

n

aaa

aaaaaa

...............

...

...

21

22221

11211

Le scritture [ ]ika , ( )ika , ika con 1 ≤ i ≤ m e 1 ≤ k ≤ n sono modi per indicare una matrice di m righe e n colonne. Definizione: Matrice rettangolare Una matrice è rettangolare se m ≠ n; Definizione: Matrice quadrata Una matrice è quadrata se m = n;

nnnnn

n

n

aaa

aaaaaa

...............

...

...

2

22221

11211

Definizione: Matrice NULLA Una matrice A si dice nulla se ha tutti gli elementi uguali a 0. La si indica sinteticamente anche con A=0 Definizione: Matrici dello stesso tipo Due matrici A e B si dicono dello stesso tipo se hanno lo stesso numero di righe e di colonne. In due matrici dello stesso tipo gli elementi di ugual posto si dicono corrispondenti. Definizione: Matrici EGUALI Due matrici A e B si dicono eguali se hanno lo stesso numero di righe e di colonne e tutte le componenti corrispondenti identiche. La relazione di eguaglianza tra matrici gode delle proprietà Riflessiva A = A, Simmetrica se A = B segue B = A e Transitiva se A = B e B = C segue che A = C. Definizione: Matrice RIGA e Matrice COLONNA Si dice matrice (o vettore) riga una matrice con un’unica riga, cioè una matrice del tipo 1 x n. Si dice matrice (o vettore) colonna una matrice con un’unica colonna, cioè una matrice del tipo m x 1.


Definizione: Diagonale principale e secondaria, elementi coniugati di una matrice quadrata, matrice simmetrica In una matrice quadrata

nnnn

n

n

aaa

aaaaaa

...............

...

...

21

22221

11211

gli elementi a11, a22, …, ann costituiscono la diagonale principale, gli elementi a1n, …, an1 quella secondaria. Gli elementi aik e a ki, con gli stessi indici ma in ordine inverso si dicono coniugati e i loro posti sono simmetrici rispetto alla diagonale principale. Se gli elementi coniugati sono fra loro uguali, cioè se aik = aki, allora la matrice si dice simmetrica. Definizione: Matrice diagonale Si dice matrice diagonale una matrice quadrata che ha tutti i termini nulli tranne quelli della diagonale principale.

nna

aa

...00............0...00...0

22

11

Definizione: Matrice triangolare superiore (inferiore) Si dice matrice triangolare superiore (inferiore) una matrice quadrata che ha nulli i termini aik =0 se i>k (aik = 0 se i<k)

Mat. Triangolare superiore

nn

n

n

a

aaaaa

...00............

...0

...

222

11211

Mat. Triangolare inferiore

nnnnn aaa

aaa

...............0...0...0

2

2221

11

Definizione: Matrice Identità (o Unità) La matrice Identità è una matrice quadrata del tipo n x n con tutti gli elementi della diagonale principale uguali a 1 e tutti i restanti nulli.

1...00............0...100...01


Definizione: Matrice Trasposta

Si dice Matrice trasposta di A del tipo m x n e la si indica con AT la matrice ottenuta dalla A trasformando ordinatamente le righe di A in colonne di AT che sarà del tipo n x m

=

mnmm

n

n

aaa

aaaaaa

A

...............

...

...

21

22221

11211

=

mnnn

m

m

T

aaa

aaaaaa

A

...............

...

...

21

22212

12111

Definizione: Moltiplicazione di una matrice per uno scalare Data la matrice A di tipo m x n e un numero reale r si chiama prodotto della matrice A per lo scalare r la matrice di tipo m x n ottenuta moltiplicando per il reale r gli elementi della matrici A.

[ ]ikar ⋅=⋅=⋅ ArrA Definizione: Addizione di matrici La matrice somma di due matrici A e B dello stesso tipo m x n é una matrice C del tipo m x n ottenuta sommando gli elementi corrispondenti delle due matrici A e B. Siano A e B due matrici dello stesso tipo m x n e siano r e s due numeri reali valgono le seguenti proprietà:

1. r(sA)= (rs)A 2. r(A + B) = rA + rB 3. 0·A=A·0=0

4. (r + s)A = rA + sA 5. 1·A=A 6. (rA)T=rAT

12.1 Proprietà delle matrici rispetto all’addizione L’insieme delle matrici del tipo m x n formano un gruppo commutativo rispetto all’operazione di addizione. Infatti:

1. La somma è una legge di composizione interna; 2. E’ associativa (A + B)+C = A + (B + C) 3. E’ commutativa A + B = B + A 4. Ha per elemento neutro la matrice Nulla A + 0 = 0 + A = A 5. Ogni matrice è dotata di un’opposta ottenuta da A cambiando il segno di tutte le componenti

e si indica con (–A) tale che A +(−A )= 0 Vale inoltre la legge di semplificazione: se A + C = B + C segue che A = B Definizione: Moltiplicazione tra matrici La moltiplicazione tra le matrici A e B è possibile solo se il numero di colonne della prima matrice coincide con il numero di righe della seconda. In altri termini per poter moltiplicare A per B A deve avere dimensione m x p e B p x n. Il prodotto è la matrice C del tipo m x n ottenuta moltiplicando i termini di ogni riga di A con i corrispondenti termini delle colonne di B e sommando i prodotti ottenuti.

Per esempio

a11 a12 a21 a22

b11 b12 b13 b21 b22 b23 x =

(a11.b11+a12.b21) (a11.b12+a12.b22) (a11.b13+a12.b23) (a21.b11+a22.b21) (a21.b12+a22.b22) (a21.b13+a22.b23)

Appunti java 1.0 Cap 12 Sistemi 4

12.2 Proprietà delle matrici rispetto alla moltiplicazione Nell’insieme delle matrici la moltiplicazione

1. è una legge di composizione interna; se la prima matrice è del tipo m x p e la seconda del tipo p x n, la matrice prodotto è del tipo m x n;

2. è associativa (A * B) * C = A * (B * C) INOLTRE

• NON vale la proprietà COMMUTATIVA * *A B B A≠ (evidente, se di ordini m x p e p x n con m diverso da n, ma non vale anche se le matrici sono n x n)

• NON vale la legge di annullamento del PRODOTTO * 0 0 0A B non segue A B= = ∨ =

1 0 0 00 0

2 0 0 0 * 0 0 03 4

1 0 0 0A B A B

= ≠ = ≠ = = −

• NON vale la legge di semplificazione 1 0 1 2 1 2

1 2 1 22 0 * 2 4 * 2 4

3 4 1 11 0 1 2 1 2

A B C A B A C

= = = = = = − − − − −

• Vale la proprietà (A * B)T = BT * AT • Vale la proprietà distributiva a sinistra del moltiplicazione rispetto all’addizione

A*(B +C)=A*B+A*C • Vale la proprietà distributiva a destra del moltiplicazione rispetto all’addizione

(B + C)*A=B*A+C*A 12.3 Determinante di una Matrice quadrata Definizione: Determinante di una matrice quadrata Ad ogni matrice quadrata è associato un numero che si chiama determinante. Il determinante della matrice A si indica con A.

Definizione: Minore complementare di un elemento di una matrice quadrata Si dice minore complementare di un elemento aik di una matrice quadrata A di ordine n e lo si indica con Mik il determinante della matrice quadrata di ordine n-1 che si ottiene dalla A eliminando tutti gli elementi della riga e della colonna a cui appartiene aik . |A|= il minore compl. di a11 è 11M = |A|= il minore compl. di a12 è 12Μ = Definizione: Complemento algebrico di un elemento di una matrice quadrata Si dice complemento algebrico di un elemento aik di una matrice quadrata A di ordine n e lo si indica con Aik il minore complementare Mik preceduto dal segno positivo se i+k è pari, negativo se dispari.

Aik=(-1)i+k.Mik

a11 a12 a13 a21 a22 a23 a31 a32 a33

a22 a23 a32 a33

a11 a12 a13 a21 a22 a23 a31 a32 a33

a21 a23 a31 a33


Il calcolo del determinante può essere definito ricorsivamente nel seguente modo: • Il determinante di una matrice A del tipo 1 x 1 è il valore della sua unica componente e si

indica con ikA a= • Il determinante di una matrice A del tipo n x n lo si ottiene come somma dei prodotti di

ciascun elemento di una linea qualsiasi, riga o colonna, per il rispettivo complemento algebrico.

Il determinante di una matrice diagonale o di una matrice triangolare è uguale al prodotto degli elementi della diagonale principale. Definizione: Matrice SINGOLARE Una matrice con determinante nullo si dice singolare o degenere; viceversa una matrice con determinante non nullo si dice non singolare o regolare. 12.3.1 PROPRIETÀ dei determinanti

1. Una matrice quadrata e la sua trasposta hanno lo stesso determinante.

2. Se una riga (o una colonna) di una matrice quadrata ha tutti gli elementi nulli il determinante è 0.

3. Scambiando fra loro due righe (o due colonne) il determinante cambia di segno

4. Se in una matrice quadrata due righe o due colonne hanno gli elementi proporzionali il

determinante è nullo.

5. Se si moltiplicano gli elementi di una riga o una colonna per una costante reale k, il determinante della matrice resta moltiplicato per k.

6. Il determinante di una matrice non cambia se ad una linea si aggiunge una linea parallela

moltiplicata per un numero k.

7. Sia B una matrice dello stesso ordine di A, il determinante di A∗B è uguale al prodotto dei determinanti delle due matrici A e B.

8. La somma dei prodotti degli elementi di una riga (colonna) per i complementi algebrici di

una riga (colonna) diversa vale zero (teorema di Laplace).

9. Se gli elementi di una riga (colonna ) sono la somma di due (o più) addendi, il determinante della matrice è uguale alla somma di due (o più) determinanti, che si ottengono dal determinante dato conservando le altre righe (colonne) e sostituendo a quella binomia (polinomia) una volta i primi addendi, un'altra i secondi addendi (e così via).

Es.

nnn2n1

2n2221

1n1211

nnn2n1

2n2221

1n1211

nnn2n1

2n2221

1n1n12121111

a ... a a.........................

a ... a ab ... b b

a ... a a.........................

a ... a aa ... a a

a ... a a ............................................

a ... a a ba ... ba ba

+=

+++


12.3.2 Matrici quadrate con determinante non nullo L’insieme delle matrici quadrate del tipo n x n formano un gruppo non commutativo rispetto all’operazione di moltiplicazione:

1. il prodotto di due matrici del tipo n x n è una legge di composizione interna; 2. E’ associativa (A*B)*C = A*(B*C) 3. Ha per elemento neutro la matrice Identità A*I = I*A=A 4. Ogni matrice con determinante non nullo è dotata di inversa che si indica con A-1 tale che

A-1*A=A*A-1=I Inoltre

• NON vale la proprietà COMMUTATIVA • NON vale la legge di annullamento del PRODOTTO • Se il determinante di C non è nullo vale la legge di semplificazione:

A*C = B*C segue che A=B Infatti C-1 esiste, quindi A*C*C-1=B*C*C-1 da cui A*I=B*I da cui A=B

• Vale la proprietà (A*B)-1=B-1*A-1 • Vale la proprietà distributiva a sinistra della moltiplicazione rispetto all’addizione

A*(B+C)=A*B+A*C • Vale la proprietà distributiva a destra della moltiplicazione rispetto all’addizione

(B+C)*A=B*A+C*A Matrice inversa

Definizione: INVERSA di una matrice quadrata Si dice inversa di una matrice quadrata A di ordine n la matrice quadrata di ordine n, se esiste, A-1 che moltiplicata a destra e a sinistra per la matrice data dà la matrice identità. Cioè:

A*A-1= A-1*A=I.

Teorema: di esistenza dell’inversa di una matrice quadrata.

Si dimostra che

− esiste l'inversa solo delle matrici non singolari − l'inversa di una matrice quadrata, se esiste, è unica;

Data la matrice

=

nnn2n1

2n2221

1n1211

a ... a a.........................

a ... a aa ... a a

A con D ≠ 0 l'inversa è data da

=−

DA ...

DA

DA

......................... D

A ... D

A D

AD

A ...

DA

D

A

nn2n1n

n22212

n12111

1A

dove Aij è il complemento algebrico di aij Infatti, per la proprietà 8 dei determinanti (Teorema di Laplace), si ha:


=

1 ... 0 0............... 0 ... 1 00 ... 0 1

DA ...

DA

DA

......................... D

A ... D

A D

AD

A ...

DA

D

A

*

a ... a a.........................

a ... a aa ... a a

nn2n1n

n22212

n12111

nnn2n1

2n2221

1n1211

Regola per ottenere la matrice inversa della matrice A avente per determinante D.

1. Si determina la trasposta di A 2. Si sostituisce ciascun elemento con il rispettivo complemento algebrico diviso per D

nn2n1n

n22212

n12111

a ... a a.........................

a ... a aa ... a a

DA ...

DA

DA

......................... D

A ... D

A D

AD

A ...

DA

D

A

nn2n1n

n22212

n12111

Oppure

1. Si sostituisce ciascun elemento di A con il rispettivo complemento algebrico diviso per D . 2. Si determina la trasposta della matrice ottenuta.

DA ...

D2A

DA

......................... D

A ... D

A D

AD

A ... D

A D

A

nn2nn1

2n2221

1n1211

DA ...

DA

DA

......................... D

A ... D

A D

AD

A ...

DA

D

A

nn2n1n

n22212

n12111

Definizione: Matrice aggiunta

Si dice matrice aggiunta della quadrata di ordine n A e si indica con A+

nn2n1n

n22212

n12111

A ... A A.........................

A ... A AA ... A A

Pertanto DAA

+− =1 e DAADA ⋅=⋅= −−+ 11

Inoltre IDDAADAAAA ⋅=⋅⋅=⋅⋅=⋅ −−+ )()( 11

Esempio:

A=

− 11

21 A = 3 [αik]=

−

−−

31

32

31

31

A-1=[αki]=

−

31

31

32

31

Verificare eseguendo A*A-1=I


12.4 Progettare in java la classe matrici Sulla base delle proprietà elencate si potrebbe realizzare la seguente classe: Esempio 1: “Si desidera calcolare il determinante di una matrice quadrata in modo ricorsivo” Per ricordare le modalità con cui si progetta un algoritmo ricorsivo, riprendiamo l’esempio del fattoriale di un numero N. Fattoriale ricorsivo:

Se N=0; fat(0)=1; (oppure N=1; fat(1)=1); Se N>1; fat(N)=N*fat(N-1);

Si riporta il metodo statico del fattoriale in Java: public class Mia{

public static long fat(long n) { if (n==0) return 1; else return n*fat(n-1); }

} Esempio di invocazione long R=Mia.fat(7);

Matrice - double[][] A;

+Matrice(double[][] a); +Matrice(double[]a, int c); +Matrice(int r, int c, double mn, double mx); +Matrice(int r, int c); +toString():String; +sum(Matrice b): Matrice; +per(Matrice b): Matrice; +opp() : Matrice; +det() : double; +inv() : Matrice; +mco() : Matrice;


Riprendiamo la definizione ricorsiva del determinante: Se n=1 segue det(A,1) = A[0][0];

se n>1 segue det(A,n) = 1

00

0( 1) [0][ ] det( , 1)

nk

kk

A k A n−

+

=

− ⋅ ⋅ −∑

dove A0k è la matrice che si ottiene eliminando la riga e la colonna cui appartiene l’elemento di posizione 0, k . Sia double[][] A l’attributo della classe Matrice:

public double det() { // metodo dinamico della classe Matrice double d=0 ; if (A.length != A[0].length) { System.out.print("Dim. Illegittima"); System.exit(1); } else if (A.length==1) d=A[0][0] ; else for (int c=0 ; c<A.length; c++) if (c%2==0) d=d+A[0][c]*(mco(0,c)).det(); else d=d - A[0][c]*(mco(0,c)).det(); return d; }

public Matrice mco(int r, int c) { // restituisce la matrice coniugata di a(r,c) ; int R=A.length; int C=A[0].length; double[][] m=new double[R-1][C-1]; if (r<R && c<C) { for (int i=0; i<r; i++) { for (int j=0; j<c; j++) m[i][j]=A[i][j]; for (int j=c+1; j<C; j++) m[i][j-1]=A[i][j]; }

for (int i=r+1; i<R; i++) { for (int j=0; j<c; j++) m[i-1][j]=A[i][j]; for (int j=c+1; j<C; j++) m[i-1][j-1]=A[i][j]; } } else { System.out.println("parametri illegittimi."); System.exit(1); } Matrice Ris=new Matrice(m); return Ris; } Esempio di invocazione double[][] a={{1,3},{2, 5}}; Matrice M=new Matrice(a); double D=M.det(); System.out.println(D);


12.5 Sistemi lineari. Alcune definizioni sui sistemi Un sistema si dice lineare se tutte le equazioni sono di primo grado nelle incognite.

Un sistema lineare si dice − omogeneo se i termini noti di tutte le equazioni sono nulli − non omogeneo se il termine noto di almeno una equazione è diverso da zero − incompatibile o impossibile se l’insieme delle soluzioni è vuoto − compatibile se l’insieme delle soluzioni non è vuoto. Un sistema compatibile può essere

• determinato se ammette una ed una sola soluzione • indeterminato se ammette infinite soluzioni.

Rappresentazione di un sistema lineare con le matrici.

Un sistema lineare di n equazioni in n incognite

(1)

11 1 12 2 1 1

21 1 22 2 2 2

1 1 2 2

......

.............

n n

n n

n n nn n n

a x a x a x ba x a x a x b

a x a x a x b

+ + + = + + + = + + + =

può essere rappresentato tramite le matrici

11 12 1

21 22 2

1 2

...

...... .... ... ...

...

n

n

n n nn

a a aa a a

A

a a a

=

1

2

...

n

xx

X

x

=

1

2

...

n

bb

B

b

=

con A matrice dei coefficienti, X vettore colonna delle incognite, B vettore colonna dei termini noti.

In base alla definizione della moltiplicazione tra matrici, il sistema (1) può essere rappresentato dall’equazione matriciale:

A*X=B cioè, esplicitando,

11 12 1 1 1

21 22 2 2 2

1 2

...

...*

... .... ... ... ... ......

n

n

n n nn n n

a a a x ba a a x b

a a a x b

=

(2)

Pertanto la scrittura (1) del sistema è equivalente alla (2). Esempio di sistema lineare in due incognite :

Il sistema 3

1 2 5x yx y

+ =

− − = − (3) può essere scritto come

1 11 2

− −

*xy

=35

−

, eseguendo il

prodotto si ottiene:

−

=

−−+

53

y2x1y1x1

che coincide con il sistema (3).


12.5.1 Risoluzione dei sistemi: metodo della matrice inversa Se la matrice dei coefficienti non è singolare, cioè se det A ≠ 0, allora esiste la matrice inversa di A e si possono moltiplicare a sinistra entrambi i membri dell’equazione matriciale per A-1 ottenendo così il vettore delle soluzioni del sistema. In simboli: Se 1 1 1 1 10 * * * * *A A quindi se A X B A A X A B I X A B X A B− − − − −≠ ⇒ ∃ = ⇒ = ⇒ = ⇒ = Pertanto segue che la soluzione X di un sistema lineare con determinante della matrice dei coefficienti A non nullo, si ottiene moltiplicando l’inversa A-1 per il vettore dei termini noti B. Esempio

La soluzione del sistema (3) 3

2 5x yx y

+ =

− − = − considerato in precedenza la si può ottenere come

segue:

A = 1 11 2

− −

determinante di A A = -1

matrice inversa [ ] IKIK

AA

α

=

ovvero [ ] IKIK

AA

α

=

=

2 11 11 11 1

− − −

− − −

da cui [ ] 1 2 11 1KI Aα −

= = − −

pertanto il vettore delle soluzioni è [ ] 2 1 3 1*

1 1 5 2X

= = − − − .

Problema Progettare e realizzare la classe Sistema che preveda il metodo solInversa ( ) per la risoluzione dei sistemi lineari di n equazioni in n incognite utilizzando il metodo della matrice inversa. Costruire un main di prova. Indicazioni per un prototipo della classe Sistema:

Sistema

−MC, MN, MCP: Matrice; + Sistema(double a[][], double b[]) + Sistema(Matrice a, Matrice b) + toString( ):String; + solInversa( ):Matrice;


dove MC è la Matrice dei Coefficienti MN è la Matrice colonna dei termini Noti, MCP è la Matrice Completa

• Sai costruire un metodo per eseguire il prodotto di matrici? • Qual è l’algoritmo per determinare l’inversa di una matrice ?

12.5.2 Risoluzione dei sistemi: metodo di Cramer

Teorema di Cramer: Se il determinante A della matrice dei coefficienti del sistema è diverso da zero, il sistema ammette una ed una sola soluzione data da:

1 21 2 ........ n

nD D Dx x xA A A

= = =

dove i numeratori Di rappresentano i determinanti che si ottengono dalla matrice dei coefficienti sostituendo la colonna i-esima con la colonna dei termini noti B.

Consideriamo di nuovo la soluzione X = A−1*B dell’equazione A*X=B;

=

nn b

b

b

x

x

x

...*

DA ...

DA

DA

......................... D

A ... D

A D

AD

A ...

DA

D

A

...2

1

nn2n1n

n22212

n12111

2

1

dove D = |A| è il determinante della matrice dei coefficienti, Aij è il complemento algebrico di aij; il valore di x1 è dato da:

( )nn bbbbbbx n1221111n1

221

111

1 A...AAD1

DA...

DA

DA

+++=+++=

Poiché A11 è il complemento algebrico di a11, A21 è il complemento algebrico di a21, … An1 è il complemento algebrico di an1, nbbb n1221111 A...AA +++ è lo sviluppo del determinante:

nnnn

n

n

aab

aabaab

...............

...

...

2

2222

1121

Pertanto D

aab

aabaab

x nnnn

n

n

...............

...

...

2

2222

1121

1 = dove D è il determinante della matrice dei coefficienti, mentre al

numeratore si ha il determinante della matrice ottenuta dalla matrice dei coefficienti sostituendo alla prima colonna il vettore colonna dei termini noti. Il valore x2 è dato da:


( )nn bbbbbbx n2222112n2

222

112

2 A...AAD1

DA...

DA

DA

+++=+++=

Poiché A12 è il complemento algebrico di a12, A22 è il complemento algebrico di a22, … An2 è il complemento algebrico di an2, nbbb n2222112 A...AA +++ è lo sviluppo del determinante

nnnn

n

n

aba

abaaba

...............

...

...

1

2221

1111

Pertanto D

aba

abaaba

x nnnn

n

n

...............

...

...

2

2222

1112

2 = dove D è il determinante della matrice dei coefficienti, mentre al

numeratore si ha il determinante della matrice ottenuta dalla matrice dei coefficienti sostituendo alla seconda colonna il vettore colonna dei termini noti. In generale il valore x i è dato da:

( )nni bbbbbbx ni22i11ini

22i

11i A...AA

D1

DA...

DA

DA

+++=+++=

Poiché A1i è il complemento algebrico di a1i, A2i è il complemento algebrico di a2i, … Ani è il complemento algebrico di ani. nbbb ni22i11i A...AA +++ è lo sviluppo del determinante

nnnnn

n

n

abaa

abaaabaa

........................

......

......

21

222221

111212

Pertanto D

abaa

abaaabaa

x nnnnn

n

n

i

........................

......

......

21

222221

111212

= dove D è il determinante della matrice dei coefficienti,

mentre al numeratore si ha il determinante della matrice ottenuta dalla matrice dei coefficienti sostituendo alla i-sima colonna il vettore colonna dei termini noti. Si può quindi concludere che il Metodo di Cramer per risolvere sistemi lineari di n equazioni in n incognite coincide con il Metodo della Matrice inversa. Esempio Risoluzione del sistema (3) con il metodo di Cramer

32 5

x yx y

+ =

− − = −


A=1 11 2

− −

D = |A| = −1 1

3 11

5 2D = = −

− − 2

1 32

1 5D = = −

− −

1 21 21 1

x y− −= = = =

− −

Problema Progettare e realizzare un programma (con le classi necessarie) che consenta di risolvere sistemi lineari di n equazioni in n incognite utilizzando il metodo di Cramer. Indicazioni per un prototipo della classe Sistema:

Sistema

−MC, MN, MCP: Matrice;

+ Sistema(double a[][], double b[]) + Sistema(Matrice a, Matrice b)

− sost( int i):Matrice + cramer( ):Matrice; + solInversa( ):Matrice; + toString( ):String;

Sai costruire un metodo sost che sostituisca un vettore colonna di una matrice A nxn con il vettore dei termini noti B ?

Di seguito è riportato lo sviluppo del metodo di Cramer: public Matrice cramer() { int N=MC.length; double D=MC.det(); // determinante della matrice dei coefficienti

double x[]=new double[N]; // vettore che conterrà le soluzioni double dris[]=new double[N]; /* vettore il cui elemento i-simo è il determinante della

matrice M, ottenuta dalla matrice dei coefficienti sostituendo alla i-sima colonna il vettore colonna dei termini noti*/

double tutti=0; for (int i=0; i<N; i++){ Matrice M=MC.sost(i); dris[i]=M.det(); tutti=tutti+Math.abs(dris[i]); // tutti=0 se e solo se ogni elemento di dris è zero

} if (D!=0) { for (int i=0; i<N; i++) x[i]=dris[i]/D;

} else if (tutti==0) { System.out.println(“Sistema indeterminato.”); System.exit(1); } else { System.out.println(“Sistema impossibile.”); System.exit(1); } Matrice R=new Matrice(x,1); return R;

}


Il seguente spezzone di main() utilizza le classi Matrice e Sistema: double[][] a={{1, 2, 3},{1, 0, 1},{0, 4, -2}}; double[] b={4, 2, 1}; Sistema S=new Sistema(a,b); System.out.println(S); Matrice r=S.cramer( ); System.out.println(r);

12.5.3 Risoluzione del sistema: metodo della sostituzione a ritroso Se il sistema è nella forma

=

=+

=+++

=++++

−−−−−

−−

−−

nnnn

nnnnnnn

nnnn

nnnn

bxabxaxa

bxaxaxabxaxaxaxa

,

1,111,1

2,211,222,2

1,111,122,111,1

...................................................................

e il determinante della matrice dei coefficienti è diverso da zero, pertanto a ii ≠ 0 con i = 1, … n, si può determinare il valore dell’incognita x n dall’ultima equazione

nn

nn a

bx,

=

Sostituendo il valore trovato nella penultima equazione si avrà una equazione nell’incognita xn-1 risolvendo la quale si otterrà il valore dell’incognita xn-1

1,1

,111

−−

−−−

−=

nn

nnnnn a

xabx

Sostituendo a ritroso i valori trovati nell’equazione precedente fino alla prima e risolvendo man mano le equazioni si otterranno i valori di tutte le incognite; si avrà così la soluzione del sistema. Il valore della i_esima incognita è dato da:

ii

nniiiiiiiii a

xaxaxabx

,

,22,11, ...−−−−= ++++ con i = n−1, … , 2, 1

che può essere anche scritto come

ii

n

ikkkii

i a

xabx

,

1,∑

+=

−= con i = n−1, … , 2, 1


12.5.4 Risoluzione dei sistemi: metodo della matrice Triangolare Superiore (Gauss).

=+++

=+++=+++

nnnnnn

nn

nn

bxaxaxa

bxaxaxabxaxaxa

............................................

......

2211

22222121

11212111

Se il sistema dato si riesce a ricondurre alla forma, riportata di seguito, nella quale manca l’incognita x1 a partire dalla seconda equazione, manca l’incognita x2 a partire dalla terza equazione e così via; pertanto nell’ultima equazione è presente solo l’incognita xn ,

=

=+

=++=+++

−−−−−

nnnn

nnnnnnn

nn

nn

bxabxaxa

bxaxabxaxaxa

1,111,1

22222

11212111

...............................................

(1)

per risolverlo si può applicare il metodo della sostituzione a ritroso. La matrice dei coefficienti del sistema, ridotta nella forma (1), è triangolare superiore. Regola di costruzione della matrice triangolare superiore:

1. Si scrive la matrice dei coefficienti e si aggiunge ad essa la colonna dei termini noti 11 12 1 1

21 22 2 2

1 2

...

...... ... ... ... ...

...

n

n

n n nn n

a a a ba a a b

a a a b

2. SE a11 = 0 si scambia la 1a riga con una qualsiasi riga avente il primo elemento diverso da ZERO (dal punto di vista numerico conviene scambiare la riga con quella in cui il coefficiente di x1 è massimo in valore assoluto). Se tutti gli elementi della prima colonna sono zero il sistema è incompatibile.

3. Si moltiplicano tutti termini della 1a riga per 21

11

aa

, si sottrae la riga così ottenuta dalla

seconda e si sostituisce la seconda riga con il risultato ottenuto; si ottiene:

11 12 1 1* * *22 2 2

1 2

...0 ...... ... ... ... ...

...

n

n

n n nn n

a a a ba a b

a a a b

4. Per rendere 0 tutti i rimanenti elementi della prima colonna si ripete il procedimento

descritto; in generale si moltiplica la 1a riga per il termine 1

11

Kaa

, si sottrae la riga così

ottenuta dalla k-esima riga e si sostituisce la k-sima riga con il risultato ottenuto; si ottiene:


11 12 1 1* * *22 2 2

* * *2

...0 ...... ... ... ... ...0 ...

n

n

n nn n

a a a ba a b

a a b

5. Si ripetono le operazioni (1) (2) (3) (4) per la sottomatrice estratta dalla precedente eliminando la prima riga e la prima colonna, cioè quella che inizia con *

22a e per le sottomatrici successive estratte con lo stesso criterio dalla matrice considerata in precedenza, cioè quelle che iniziano a partire da a*kk ,ottenendo una matrice triangolare superiore. La matrice completa sarà pertanto diventata:

11 12 1 1* * *22 2 2

** **

...0 ...... ... ... ... ...0 0 ...

n

n

nn n

a a a ba a b

a b

6. Si applica quindi il metodo di sostituzione a ritroso, cioè si ricava **

**n

nnn

bx

a= e si sostituisce a

ritroso per ricavare le altre incognite.

Esempio soluzione sistema (3) 3

2 5x yx y

+ =

− − = − matrice completa iniziale

1 1 31 2 5

− − −

matrice completa finale 1 1 30 1 2

− −

2 21

y −= =

− sostituendo 2 nella 1° riga si ricava x=3-2=1

Algoritmo: Progettare un programma (e le classi necessarie) che risolva sistemi lineari nxn utilizzando il metodo di Gauss. Indicazioni per un prototipo della classe Sistema:

Sistema



− sost( int i):Matrice + cramer( ):Matrice; + solInversa( ):Matrice; + gauss( ):Matrice; + toString( ):String;

1. Sai costruire un metodo per ottenere da una matrice COMPLETA (n,n+1) una matrice completa in cui la sottomatrice dei coefficienti sia triangolare superiore?

2. Sai costruire il metodo di sostituzione ritroso? 3. In quale classe collocare i metodi triangolaGauss() e sostRitroso() (MATRICE o

SISTEMA)?, (?).sostRitroso():Matrice; (?).triangolaGauss(): Matrice;


12.5.4 Risoluzione dei sistemi: metodo della matrice Diagonale (Gauss-Jordan).

Regola di diagonalizzazione:

1. Si scrive la matrice dei coefficienti e si aggiunge ad essa la colonna dei termini noti, si ha:

11 12 1 1

21 22 2 2

1 2

...

...... ... ... ... ...

...

n

n

n n nn n

a a a ba a a b

a a a b

2. SE a11 = 0 si scambia la 1° riga con una qualsiasi riga avente il primo elemento diverso da ZERO (dal punto di vista numerico conviene scambiare la riga con quella in cui il coefficiente di x1 è massimo in valore assoluto). Si divide poi la 1° riga per a11; si ha:

* * *12 1 1

21 22 2 2

1 2

1 ......

... ... ... ... ......

n

n

n n nn n

a a ba a a b

a a a b

3. Si moltiplicano tutti termini della 1° riga per 21a ; la riga così ottenuta si sottrae dalla seconda e si sostituisce la seconda riga con il risultato ottenuto; si ha:

* * *12 1 1* * *22 2 2

1 2

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

...

n

n

n n nn n

a a ba a b

a a a b

4. Per rendere 0 tutti i rimanenti elementi della prima colonna si ripete il procedimento descritto; in generale si moltiplica la 1a riga per il termine ak,1, si sottrae la riga così ottenuta dalla k-esima riga e si sostituisce la k-sima riga con il risultato ottenuto; si ha:

* * *12 1 1* * *22 2 2

* * *2

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

n

n

n nn n

a a ba a b

a a b

5. Se a22=0 si ricerca nella seconda colonna, a partire dal terzo elemento, la riga contenente l’elemento diverso da zero (meglio se si ricerca la riga contentente l’elemento massimo in valore assoluto); si scambiano le due righe.

6. Si divide la seconda riga per il termine a22 a partire dal secondo elemento della riga (il primo è uguale a zero); si ha:

***2

**2

**2

*1

*1

*12

...0...............

...10

...1

nnnn

n

n

baa

babaa

7. Si moltiplica la seconda riga, a partire dal secondo elemento, per ak2, con k ≠2, la riga così ottenuta si sottrae dalla riga k e si sostituiscono i risultati ottenuti nella riga k.


8. Si ripetono le operazioni (5) (6) (7) per tutti i rimanenti elementi aii della matrice, ottenendo una matrice completa con la sottomatrice dei coefficienti diagonalizzata. Nella colonna n+1 si avranno così i valori delle incognite, cioè il vettore soluzione del sistema.

**

**2

**1

1...00...............

0...100...01

nb

bb

Esempio soluzione sistema (3)

32 5

x yx y

+ =

− − = − e completa iniziale

1 1 31 2 5

− − −

Si divide la prima riga per a11 =1 (nulla cambia). Si moltiplica la 1° riga cosi ottenuta per a21= –1 ottenendo (–1 –1 –3). La si sottrae dalla seconda ottenendo

1 1 30 1 2

− −

Si divide la seconda riga per a22 = –1, e si ottiene (0 1 2). Si moltiplica la seconda riga per a12=1 (nulla cambia). Si sottrae la seconda riga cosi ottenuta (0 1 2) dalla prima ottenendo (1 0 1). La matrice completa finale sarà

1 0 10 1 2

I valori delle incognite sono nella terza colonna x=1 y=2. Algoritmo: Progettare un programma (e le classi necessarie) che risolva sistemi lineari nxn utilizzando il metodo di Gauss-Jordan. Indicazioni per un prototipo della classe Sistema:

Sistema



− sost( int i):Matrice + cramer( ):Matrice; + solInversa( ):Matrice; + gauss( ):Matrice; + gaussJordan ( ): Matrice; + toString( ): String;

• sai costruire un metodo per “diagonalizzare” una matrice (n,n+1) • Successivamente sai costruire un metodo per estrarre la colonna delle soluzioni?) • in quale classe collocare i metodi diagonaleGaussJordan( ) e getCol(int i)

(MATRICE o SISTEMA) ? (?).diagonaleGaussJordan( ):Matrice; (?).getCol(int i) : Matrice;


12.6 Complessità di calcolo e instabilità dei sistemi. La complessità Definizione : Si chiama complessità di calcolo in tempo di un algoritmo applicato a n dati e lo si indica con O(n) il numero di operazioni che è necessario eseguire perché l’algoritmo termini. Tale numero deve essere espresso in funzione di n. La complessità viene distinta in complessità minima (caso migliore) complessità massima (caso peggiore) e complessità media (caso medio) Esempi:

9. Se si costruisce un algoritmo di ricerca di un elemento su un array di n componenti la complessità in tempo sarà:

minima O(n)=1 (eseguo solo una operazione di confronto se l’elemento cercato è il primo) massima O(n)=n (eseguo n confronti se l’elemento cercato è l’ultimo) media O(n)=n/2 (se eseguo la ricerca per distribuzioni casuali avrò mediamente n/2 confronti)

10. Se si costruisce un algoritmo di ordinamento bubble sort che si interrompe se dopo n-1 confronti non ho eseguito scambi la complessità in tempo sarà:

minima O(n)=n-1 confronti) + 0 scambi (se i dati sono ordinati) massima O(n)=(n-1)+(n-2)+ … +(1) (confronti) + (n-1)+(n-2)+ … +(1) (scambi) =(n)(n-1) circa n 2 operazioni (se i dati sono in ordine inverso) media O(n)=sarà un valore mediano ma sempre dipendente da n2 (se eseguo la ricerca per distribuzioni casuali) Conclusioni: Gli algoritmi con complessità proporzionale a n oppure n*log(n) sono “buoni algoritmi”.Se la complessità di calcolo è proporzionale a (n2 ) o superiore, al crescere di n il tempo di calcolo può diventare molto pesante. Se l’algoritmo esegue operazione aritmetiche gli errori di arrotondamento possono diventare molto sensibili. Metodi di soluzione dei sistemi e complessità di calcolo: Il calcolo del determinante di una matrice, facendo uso della definizione ricorsiva, ha una elevata complessità (e quindi tempo elevato ed errori sensibili al crescere di n). Operazioni Somme + prodotti + n*(op_minore) Detrminante n=2 (2-1)+2+2*0=3 2!=2

n=3 (3-1)+3+3*3=14 3!=6 n=4 (4-1)+4+4*14 =63 4!=24 n=5 (5-1)+5+5*63=324 5!=120 n=6 (6-1)+6+6*324=1955 6!=720

Il metodo della matrice inversa deve fare i conti con il calcolo di molti determinanti (necessari per trovare l’inversa) quindi, in assenza di metodi diversi (più rapidi) per invertire una matrice, dobbiamo soprassedere. Per la complessità di calcolo è opportuno scartare anche Cramer. E’ sempre necessario calcolare n+1 determinanti.


La complessità di calcolo del metodo di Gauss è quella preferibile. Anzi, con il metodo di Gauss si può anche trovare il determinante di una matrice abbassando notevolmente la complessità di calcolo rispetto all’utilizzo della definizione ricorsiva di determinante. Il metodo di Gauss-Jordan esegue un numero circa doppio di operazioni rispetto al metodo di Gauss ma è molto utile per calcolare l’inversa di una matrice perché riduce notevolmente la complessità di calcolo rispetto alla definizione matematica di inversa. L’instabilità Anche utilizzando il metodo di Gauss si ottengo a volte risultati “errati” ovvero molto distanti da quelli corretti. In questi casi si dice che il sistema è instabile. Un sistema è instabile se ha un determinante “molto prossimo” allo ZERO. Non sempre si riesce ad evitare tale instabilità anche se parte di questa può essere annullata attraverso i metodi di Gauss e GausJordan calcolando preventivamente il determinante del sistema. Conclusioni: Per ragioni di complessità di calcolo si scarta il metodo di Cramer perché è sempre necessario calcolare n+1 determinanti. Rimangono “accettabili” nell’ordine i metodi di Gauss, Gauss-Jordan e Inversa (nell’ultimo caso solo se si determina A-1 con il metodo di Gauss-Jordan). 12.6.1 Tecnica per determinare la Matrice Inversa (metodo di Gauss-Jordan) Il procedimento illustrato ha il pregio di abbassare la complessità di calcolo insita nella determinazione della matrice inversa, che per la definizione matematica, implica il calcolo di molti determinanti. Partendo dalla matrice (3,3) seguente:

1 1 11 1 21 1 1

A− −

=

Si procede costruendo la matrice (3, 6) che contiene a destra la matrice identità: 1 1 1 1 0 01 1 2 0 1 01 1 1 0 0 1

M− −

=

Ora si opera per ottenere a sinistra la matrice Identità, al termine dei calcoli la matrice (3,3) di destra conterrà la matrice inversa di quella di partenza. Ciclo di Colonna (colonna uno):

1 -1 -1 1 0 0 1 1 2 0 1 0 1 1 1 0 0 1

Si fa “perno” su a00 per rendere nulli tutti gli elementi sotto di esso. 1° operazione: se a00 fosse ZERO occorre scambiare tutta la riga con una riga il cui primo elemento sia diverso da ZERO. 2° operazione: si “normalizza” la riga uno (R0) dividendo tutti gli elementi per a00 in modo che a00 divenga 1 (in questo caso lo è già)


Ciclo di riga: (Seconda riga) 3° operazione: si ottiene la “nuova” seconda riga( R1)=R1-R0*a10

1 -1 -1 1 0 0 0 2 3 -1 1 0 1 1 1 0 0 1

Ciclo di riga: (Terza riga) 4° operazione: si ottiene la “nuova” terza riga( R2)=R2-R0*a20

1 -1 -1 1 0 0 0 2 3 -1 1 0 0 2 2 -1 0 1

Ciclo di Colonna (colonna due): 1 -1 -1 1 0 0 0 2 3 -1 1 0 0 2 2 -1 0 1

Si fa “perno” su a11 per rendere nulli tutti gli elementi sotto e sopra di esso. 1° operazione: se a11 fosse ZERO occorre scambiare tutta la riga con una riga il cui secondo elemento sia diverso da ZERO. 2° operazione: si “normalizza” la riga due (R1) dividendo tutti gli elementi per a11 in modo che a11 divenga 1 (in questo caso si divide per 2)

1 -1 -1 1 0 0 0 1 3/2 -1/2 1/2 0 0 2 2 -1 0 1

Ciclo di riga: (Terza riga) 3° operazione: si ottiene la “nuova” terza riga( R2)=R2-R1*a21

1 -1 -1 1 0 0 0 1 3/2 -1/2 1/2 0 0 0 -1 0 -1 1


Ciclo di riga: (Prima riga) 4° operazione: si ottiene la “nuova” prima riga( R0)=R0-R1*a21

1 0 1/2 1/2 1/2 0 0 1 3/2 -1/2 1/2 0 0 0 -1 0 -1 1

Ciclo di Colonna (colonna tre):

1 0 1/2 1/2 1/2 0 0 1 3/2 -1/2 1/2 0 0 0 -1 0 -1 1

Si fa “perno” su a22 per rendere nulli tutti gli elementi sopra di esso. 1° operazione: se a22 fosse ZERO il determinante sarebbe ZERO e il procedimento FINITO. (NON è possibile calcolare l’inversa di un Determinante NULLO) 2° operazione: si “normalizza” la riga tre (R2) dividendo tutti gli elementi per a22 in modo che a22 divenga 1 (in questo caso si divide per -1)

1 0 1/2 1/2 1/2 0 0 1 3/2 -1/2 1/2 0 0 0 1 0 1 -1

Ciclo di riga: (Seconda riga) 3° operazione: si ottiene la “nuova” seconda riga( R1)=R1-R2*a12

1 0 1/2 1/2 1/2 0 0 1 0 -1/2 -1 3/2 0 0 1 0 1 -1

Ciclo di riga: (Prima riga) 4° operazione: si ottiene la “nuova” prima riga( R0)=R0-R2*a02

1 0 0 1/2 0 1/2 0 1 0 -1/2 -1 3/2 0 0 1 0 1 -1

Si è ottenuta la matrice identità e il procedimento ha termine con il seguente risultato:

1

1 102 21 312 2

0 1 1

A−

= − − −


12.7 Trasformazioni nel piano Il diagramma seguente dovrebbe mostrare le relazioni che intercorrono tra le trasformazioni del piano: L’AFFINITA’ è la classe più generale delle trasformazioni lineari nel piano l’equazione generale sarà:

(1) A=X ax by cY dx ey f

= + +

= + +

Proprietà: • Conserva il parallelismo ovvero trasforma lati paralleli in lati paralleli (es. rettangoli in

parallegrammi) • Trasforma poligoni di n lati in poligoni di n lati • Trasforma circonferenze in ellissi

• Delta= 0a b

ae dbd e

= − ≠ altrimenti non è una trasformazione

• Delta>0 Affinità DIRETTA (Conserva l’ordine dei vertici della figura origine-trasformata). • Delta<0 Affinità INVERSA (Cambia l’ordine dei vertici della figura trasformata).

• ( 1)( )

S FD Delta ae dbS F

= = − = , ovvero il valore assoluto di Delta ae db− è un numero

che rappresenta il rapporto tra le aree di figure corrispondenti. S(F1) è la superficie della figura F1 trasformata di F ed S(F) e la superficie della figura origine F ovvero F1=A(F).

Le SIMILITUDINI sono un sottinsieme delle AFFINITA’ nel piano, l’equazione generale di una similitudine è

1 2

X ax by c X ax by cS o anche S

Y bx ay f Y bx ay f= − + = + +

= = = + + = − +

Proprietà:

• Conserva parallelismo, angoli e rapporto tra i lati. • Trasforma poligoni di n lati in poligoni Simili di n lati • Trasforma circonferenze in circonferenze • Notare la simmetria dei coefficienti a e b.

• Delta= 2 2 0a b

a b Similitudine DIRETTAb a

−= + >

Affinità

Omotetie

Similitudini

Isometrie


• Delta= 2 2 0a b

a b Similitudine INVERSAb a

= − − <−

• 2 2 ( 1)( )

S FD Delta a bS F

= = + = ,

• 2 2 ( 1)( )

S FD Delta a bS F

= = − − = , rapporto tra aree corrispondenti

• k = 2 2D a b= + Rapporto della similitudine diretta, o rapporto tra lati corrispondenti

• k = 2 2D a b= − − Rapporto della similitudine inversa, o rapporto tra lati corrispondenti

Le OMOTETIE sono sottinsieme delle Similitudini ma sono trasformazioni DIRETTE, l’equazione generale di una omotetia e

1 2

X kx c X kx cO o anche O

Y ky f Y ky f= + = − +

= = = + = − +

Come per le similitudini si avrà che

• Conserva parallelismo, angoli e rapporto tra i lati.

• Ha sempre un punto unito che è il suo centro C

−− kf

kc

1;

1

• Notare la simmetria dei coefficienti a=k e b=0 come per le similitudini

• Delta= 20 00

0 0k k

k sempre DIRETTAk k

−= = >

−

• 2 ( 1)( )

S FD Delta kS F

= = = , rapporto tra aree corrispondenti

• K= 2D k= Rapporto di omotetia o rapporto tra lati corrispondenti Le ISOMETRIE sono un sottinsieme delle Similitudini nel piano, l’equazione generale di una isometria è

1 2

X ax by c X ax by cI o anche I

Y bx ay f Y bx ay f= − + = + +

= = = + + = − +

Proprietà: • Conserva lati e angoli. • Notare la simmetria dei coefficienti a e b

• Delta= 2 2 1 0a b

a b DIRETTAb a

−= + = >

• Delta= 2 2 1 0a b

a b INVERSAb a

= − − = − <−

• 2 ( 1) 1( )

S FD Delta kS F

= = = = , le figure sono congruenti e hanno la stessa area

In particolare le TRASLAZIONI di vettore (c, f) ha equazione

( , )c f

X x cT

Y y f= +

= = +


Delta S(x=a) =1 0

1 00 1

= > isometria sempre Diretta

In particolare una ROTAZIONE di centro (xc, yc) e angolo α ha equazioni:

cos( ) ( )( ) cos( )A

X x ysen cR

Y xsen y fα α

α α= − +

= = + +

Poiché il centro di una rotazione è un punto unito, se si sostituiscono le coordinate xc e yc al posto di x e y e di X e Y, si ottiene

( )( )

−−=+−=

αααα

senxyfsenyxc

cc

cc

cos1cos1

Risolvendo rispetto a xc e yc si ottengono le relazioni che esprimono xc e yc in funzione di α, c, f.

( )( )

( )( )

−+−

=

−−−

=

ααα

ααα

cos12cos1

cos12cos1

csenfy

fsencx

c

c

Delta= 2 2cos( ) ( )cos 1 0

( ) cos( )sen

sensen

α αα α

α α−

= + = >

0isometria sempre DIRETTA e rotazione antioraria se α >

In particolare le SIMMETRIE ORTOGONALI di assi x=a o y=b saranno

( ) ( )

22o x a o y b

X x a X xS o anche S

Y y Y y b= =

= − + = = =

= = − +

Delta S(x=a) =1 0

1 00 1−

= − <

Delta S(y=b) =1 0

1 00 1

= − <−

Sempre Isometrie Inverse

In particolare le SIMMETRIE CENTRALI di centro (a,b) saranno

( , )

22c a b

X x aS

Y y b= − +

= = − +

Delta S(y=b) =1 0

1 00 1−

= >−

Sempre Isometrie Dirette


12.8 Trasformazioni nel piano come modello applicativo per le matrici. Rappresentazione di una trasformazione con matrici. Una generica trasformazione lineare ha equazioni

(1) X ax by cY dx ey f

= + +

= + + con 0

a bae db

d e= − ≠

potrebbe essere rappresentata dalle seguenti matrici

a b cA

d e f

=

x

By

=

XC

Y

=

A matrice completa dei coefficienti, B, C vettori colonna delle variabili. Scritte in questo modo NON è possibile rappresentare la trasformazione come prodotto di matrici. Se invece si riscrivono le tre matrici con l’aggiunta di una opportuna riga “TUTTO funziona”:

0 0 1

a b cA d e f

=

1

xB y

=

1

XC Y

=

anche in questo caso0 0 1

a b cae dbd e f = −

Si nota che, sulla base delle proprietà dell’operazione prodotto definito sulle matrici, la trasformazione (1) può essere rappresentata da

C=A*B infatti *1 0 0 1 1

X a b c xY d e f y

=

(2)

Eseguendo il prodotto a destra si ha

1 1

X ax by cY dx ey f

+ + = + +

La scrittura del sistema (1) è equivalente alla (2) se si “astrae” dall’ultima riga 1=1 Esempio: Traslazione di vettore (1, -2) :

(3) 12

X xY y

= +

= − può essere scritta anche

1

XY

=

1 0 10 1 2 *0 0 1 1

xy

−

eseguendo il prodotto si

ottiene:

1

XY

=

1 0 10 1 2

1

x yx y

+ + + −

che equivale alla (3)


12.8.1 Come si trasforma un punto P(x,y) con le matrici Assegnato il punto P(x, y) per ottenere il suo trasformato con la trasformazione T, simbolicamente si scrive P’=T(P), è sufficiente moltiplicate la matrice T di tipo 3 x 3 della trasformazione con la matrice colonna P di tipo 3 x 1. Si otterrà una Matrice 3 x 1 che rappresenta il punto P’.

Esempio: Assegnato il punto P(1,1) e la precedente Traslazione di vettore (1, -2) T=12

X xY y

= +

= − la

loro forma equivalente con le matrici diviene:

T=1 0 10 1 20 0 1

−

P=111

da cui moltiplicando T(P)=1 0 1 2

' 0 1 2 10 0 1 1

P+ +

= + − = − + +

Si può facilmente

vedere che P’(2,-1) è il corrispondente di P nella traslazione. 12.8.2 Come si Trasforma una Figura con le matrici Una figura, disegnabile su un pannello grafico o su un foglio, può sempre essere rappresentata da una poligonale (xi,yi); se la figura è curvilinea è sufficiente prendere segmenti molto piccoli. Ne segue che, se un punto è una matrice colonna del tipo 3 x 1, un poligono (una figura) è una matrice del tipo 3 x n dove n è il numero di punti o vertici del poligono. Un rettangolo con lati paralleli agli assi e vertice sinistro-basso in (1,1) sarà rappresentata dalla matrice 3 x 4 seguente:

F=1 4 4 11 1 3 31 1 1 1

La figura trasformata F’ di F nella simmetria centrale di cento (0,0)

Sc(0,0)= 1 0 0

0 1 00 0 1

− −


la si ottiene immediatamente come prodotto di

Sc ⊗ F=1 0 0

0 1 00 0 1

− −

⊗

1 4 4 11 1 3 31 1 1 1

=F’=1 4 4 11 1 3 3

1 1 1 1

− − − − − − − −

12.8.3 La Matrice inversa di una trasformazione e la trasformazione inversa. E’ noto che il prodotto di una trasformazione geometrica del piano per la corrispondente trasformazione inversa genera la trasformazione identica. Questo fatto corrisponde alla definizione di inversa di una matrice quadrata nella struttura delle matrici. Ne consegue che assegnata la matrice di una trasformazione T (del tipo 3 x 3), utilizzando l’inversa della matrice, si determina l’equazione della trasformazione geometrica inversa T-1 di T. Esempio: Si ricorderà sicuramente che l’inversa di una traslazione di vettore (1,-2) è la traslazione di vettore (-1, 2).

T(1,-2)=1 0 10 1 20 0 1

−

T-1(-1, 2)=

1 0 10 1 20 0 1

−

Inoltre l’inversa di una simmetria ortogonale di asse x=0 è ancora la simmetria ortogonale stessa.

S(x=0)= 1 0 0

0 1 00 0 1

−

S-1(x=0)=

1 0 00 1 00 0 1

−

E’ facile verificare, con semplici calcoli che T*T-1=I ed anche che S*S-1=I 12.8.4 Composizione di trasformazioni. Se le matrici quadrate del tipo 3 x 3 formano un gruppo non commutativo rispetto al prodotto, ne segue che le trasformazioni lineari del piano sono un gruppo non commutativo. Esempio: verifichiamo che la composizione di due traslazioni T1 e T2 genera una Traslazione T3 di vettore pari alla somma vettoriale dei due vettori componenti.


T(2,1) ⊗ T(1,2)=T(3,3) infatti 1 0 20 1 10 0 1

⊗

1 0 10 1 20 0 1

=1 0 30 1 30 0 1

Verifichiamo anche che la composizione di due simmetrie ortogonali con assi perpendicolari tra loro genera una simmetria centrale di centro l’intersezione dei due assi. Si ricorda che una simmetria ortogonale di asse x=a ha equazione:

S(x=a)=2X x a

Y y= − +

=

quindi che la simmetria ortogonale di asse y=a vale S(y=a)=2

X xY y a

=

= − +

Se componiamo due simmetrie, una di asse x=1 e l’altre di asse y=1 si avrà:

S(x=1) ⊗ S(y=1)=Sc(1,1) infatti 1 0 2

0 1 00 0 1

− ⊗

1 0 00 1 20 0 1

−

=1 0 2

0 1 20 0 1

− −

Il risultato è una simmetria centrale di centro (1,1) che ha equazione

vale Sc(1,1)=22

X xY y

= − +

= − +

12.8.5 Progettare la soluzione della seguente situazione problematica: Sarebbe desiderabile realizzare un programma che consenta di rappresentare Figure su un sistema di Assi Cartesiani e consenta di applicare alle figure stesse le Trasformazioni geometriche studiate visualizzandole. Realizzare il progetto per fasi: Analisi, disegno e codifica facendo il caso semplificato nel quale si utilizza come unica trasformazione una Traslazione. Successivamente generalizzare il problema cercando di realizzare tutte le trasformazioni note del piano.

• CASI D’USO (L’utente quali funzionalità desidera ?) • CLASSI (Quali? Ricordate CHI FA CHE COSA ?) • Relazioni tra le classi (HA UN ? E’ UN ?)


Ipotesi di Soluzione: CASI D’USO Disegno Classi : CHI FA CHE COSA Nella classe Figura l’attributo A è l’oggetto Matrice costruito a partire da un array bidimensionale 3 x n avente le prime due righe costituite dalle coordinate cartesiane degli n punti della figura e l’ultima riga costituita da tutti 1. L’array bidimensionale a[ ][ ] (2 x n) rappresenta le coordinate cartesiane degli n punti della figura; gli array monodimensionali x[ ] ed y[ ] contengono rispettivamente le ascisse e le ordinate degli n punti della figura. Il metodo get( ) restituisce il valore della Matrice A, attributo privato della classe Figura. Nella classe Trasfor l’attributo A è l’oggetto Matrice costruito a partire da un array bidimensionale 3 x 3 avente le prime due righe costituite dai coefficienti delle equazioni della trasformazione e come ultima riga 0 0 1. Il metodo trasfor(Figura F) applicato ad una Figura F e invocato con un oggetto della classe Trasfor, trasforma la Figura F nella sua immagine.

Classe : Figura -Matrice A; Figura(double a[][]) Figura(double x[],double y[]) + get(): Matrice; + toString(): String

Classe : Trasfor

-Matrice A; Trasfor(double a, double b, double c, double d, double e, double f) + trasfor(Figura F):Figura; + toString(): String

Crea_figura

Crea_trasform

Trasforma_fig

Crea_pann_assi

Disegna_figura


Codifica: Cominciamo dal main(). Senza usare la classe ASSI public class pro_tra{ public static void main(String arg[]) { Figura F= new Figura(.....); System.out.println(F);// stampa le coordinate di F per controllo Traslazione T=new Traslazione(.....); System.out.println(T); // stampa la matrice traslazione per controllo Figura F1=T.trasla(F); System.out.println(F1);// stampa le coordinate di F1 per controllo } } Codifica: Cominciamo dal main(). CON la classe ASSI public class pro_tra{ public static void main(String arg[]) { double f[][]={{1,1,2,2,1},{1,3,3,2,2}}; Figura F= new Figura(f); Assi A=new Assi(); A.disegna(F); Traslazione T=new Traslazione(-3,2); Figura F1=T.trasla(F); A.disegna(F1);

} 12.8.6 Progettare un qualificatore di trasformazioni Progettare un programma (o metodo da inserire in una opportuna Classe) che qualifichi le trasformazioni nel senso che assegnata una trasformazione qualsiasi stabilisca se:

• non è una trasformazione • è un’affinità diretta/inversa • è una similitudine diretta/inversa di rapporto k • è un’omotetia di rapporto k e centro xc,yc • è un’isometria diretta/inversa (Si possono distinguere ? quali ?)

Classe : Assi extends JFrame - int L, H, Xmin, Xmax, Ymin, Ymax; - altro???

Assi() Assi(int larga, int alta) Assi(int larga, alta, xmin, xmax, ymin, ymax ) +disegna(Figura, Color):void +dis_assi():void


12.8.7 Traccia per il codice della classe Assi Supponiamo che si desideri un pannello di default che mostri gli assi CENTRATI ed evidenzi una griglia da –5 a 5 per le X e da –5 a 5 per le Y come il seguente:

La classe Assi: import javax.swing.*; import java.awt.*; public class Assi extends JFrame { private Image IM=null; // immagine fuori schermo su cui disegnare private Graphics k; // Oggetto "astratto" sul quale si disegna è associato alla immagine IM private static int L=300,H=300; // dimensione pannallo grafico di default private static int xmin=-5,ymin=-5, xmax=5, ymax=5; // estremi assi cartesiani di deafault private static int Ux=L/(xmax-xmin), Uy=H/(ymax-ymin); // Ux, Uy = numero di pixel per unità cartesiana private int xc=Math.abs(xmin)*Ux, yc=Math.abs(ymax)*Uy; // xc,yc = coordinate centro in pixel // COSTRUTTORE public Assi(int larg, int alt, int mix, int max, int miy, int may) { L=larg; H=alt; xmin=mix; xmax=max; ymin=miy; ymax=may; Ux=L/(xmax-xmin); Uy=H/(ymax-ymin); xc=Math.abs(xmin)*Ux; yc=Math.abs(ymax)*Uy; setGui(); setEvent();

}

// COSTRUTTORE di DEFAULT public Assi() { setGui(); setEvent(); } private void setGui() { setBounds(0,0,L,H); setVisible(true); setResizable(false); dis_assi(); }


private void setEvent() { setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); } private void dis_assi() { IM=createImage(L,H); // cattura dal Component (this) i pixel e li copia in IM (immagine fuori schermo) k=IM.getGraphics(); // costruisce un oggetto "astratto" graphics associato a IM sul quale tracciare segmenti // Disegno assi disegna_seg(Color.BLACK,k,xmin,0,xmax,0); // asse x disegna_seg(Color.BLACK,k,0,ymin,0,ymax); // asse y // disegno griglia for (int i=xmin; i<xmax; i++) if (i!=0) disegna_seg(Color.GREEN, k,i,ymin,i,ymax); // segm. di griglia delle unita X for (int j=ymin; j<ymax; j++) if (j!=0) disegna_seg(Color.GREEN,k,xmin,j,xmax,j); // segm. di griglia delle unita X repaint(); // Ridisegna gli assi (la IM) chiamando paint() } // FINE COSTRUTTORE public void paint(Graphics g) { Graphics2D g2=(Graphics2D) g; if (IM!=null) g2.drawImage(IM,0,0,this); //all'avvio IM=null non disegna } // METODO Publico DISEGNA public void disegna(Figura F, Color C) { Color HC=k.getColor(); k.setColor(C); Matrice f=F.get(); // mi serve la matrice (3,n) della figura double Xcart[]=(f.get())[0]; //serve la riga 0 dell'array (3,n) della figura double Ycart[]=(f.get())[1]; //serve la riga 1 dell'array (3,n) della figura int N=f.getCol(); //N numero di punti int x[]=new int[N]; // x[], y[] array necessari per disegnare int y[]=new int[N]; // con il metodo drawPolyline() o drawPolygon() for (int i=0; i<N; i++){ x[i]=trX(Xcart[i]); // trasformazione pixel y[i]=trY(Ycart[i]); } k.drawPolygon(x,y,N); // disegno del poligono chiuso drawPoligon() poligonale aperta drawPolyline() repaint(); k.setColor(HC); } private void disegna_seg( Color c, Graphics g, double x1, double y1, double x2, double y2) { g.setColor(c); g.drawLine(trX(x1),trY(y1),trX(x2),trY(y2)); } private int trX(double x) { int Xp=(int) Math.round(xc+x*Ux); return Xp; } private int trY( double y) { int Yp=(int) Math.round(yc-y*Uy); return Yp; } }

12. Matrici Sistemi Trasformazioni - copernico.bo.it · Definizione: Minore complementare di un ......

Documents

Transcript of 12. Matrici Sistemi Trasformazioni - copernico.bo.it · Definizione: Minore complementare di un ......