Mat - Prova

orme vettoriali e matriciali

N

Def. Norma Vettoriale:

Ilxll funzione da R'' ~ è una norma vettoriale di x che verifica le seguenti

R,

Proprietà:

1) Ilxll:2: O e Ilxll = O = O Vx E R"

H X

2) Ilaxll = lal'llxll Va E R Vx E R''

n

3) Ilx+YII::;llxll+IIYII Vx,yER r

Esempi: Jt 1

n (tIX;IP

Ilxll

Ilxll xi Ilxlli = Llxil =

= p

i=l

Jt

Ilxll, M e

xi

Ilxll = J(x,x) H Trasposto coniugato

= = =

<-

Esercizio: x = [1,2] calcolare norme:

Ilx111=3 Ilxllz=V5 Ilxlloo=2

Teorema:

Siano Il'11' e Il'11'' due norme vettoriali Allora esse sono topologicamente equivalenti cioè:

> n

3a, ~ a,~,

E R con O T. C. Vx E R

allxll" ::; Ilxll' ::; ~llxll"

Proprietà: Vx E (Cn

1) Ilxlloo::; Ilxllz ::; 0lllxlloo

Ilx111::;

2) Ilxllz::; 0lllxllz

3) Ilxlloo::; IIxl11 ::; nllxlloo

Def. Norma Matriciale:

nxn è una norma matriciale di A che verifica le seguenti

IIAII funzione da R R,

~

Proprietà:

1) IIAII:2: O e IIAII = O A = O

H nxn

2) IlaA11 = lal'IIAII Va E R VA E R

n

3) IIA+BII::;IIAII+IIBII VA,BER n

4) IIABII::;IIAII'IIBII VA,BER

Oss: ad ogni norma di vettore si può associare una norma di matrice nel modo seguente:

IIAxl1

P-

IIAII:= sU -I = max IIAxl1

[x] Il ll=l

x

xse 1

O

Una norma così ottenuta viene definita naturale o indotta da quella di vettore.

Dim. proprietà:

1) Se A O

= Allora IIAxl1 = O ~ IIAII = O

Se IIAII = Allora IIAxl1 = Vx A =

O O O ~ O

=1=

max IlaAxl1 = max [«] ·IIAxll = [«] max IIAxl1

2) Ilxll=l Ilxll=l Ilxll=l

+ + +

max II(A B)xll = max IIAx Bxll ::; max 11(IIAxll IIBxll)11 ::;

3) Ilxll=l Ilxll=l Ilxll=l

+

::; max IIAxl1 max IIBxl1

Ilxll=l Ilxll=l

Se AB = Allora IIABII = IIAII'IIBII

4) O O::;

Se AB = Allora 3y IIYII = e IIABYII = max IIABYII

O R'' T. C. 1 O

E =1=

Ilxll=l

Posto z = By risulta z e si ha:

O

=1= I I z

R

IIAzl1 Az

IIA(BY)II = IIAzl1 = Ilzll' = IIBYII· fzTI ~ u=fzTI

Quindi: max IIABxl1 = IIAull·IIBYII ::; max IIAvll· max IIBwl1 Iluli =

T.C. 1

Ilxll=l Ilvll=l Il ll=l

w

Esempi - norme indotte: n

1) IIAII := max IIAxl1 = .E1ax "'Iaid

L

Ilxll =1 1-1.....

n

00 00 j=l j=l

00 n

IIAII := max IIAxl1 = .E1ax '" laid

2) L

1 Ilxll =1 1 J-1.....

n

i=l i=l

1 J

IIAII := max IIAxl1 = p(AHA) ~ p(A) = max {IÀi I : Ài autovalore di A}

3) z Il =1

x Z

11 2

p(A) := raggio spettrale di A := massimo autovalore della matrice A

Dimostrazione: f f

1) ma~ IIAxlloo = ma~ (.!_l1ax aijxj )::; ma~ IIAxlloo (.!_l1ax laid 'Ixd ) ::;

L L

Ilxll -1 Ilxll -1 1-1.....n Ilxll -1 1-1.....n

J=l J=l

00 00 00

n

L

::; iEl~~n laid

j=l j=l n

- Ora si deve verificare che 3x con Ilxll = 1 per cui: max IIAxl1 = .E1ax '" laij I

L

Ilxll =1 1-1.....n

00 00 j=l j=l

00

L L

n n

- Sia k l'indice di riga di A per cui IakjI = iEl~~n Iaij I allora x dato da Xj = IakjI

è

j=l j=l j=l

Se akj allora x = altrimenti:

O O

=1= n n n n n n

max IIAxl1 = max '" '" aijxj ::; max '" '" laid Ixd = max '" Ixd '" laid ::;

2) =lL L =lLL =lL L

