Calculul numeric al valorilor proprii ale unei matrice - Metoda puterii directe

Calculul numeric al valorilor proprii ale unei matrice

Tematica lucrarii: 1. Generalitati;

2. Metoda puterii directe;

3. Metoda puterii inverse;

4. Metoda lui Leverrier;

5. Rezolvarea in MathCad;

6. Problema de rezolvat;

7. Concluzii.

1. Generalitati

Multimea valorilor proprii asociata unui anumit operator numita si spectrul operatorului este o multime numerica si ofera anumite informatii despre caracteristicile operatorului. In cazul matricelor, analiza spectrului este utila pentru caracterizarea convergentei si vitezei de convergenta pentru metodele iterative de rezolvare a sistemelor de ecuatii liniare sau pentru determinarea numarului de conditionare a acestora.

Multimea valorilor proprii = este determinata prin rezolvarea ecuatiei:

det(A-I) = 0      (1)

unde I reprezinta matricea unitate iar 0 matricea nula.

Determinantul det(A-I) poarta denumirea de polinom caracteristic si este un polinom de gradul n. Aceasta ecuatie poarta denumirea de ecuatie caracteristica avand solutia _n. Valorile proprii sunt numere reale sau complexe avand valori distincte sau multiple.

2. Metoda puterii directe

Metoda puterii directe se utilizeaza atunci cand este cautata numai valoarea proprie maxima, eventual cateva valori proprii cu valoari mari. Aceasta metoda poate fi aplicata numai in cazul matricelor diagonalizabile cu valori proprii distincte.

Fie valoarea proprie dominanta a matricei A, avand proprietatea:

| | >> |_i i = 2 ,,n (2)

Fie _i=1,N = un sistem de vectori proprii liniar independenti si normalizati (avand componenta maxima unitara). Acestia formeaza o baza a spatiului vectorial. Fie y Rⁿ un vector din spatiul real n-dimensional. Acesta poate fi reprezentat in functie de elementele bazei _i=1,N

y = c v + c v + + c_nvⁿ (3)

unde c , c , , c_n sunt coeficienti exprimati prin numere reale.

Sa construim sirul de vectori y , y² ,, y^k prin aplicarea recursiva a operatorului matriceal A, pornind cu vectorul initial y

y = Ay (4)

y = Ay = A y

..

y^k = Ay^k-1 = A^k-1y

Daca facem calculele, folosind reprezentarea explicita a matricii A, si dam factor comun (fortat) pe ^k desvoltarea vectorului y^k poate fi exprimata sub forma:

(5)

Daca valoarea proprie este dominanta, adica mult mai mare decat celelalte valori proprii, puterile de ordinul k ale rapoartelor valorilor proprii vor avea valori cu atat mai mici cu cat k este mai mare. Atunci termenii vectoriali continand puterile de ordinul k au module de valoari mici si pot fi inglobati intr-un vector de eroare de ordinul k, notat ^k Astfel vectorului y^k poate fi exprimat prin relatia:

