Mathematical Engineering - Matematica Numerica

Exercise - 03 - Solution

Divided by topic

MATEMATICA NUMERICA A.A. 2018 - 2019 Ingegneria Matematica Prof. A. Quarteroni Prof. A. Manzoni, Dr. I. Fumagalli Esercitazione 3 - SoluzioneAlgebra Lineare Esercizio 1 Si consideri la norma matriciale di Frobenius di una matriceA2Rn n , ovvero kAk F=v u u tn X i;j=1a 2 ij: a)Provare chek
k Fè eettivamente una norma su Rn n . b)Provare che la norma di Frobenius ècompatibilecon la norma euclidea : kAxk 2 k Ak Fk xk 28 x2Rn : c)DettaIla matrice identità, si calcolikIk F, e si usi il risultato per dimostrare che per n >1la norma k
kFnon è indotta da alcuna norma vettoriale su Rn . Soluzione 1a)Mostriamo chek
k Fsoddisfa le proprietà richieste dalla denizione di norma. i)OvviamentekAk F 08A2Rn n ; inoltrekAk F= 0 implicaa ij= 0 per ognii; j= 1; : : : ; n. ii)Se2ReA2Rn n , si ha kAk F=v u u tn X i;j=1 2 a2 ij= jjv u u tn X i;j=1a 2 ij= jjkAk F: iii)Se consideriamo il vettorea2Rn 2 degli elementia ijdi A, abbiamo ovviamentekAk F= kak 2, ovekak 2è la norma euclidea di a. Dato che per quest'ultima vale la disuguaglianza triangolare ka+bk 2 k ak 2+ kbk 2in Rn 2 , la stessa deve valere anche per la norma di Frobenius. Infatti : kA + Bk F=v u u tn X i;j=1( a ij+ b ij)2 v u u tn X i;j=1a 2 ij+v u u tn X i;j=1b 2 ij= kAk F+ kBk F: Alternativamente, avremmo potuto utilizzare la disuguaglianza di Cauchy-Schwarzn X i;j=1a ijb ijv u u tn X i;j=1a 2 ijv u u tn X i;j=1b 2 ij1 e scrivere n X i;j=1( a ij+ b ij)2 =n X i;j=1a 2 ij+n X i;j=1b 2 ij+ 2n X i;j=1a ijb ij n X i;j=1a 2 ij+n X i;j=1b 2 ij+ 2v u u tn X i;j=1a 2 ijv u u tn X i;j=1b 2 ij=0 @v u u tn X i;j=1a 2 ij+v u u tn X i;j=1b 2 ij1 A2 ; da cui la disuguaglianza triangolare per la norma di Frobenius. b)Grazie alla disuguaglianza di Cauchy-Schwarz, si ha kAxk2 2=n X i=10 @n X j=1a ijx j1 A2 n X i=1n X j=1a 2 ijn X j=1x 2 j= kAk2 Fk xk2 28 x2Rn : Pertantok
k Fè compatibile con la norma euclidea. c)Sek
kè la norma matriciale suRn n indotta da una norma vettorialek
ksuRn kIk= sup x6 =0k Ixkk xk= sup x6 =01 = 1 : EssendokIk F=qP n i;j=12 ij=pn , concludiamo allora che pern >1la norma di Frobenius non è indotta da alcuna norma vettoriale. Esercizio 2 Si deniscep-norma, per ognip2(0;1], l'espressione seguente : kxk p=8 > > > < > > > : n X i=1j x ijp! 1p p6 =1; kxk 1= max i=1;:::;nj x ij p=1;8 x2Kn :(1) Per ogniA2Rm n si denisce la norma matricialek
k p, detta indottadallap-norma vettoriale (1)k
k p, come kAk p= sup 06 =x2Rmk Axk pk xk p: Dimostrare le relazioni seguenti, doveB = AT A: kAk 1= max j=1;:::;nm X i=1j a ijj ;kAk 1= max i=1;:::;mn X j=1j a ijj ;kAk 2= max i=1;:::;mp i(B) :(2) Soluzione 2 Cominciamo col considerare la normakAk 1(per la norma kAk 1il procedimento è analogo). Per denizione, si ha kAk 1= sup x6 =0k Axk 1k xk 1= sup x6 =0P m i=1j y ijP n j=1j x ij; (3)2 essendo y i=P n j=1a ijx jla i-esima componente del vettorey= Ax. Sfruttando la disuguaglianza m X i=1 n X j=1a ijx j m X i=1n X j=1j a ijjj x jj  max j=1;:::;nm X i=1j a ijj! n X j=1j x jj = max j=1;:::;nm X i=1j a ijj! kxk 1; sostituendo nella (3) otteniamokAk 1 M = max j=1;:::;nm X i=1j a ijj :(4) Per provare che nella (4) vale il segno di uguaglianza, procediamo come segue. Siaj l'indice tale che m X i=1j a ijj = max j=1;:::;nm X i=1j a ijj =M : Siax il vettore di componenti x j= 0 perj6 =j , x j= 1 . Si ha allora chekx k 1= 1 ; inoltreky k 1= M , ovey = A x . Dunque, dalla (3), si ha che kAk 1 M : (5) Da (4) e (5) abbiamo allora che deve necessariamente essere kAk 1= max j=1;:::;nm X i=1j a ijj : Si procede in maniera simile per provare chekAk 1= max i=1;:::;mn X j=1j a ijj : In particolare, si trova che per qualunquex2Rn vale la disuguaglianza kAxk 10 @max i=1;:::;mn X j=1j a ijj1 Amax jj x jj =M kxk 1; e che il vettorex = [1;1; : : : ;1]T , per il qualekx k1= 1 , verica l'uguaglianzakAx k1= M . Veniamo ora alla normakAk 2. Notiamo innanzitutto che la matrice B = AT Aè simmetrica per costruzione, pertanto tutti i suoi autovalori e autovettori sono reali. Inoltre, tutti gli autovalori sono non-negativi, infatti, denominando convun autovettore associato ad un autovalore i(B) , abbiamo : AT Av= Bv= i + i=v T AT Avv T v= k Avk2 2k vk2 2 0: Sia orafv igm i=1una base ortonormale di autovettori della matrice B, relativa agli autovalori i; i = 1; : : : ; m (tale base esiste in quanto la simmetria diBgarantisce che tale matrice sia ortogonalmente diagonalizzabile) : vT iv j=( 1sei=j; 0sei6 =j;8 i; j= 1; : : : ; m:3 Allora, ogni vettore x2Rm si può scrivere come combinazione lineare univoca dei versoriv i: x=c 1v 1+


+c mv m: Pertanto,Bx=c 1 1v 1+


c m mv m: Senza perdita di generalità, possiamo assumere che gli autovalori siano ordinati come (0) 1  2 : : : m: Sfruttando la denizione di normavettorialek
k 2e l'ortonormalità dei v i, si mostra che kAxk2 2= xT AT Ax=xT Bx=c2 1 1+


+c2 m m  c2 1+


+c2 m
m=  mk xk2 2; per qualsiasi vettorex2Rm . Di conseguenza, kAk 2= sup 06 =x2Rmk Axk 2k xk 2p m= max i=1;:::;mp i(B) : Per mostrare l'uguaglianza, è suciente sceglierex=v m, cosicché siano c 1=


=c m1= 0 ec m= 1 . Esercizio 3 Si dimostrino le relazioni seguenti : a)Per ognix2Rn kxk 2 k xk 1pn kxk 2; kxk 1 k xk 2pn kxk 1; 1n k xk 1 k xk 1 k xk 1: b)Per ogniA2Rn n 1n K 2(A) K 1(A) nK 2(A) ;1n K 1(A) K 2(A) nK 1(A) 1n 2K 1(A) K 1(A) n2 K1(A) :4 Soluzione 3 a)Per l'equivalenza delle norme vettoriali, si può procedere come segue : kxk 1=n X i=1j x ij  ()v u u tn X i=1j x ij2v u u tn X i=11 2 =pn kxk 2; kxk2 1= n X i=1j x ij! 2 =n X i=1j x ij2 +X i6 =jj x ijj x jj  k xk2 2; kxk 2=v u u tn X i=1j x ij2 v u u tmax ij x ij2n X i=11 = pn kxk 1; kxk2 1= max ij x ij2 n X i=1j x ij2 =kxk2 2; kxk 1= max ij x ij n X i=1j x ij =kxk 1; kxk 1=n X i=1j x ij  max ij x ijn X i=11 = nkxk 1; ove abbiamo applicato la disuguaglianza di Cauchy-Schwarz in(). b)Per quanto riguarda l'equivalenza tra i numeri di condizionamento, si utilizzeranno i risultati prece-denti. Per denizione si haK 2(A) = kAk 2k A 1 k2e K 1(A) = kAk 1k A 1 k1. Utilizzando l'equivalenza di norme vettoriali si ha kAk 2= sup x6 =0k Axk 2k xk 2 sup x6 =0k Axk 11 p n k xk 1= pn sup x6 =0k Axk 1k xk 1= pn kAk 1: In modo analogo si ottiene chekA 1 k2pn kA 1 k1; di conseguenza K2(A) = kAk 2k A 1 k2 nkAk 1k A 1 k1= nK 1(A) ; e quindi1n K 2(A) K 1(A) : Allo stesso modo si ha kAk 1= sup x6 =0k Axk 1k xk 1 sup x6 =0pn kAxk 2k xk 2= pn sup x6 =0k Axk 2k xk 2= pn kAk 2: ed anchekA 1 k1pn kA 1 k2, quindi K1(A) = kAk 1k A 1 k1 nkAk 2k A 1 k2= nK 2(A) : Le altre disuguaglianze si dimostrano in modo analogo.5 Esercizio 4 Si dimostri che una norma matriciale indotta è sub-moltiplicativa. Si sfrutti il risultato trovato per provare che date due matrici quadrate non singolariA;B2Rn n , alloraK(AB)K(A)K(B). Soluzione 4 Siak
kuna norma matriciale indotta da una norma vettoriale che indichiamo, con leggero abuso di notazione, con lo stesso simbolo. Per denizione, si ha kABk= sup x6 =0k ABxkk xk= sup x= 2ker(B)k ABxkk Bxkk Bxkk xk: DunquekABk sup y6 =0k Aykk yksup x6 =0k Bxkk xk= kAkkBk; ovvero la norma matriciale indotta risulta sub-moltiplicativa. Sfruttando il risultato trovato, avremo cheK(AB) =kABkkB 1 A 1 k  kAkkBkkB 1 kkA 1 k =kAkkA 1 kkBkkB 1 k=K(A)K(B); ovvero anche il numero di condizionamento è sub-moltiplicativo. Esercizio 5 Si consideri la matriceA2R2 2 , A = 1 0 1 ; 0: Si considerino inoltre il sistema lineareAx=be il sistema lineareperturbatoA(x+x) =b+b. a)Siab= [1;0]T . Trovare una limitazione per la variazione relativa della soluzionek xk 1k xk 1in termini della variazione relativa dei datik bk 1k bk 1. Il problema è stabile rispetto alle perturbazioni bquando ! 1? b)Ripetere l'analisi del punto precedente perb= [1;1]T . c)CalcolareK 1(A) eK 1(A) . Trovare una limitazione analoga a quella dei punti a), b), che valga per ognib. Soluzione 5 Ci sarà utile calcolare alcune norme matriciali diAe della sua inversa. Innanzitutto notiamo cheA =  1 0 1 eA 1 = 1 0 1 :Poiché 0, otteniamo kAk 1= max j=1;22 X i=1j a ijj = maxf1;1 + g= 1 + ; kAk 1= max i=1;22 X j=1j a ijj = maxf1 + ;1g= 1 + ; kA 1 k1= max f1;1 + g= 1 + ; kA 1 k1= max f1 + ;1g= 1 + :6 a)La soluzione del sistema lineare per b= [1;0]T è data dax= [1;0]T . Si osservi inoltre chekbk 1= kxk 1= 1 . Il sistema perturbato è della forma A(x+x) = (b+b); da cui, sfruttandoAx=b, otteniamox= A 1 b. Pertanto, sfruttando la sub-moltiplicatività, avremokxk 1 k A 1 k1k bk 1; e, dividendo perkxk 1, kxk 1k xk 1 k A 1 k1k xk 1k bk 1: (6) Poichékxk 1= kbk 1= 1 si può scrivere kxk 1k xk 1 k A 1 k1k bk 1k bk 1= (1 + )k bk 1k bk 1: Osserviamo quindi che per ! 1, perturbazioni sul datobvengono sempre più amplicate sulla soluzionexdel problema. Il problema non è dunque stabile rispetto alle perturbazioni sui dati per grande. b)La soluzione del sistema lineare conb= [1;1]T è data dax= [1 ;1]T . Si osservi, inoltre che kbk 1= 1 ekxk 1= max f1;j1 jg. Ripetendo il procedimento seguito al punto precedente, dalla (6) si ottiene kxk 1k xk 1 k A 1 k1k bk 1k bk 1= 1 + max f1;j1 jg |{z} C( )k bk 1k bk 1: Dato cheC( )!1quando ! 1, nel caso corrispondente ab= [1;1]T il problema è stabile rispetto alle perturbazioni sui dati anche per grande. c)Si haK1(A) = kAk 1k A 1 k1= K 1(A) = kAk 1k A 1 k1= (1 + )2 : Il numero di condizionamento tende quindi all'innito quando ! 1. In generale, si può ottenere una stima teorica valida perbqualunque sostituendokxk 1 k Ak 1 1k bk 1 nella (6), ottenendo kxk 1k xk 1 K 1(A)k bk 1k bk 1= (1 + )2 k bk 1k bk 1: Tale stima vale per ogni scelta dib, ed è dunque la più pessimistica (ma anche la più generale). A partire da tale stima si conclude che il sistemapuò essere, in generale, instabile rispetto a perturbazioni sui dati quando ! 1. Abbiamo visto che in realtà, per alcuni casi particolari come quello considerato in b), questo può anche non vericarsi.7