Calcul Numeric

Cursul 10

2015

Anca Ignat

1

Forma superioar Hessenberg Spunem c o matrice n nH este n form superioar Hessenberg dac:

0 , 1, , , 1, , 2ijh i n j i O matrice n form Hessenberg arat astfel:

11 12 13 1 1 1

21 22 23 2 1 2

32 33 3 1 3

43 4 1 4

1

00 0

0 0 0

n n

n n

n n

n n

nn nn

h h h h hh h h h h

h h h hH

h h h

h h

2

Ne intereseaz un algoritm care s transforme o matrice ptratic A oarecare ntr-o matrice Hessenberg superioar H care s aib aceleai valori proprii:

1a.. H , , matrice nesingularA H A H PA P P

Algoritmul este o adaptare a algoritmului lui Housholder i se desfoar n (n-2) pai, folosind matricile de reflexie pentru a transforma matricea.

Pas 1 se efectueaz operaiile A=P1 A P1 (matricea P1 se alege astfel nct coloana 1 s fie transformat n form superior Hessenberg)

3

Pas 2

2 2 2 1 2= ( )initA P AP P P A P

(P2 transform coloana 2 n form superior Hessenberg fr s schimbe coloana 1) Pas r

1 1 1 1( )init

r r r r r rA P AP P P P A P P P (se transform coloana r n form superior Hessenberg fr s schimbe primele (r-1) coloane)

4

Pasul r (r=1,2,,n-2)

La intrarea n pasul r matricea A are primele (r-1) coloane n form superior Hessenberg. La ieirea din pasul r matricea A va avea primele r coloane n form superior Hessenberg:

2

,

= 2 ( ) , , || || = 1ies r intr r ies intr

r r T r n rr n

A P A P A A

P I v v v R v

Vectorul vr se alege astfel ca matricea Aies s aib coloana r n form superior Hessenberg i s nu schimbe primele (r-1) coloane ale matricii Aintr .

5

Calculul matricii Pr 1 T

nP I uu 1= r rk a

2 2 2 2 21

= 1= = = =

n

r r ir nr iri r

k a a a a k

1semn = semn r rk a

6

1

0

0

:= r r

ir

nr

a ku

a

a

0 1 ( )nr r P I

Algoritmul de trecere de la matricea A la matricea Pr A este urmtorul:

7

1 2

pentru = 1, , 1

( ) = ( , , , , ,0, ,0) pentru =

pentru = 1, ,

j

Tr j r r rr

jj

Ae j r

P A e a a a k j r

Ae u j r n

= 1= ( , ) =n

n

j j i iji r

Ae u u a

1 1= 0, = 1, , , = , = , = 2, ,i r r r i iru i r u a k u a i r n Vom descrie n continuare cum se efectueaz operaia A:=APr

fr a face nmulire matricial (matricea A este cea obinut mai sus avnd primele r coloane n form superior Hessenberg).

8

Vom arata c aceast operaie nu schimb forma superior Hessenberg obinut. Vom pune n eviden transformrile liniilor matricii A. Pentru i=1,...,n avem:

noua linie a matricii 1( ) )( )

1 ( )

T T Ti i n

T T T T Tii i i

e AP i AP e A I uu

e A e A u u e A u

unde 1 1( )

Ti i ir r in ne A u a u a u

Elementele liniei i se schimb astfel:

, 1, , , 1, ,iij ij ja a u j r n i n

Operaia A:=APr nu modific primele r coloane ale matricii A, ele rmnnd n form superior Hessenberg.

9

Algoritmul de obinere a formei superior Hessenberg

forconstrucia matricii constanta i vectorul

if break ;

2

= 1

1, , 2

= ;

( ) / / 1

= ;

rn

iri r

r n

r nP u

a

r r P I

k

if 1

1

1 1

( 0 ) ;;; , 2, , ;

r r

r r

r r r i ir

a k kk a

u a k u a i r n

10

transformarea coloanelorfor

for= 1

1, ,1, ,

( / ) ( , ) / = ( ) / ;

1, ,

r

n

j j i iji r

A P Aj r n

j r n

Ae u u a

i r n

transformarea coloanei a matricii

1

;

; 2, , ;

ij ij i

r r ir

a a u

r Aa k a i r n

11

transformarea liniilorfor

for= 1

1, ,1, ,

( / ) (( ) ) / = ( ) / ;

1, ,

r

nT

i i j ijj r

A A Pi n

i n

e A u u a

j r n

;ij ij ja a u

12

Algoritmul QR de aproximare a valorilor proprii ale unei matrici oarecare

