8/7/2019 CALCULUL NUMERIC AL VALORILOR SI VECTORILOR PROPRII

1/4

Carmen-Sanda Georgescu, Tudor Petrovici, Radu Popa

Metode numerice. Fisa nr. 14:CALCULUL NUMERIC AL VALORILOR SI VECTORILOR PROPRII

9 . VALORI SI VECTORI PROPRIIFie A Cn x n . Un numar C se numeste valoare proprie a matricii A daca exista unvector nenul x Cn , x 0, astfel incat

Ax= x (14.1) Vectorul x se numeste vector propriu al lui A asociat valorii proprii . Orice matricepatratica A R n x n are exact n valori proprii k , k=1,2, . . . ,n si k C. Folosind relatia(14.1) rezulta ca valorile proprii ale matricii A sunt radacinile polinomuluicaracteristic al matricii A si anume det( I n -A)=0 (det( I n-A) reprezinta determinantulmatricii ( I n -A) , I n este matricea unitate iar det( I n -A)= P A( ) este polinomulcaracteristic al matricii A).

P A( )=a 1 n + a 2 n-1 + a 3 n-2 + . . . a n+ a n+1 (14.2)Daca k ,k=1,1, . . . ,n, este o valoare proprie atunci orice solutie nenula x k a ecuatiei

(A- k I n)x k = 0 (14.3)

este vector propriu.Se defineste de asemenea spectrul radial (A) al matricii A ca (A)=max(| k |),k=1,2, . . . ,n

9.1. LOCALIZAREA VALORILOR PROPRIILocalizarea valorilor proprii se poate face cu ajutorul algoritmului care rezulta dinteorema lui Gersgorin si anume: daca ACn x n atunci fiecare valoare proprie a sa se

gaseste in cel putin un disc cu centrul in a kk si raza r k = sau r=

n

k j j

kja1

|| j= (14.4)=

n

jk k

kja1

||

unde k,j=1,2, . . . ,nExemplul 1. Fie matricea A=[0 1 1;1 0 1;1 1 0]. Sa se stabileasca domeniul in caresunt localizate valorile proprii ale matricii.Rezolvare: Folosind formulele (14.4) rezulta r 1 =2, r 2=3, r 3=2 . Rezulta ca valorileproprii ale matricii A se gasesc in reuninunea domeniilor circulare{z||z-1| 2} {z||z| 3} {z||z| 2}

9.2. METODE DE CALCUL PENTRU VALORILE PROPRIIPe langa metoda analitica , metodele numerice de determinare a vectorilor si valorilorproprii sunt de doua feluri: metode directe si metode indirecte (iterative si partialiterative); pentru matrici hermitiene exista metode specifice.

REZOLVAREA ECUATIEI CARACTERISTICE SI OBTINEREA VECTORILOR PROPRII9.2.1. METODA ANALITICAExemplul 2. Fie matricea A=[0 1 1;1 0 1;1 1 0]. Sa se determine valorile si vetoriiproprii asociati matricii A. Sa se verifice teorema lui Gersgorin.Rezolvare: Polinomul caracteristic al matricii A este P A( )= 3 -3* +2. Din P A( )=0

rezulta valorile proprii 1=2, 2=-1, 3 =-1. Folosind relatia (14.3) calculam vectoriipropriiPentru 2= 3 =-1 se obtine pentru vectorii proprii x 2 = x 3 = (x 1 , x 2 , x 3 ) T , sistemul liniaromogen

x 1 +x 2+x 3 =O x 1 +x 2+x 3 =O x 1 +x 2+x 3 =Ocare inafara solutiei banale are si solutiile x 2 = x 3=( , , -( + )) T unde , R-{0}Pentru 1=2 se obtine pentru vectorul propriu x 1 =(x 1 , x 2 , x 3) T ,sistemul liniar omogen

8/7/2019 CALCULUL NUMERIC AL VALORILOR SI VECTORILOR PROPRII

2/4

-2*x 1+x 2 +x 3=O x 1 -2*x 2 +x 3 =O x 1 +x 2-2*x 3 =Ocare inafara solutiei banale are si solutiile x 1=( , , ) T unde R-{0}Daca se considera = = =1 si se normalizeaza vectorii x 1 , x 2 , x 3 se obtin vectoriiproprii x 2 =[0.40825 0.40825 -0.81650] T , x 3 =[ 0.70711 -0.70711 0.00000] T ,

x1

=[0.57735 0.57735 0.57735]T

(baza oronormala a spatiului vectorial R 3

/R in carematricea A capata forma diagonala) Verificarea ceruta rezulta din Exemplul 1 Metoda numerica in Octave/Matlab . In Octave, calculul polinomului caracteristic almatricii A se face folosind functia poly(A) , calculul valorilor proprii si a vectorilorproprii se face folosind functia eig(A) . Astfeloctave#1> A=[0 1 1;1 0 1;1 1 0];p=poly(A), valori_proprii=roots(p)octave#2> [V,lambda]=eig(a) # Returneaza rezultatelep = 1.00000 0.00000 -3.00000 -2.00000lambda = 2.00000 -1.00000 -1.00000