Ilxll =1 1 Ilxll Ilxll Ilxll

i=l j=l i=l j=l j=l i=l

1 1 1 1

n) n n

s ma~ .!_l1ax'" laid '" Ixd = .!_l1ax'" laid

nL nL

L

(

Ilxll -1 J-1..... J-1.....

i=l j=l i=l

1

- Inoltre 3x = ek = dove l'indice della colonna di A per cui:

(O, ... ,1, ... ,O)T k è

L

n

IIAek Il (a1k, aZk, ... , ank)T laik I

= =

11 11

1 1 i=l UDUH

3) AHA è Hermitiano (ossia (AHA)H AHA) Allora risulta AHA

= =

Dove U è unitaria e D diagonale con gli autovalori di AHA

Se A O Allora p(AHA) O

= =

Se p(AHA) O Allora D O e quindi A O

= = =

Se A O

=1=

- Gli autovalori di AHA sono non negativi e per almeno uno di essi, corrispondente al raggio

spettrale di AHA si ha:

>

À1 p(AHA) O ~ Autovalore massimo

=

- Sia x T. C. Ilxllz 1 ~ Y UHx Allora IIYllz 1 (poichè U è matrice unitaria)

= = =

n A. J

IYiIZ

::; max /Ài '" p(AHA)

= =

L

IIY112=1 i=l

(H sopra trasposto nei reali per complessi)

= J

- Inoltre 3 un vettore x T. C. Ilxllz 1 e IIAxllz p(AHA) è l'autovettore Xl

= =

relativo all' autovalore À1 normalizzato:

xrAHAxl À1XrXl À1 p(AHA)

= = =

Def:

Data una norma di matrice e una di vettore, diciamo che sono compatibili se:

nxn,

IIAxll::; IIAII'llxll VA Vx

R R

E E

Oss:

Ogni norma naturale risulta compatibile con la norma vettoriale da cui è indotta.

1 1

Per ogni norma matriciale IlI Il :2: Per ogni norma indotta IlI Il =

Esempio - Norma di Frobenius n.m z ~ p(A) ::; IIAII

IIAII ILlaid

:=

F i,j=l

nxn

Proprietà: VA si ha:

R

E

1

1) 0lIIAlloo::; IIAllz ::; 0lliAlloo

1 s

2) 0lIIAlll::; IIAllz 0lllAIll

3) IIAllz::; ~IIAlll1IAlloo

4) IIAllz::; IIAIIF ::; nllAllz

(si estende una matrice rettangolare con elementi nulli per portarla alla stessa dimensione

di quella quadrata)

Sistemi lineari

b

Ax =

- Il sistema ammette soluzione se il vettore b allo spazio lineare generato dalle colonne di A

E

A (avaz, .a.,) ai R''

= E

Infatti: x (xv xz, , xn)T Xi

= R

E

b Xlal +xzaz + .. ·+xnan

=

- La soluzione è unica se la matrice è non singolare:

A

A- b

1

x =

Regola di Cramer

