Post on 08-Apr-2018
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 .