V=0.40825 0.70711 0.577350.40825 -0.70711 0.57735

-0.81650 0.00000 0.57735lambda=

-1.00000 0.00000 0.000000.00000 -1.00000 0.000000.00000 0.00000 2.00000

9.2.2. METODE DIRECTE. Dintre metodele directe vom mentiona metoda Lavrentiev-Fadeev si metoda Krilov. Se prezinta metoda Lavrentiev-Fadeev

Metoda Lavrentiev-FadeevAlgoritm:

1. Fie o matrice A R n x n Se determina coeficientii a k ,k=1,2, . . ., n+1 ai ecuatiei caracteristice (14.2) astfel:Pas_1: Se considera a 1=1 si se initiaza primul pas de iteratie considerand matricea ajutatoare C

(1)=A si

apoi .

Pas_k=2,3, . . .Pentru pasii k=2,3, ,n , matricea ajutatoare C

=

=n

k

kk ca1

)1(2

(k) se obtine astfel C (k)=A*( C (k-1) +a k*I) iar

coeficientii folosind formula =

+ =n

k

k kk k ck

a1

)(1

1

2. Se calculeaza valorile proprii prin rezolvarea ecuatiei caracteristice P A( )=0 3. Se determina vectorii proprii pentru valorile proprii gasite

Exemplul 3. Sa se aplice metoda Lavrentiev-Fadeev pentru problema de la exemplul 2.Pas_1: Se considera a 1=1 si matricea ajutatoare C (1) =A. Rezulta a 2=0Pas_2: Se calculeaza C (2) =A*( C (1) +0*I 3)= [0 1 1;1 0 1;1 1 0]* [0 1 1;1 0 1;1 1 0]=[2 1 1;1 2 1;1 1 2].

Rezulta a 3 =-3Pas_3: Se calculeaza C (3) =A*( C (2) -3*I 3 )= [0 1 1;1 0 1;1 1 0]* [-1 1 1;1 -1 1;1 1 -1]=[2 0 0;0 2 0;0 0 2].

Rezulta a 4 =-2Pas_3: Rezulta ecuatia caracteristica P A( )= 3-3* -2Pas_4: Rezulta ecuatia caracteristica 3 -3* -2=0 care are valorile proprii 1=2, 2=-1, 3=-1

Pas_5: Calculul vectorilor proprii. Pentru valoarea proprie 1=2 se obtine pentru vectorul propriu x1

conform relatiei (14.3) sistemul-2*x 1 +x 2+x 3 =O

x 1-2*x 2+x 3=O x 1+x 2 -2*x 3=ODaca se considera x 3 =1, rezulta x 2 =x 2 =1. Daca facem normalizarea vectorului x 1 se obtinevectorul propriu x 1 =[0.57735 0.57735 0.57735] T. Se procedeaza la fel pentru valorile proprii 2 = 3 =-1

9.2.3. METODE ITERATIVE. Dintre metodele iterative vom mentiona metoda luiRutishauser (factorizarea LR) si metoda bazata pe factorizarea QR. Se prezinta metodaRutishauser

8/7/2019 CALCULUL NUMERIC AL VALORILOR SI VECTORILOR PROPRII

3/4

Metoda lui Rutishauser (bazata pe factorizarea LR Doolittle) Algoritm:

1. Fie o matrice A R n x n .Se porneste algoritmul astfel: se initializeaza A (0)=A= L (1)*R(1)2. Pentru pasii k=1,2, . . .ai pricesului iterativ se efectuiaza facrorizarea Doolittle A (k-1) =L (k)*R(k) si rezultafactorii L (k) si R (k). La acelasi pas k se calculeaza A (k)= R (k)* L(k)

3. Procesul iterativ se termina atunci cand cu dat1,...,2,1;,...,3,2,|| )( == i jnil k ij

4. Valorile aproximative ale valorilor proprii rezulta ca fiind , i=1,2, . . .,n)()( k iik iii ar Exemplul 4. Sa se aplice metoda lui Rutishauser pentru problema de la exemplul 2 cu =10 -3Pas_1: Se initializeaza A (0) =A= L (1) *R (1) =[1 0 0;0 1 0;1 1 1]*[1 0 1;0 1 1;0 0 -2] si se calculeaza A (1) =R (1) *L (1) = [1 0 1;0 1 1;0 0 -2]* [1 0 0;0 1 0;1 1 1]=[2 1 1;1 2 1;-2 -2 -2]. Se testeaza |l (1) ij |> cu i=2,3 si

j=1,2. Algoritmul continuaPas_2: Se calculeaza factorizarea A (1) =A= L (2) *R (2) =[1 0 0;0.5 1 0;-1 -0.66667]*[2 1 1;0 1.5 0.5;0 0 -0.66667] si se calculeaza A (2) = R (2) *L (2) = [1.5 0.3333 1;0.25 1.16 0.5;0.6666 0.4444 -0.66667]. Setesteaza |l (2) ij |> cu i=2,3 si j=1,2. Algoritmul continua..

Algoritmul se continua pana cand 2,1;3,2,|| )( == jil k ij Observatie: In Octave/Matlab factorizarea LR se obtine aplicand functia lu 9.2.4. METODE PARTIAL ITERATIVE. In anumite probleme se cere calculul valorilor proprii extreme. Astfel pentru calculul valorii proprii de modul maxim se foloseste metoda

lui Rayleigh iar pentru calculul valorii proprii de modul minim se foloseste metoda puteriiinverse. Se prezinta metoda lui Rayleigh Metoda lui Rayleigh

Algoritm:1. Fie o matrice A R n x n .Se porneste algoritmul astfel: se initializeaza vectorul propriu x 1=x (0) ales arbitrar 2. Se introduce un vector auxiliar y. Pentru pasii k=1,2, . . .ai pricesului iterativ se calculeaza vectorulauxiliar y (k)=A*x (k-1) . La acelasi pas se calculeaza noua valoare a vectorului propriu x (k) a lui x 1 conform

formulei ni yunde y x k iik k

k k ,...,2,1|),(|max,

1 )()()( ===

3. Procesul iterativ se termina atunci cand cu datni x x k ik

i ,...,2,1,||)1()( =

4. Valoarea aproximativa a valorii proprii cautate si a vectorului propriu corespunzator rezulta ca fiind

, i=1,2, . . .,n)(1)( k k x xsi ==

Exemplul 5. Sa se aplice metoda lui Rayleigh pentru problema de la exemplul 2 cu =10-2

Pas_1: Se initializeaza vectorul propriu domonant in modul x 1=x (0) =[1 1 0] T .Pas_2: Se calculeaza prima aproximatie a vectorului propriu, y (1) =A* x (0) = [0 1 1;1 0 1;1 1 0]* [1 1 0] T=[11 2] T. Se face normalizarea referitor la valoarea maxima din y (1) si rezulta x (1) =[0.5 0.5 1] T

Pas_3: Se calculeaza a doua aproximatie a vectorului propriu, y (2) =A* x (1) = [0 1 1;1 0 1;1 1 0]* [0.5 0.5 1] T =[1.5 1.5 1] T. Se face normalizarea referitor la valoarea maxima din y (2) si rezulta x (2) =[1 1 0.66667] T

..

Algoritmul se continua pana cand ni x x k ik

i ,...,2,1,||)1()( =

9.2.5. METODE PENTRU MATRICI HERMITIENE. Matricile hermitiene (matrici patraticesimetrice si cu elemente reale) au proprietatea ca toate valorile lor proprii sunt reale.Pentru astfel de matrici se poate aplica oricare dintre metodele deja prezentate dar existasi metode specifice. Dintre metodele specifice matricilor hermitiene remarcam metodaJacobi, metoda lui Givens si metoda lui Hauseholder. Se prezinta metoda lui JacobiAlgoritm:

1. Fie o matrice A R n x n hermitiana adica a ij=a ji cu i,j=1,2,,n.Se porneste algoritmul astfel: se initializeazaA(0)=A

2. Pentru pasii k=1,2, . . .ai pricesului iterativ se determina A (k)=(S (k))T*A(k-1) * S (k) unde S (k) se alege astfel incatsa determine anularea elementului nediagonal maxim in modul al matricii A (k) .

3. Procesul iterativ se termina atunci cand cu dat1,...,2,1;,...,3,2,|| )( == i jnia k ij

4. Valorile aproximative ale valorilor proprii rezulta ca fiind =)( k A unde este o matrice diagonala ,avand pe diagonala valorile proprii ale matricii A

8/7/2019 CALCULUL NUMERIC AL VALORILOR SI VECTORILOR PROPRII

4/4

APLICATII

Problema 1. Se da matricea A=[7 4 -1;4 7 -1;-4 -4 4] Sa se calculeze polinomul caracteristic, valorile proprii si vectorii proprii pentru matricea A prin metodaanalitica si prin metoda directa Lavrentiev-Fadeev. Sa se compare rezultatele cu rezultatele obtinutefolosind functiile Octave poly(A) si eig(A)Problema 2. Sa se rezolve sistemul de ecuatii diferentialedx/dt=y+zdy/dt=x+zdz/dt=x+yfolosind metoda cu valorile si vectorii propriiRezolvare: Cu ajutorul valorilor si vectorilor proprii solutia sistemului se scrie sub forma

t t t evC evC evC X 321 332

21

1 ++= unde v 1 , v 2 , v 3 sunt vectorii proprii corespunzatori valorilor

roprii 1 , 2 , 3 pentru matricea asociata sistemului A=[0 1 1;1 0 1;1 1 0]p