Mat - Prova

Norme vettoriali e matriciali

Def. Norma vettoriale

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

• Ilxll:2: O e Ilxll = O = O Vx E R"H X
• Ilaxll = lal'llxll Va E R Vx E R''n
• Ilx+YII::;llxll+IIYII Vx,yER r

Esempi

Jt 1n (tIX;IPIlxllIlxll xi Ilxlli = Llxil == pi=lJtIlxll, M exiIlxll = 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è:

> n3a, ~ a,~,E R con O T. C. Vx E Rallxll" ::; Ilxll' ::; ~llxll"

Proprietà

Vx E (Cn1)

• Ilxlloo::; Ilxllz ::; 0lllxlloo
• Ilx111::;2) Ilxllz::; 0lllxllz
• Ilxlloo::; IIxl11 ::; nllxlloo

Def. Norma matriciale

nxn è una norma matriciale di A che verifica le seguenti IIAII funzione da R R,~ Proprietà:

• IIAII:2: O e IIAII = O A = OH nxn
• IlaA11 = lal'IIAII Va E R VA E Rn
• IIA+BII::;IIAII+IIBII VA,BER n
• IIABII::;IIAII'IIBII VA,BER

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

IIAxl1P-IIAII:= sU -I = max IIAxl1[x] Il ll=lxxse 1O

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 IIAxl12) 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 IIBxl1Ilxll=l Ilxll=l

Se AB = Allora IIABII = IIAII'IIBII4) O O::;

Se AB = Allora 3y IIYII = e IIABYII = max IIABYIIO R'' T. C. 1 OE =1=Ilxll=l

Posto z = By risulta z e si ha:O=1= I I zRIIAzl1 AzIIA(BY)II = IIAzl1 = Ilzll' = IIBYII· fzTI ~ u=fzTI

Quindi: max IIABxl1 = IIAull·IIBYII ::; max IIAvll· max IIBwl1 Iluli =T.C. 1Ilxll=l Ilvll=l Il ll=lwE

Esempi - norme indotte

n1) IIAII := max IIAxl1 = .E1ax "'IaidLIlxll =1 1-1.....n00 00 j=l j=l00 n

IIAII := max IIAxl1 = .E1ax '" laid2) L1 Ilxll =1 1 J-1.....ni=l i=l1 J

IIAII := max IIAxl1 = p(AHA) ~ p(A) = max {Iλi I : λi autovalore di A}3) z Il =1x Z11 2

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

Dimostrazione

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

L LIlxll -1 Ilxll -1 1-1.....n Ilxll -1 1-1.....nJ=l J=l00 00 00nL::; iEl~~n laidj=l j=l n-

Ora si deve verificare che 3x con Ilxll = 1 per cui: max IIAxl1 = .E1ax '" laij ILIlxll =1 1-1.....n00 00 j=l j=l00

L Ln 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 LIlxll =1 1 Ilxll Ilxll Ilxlli=l j=l i=l j=l j=l i=l1 1 1