det(Aa .

Xi det(A) n

= = 1, ... ,

l

Ai matrice a cui la i-esima colonna è stata sostituita con b

= A

L

n

det(A) (-l)j+l a1j det(Ala

= j=l 1

A1j matrice di ordine n-l ottenuta eliminando la riga e la esima colonna

= j -

a

Costo superiore a (n + l)!

=

Def. Condizionamento:

la risposta di un problema all'introduzione di errori nei dati, a prescindere dall'algoritmo utilizzato

E'

per risolverlo. 1:~x~:1

Un problema si dice ben condizionato se, a "piccole" perturbazioni sui dati

x +

x Sx

=

corrispondono errori dello stesso ordine sui risultati:

Ilf(x) - f(x) Il f(x) O

=1=

Ilf(x)11

Mal condizionato, in caso contrario.

Condizionamento di un sistema lineare

- Supponiamo di introdurre una perturbazione del termine noto:

A-18b

A(x + Sx) b + Sb da cui A8x Sb e Sx

= = =

IIA-111·118bll

118xll IIA-18bll::;

=

Poiché: Ilbll IIAxl1 ::; IIAII'llxll

=

118xll ll

I -11118b

1-

.< lA -

- Ibl

1 1

E quindi:

Condizionamento di una matrice A

·IIA-111

cond(A) IIAII

:=

Oss: :2: 1

Poiché: Allora cond(A) C.

- Supponiamo di introdurre una perturbazione della matrice 8A T.

8A) O

det(A + =1=

+ +

8A)(x b da cui:

=

(A Sx) -A-18A(x

= =

A8x -8A(x + Sx) ~ Sx + Sx)

IIA-111·118AII·llx

118xll ::; + 8xll

118xll < cond(A) 118AII

Ilx+8xll- IIAII Sb

- Supponiamo di introdurre una perturbazione del termine noto e della matrice òA T.C.

8A) O

det(A + =1= b B

Sx) Sb ~ ~ Sb ~

= =

(A + 8A)(x + + + 8Ax + (A + 8A)8x +

8A)-1 .

= =

~ (A + 8A)8x 8b - 8Ax ~ Sx (A + (8b - 8Ax) ~

A-18A)-1 . A-l.

=

~ Sx 0+ (8b - 8Ax)

+A-18A)-111·IIA-111· (118bll-118AII'llxll)

118xll ::; Ilo

118AII·IIA-111::; 1

- Se

118xll < cond(A) (118AII + 118bll)

-1- deA)

Ilxll 118AII IIAII Ilbll

con IIAII

Oss:

- una matrice è "quasi singolare" non significa necessariamente matrice malcondizionata.

- Il determinante non è legato al numero di condizionamento:

10-

1 10-1

=

D(n) O

( 10

=

[D(n)r' O 10

(

Proprietà:

8x <

11 ll cond(A)~ Sx) -

= :=

con Ilrll IIA(x + bll residuo b - Ax

Ilxll - Ilbll

Dim: A-1(Ax A-1(Ax A-1r

Sx := X - = = =

- Ax) - b) ~ 118xll ::; IIA-111·llrll

X

Ax+ Ilbll ::; IIAII'llxll

b

Oss:

Per una matrice malcondizionata, il residuo non è una buona indicazione della precisione di una

x

soluzione approssimata rispetto alla soluzione esatta.

Esempi di matrici malcondizionate:

Matrici di Milbert - di ordine n

M~n) 1

:= 1, ...,

j = n

i,

+ 1

i j -

IJ

Matrici di Vandermonde - di ordine n

{xJP=o

Nodi distinti

1 Xo X6

1

=

v.(n) Xl xi

I •

( Z

1 X X

n n

- Osservare l'aumento del condizionamento all'aumentare di n

Metodi numerici per la risoluzione di sistemi lineari

Ax

- Dati: b non singolare

= =

Metodi diretti (matrici fortemente sparse; pochi elementi O rispetto a quelli diversi da O)

Metodi iterativi Metodi diretti

Se A è diagonale:

a

ll O

aii =1=

A= 1, ...,

i = n

( O

- "Algoritmo" soluzione: 1, ...,

i = n

- Costo: n (divisioni)

Se A è tridiagonale inferiore:

a O

ll

a a

Z1 22 O

aii =1=

I a a

A a

= 31 3Z 33 1, ...,

i = n

... ...

a a

n(n-l)

n1

b b a x

- l

1 z Z1

Xl=- Xz =

a a

zz

ll

- Algoritmo soluzione:

n (divisioni per n incognite)

(n - l)n somme

Z)

- Costo: O(n 2

(n - l)n prodotti

2

Se A è tridiagonale superiore: O

aii =1=

1, ...,

i = n

b n

x =--

a

n nn

- Algoritmo soluzione: ~ sostituzione all'indietro

bi - IJ=i+l aijXj

xi =

Z)

- Costo: O(n

Se A matrice non singolare qualunque:

Teorema di cramer C~l

a~n) a~n)

... ...

... a ,i-l b aU+l

C' 1 1

A= : A; =

... ... ...

a a a a

b

a ,i-l a ,i+l

n n

n1 nn n1 nn

n

det(Ai)

- Soluzione: 1, ...,

i = n

Xi = det(A)

Costo: si ricava in termini di prodotti per calcolare il determinate di una matrice di ordine n

+ :2:

C, = n . C n n . C

n- n-

1 1

+ :2: :2:

C = (n - 1) . C n-l (n - 1) . C ~ C n(n - l)C

z z

n-1 n-1 n- n-

n

+ :2: :2:

C = (n - 2) . C n - 2 (n - 2) . C C n(n - l)(n - 2)C

z z

n- n- n-3 ~ n-3

n

:2: il

C n(n - l)(n - 2) ... Cz ~ Cz: sono necessari 2 prodotti per calcolare det(Cz)

n :2:

- Costo: C n!

n

Oss:

Cercare di trasformare il sistema di partenza in un sistema che ha una matrice triangolare con un ridotto

costo computazionale.

- Trovare quindi una matrice non singolare T.C.:

M

MAx = Mb MA ~ triangolare

Metodo di eliminazione di Gauss

il

In Matlab si utilizza comando "\" per ottenere la soluzione x : = A\b

X

- Sistema lineare di partenza:

*(1) passo 1

:=

(1) (1) (1) _ (1)

+ + ...+

a11 Xl a12 X2 a1n Xn - b1 a(l))

(1) (1) (1) _ (1) ln

+ + ...+

a21 Xl a22 X2 a2n Xn - b2 a(l)

nn

(1) (1) (1) _ (1)

+ + ...+

an1 Xl an2 X2 ann Xn - bn Ax 6 A

= =

- Trasformo il sistema di partenza Al X b1 in un sistema equivalente con matrice di

forma triangolare superiore tramite combinazioni lineari delle equazioni lineari di partenza.

l°: O

Passo Ip: ai~ =1= (1)

i1.

. l" a 2

tìp

M l icatorì: Ci)

= - = , ...,

o mil n

l

a

11

+ (i. (i.

(la =

mil . riga) esima riga) esima riga)

(2) (1) (1)

+

a; a.,

= mil . al· (2)

2, ..., O)

