8/6/2019 c13mn

1/10

8/6/2019 c13mn

2/10

2

0,...,0,,...,,diagCVV r21T .Valorile proprii nenule ale matricei C sunt pozitive ntruct

0AVeAVeVAeee2

iiTT

iiTii i, prin urmare, fr a reduce generalitatea,

putem considera c acestea au fost ordonate descresctor, i.e

.n:1rj,0

,0

...

jr321 i defini numerele pozitive

.n:1j, jj

00

0CVV

21T

Considerm urmtoarea partiie a matricei V

21 VVV ,unde )n:1r,:(VV),r:1,:(VV 21

00

0

VCVVCV

VCVVCV 21

2T21

T2

2T11

T1

i de unde rezult, printre altele, egalitatea blocurilor diagonale

.0AVAV,VAAV 2TT

2211

TT1

Cum blocul rr1 R este o matrice nesingular, rezult r111T111111TT111 IVAVAVAAV , i.e. matricea

rm1111 RAVU

are coloanele ortogonale i, prin urmare, poate fi completat cu o matrice rmm2 RU

pn la o matrice

21 UUU ortogonal. De asemenea, rezult 11

T1 VAU i 0UUVAU 11T21T2 . Pe de alt

parte, rezult, evident, 0VA 2 ..

00

0

VAUVAU

VAUVAUAVU

1

2T21

T2

2T11

T1T

n virtutea teoremei de mai sus observm cT111

T VUVUA ,relaie care definete descompunerea (sau factorizarea) valorilor singulare ale matricei A.Numerele r:1j,0j mpreun cu numerele n:1rj,0j senumesc valori singulare ale matricei A. Coloanele n:1j,RVev njj , alematricei V se numesc vectori singulari (la dreapta) ai lui A asociai valorilor singulare

8/6/2019 c13mn

3/10

3

n:1j,j , iar coloanele n:1j,RUeu mjj ale matricei U se numescvectori singulari la stnga ai lui Aasociai acelorai valori singulare. Rezult c orice matrice

nmRA se poate scrie ca sum de produse externe de vectori singulari ponderai cuvalorile singulare nenule

r

1j

T

jjj

T

111vuVUA ,

relaie numit i descompunerea redus a valorilor singulare, unde matriceler:1j,vuW Tjjj se numesc componentele principale ale matricei A. Matricea se

numeteforma canonic pseudodiagonala matricei A.

n legtur cu unicitatea DVS a unei matrice A, din demonstraia teoremei rezult c valorilesingulare sunt rdcinile ptrate pozitive ale valorilor proprii ale matricei AAT i, nconsecin, sunt unic determinate. n ceea ce privete matricele de transformare, vectoriisingulari asociai valorilor singulare nenule, i.e. submatricele 1U i 1V sunt, n esen (n

sensul c putem multiplica simultan coloane individuale ale acestor matrice cu 1 , iar n cazulcomplex cu orice numr de modul unitar), unice n timp ce submatricele 2U i 2V pot fi orice

completri ortogonale ale submatricelor 1U i 1V .Cadrul definitoriu de mai sus al valorilor singulare sugereaz urmtoarea procedur de calcul

1. Se calculeaz AAC T 2. Folosind, de exemplu, algoritmul QRsimetric se calculeaz n21 ,,,C cu n:2i, 1ii 3. n:1i, ii ,care, din pcate, nu este recomandat n aplicaii practice din cauza erorilor introduse nformarea produsului AAT , erori ce pot fi amplificate ulterior pe parcursul calculelelor.Algoritmul de calcul al valorilor singulare care s-a impus n practic, numit algoritmul DVS

este un algoritm QR"mascat" n sensul c acioneaz exclusiv asupra matricei Antr-un modechivalent cu aciunea algoritmului QRsimetric cu deplasare implicit asupra matricei C.

Aplicaii ale DVS

Descompunerea valorilor singulare reprezint un instrument deosebit de util i de sigur nrezolvarea a numeroase probleme cu caracter aplicativ din diverse domenii tiinifice i tehnice,cum sunt teoria sistemelor, prelucrarea semnalelor, statistic etc.

1. Calculul normelor matriceale ortogonal invarianteFie matricea nmRA ( nmCA ). Vom spune c o norm matriceal

RR: nm ( RC: nm ) este ortogonal (unitar) invariant dacAUAV pentru toate matricele V,U ortogonale (unitare).

Norma matriceal2

indus de norma euclidian, i.e. definit de2

1x2

AxmaxA2

numit norma spectral,precum i norma Frobenius

F definit de

8/6/2019 c13mn

4/10

4

)AA(traAT

n

1i

n

1j

2ijF

sunt ortogonal invariante i, n consecin, se exprim foarte simplu n termenii valorilorsingulare )A(i . Concret, avem

12 A ,2

r

2

2

2

1FA .

ntr-adevr

1

r

1i

2i

2i

1y21y21x22ymaxymaxxmaxA

222

,

se obine imediat dinFF

A .

Desigur, pentru a calcula norma Frobenius a unei matrice determinarea prealabil a valorilorsingulare este o cale total neeficient. n schimb, dac se dispune de valorile singulare, calcululacestei norme pe baza relaiei de definiie devine ineficient. Calculul normei spectrale este

echivalent cu evaluarea valorii singulare maxime, ceea ce presupune un efort de calculimportant i, de aceea, norma spectral este utilizat destul de rar n aplicaii dar joac un rolimportant n dezvoltrile teoretice.Dac matricea nnRA este ptrat i nesingular, avnd descompunerea valorilorsingulare TVUA , atunci matricea invers 1A are expresia

T

n21

T11 U

1,,

1,

1diagVUVA

,

i.e.

11nn

1

1,,

1,

1)A(

ntruct valorile singulare sunt ordonate ntotdeauna descresctor. Rezult c descompunerea

valorilor singulare pentru matricea 1A este T1 V~~U~A , unde)1:1:n,:(VU

~ , )1:1:n,:(UV~ , iar

11nn

1,,

1,

1diag

~ . Aceste observaii permit o exprimare interesant a

numerelor de condiionare la inversare a matricei nesingulare A. Avem

n

1

2

1

22

AA)A(

i n

1i

n

1i

2i

2iF

1

FFAA)A( .

Prin urmare, o matrice este cu att mai bine condiionat la inversare cu ct valorile salesingulare sunt mai grupate. n particular, matricele ortogonale (unitare) Q, avnd toate valorilesingulare egale cu 1, au 1)Q(2 i, prin urmare, sunt perfect condiionate la inversare.

8/6/2019 c13mn

5/10

5

2. Calculul rangului

Dou matrice A i B, de aceleai dimensiuni, se numesc echivalente dac exist matriceleptrate nesingulare Si T astfel nct

TASB i ortogonal (unitar) echivalentedac matricele Si Tsunt ortogonale (unitare).Rangul unei matrice nmRA este dat de numrul liniilor (sau coloanelor) sale liniarindependente.Considerm cunoscut faptul c transformrile de echivalen conserv rangul unei matrice. nconsecin, din descompunerea valorilor singulare TVUA , rezult c orice matrice esteortogonal (unitar) echivalent cu forma sa canonic pseudodiagonal i, prin urmare, obinemimediat urmtorul rezultat.

Teorema 2. Rangul unei matrice este egal cu numrul valorilor sale singulare nenule, i.e.rrangArang .

Din nefericire, aa cum s-a mai menionat, acest rezultat nu poate fi folosit ca atare naprecierea numeric a rangului unei matrice date ntruct descompunerea valorilor singularecalculat ntr-un mediu de calcul aproximativ (cum este cel care folosete reprezentarea nformat virgul mobil) este descompunerea valorilor singulare exact a unei matrice uor

perturbate. Cum ns n vecintatea oricrei matrice exist o mulime dens de matrice de rangmaximal rezult c exist toate ansele ca forma canonic pseudodiagonal calculat, pe care o

vom nota cu , s fie de rang maximal. De aceea, n practica numeric se utilizeaz conceptulde rang numericcare se definete n modul urmtor.

Definiia 1. Dat o toleran 0 , rangul numeric r al matricei nmRA estedefinit de cel mai mic dintre rangurile matematice ale tuturor matricelor de aceleaidimensiuni aflate la o distan definit corespunztor de matricea A mai mic dect

tolerana, i.e..)Xrang(minr

nmRX

)X,A(dist

Dac se utilizeaz distana dintre dou matrice definit cu ajutorul normei matriceale spectrale

22XA)X,A(dist

sau, respectiv, cu ajutorul normei Frobenius

,XA)X,A(distFF

atunci descompunerea valorilor singulare ofer mijloace de exprimare comode a ranguluinumeric. Baza acestor rezultate rezid n urmtoarea teorem.

Teorema 3. Fie )A(rangr i

r1j

Tjjj

TvuVUA descompunerea valorilor

singulare a matricei nmRA , unde )j,:(Vv),j,:(Uu jj sunt coloanelematricelor ortogonale de transformare. Considerm un ntreg rk i definimmatricea

8/6/2019 c13mn

6/10

6

.vuAk

1j

Tjjjk

Atunci

1k2k2

RXkXrang

AAXAminnm

i

.min1

222

rang

r

ki

iFkF

RX

kXAAXA

nm

Demonstraie. Pentru precizare considerm nm iar pentru simplificarea notaiilor notmnorma vectorial euclidian cu . Din datele teoremei, mai precis din expresia matricei

kA ,

avem n mod evident relaia )0,,0,,,,(diagVAU k21kT

de unde rezult

egalitatea )0,,0,,,,0,,0(diagV)AA(U r1kkT

i, prinurmare, inndseama de conservarea normelor vizate la transformri ortogonale, obinem

1k2k

AA i n21

,,,)A( Fie acum o matrice nmRX de rangkdar altfel arbitrar. Pentru nceput, notnd 1kV)1k:1,:(V , vom arta c existun vector nenul nRw astfel nct 1kVImXKerw , i.e. 0wX i

z)1k:1,:(Vw . ntr-adevr, considernd DVS T111 V~~U~X a lui X , matricea)1k(k

1kT1 RVV~

Y avnd mai multe coloane dect linii are un subspaiu nucleu 0Ker Y , i.e. exist un vector 0\Rz n cu 1z astfel nct 0zY . Prin

urmare, zVw 1k este vectorul cutat. Pe aceast baz avem secvena de inegaliti

zUzAVAww)XA(y)XA(max)XA( 1k1k2

1k

222

1y

2

1

2

1k

k

1i

k

1i

k

1i

2

1k

2

i

2

1k

2

i

2

i

2

1k

2

i

2

i

2

i

1k

1i

2

i z)()z1(zz

,unde ultima inegalitate rezult din ordonarea descresctoare a valorilor singulare. Cum

matricea Xa fost o matrice arbitrar de rang k iar 22

21 XA)XA( rezult c prima

egalitate a teoremei este demonstrat.Pentru demonstrarea celei de a doua egaliti a teoremei vom utiliza inegalitatea lui Weyl [28],conform creia )C()B()CB( ji1ji . Lund matricea Xo matrice arbitrar derang k avem 0)X( 1k i, prin urmare, aplicnd inegalitatea lui Weyl obinem

).XA()X()XA()XXA()A( i1kiikik

n

1ki

2i

kn

1i

2i

n

1i

2i

2

F)A()XA()XA(XA

ceea ce trebuia demonstrat.Pe baza teoremei de mai sus se poate utiliza descompunerea valorilor singulare pentruexprimarea rangului numeric conform urmtorului rezultat.

Teorema 4. Fie n21 ,,,)A( spectrul de valori singulare al matricei A.

8/6/2019 c13mn

7/10

7

Dac utilizm funcia distan atunci rangul numeric r al matricei A este egal cunumrul valorilor sale singulare superioare toleranei , i.e. este ntregul

r care

satisface condiia1rr

.Dac utilizm funcia distan, atunci rangul numeric

r al matricei Arezult din relaia

.

rj

2j

2

1rj

2j

Demonstraia acestor rezultate este imediat i este lsat n sarcina cititorului.Important este faptul c expresiile de mai sus, pentru definirea rangului numeric, pot fi utilizatecu succes pentru calculul acestuia pe baza descompunerii valorilor singulare ale matricei date calculate cu algoritmul DVS. De exemplu, numrul

r al valorilor singulare calculate

j superioare toleranei date este o foarte bun estimare a numrului r de valori singulare

exacte j superioare valorii toleranei .

ncheiem acest paragraf cu sublinierea faptului c orice referire corect, din punctul de vedereal calculului numeric, la rangul unei matrice trebuie s fac apel la valorile sale singulare i la

conceptul de rang numeric. De exemplu, cea mai bun msur a apropierii unei matrice ptratede o matrice singular este dat de valoarea sa singular minim. Alte criterii cum ar fivaloarea determinantului sau cel mai mic dintre modulele valorilor proprii pot furniza n acestsens o apreciere cu totul eronat.

Rezolvarea problemei generale ale celor mai mici ptrate

Descompunerea valorilor singulare ofer o soluie problemei generale a rezolvrii, n sensulcelor mai mici ptrate, a sistemelor liniare. Fie sistemul liniar cu m ecuaii i n necunoscute

bAx ,respectiv cu nmRA i mRb . Cazurile n care matricea A este de rang maximal (monic

i/sau epic) au fost tratate n capitolele precedente ale lucrrii. De aceea acum vom presupunesituaia general n care

)n,m(min)A(rang .n cazul n care inegalitatea este satisfcut strict, sistemul este, n general, incompatibil iadmite o infinitate de pseudosoluii n sensul celor mai mici ptrate. ntr-o astfel de situaie sedorete calculul pseudosoluiei CMMP de norm euclidian minim numit pseudosoluianormala sistemului. Rezultatul fundamental care permite rezolvarea acestei probleme estedat de urmtoarea teorem.

Teorema 5 . Soluia problemei generale a celor mai mici ptrate: Oricare ar fi matriceanmRA i vectorul mRb , sistemul bxA admite o pseudosoluie normal

unic n* Rx . Dac r)A(rang i T111T VUVUA este decompunereavalorilor singulare a matricei A , atunci pseudosoluia normal poate fi scris n forma

bAx* unde

mnT1

111 RUVA

este pseudoinversa (Moore-Penrose) a matricei A .

8/6/2019 c13mn

8/10

8

Demonstraie: Considerm reziduul de ecuaie Axbr al sistemului (141) i calculmnorma sa euclidian innd seama de descompunerea valorilor singulare ale matricei A .ntruct transformrile ortogonale conserv norma euclidian, avem

xVbUxVbUUxVUbr TTTTT .Introducem notaiile i partiiile

rn

rT

rm

rT

y

yxVy,

d

dbUd

,

cu care devine

22

1

1dyd

d

ydydr

.

Cum d nu depinde de x, minimul normei lui r corespunde minimului termenului0yd 1 care minim, datorit faptului c 1 este nesingular, este nul i se obine

pentrudy 11 .

toate pseudosoluiile n sens CMMP ale sistemului se scriu sub forma

y

dVx

11

cu rnRy arbitrar. Dintre acestea exist una singur de norm euclidian minim, ianume cea care corespunde lui 0y , ntruct

221

1 ydx .n concluzie, unica pseudosoluie normal este

bUV

0

)r:1(bUVx

T1

111

T11*

.

Teorema este demonstrat.Rezultatele de mai sus pot fi extinse fr dificulti la cazul matricelor complexe nmCA .Evident, calculul pseudosoluiei normale se face fr a calcula explicit pseudoinversa matriceiA ci utiliznd n mod eficient ultima din relaiile de mai sus, i.e.

r

1j j

TT1

111

*

b))j(:,U()j(:,VbUVx ,

unde r este rangul matricei A iar r:1j,j sunt valorile sale singulare nenule. Rezulturmtoarea schem de calcul.

1. Se calculeaz DVS AVUT cu acumularea transformrilor U i V .2. Se determin r - rangul (numeric al) matricei A .3. 0x

8/6/2019 c13mn

9/10

9

4. Pentru rj :1

1. bjU T)),:((

2.j

3. ),:( jVxx

Problema CMMP poate fi extins impunnd minimizarea normei euclidiene a reziduului deecuaie a unui sistem liniar supradeterminat n prezena diverselor tipuri de restricii.

3. Calculul pseudoinversei

Pseudoinversa unei matrice generalizeaz conceptul de invers, definit pentru matricele ptratei nesingulare, la cazul unei matrice nm oarecare.

Definiia 5. Fie matricea nmRA . O matrice mnRX se numete pseudoinversamatricei Adac satisface urmtoarele patru condiii Moore-Penrose

XA)XA(

AX)AX(

XXAX

AAXA

T

T

n cazul complex pseudoinversa este o matrice complex care satisface cele patru condiiide mai sus n care transpunerea se nlocuiete cu conjugarea hermitic.

Urmtorul rezultat afirm existena i unicitatea pseudoinversei i sugereaz o modalitateeficient de calcul a acesteia.

Teorema 5. Orice matrice nmRA admite o pseudoinvers unic. Dac TVUA este descompunerea valorilorsingulare a matricei A, atunci pseudoinversa sa esteTUVAX ,unde este pseudoinversa matricei i are expresia

mn1

1R

00

0

.

Demonstraie. Pentru nceput observm c mmr

R00

0I

innr

R00

0I

, de unde rezult c satisfacecele patru condiii Moore-Penrose.n continuare avem egalitile

AVUVUVUUVVUAAA TTTTT ,Pentru demonstraia unicitii, presupunem existena a dou pseudoinverse mnRY,X ifie YXD . Din condiiile Moore-Penrose rezult

8/6/2019 c13mn

10/10

10

.DA)DA(

AD)AD(

DYADDAYDAD

0ADA

T

T

De aici obinem 0ADADAD)AD(T

, de unde rezult 0AD . Similar0DADADA)DA( T , deci 0DA . Din a doua din relaiile de mai sus rezult D=0,

deci X=Y. Prin urmare pseudoinversa unei matrice este unic.Pentru calculul pseudoinversei unei matrice se calculeaz DVS dup care se utilizeaz expresia(154), conform creia obinem urmtoarea expresie de calcul

)k,:(Vv),k,:(Uu,)A(rangr,

uvA kk

r

1k k

Tkk

sau, pe componente,

.m:1j,n:1i,

uv)j,i(A

r

1k k

jkik

Observaie. Menionm c pentru matricele nmRA monice pseudoinversa se identific cu

pseodoinversa Moore-Penrose T1T AAAA , care este o invers la stnga ntructnIAA , iar pentru matricele nmRA epicepseudoinversa se identificpseudoinversa

normal 1TT AAAA , care este o inversla dreapta ntruct mIAA .Una dintre proprietile cele mai interesante ale pseudoinversei (care se demonstreaz frdificultate) este aceea c pseudoinversa unei matrice nmRA este unica soluie de normFrobenius minim a problemei de minimizare

FmRXIAXmin

mn .