y^k = [c v ^k (6)

Pentru o valoare suficient de mare a lui k termenul ^k poate fi neglijat, rezultand:

y^{k k} c v (7)

Analog, pentru vectorul de ordinul k+1 obtinem:

y^{k+ k+1} c v (8)

Se observa ca vectorii y^k si y^k+1 sunt multiplii ai aceluiasi vector v si deci au componentele proportionale. Rezulta ca daca facem raportul dintre componentele de ordinul i, pentru un i oarecare, a vectorului y^k+1 si vectorului y^k se obtine:

(9)

Deci valoarea proprie cea mai mare, a matricii A poate fi evaluata prin relatia:

(10)

3. Metoda puterii inverse

Metoda puterii inverse este utilizata pentru determinarea celei mai mici valori proprii a unei anumite matrici A. Este cunoscut faptul ca daca este o valoare proprie a matricei A, atunci 1/, inversa lui este valoare proprie inversei matricei A, A

Sa presupunem ca matricea A are valori proprii reale. Analog ca mai sus sa consideram un vector initial y si o baza de vectori proprii normati la valoare unitara. Apoi sa construim sirul de vectori y , y² ,, y^k prin aplicarea recursiva a operatorului matriceal A , pornind cu vectorul initial y

y = A y (11)

y = A y = (A y

..

y^k = A y^k-1 = (A ^k-1y

Daca dam factor comun (fortat) pe 1/_n^k desvoltarea vectorului y^k poate fi exprimata sub forma:

(12)

Daca valoarea proprie _n este cea mai mica valoare proprie a matricii A atunci 1/_n este cea mai mare valoare proprie a matricii A (valoare proprie dominanta). Rezulta ca termenii sumei de mai sus care contin pe _n au valori cu atat mai mici cu cat k are valoare mai mare. Acestia pot fi inglobati intr-un vector de eroare de ordinul k, notat ^k Astfel vectorului y^k poate fi exprimat prin relatia:

(13)

Pentru o valoare suficient de mare a lui k termenul ^k poate fi neglijat, rezultand:

(14)

Analog, pentru vectorul de ordinul k+1 obtinem:

(15)

Daca facem raportul dintre componentele de ordinul i, pentru un i oarecare, ale vectorului y^k+1 si vectorului y^k se obtine:

(16)

Astfel valoarea proprie cea mai mica, _n a matricii A poate fi evaluata prin relatia:

(17)

4. Metoda lui Leverrier

Cu ajutorul metodei lui Leverrier poate fi determinat pe o cale mai directa polinomul caracteristic al unei matrice A. Apoi prin rezolvarea acestuia pot fi calculate toate valorile proprii ale matricii.

Sa consideram ca polinomul caracteristic are gradul n, coeficientii c , c c_n si este reprezentat sub forma:

det(A-I) = ⁿ + c ^n-1 + + c_n-1 + c_n (18)

Sa consideram sumele:

s_k = ^{k k} _n^k pentru k = 1, 2, , n (19)

Se poate demonstra ca fiecare dintre sumele s_k sunt este egala cu urma matricei A^k (notata tr(A) dela cuvantul englez 'trace'), unde matricea A^k este egala cu matricea A ridicata la puterea k :

s_k = tr(A^k (20)

Urma unei matrice este data de suma elementelor diagonale ale matricii respective:

(21)

Rezulta ca daca notam cu a_ii ^k) elementele corespunzatoare ale matricei A^k , sumele s_k pot fi calculate cu relatia:

(22)

Se poate demonstra ca exita anumite relatii intre sumele s_k si coeficientii polinomului caracteristic (numite formulele lui Newton). Pentru toate valorile lui k, acestea sunt reprezentate de relatiile:

s_k + c s_k-1 + c s_k-2 + + c_k-2s + c_k-1s + kc_k pentru k = 1, 2, , n (23)

Rezulta ca utilizand relatiile lui Newton pot fi determinati coeficientii polinomului caracteristic prin relatiile recursive:

(24)

Valorile proprii ale matricei A vor fi determinate prin calculul radacinilor polinomului caracteristic avand coeficientii c , c c_n . Acasta se va efectua utilizand o anumita metoda numerica specifica rezolvarii ecuatiilor polinomiale. Mentionam ca prin aplicarea metodei lui Leverrier se pot determina toate valorile proprii corespunzatoare matricei A .

5. Rezolvarea in MathCad

Metoda puterii directe

In cadrul MathCad exista posibilitatea definirii sirurilor de vectori, indexate dupa o anumita variabila sir. Sirul de vectori este specificat prin indice superior plasat intre paranteze ascutite. Astfel daca consideram o variabila si k, definita in MathCad prin notatia: k := 0..N .

Daca consideram un vector initial y^<0> cu componente nenule, atunci prin aplicarea succesiva a matricei A poate fi construit sirul de vectori:

y^<k+1>:=Ay^<k> (25)

Daca afisam variabila y , aceasta se prezinta ca o matrice avand atatea linii cate componente are matricea A si N coloane, corespunzatoare numarului elementelor sirului de vectori construiti. Se observa ca pentru un numar k suficient de mare raportul dintre doua componente care corespund la doi pasi succesivi se conserva. Acesta reprezinta tocmai valoarea proprie maxima max :

(26)

Metoda puterii inverse urmareste acelasi procedeu, cu deosebirea ca este aplicata succesiv matricea A Rezulta un alt sir de vectori y :

y^<k+1>:=A y^<k> (27)

De data aceasta valoarea proprie minima min este aproximata insa data de inversul raportului componentelor corespunzatoare la doi pasi succesivi:

(28)

Metoda lui Leverrier pentru calculul coeficientilor polinomului caracteristic presupune evaluarea sumelor s_k si a relatiilor (24). Programul MathCad are posibilitatea calcularii directe a puterii unei matrice si a urmei acesteia. Rezulta:

s_k := tr(A^k (29)

Pentru calculul recursiv al coeficientilor c , c , , c_n utilizam valoarea de pornire pentru c = -s si relatia recursiva pentru k := 2..n si i := 1..n :

(30)

6. Problema de rezolvat

a) Calculul numeric al valorilor proprii ale unei matrice

Se considera matrice patrata de ordinul patru A si vectorul aproximatiei initiale Y^{<0> :}

(31)

Pentru aplicarea metodelor puterii directe si inverse se considera numarul maxim de iteratii:

N := 10 si variabila sir k := 0..N (32)

Astfel se pot scrie ecuatiile recursive pentru calculul vectorilor Y^<k> la pasi succesivi:

Metoda puterii directe: (33)

Metoda puterii inverse: (34)

Dupa realizarea calculelor pentru toate valorile lui k, simbolul Y (fara indice superior) va desmna in MathCad o matrice de dimensiune 4 x N+1 ale carei coloane reprezinta vectorii Y^<k> corespunzatori tuturor pasilor de iteratie.

Valorile proprii maxime si minime ale matricii A pot fi estimate apoi, utilizand vectorii Y^{<k> calculati} la pasi succesivi. Dupa un numar suficient de iteratii se observa ca vectorii Y^<k> si Y^<k+1> au componentele proportionale. Astfel ca valorile proprii pot fi estimate ca raportul a doua componente oarecare, de acelasi rang, a vectorilor Y^<k> calculati la pasi succesivi. Aplicand cele doua metode (utilizand componenta de ordin unu) rezulta:

Metoda puterii directe: (35)

Metoda puterii inverse: (36)

Daca sunt afisate cele doua valori rezulta:

_{max min} (37)

b) Determinarea coeficientilor polinomului caracteristic prin metoda lui Leverrier

Intreg spectrul unei matrice poate fi determinat daca sunt calculate radacinile polinomului caracteristic corespunzator. Acesta este definit de relatia:

P() = det(A - I) (38)

Calculul determinantului este un proces laborios, ineficient din punct de vedere numeric. Deaceea se prefera utilizarea unor metode alternative pentru determinarea coeficientilor polinomului caracteristic. Una dintre acestea este metoda lui Leverrier.

Sa consideram urmatoarea matrice patrata de ordinul patru:

(39)

Sa notam cu N numarul de linii ale matricii si sa consideram variabila sir k :

N := rows(A) k := 1..N (40)

Sa notam cu s_k urma matricii A ridicata la puterea k. Atunci s_k poate fi definit in MathCad:

s_k := tr(A^k (41)

Pentru a calcula coeficientilor polinomului caracteristic definim variabilele sir i si k astfel:

i := 1..N k := 2..N (42)

Pentru a aplica metoda lui Leverrier, se defineste c = -s si se utilizeaza ecuatia recursiva:

(43)

Dupa realizarea calculelor vectorul c_k va contine coeficientii polinomului caracteristic. In forma transpusa, rezulta:

(44)

In forma explicita polinomul caracteristic poate fi scris sub forma unei functii MathCad, notate prin P(x):

(45)

c) Determinarea tuturor valorilor proprii pe baza polinomului caracteristic

Pentru a putea aplica o metoda locala pentru aproximarea fiecarei radacini reale este necesara determinarea subintervalelor corespunzatoare. Aceasta se poate realiza prin trasarea graficului functiei q(x). In acest scop se alege intervalul total de variatie care sa contina toate radacinile, [a,b] = [-5,10] , pasul de variatie h si este definita variabila independenta discreta x_k

a := -5 b := 10 h := 0.1 x_k := a, a+h,..,b (46)

Rezulta graficul lui q(x) sub forma:

Se observa ca radacinile se afla in vecinatatea punctelor: -3, 0, 3, 9 .

Pentru estimarea precisa a radacinilor se poate utiliza instructiunea MathCad 'root'.

Fiecare radacina a polinomului caracteristic, determinat prin metoda lui Leverrier, trebuie sa corespunda cate unei valori proprii a matricei. Pentru a verifica acest lucru dupa fiecare utilizare a instructiunii 'root' calculam in punctul respectiv polinomul caracteristic conform definitiei matriceale P() = det(A - I). Pentru determinarea matricei diagonale D = I definim matricea unitate I , pentru care apoi redefinim termenii diagonali, indexati dupa variabila j, conform valorii proprii respective. Astfel:

j := 0..3 (47)

Procedura descrisa poate fi concretizata, utilizand notatiile limbajului MathCad, sub forma secventei de calcul prezentata mai jos. Eroarea de calcul este estimata prin evaluarea formei matriceale a polinomul caracteristic, date de determinantul |A - D

x := root(P(x),x)      D_j,j |A - D| = 1.424 10 (48)

x := root(P(x),x)      D_j,j |A - D| = -2.684 10 (49)

x := root(P(x),x)      D_j,j |A - D| = -1.129 10 (50)

x := root(P(x),x)      D_j,j |A - D| = 5.825 10 (51)

Se cere:

* Implementarea algoritmilor de rezolvare in limbaj MathCad;

* Determinarea numerica a valorilor proprii extreme;

* Parcurgerea etapelor de calcul, pentru toate valorile proprii;

* Analiza rezultatelor obtinute si a calitatii aproximatiei numerice.

7. Concluzii

Calculul valorilor proprii pentru o matrice este util pentru aprecierea bunei conditionari a unui sistem de ecuatii si pentru stabilirea proprietatilor de convergenta a unei metode iterative.

Anumite metode numerice permit calculul tuturor valorilor proprii (cazul metodei lui Leverrier), iar alte metode permit numai evaluarea valorilor proprii extreme. Acestea sunt totusi foarte utile in cazurile specificate la punctul (a).

In cazul metodei puterii directe si puterii inverse viteza de convergenta este cu atat mai mare cu cat valoarea proprie este mai puternic dominanta.