IJ J IJ . _ . _ _

J - J -

(2) _ . (1) (1) n (per 1, ai1 -

[ +

bi - mil b1 bi (n - 1) divisioni: per calcolo moltiplicatori

(n - 1) per termine noto

+

l°:

- Costo passo (n - 1) (n - 1)2 prodotti: (1)2 l . .

n - per e ernentì matnce

{ +

(n - 1) (n - 1)2 somme

°

il l

Dopo aver applicato passo, si ottiene questo sistema:

a(l) a(l) a(l) ... a(l)ì (b(l)

11 12 13 ln 1

b

(2) (2) (2) (2)

O

I

= =

A2 a22 a23 ... a2n b2 2

a(2) a(2)

o n2 n3

a~1

2°:

Passo O

Ip: =1= (2)

i2.

. l" a 3

tìp

M l icatorì: -(2)

= 1=, ...,

o mi2 n

a

22

+

a (i. (i.

(2 =

mi2 . riga) esima riga) esima riga)

+

[ a(3) m;, . a;') al')

=

IJ J IJ 2, O)

j = 3, ... , n j = =

(per ag)

+

b(3) - .' b(2) b(2)

i - ml2 2 i

{ (n - 2) divisioni

+

2°: (n - 1) (n - 1)2 prodotti

- Costo passo +

(n - 1) (n - 1)2 somme

(1) (1) (1) (1)

... b(l)

a11 a12 a13 a1n 1

(2) (2) (2)

... b(2)

O a22 a23 a2n 2

I (3) (3) b, =

...

=

A3 b(3)

O O a33 a3n 3

(3) (3)

... b (3)

O O an3 ann n

Passo k": O

Ip: a~~ =1= (k)

aik.

. l" k 1

tìp

M l

o icatorì: mik = -Ck)" 1= + , ... ,n

a

kk

(k. (i. (i.

mik . esima riga) + esima riga) = esima riga)

(k+1) (k) (k) O)

aij = mik . akj + aij (k+l) =

j=k+l, ... ,n aik

(k+l) - .' b(k) + b(k)

[ b i - mlk k i

(n - k) divisioni

- Costo passo k": (n - k) + (n - k)2 prodotti

{ +

k)

(n - (n - k)2 somme

(1) (1)

a

a ,k+l 1n

1

(2) (2)

o a2n

a2,k+l

(k) (k) (k)

o o b(k)

akn

akk ak,k+l k

(k+l) (k+l) b(k+l)

o

O O a

ak+ ,k+l +

k 1,n k+l

1 b(k+l)

(k+l) (k+l)

o o o a

an,k+l n

nn

n-l

i = 1, ... ,

Ip: a~~ O

=1=

l

il

(n - 1) passi, procedimento si conclude.

Dopo a(l) a(l) ... a(l) (b(l)

ln

11 12 1

a(2) ... a(2) b(2)

22 2n bn = 2

o a~~+l)/ \b~n) 1)

n(n -

(n - 1) + (n - 2) + ... + 1 = 2 divisioni

L. L·

(~3) n-l n-l 3

1]

n(n - 1) (n - 1)n[2(n - 1) + n n

-

+

2

_ Costo totale: O prodotti

= =--

L+ L 2 6 3

i=l i=l

3

n n

- somme

3

Algoritmo di eliminazione di Gauss per sistemi lineari di ordine n:

per k = n-l

1, ... ,

per i = k + 1, ... , n

(k)

aik

mik =-Ck)"

a

kk

per j = k + 1, ... , n

(k+l) _ (k) (k)

[

aij - mikakj + aij

b(k+l) - . b(k) + b(k)

i - mlk k i

fine ciclo

Oss:

Abbiamo fatto l'ipotesi che ad ogni passo k, a~~ O (elemento pivot).

=1=

Se ciò non dovesse succedere allora occorre scambiare la k-esima riga del sistema con una successiva

>

con

per cui: a~~) O k che esisterà sicuramente altrimenti il sistema avrebbe matrice singolare.

r

=1= +

Esempio - Eliminazione Gauss Algoritmo di sostituzione all'indietro:

+ + +

20Xl 5x 2x x 28

=

2 3 4

+ +

4x x

10x2 15

=

3 4

+ +

5x 10x 2x 17

=

{ 2 3 4

+ + +

10x x 2x 3x 16

=

1 2 3 4

Eliminazione di Gauss:

- Passo 10: a(l) 10 1

41 = __

m

Moltiplicatori: O

= m41 Ci) - 20 2

= -

21 a41

+ a a

m41 . riga) (4 riga) (4 riga)

=

(la

+ + +

20x 5x 2x x 28

=

1 2 3 4

+ +

4x x

10x2 15

=

3 4

+ +

5x 10x 2x 17

=

2 3 4

3 5

- "2 + +"2

x x x 2

=

2 3 4

- Passo 2 0: 5 1

a(2)

32

Moltiplicatori: m =-(2)=-10=-"2

32 a22

+

a a a

m (2 riga) (3 riga) (3 riga)

=

.

32 +

a a a

m . (2 riga) (4 riga) (4 riga)

=

42 + + +

20x 5x 2x x 28

=

1 2 3 4

+ +

4x x

10x2 15

=

3 4

3 19

2

+"2

8x =

X4

3

8 53 17

4

SX + 20 X4 =

3 1

a(3)

. l" 43 5

tìp m

o icatorì: (3)

M l = - = -

43 a

33

+

a a a

m43 . (3 riga) (4 riga) (4 riga)

=

+ + +

20Xl 5X2 2X3 X4 28

=

+ +

10x2 4X3 X4 15

= 19

3 2

+"2

X4

8X3 =

47 47

-x --

20 4 - 20

- Ora si applica l'algoritmo di sostituzione all'indietro:

1

X4 = 19 3 (t)

2-Z 1

x = =

3 Soluzione: x =

15 - 1- 4 1

X2 = =

10

28 - 1- 2 - 5 1

Xl = =

20

Eliminazione con Gauss:

OSSo

L'algoritmo è stabile se si lavora in aritmetica esatta ma, in caso contrario, per maggiore stabilità si

possono applicare strategie di:

Pivoting parziale:

ad ogni passo k si sceglie di scambiare la k-esima equazione con la r-esima per cui:

I I

a(k) max la~k)

=

l rk kstsn ik

Pivoting totale:

ad ogni passo k scelgo (r, s) tale che:

I I

a~~) max la~k)

=

l IJ

ksi.jsn

e scambio la k-esima equazione con la r-esima e scambio l'incognita k-esima con la s-esima

Oss:

- Solitamente si ricorre al pivoting parziale, buon compromesso per la stabilità perché il pivoting totale

è computazionalmente piuttosto oneroso.

- L'operazione di pivoting risulta superflua nel caso di matrici:

n n

1, ...,

1) a dominanza diagonale per righe: i =

n

Llajd ,n

laiil

2) a dominanza diagonale per colonne: i=l, ...

:2: j=l

j*i

3) s