n) n ns ma~ .!_l1ax'" laid '" Ixd = .!_l1ax'" laidnL nLL(Ilxll -1 J-1..... J-1.....i=l j=l i=l1-

Inoltre 3x = ek = dove l'indice della colonna di A per cui:(O, ... ,1, ... ,O)T k è

LnIIAek Il (a1k, aZk, ... , ank)T laik I= =11 111 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. JIYiIZ::; max /λi '" p(AHA)= =LIIY112=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)= = =

Definizione di compatibilità

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

nxn,IIAxll::; IIAII'llxll VA VxR RE 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) ::; IIAIIIIAII ILlaid:=F i,j=lnxn

Proprietà: VA si ha:RE

• 0lIIAlloo::; IIAllz ::; 0lliAlloo
• 0lIIAlll::; IIAllz 0lllAIll
• IIAllz::; ~IIAlll1IAlloo
• IIAllz::; IIAIIF ::; nllAllz

(si estende una matrice rettangolare con elementi nulli per portarla alla stessa dimensione di quella quadrata)

Sistemi lineari

bAx =- Il sistema ammette soluzione se il vettore b allo spazio lineare generato dalle colonne di AEA (avaz, .a.,) ai R''= E

Infatti: x (xv xz, , xn)T Xi= REb Xlal +xzaz + .. ·+xnan=-

La soluzione è unica se la matrice è non singolare:AA- b1x =

Regola di Cramer

det(Aa .Xi det(A) n= = 1, ... ,lAi matrice a cui la i-esima colonna è stata sostituita con b= ALndet(A)

(-l)j+l a1j det(Ala= j=l 1A1j matrice di ordine n-l ottenuta eliminando la riga e la esima colonna= j -a

Costo superiore a (n + l)!=

Condizionamento

Def. Condizionamento:la risposta di un problema all'introduzione di errori nei dati, a prescindere dall'algoritmo utilizzato E'per risolverlo.

1:~x~:1Un 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-18bA(x + Sx) b + Sb da cui A8x Sb e Sx= = =

IIA-111·118bll118xll IIA-18bll::;=

Poiché: Ilbll IIAxl1 ::; IIAII'llxll=118xll llI -11118b1-.< lA -- Ibl1 1E quindi:

Condizionamento di una matrice

A·IIA-111cond(A) IIAII:=

Oss: :2: 1Poiché: Allora cond(A) C.

Supponiamo di introdurre una perturbazione della matrice 8A T.8A) Odet(A + =1=+ +8A)(x b da cui:=(A Sx) -A-18A(x= =A8x -8A(x + Sx) ~ Sx + Sx)

IIA-111·118AII·llx118xll ::; + 8xll118xll < cond(A) 118AIIIlx+8xll- IIAII Sb

Supponiamo di introdurre una perturbazione del termine noto e della matrice òA T.C.8A) Odet(A + =1= b BSx) 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 ::; Ilo118AII·IIA-111::; 1- Se118xll < cond(A) (118AII + 118bll)-1- deA)Ilxll 118AII IIAII Ilbllcon 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 - AxIlxll - Ilbll

Dim: A-1(Ax A-1(Ax A-1rSx := X - = = =- Ax) - b) ~ 118xll ::; IIA-111·llrllXAx+ Ilbll ::; IIAII'llxllb

Oss:Per una matrice malcondizionata, il residuo non è una buona indicazione della precisione di una xsoluzione approssimata rispetto alla soluzione esatta.

Esempi di matrici malcondizionate

Matrici di Milbert - di ordine nM~n) 1:= 1, ...,j = ni,+ 1i j -IJ