Prezentm n continuare cel mai folosit algoritm de aproximare a valorilor proprii pentru matrici ptratice oarecare. Spunem c o matrice n nS este n form Schur real dac matricea S este n form superior Hessenberg i n plus este bloc-diagonal:

11 12 1

22 2

0

p

p

pp

S S S

S SS

S

13

blocurile Sii sunt astfel ca: - iiS - este valoare proprie real - 2 2iiS

- este bloc corespunztor valorilor proprii complexe

Valorile proprii corespunztoare blocului 2 2iia b

Sc d

sunt rdcinile ecuaiei :

2-

( - )( - ) - ( ) 0- -

a ba d bc a d ad bc

c d

Se presupune c aceast ecuaie de gardul 2 are rdcini complexe.

14

Algoritmul QR de aproximare a valorilor proprii construiete un ir de matrici ( )k n nA , matrici asemenea cu matricea A,

( ) ,kA A k , ir care converge la o matrice n form Schur real, ( ) ,kA S k . Matricea limit S este asemenea cu matricea

A, valorile prorii ale matricii S fiind uor de calculat. irul A(k) se construiete astfel:

descomp. calc. pentru matricea

descomp. calc pentru matricea

descomp. calc pentru matricea

(0) (0) (0)0 0

(1) (1) (1)0 0 1 1

(2)1 1

( ) ( )

( 1)

: , ( )

: , ( . )

:

( . ) ,

:

k kk k

k

A A A Q R QR A

A R Q A Q R QR A

A R Q

A Q R QR A

A

, 0,1,2,k kR Q k

15

Matricile Qk sunt matrici ortogonale ( 1 Tk kQ Q ) iar matricile Rk

sunt superior triunghiulare. Matricile A(k) i A(k+1) sunt asemenea:

( ) ( )

( 1) ( ) ( 1) ( )

|

,

T k T kk k k k k

k T k k kk k k k

Q A Q R R Q A

A R Q Q A Q A A k

Matricile irului construit sunt toate asemenea prin urmare au aceleai valori proprii anume cele ale matricii iniiale A= A(0):

(0) (1) ( )kA A A A S

16

Dac matricea A(k) este n form superioar Hessenberg, atunci descompunerea QR realizat cu algoritmul lui Givens se simplific. Reamintim algoritmul lui Givens:

1 1 1 1 1 1 12 12( ) ( ) ( ) ( ) ( )n n n n pn pn pp pp n nR R R R R A R

Dac matricea A este n form Hessenberg n algoritmul lui

Givens, din cele ( 1)2

n n nmuliri cu matrici de rotaie rmn doar (n-1):

1 1 1 1 23 23 12 12( ) ( ) ( ) ( )n n n n pp ppR R R R A R . Problema care se pune este dac pornind cu o matrice n form Hessenberg, toate matricile irului rmn n form Hessenberg:

17

n form Hessenberg) cu Givens)

este tot n form Hessenberg

( )

( 1) ( )

( ( ?kk T k T

A H QRA H RQ Q A Q Q HQ

Avem:

12 12 1 1 1 1( ) ( ) ( )T T T T

rr rr n n n nH Q HQ R R R R Notm cu:

12 12( )TR R R

pentru care avem:

1 1 2 1 1

2 1 2 2 2

, 0, 2, , 0, 3, ,, 0, 3, , 0, 3, ,

i i i i i

i i i i i

r cr sr i r i n r i nr sr cr i r i n r i n

18

deci coloana 1 se transform n form Hessenberg iar coloana 2 rmne n form suprior triunghiular. La pasul p avem: 12 12 1 1 1 1 1 1

12 12 1 1

( ) ( ) ( ) ( ) ,

( ) ( )

T T T Tp p p p pp pp pp pp

T Tp p p p

R R R R R R R

R R R R

matricea R are primele (p-1) coloane n form Hessenberg iar restul coloanelor sunt n form superior triunghiular. Vom arata c la acest pas matricea R va avea primele p coloane n form Hessenberg iar restul coloanelor n form superior triunghiular. Operaia 1 1( )

Tpp ppR R R presupune doar schimbarea

elementelor coloanelor p i p+1:

19

1

1 1 1

1

, 0, 1, ,

, 0, 2, ,

0, 2, ,

0, 2, ,

ip ip ip ip

ip ip ip ip

ip

ip

r cr sr i r i p n

r sr cr i r i p n

r i p n

r i p n

.

Observm din relaia de mai sus c n matricea R coloana p are form Hessenberg iar coloana p+1 rmne n form superior triunghiular (celelalte elemente din matrice nu se modific). Prin urmare dup pasul n-1 matricea ( 1)kH A este n form superioar Hessenberg. Algoritmul QR de aproximare a valorilor proprii folosind descompunerea Givens pstreaz forma Hessenberg.

20

Algoritmul QR pentru valori proprii

se aduce matricea la forma Hessenberg

while forma Schur realse ca

;0;

( ); / /

T

AA Q A Qk

AA QR

lculeaz cu algoritmul Givenssau ;

1;

TA RQ Q AQk k

21

n practic se presupune c matricea A este n form Hessenberg neredus, adic:

1 0 2, ,iia i n Dac matricea nu este n form neredus, problema se decupleaz:

sau11 1221 22

, 1 2A A p

A p n nA A n pp n p

22

Algoritmului QR cu deplasare (shift) simpl Algoritmul cu deplasare simpl este urmtorul:

aducerea la forma Hessenberg neredus

while forma Schur realse calc cu alg.

;0;

( ); / / .

T

k n

A Q A Qk

AA d I QR

Givens: ;

1;k nA RQ d I

k k

kd sunt constantele de deplasare.

23

Dac A - d In = QR (A(k)) i nA RQ d I ( A(k+1)), se pune problema dac cele dou matrici sunt asemenea ( A A ) (irul de matrici construit cu pasul QR cu deplasare simpl au aceleai valori proprii).

( )T T T TnA Q QRQ d Q Q Q QR d I Q Q AQ A A Varianta cu deplasare se efectueaz pentru a accelera convergena algoritmului. Dac 1, 2,..., n sunt valorile proprii ale matricii A ordonate astfel ca:

1 2 nd d d

24

Rapiditatea cu care ( )1 0 ,k

p pa k este dat de rata de

convergena a expresiei 1k

p

p

dd

. Dac se alege nd

convergena ( )1 0k

n na este rapid. Avem urmtorul rezultat: Teorem Fie d o valoare proprie a unei matrici Hessenberg nereduse H. Dac nH RQ d I , cu nH d I QR descompunerea QR a matricii nH d I QR . Atunci:

1 0 ,nn nnh h d

25

Algoritmul QR cu deplasare simpl gsete valoarea proprie d ntr-un singur pas. Euristic s-a constatat c la fiecare pas, cea mai bun aproximare a unei valori proprii este ( )knna .

( )kk nnd a

Algoritmul QR cu deplasare simpl

aducerea la forma Hessenberg neredus

while forma Schur realse calc cu algoritmul Given

;0;

( ); / / .

T

nn n

A Q A Qk

AA a I QR

s: ;

1;nn nA RQ a I

k k

26

Algoritmului QR cu deplasare (shift) dubl

n cazul cnd valorile proprii a1, a2 corespunztoare blocului:

, 1pp pn

np nn

a aG p n

a a

sunt complexe, 1 2,a a , abordarea cu deplasare simpl nu mai asigur accelerarea convergenei. Avem:

2 1 2

2 21 2 1 2

det( ) ( )( ) ( )( )

( ) ( )pp nn pn np

pp nn pp nn pn np

I G a a a a a a

a a a a a a a a a a

27

1 2 1 2( ) , detpp nn pp nn pn npa a a a trace G a a a a a a G Algoritmul QR cu deplasare dubl const n trecerea de la

matricea A = A(k) la matricea A2 = A(k+1) realiznd doi pai cu

deplasare simpl :

A A1 (deplasare simpl a1), A1 A2 (deplasare simpl a2) 1 1 1

1 1 1 1

1 2 2 2

2 2 2 2

n

n

n

n

A a I Q RA R Q a I

A a I Q RA R Q a I

28

Fie matricea :

1 2 2 1 1 2 2 1 1 1 2 1

1 1 1 2 1 1 1 1 1 2 1 1

2 1 1 2 1

: nT T

n

n n n

M Q Q R R Q Q R R Q A a I R

Q Q AQ a I R Q Q AQ R a Q R

A a I Q R A a I A a I

1 2 2 1 2 12

1 2 1 2( )n n

n

M Q Q R R A a I A a I

A a a A a a I

Avem urmtoarele relaii de asemnare:

1 1 1 2 2 1 2 2 1 1 2 1 2 1 2

2 1 2 1 2 1 2, :

TT T T T

T T

A A Q AQ A Q A Q Q Q AQ Q Q Q A Q Q

A Q Q A Q Q Q AQ Q Q Q

29

Matricea Q care asigur trecerea de la matricea A la matricea A2 este matricea ortogonal din descompunerea QR a matricii 2 1n nM A a I A a I . Pasul QR cu deplasare dubl se face urmnd etapele:

1) se calculeaz matricea 2 nM A s A qI cu

s = a1+a2 = app+ann , q = a1a2 = app ann - apnanp ;

2) se calculeaz descompunerea QR a matricii M; 3) A2:=QTAQ.