Matrici di Vandermonde - di ordine n{xJP=oNodi distinti1 Xo X61=v.(n) Xl xiI •( Z1 X Xn 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

all Oaii =1=A= 1, ...,i = n( O

"Algoritmo" soluzione: 1, ...,i = n

Costo: n (divisioni)

Se A è tridiagonale inferiore

a Olla aZ1 22 Oaii =1=I a aA a= 31 3Z 33 1, ...,i = n... ...a an(n-l)n1

b b a x- l1 z Z1Xl=- Xz =a azzll- Algoritmo soluzione:n (divisioni per n incognite)(n - l)n sommeZ)

Costo: O(n 2(n - l)n prodotti2

Se A è tridiagonale superiore

Oaii =1=1, ...,i = nb nx =--an nn- Algoritmo soluzione: ~ sostituzione all'indietrobi - IJ=i+l aijXjxi =Z)

Costo: O(n

Se A matrice non singolare qualunque

Teorema di Cramer C~la~n) a~n)... ...... a ,i-l b aU+lC' 1 1A= : A; =... ... ...a a a aba ,i-l a ,i+ln nn1 nn n1 nnn

det(Ai)- Soluzione: 1, ...,i = nXi = 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 . Cn- n-1 1+ :2: :2:C = (n - 1) . C n-l (n - 1) . C ~ C n(n - l)Cz zn-1 n-1 n- n-n+ :2: :2:C = (n - 2) . C n - 2 (n - 2) . C C n(n - l)(n - 2)Cz zn- n- n-3 ~ n-3n:2: ilC 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.:MMAx = Mb MA ~ triangolare

Metodo di eliminazione di Gauss

ilIn Matlab si utilizza comando "\" per ottenere la soluzione x : = A\bX

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.

Passo 1

l°: OPasso Ip: ai~ =1= (1)i1.. l" a 2tìpM l icatorì: Ci)= - = , ...,o mil nla11+ (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 1b(2) (2) (2) (2)OI= =A2 a22 a23 ... a2n b2 2a(2) a(2)o n2 n3

Passo 2

a~12°: Passo OIp: =1= (2)i2.. l" a 3tìpM l icatorì: -(2)= 1=, ...,o mi2 na22+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 2I (3) (3) b, =...=A3 b(3)O O a33 a3n 3(3) (3)... b (3)O O an3 ann n

Passo k

Passo k": OIp: a~~ =1= (k)aik.. l" k 1tìpM lo icatorì: mik = -Ck)" 1= + , ... ,nakk(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)aa ,k+l 1n1(2) (2)o a2na2,k+l(k) (k) (k)o o b(k)aknakk ak,k+l k(k+l) (k+l) b(k+l)oO O aak+ ,k+l +k 1,n k+l1 b(k+l)(k+l) (k+l)o o o aan,k+l nnnn-li = 1, ... ,Ip: a~~ O=1=lil

(n - 1) passi, procedimento si conclude.

Dopo a(l) a(l) ... a(l) (b(l)ln11 12 1a(2) ... a(2) b(2)22 2n bn = 2o a~~+l)/ \b~n) 1)n(n -(n - 1) + (n - 2) + ... + 1 = 2 divisioni

L. L·(~3) n-l n-l 31]n(n - 1) (n - 1)n[2(n - 1) + n n-+2_ Costo totale: O prodotti= =--L+ L 2 6 3i=l i=l3n n- somme3

Algoritmo di eliminazione di Gauss per sistemi lineari di ordine n

per k = n-l1, ... ,per i = k + 1, ... , n(k)aikmik =-Ck)"akkper j = k + 1, ... , n(k+l) _ (k) (k)[aij - mikakj + aijb(k+l) - . b(k) + b(k)i - mlk k ifine 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>conper 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 x10x2 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 141 = __mMoltiplicatori: O= m41 Ci) - 20 2= -21 a41+ a am41 . riga) (4 riga) (4 riga)=(la

+ + +20x 5x 2x x 28=1 2 3 4+ +4x x10x2 15=3 4+ +5x 10x 2x 17=2 3 43 5- "2 + +"2x x x 2=2 3 4

Passo 2 0: 5 1a(2)32Moltiplicatori: m =-(2)=-10=-"232 a22+a a am (2 riga) (3 riga) (3 riga)=.32 +a a am . (2 riga) (4 riga) (4 riga)=42

+ + +20x 5x 2x x 28=1 2 3 4+ +4x x10x2 15=3 43 192+"28x =X438 53 174SX + 20 X4 =3 1

a(3). l" 43 5tìp mo icatorì: (3)M l = - = -43 a33+a a am43 . (3 riga) (4 riga) (4 riga)=

+ + +20Xl 5X2 2X3 X4 28=+ +10x2 4X3 X4 15= 193 2+"2X48X3 =47 47-x --20 4 - 20-

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

1X4 = 19 3 (t)2-Z 1x = =3 Soluzione: x =15 - 1- 4 1X2 = =1028 - 1- 2 - 5 1Xl = =20

Eliminazione con Gauss

Oss: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 Ia(k) max la~k)=l rk kstsn ik

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

I Ia~~) max la~k)=l IJksi.jsne 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 n1, ...,1) a dominanza diagonale per righe: i =nLlajd ,nlaiil
• A dominanza diagonale per colonne: i=l, ...:2: j=lj*i
• S