30

Vectori proprii Considerm dou matrici asemenea A i B:

matrice nesingular1 ,A B A PBP P tim c cele dou matrici au acelai polinom caracteristic,

( ) ( )A Bp p , deci au aceleai valori proprii. Ne intereseaz care este legtura ntre vectorii proprii asociai aceleiai valori

proprii. Fie u vector propriu asociat valorii proprii pentru matricea A i w vector propriu asociat valorii proprii pentru matricea B. Care este relaia ntre u i w?

31

1 1

1 1 1

, ,,

Au u Bw w A PBP PBP u uBP u P u w P u u Pw

Dac se aplic algoritmul QR unei matrici simetrice, forma Schur

real la care se ajunge este o matrice diagonal:

S = = diag[1, 2, ..., n]

Legtura dintre matricea simetric iniial A i matricea diagonal este de forma:

S = = diag[1, 2, ..., n] = UTA U

unde U este o matrice ortogonal, coloanele matricii U fiind

32

vectori proprii asociai valorilor proprii reale 1, 2, ..., n . Matricea U se poate calcula astfel:

Algoritmul QR pentru matrici simetrice (valori +vectori proprii)

se aduce matricea la forma Hessenberg;

;0;

while ( matricediagonal ); / /

T

T

AA Q A QU Qk

AA QR

se calculeaz cu algoritmul Givenssau AQ;

;1;

TA RQ QU UQk k

33

Descompunerea dup valori singulare (Singular Value Decomposition)

Teorem Fie m nA . Atunci exist o matrice ortogonal ptratic de dimensiune m, m mU , o matrice ortogonal ptratic de dimensiune n, n nV i constantele pozitive: 1 2 r >0, r min{m,n} a..

( )

( ) ) ( )

1

0, , ,

0 0

, diag , ,

r n rT m n

m r r m r n r

r rr

DA U V

D D

(1)

Constanta r este chiar rangul matricii A, r = rang(A). Constantele 1, 2, , r poart numele de valori singulare ale matricii A.

34

Folosind relaia (1) avem:

2

( )

( ) ( ) ( )

,

,

0

0 0

TT T T T

T T T T T T Tm

r m rT m mm

m r r m r m r

A U V V U

AA U V V U U U U U

D

2( )

( ) ( ) ( )

,

0

0 0

T T T T T T Tn

r n rT n nn

n r r n r n r

A A V U U V V V V V

D

35

innd cont de ortogonalitatea matricilor U i V, putem rescrie relaiile de mai sus astfel:

2 2 21 2

2 2 21 2

( ) , diag , , , ,0, ,0

( ) , diag , , , ,0, ,0

T m mm m r

T n nn n r

AA U U

A A V V

Din aceste relaii deducem c 2 2 21 2, , , r sunt valorile proprii strict pozitive ale matricilor AAT i/sau ATA iar matricile U i V sunt matrici ale cror coloane sunt vectorii proprii asociai (cei ce formeaz baze ortonormate). Matricile AAT i ATA sunt matrici simetrice:

36

,T T T TT T T T T T T TAA A A AA A A A A A A i au toate valorile proprii nenegative:

2

22

2

, ,

, ,0

,

T T

TT T

AA u u AA u u u u

A uA u A uu u u

Putem folosi descompunerea dup valori singulare pentru a defini pseudo-inversa unei matrici oarecare m nA (nm).

1 11 1 1 1? ? ?,T T T TA U V A U V V U V U

37

Rmne de definit matricea 1? . Urmnd acest raionament se

definete pseudoinversa Moore-Penrose a unei matrici m nA astfel:

1( )

( ) ) ( )

1 1

1

, , ,0

1 1, diag , , .

r m rI I T I n m I n m

n r r n r m r

r r

r

DA V U A

D D

Pseudoinversa definit mai sus satisface urmtoarele proprieti:

, ; ,I I TI m n T I m nA A A A A A ,I I I IAA A A A AA A

38

Exist o proprietate care nu mai este satisfcut de psudoinvers dei este respectat de inversa clasic:

., a. I I IA B AB B A . Descompunerea dup valori singulare poate fi utilizat i pentru rezolvarea sistemelor liniare cu matrici oarecare (mn)

, , , :m n m I nAx b A b x A b .