Metode
numerice - Aplicatii
Lucrarea
14.
Metode partiale pentru calculul valorilor si vectorilor proprii: metoda puterii
directe, metoda puterii inverse, metoda puterii inverse cu decalaj spectral,
metoda iterativa inversa cu coeficient Rayleigh
Tema A: Metoda puterii directe
Tema
B: Metoda puterii inverse
Tema
C: Metoda puterii inverse cu decalaj spectral
Tema
D: Metoda iterativa inversa cu coeficient Rayleigh
Daca
unui vector n – dimensional x i se aplica o transformare definita
de matricea A de dimensiune n × n,
se obtine vectorul y=A×x. Nu întotdeauna
între vectorii x si y astfel definiti exista o corelatie
bine precizata, adica ei pot avea orientari oarecare. Exista însa anumiti vectori x pe care
matricea A îi transforma în multipli
ai lor însisi. Pentru o matrice reala, patrata A, de dimensiuni n× n, exista, în general, cel putin n vectori x pe care
transformarea liniara A îi lasa
invarianti ca directie, adica îi transforma în vectori proportionali cu ei
însisi:
Factorul
de proportionalitate l se numeste valoare proprie a matricei A, iar vectorul x – vector propriu
asociat valorii proprii l.
Pentru determinarea valorilor proprii ale
matricei A, relatia de definitie
poate fi scrisa în forma echivalenta:
unde In este matricea unitate de
rang n. S-a obtinut astfel un sistem
omogen de ecuatii liniare care admite o solutie diferita de solutia banala
– deci vectori proprii nenuli – daca determinantul sau se anuleaza:
care reprezinta ecuatia caracteristica a matricei A. Scalarii l care verifica
ultima relatie sunt tocmai valorile proprii ale acestei matrice. Prin
dezvoltarea determinantului dupa regulile cunoscute se obtine un polinom de
grad n în l, cu coeficienti
reali, numit polinom caracteristic:
ale carui radacini sunt valorile proprii.
Metodele numerice directe determina valorile proprii
prin rezolvarea ecuatiei caracteristice. Se prezinta in
continuare metoda puterii directe, metoda puterii inverse si varianta
acesteia cu deplasarea originii.
Acestea se mai numesc metode
partiale, deoarece determina numai anumite valori si vectori proprii ale
unei matrice.
Tema A: Metoda puterii directe
Vom
considera problema initiala A×x=l× x pentru care se
admite ca matricea A este
nedefectiva, adica are exact n
vectori proprii liniar independenti, care formeaza o baza în spatiul real n-dimensional. De asemenea, se admite ca
sistemul celor n vectori proprii x1, x2,…,
xn este un sistem
normalizat dupa norma infinita, deci componenta maxima a fiecarui vector este
egala cu unitatea. Metoda puterii directe, denumita uneori prescurtat metoda puterii, determina valoarea proprie maxima în
modul a matricei A si vectorul
propriu asociat acesteia.. În acest context, vom adopta ipoteza suplimentara conform careia
matricea A are o valoare proprie
dominanta si aceasta este prima :
În aceste conditii, orice vector y din spatiul n-dimensional se poate exprima ca o combinatie liniara a vectorilor
proprii:
Dupa cum spune si numele ei, metoda
puterii directe apeleaza la construirea unui sir de vectori normalizati, pe baza unei relatii de
recurenta dupa puterile matricei A. Astfel, pornind de la y(0) = y (cu =1),
se construieste sirul de vectori y(0),
y(1),…, y(k) :
k=0,1, ...
unde y(k+1)
se obtine prin normalizarea lui y’(k+1), iar . Daca se dau succesiv lui k valorile 0, 1, 2,
…., se obtine:
sau relatia de
recurenta:
,k=1,2,
...
Deoarece r(1), r(2), ...
, r(k) sunt marimi
scalare de normalizare, rezulta ca vectorul Ak×y(0) este coliniar cu y(k).
Pe de alta parte, avand în vedere descompunerea vectorului y(0) dupa baza x1,
x2,…., xn
si proprietatea A×xi=li × xi, se poate scrie:
sau, în general:
k=1,2, ...
Daca
se tine seama de caracterul dominant al valorii proprii l1 si se izoleaza
termenul de rang i=1 din ultima
relatie:
,k=1,2, ...
se verifica imediat
ca, pentru k ® ¥, termenii sumei
din se pot considera oricat de mici, iar
prin neglijarea lor rezulta:
,k=1,2, ...
Se poate afirma ca
la limita vectorul y(k)
tinde spre vectorul propriu x1.
Un rationament simplu arata ca la
limita (k ®
¥) parametrul de
normalizare r(k+1) tinde chiar catre
valoarea proprie l1 cautata.
Într-adevar, pentru k suficient de
mare, diferenta y(k+1)-y(k) tinde
spre 0 si se poate scrie:
Daca în aceasta relatie se tine seama si de expresia , se obtine:
adica, la limita r(k+1) este valoarea proprie
asociata vectorului propriu y(k). Deoarece însa, asa cum am aratat mai sus,
vectorul y(k)
tinde catre vectorul propriu x1, înseamna ca parametrul
de normalizare r(k+1) va aproxima valoarea proprie dominanta l1.
Convergenta metodei
puterii directe, depinde esential de viteza cu care rapoartele (li/l1)k tind catre 0. În practica,
metoda puterii directe se dovedeste eficienta mai ales în cazul matricelor A caracterizate
de o valoare proprie net superioara în valoare absoluta celorlalte.
Algoritmul 1 – Metoda puterii directe
1.
Definirea
matricei A=[aij], i,j=1,...,n si a preciziei Eps.
2.
Aproximatia initiala a vectorului propriu y1 ¬ [1 0 ... 0]T
si initializarea parametrului de normalizare r(1)¬ 1.
3.
Proces iterativ pentru determinarea perechii vector
propriu-valoare proprie dominanta (x1,l1):
3.1.
Initializarea contorului de iteratii: k¬ 0;
3.2.
Trecerea la o noua iteratie: k ¬ k+1;
3.3.
Calculul noii aproximatii: y'(k+1) ¬ A×y(k)
3.4.
Calculul parametrului de normalizare: r(k+1)¬
3.5.
Normalizarea noii aproximatii:
3.6.
Conditia de oprire: daca £ Eps
procesul iterativ se întrerupe si se trece la pasul
4. În caz contrar se revine la pasul 3.2.
4.
Valoarea proprie dominanta a matricei A este l1 ¬ r(k+1), iar vectorul propriu
asociat este x1 ¬ y(k+1).
Tema B: Metoda puterii inverse
Una dintre
proprietatile valorilor si vectorilor proprii afirma ca daca l este o valoare
proprie a matricei A nesingulare, atunci 1/l este valoarea
proprie a inversei A-1, iar cele doua matrice au acelasi sistem de vectori proprii. În contextul acestei
proprietati, daca l este valoarea
proprie a lui A, minima în modul, 1/l va reprezenta valoarea
proprie dominanta a inversei A-1.
Prin urmare, daca se aplica metoda puterii directe matricei A-1, se determina de fapt valoarea proprie minima în
modul a matricei A. Acest procedeu
poarta numele de metoda puterii inverse.
Se admite ca vectorii proprii ai
matricelor A si A-1 sunt liniar independenti si formeaza o baza în spatiul real n-dimensional. Orice vector y poate fi exprimat ca o combinatie
liniara a vectorilor proprii:
De aceasta data, se
face ipoteza conform careia valoarea proprie minima în modul a matricei A este ultima:
Metoda
puterii inverse construieste un sir de vectori y(0), y(1),...,y(k) pe baza relatiei de
recurenta:
k=0,1, ...
Printr-un
rationament analog celui prezentat în paragraful anterior, se poate arata ca
pentru valori suficient de mari ale lui k (k ® ¥), vectorul y(k) tinde catre
vectorul propriu xn, iar parametrul de normalizare r(k+1) tinde catre
inversa valorii proprii ln.
Algoritmul asociat acestei metode este
prezentat în continuare.. Mai întai
, inversarea matricei a se face printr-o procedura de factorizare, iar in continuare, cu inversa A-1 se calculeaza valoarea proprie si vectorul propriu
dorite.
Algoritmul
2 – Metoda puterii inverse
1.
Definirea matricei A =[ a
ij ], i,j=1,...,n
si a preciziei Eps
2. Aproximatia initiala a vectorului propriu y1 ¬ [1 0 ... 0]T si initializarea parametrului de normalizare r(1)¬ 1.
3. Inversarea matricei A: A-1.
4. Proces iterativ pentru determinarea perechii vector propriu-valoare proprie dominanta a inversei A-1:
4.1.
Initializarea contorului de iteratii: k¬ 0;
4.2.
Trecerea la o noua iteratie: k ¬ k+1;
4.3.
Calculul noii aproximatii: y'(k+1) ¬ A-1×y(k)
4.4.
Calculul parametrului de normalizare: r(k+1)¬
4.5.
Normalizarea noii aproximatii:
4.6.
Conditia de oprire: daca £ Eps procesul iterativ
se întrerupe si se trece la pasul 5. În caz contrar se revine la pasul 4.2.
5.
Valoarea proprie minima în modul a matricei A este ln ¬ 1/r(k+1), iar vectorul
propriu asociat este xn ¬ y(k+1).
Tema C: Metoda puterii inverse cu decalaj spectral
Un
procedeu mult mai eficient de calcul al tuturor valorilor proprii ale unei matrice
folosind metoda puterii inverse implementeaza Algoritmul 2 nu matricei A, ci unei matrice decalate
A-q×In unde q
este un scalar ce realizeaza translarea originii. Metoda care rezulta poarta
numele de metoda puterii inverse cu
deplasarea originii sau metoda
iterativa inversa cu decalaj spectral. Algoritmul de aplicare este
asemanator cu cel al metodei puterii inverse, însa de aceasta data parametrul
de normalizare r(k+1) tinde catre
marimea 1/(lq-q), unde
lq este valoarea
proprie a matricei A cea mai
apropiata de scalarul q.
Prin urmare, localizarea cu suficienta
precizie a valorilor proprii si aplicarea metodei puterii inverse cu decalaj
spectral permit calculul tuturor valorilor proprii, fara a
impune nici o restrictie asupra ordinii în care se calculeaza acestea. De altfel, majoritatea lucrarilor de
specialitate recomanda aceasta metoda ca pe una dintre cele mai puternice
tehnici de calcul a valorilor si vectorilor proprii, în special în cazul unor
matrice de dimensiuni nu prea mari.
Singurul dezavantaj al metodei
iterative inverse cu decalaj spectral consta în necesitatea redefinirii
matricei decalate A-q×In si recalcularii
inversei sale pentru fiecare valoare proprie ce se
determina. O alta particularitate a acestei metode este asa-numitul paradox al iteratiei inverse cu decalaj spectral,
conform caruia convergenta metodei este cu atat mai lenta cu cat decalajul
spectral q este mai aproape de
valoarea proprie cautata l. Într-adevar, pornind de la formula problemei
decalate:
(A - q×In) × x = (l - q) × x
se observa ca, la
limita, cand q ® l, relatia conduce la un sistem omogen de ecuatii
liniare, pentru care existenta unei solutii diferita de solutia banala impune
singularitatea matricei A-q×In. Prin urmare,
neexistand inversa (A-q×In)-1,
nici metoda puterii inverse nu poate fi aplicata.
Tema D: Metoda
iterativa inversa cu coeficient Rayleigh
Aplicarea cu succes a metodei
iterative cu decalaj spectral presupune o initializare cat mai rationala a
decalajului q, adica a aproximatiei initiale pentru valoarea proprie cautata. O
asemenea initializare poate folosi catul
Rayleigh definit pentru un vector x în raport cu o matrice A:
unde parantezele
unghiulare denota produsul scalar a doi vectori. De ce o asemenea initializare ? Pentru a raspunde la aceasta întrebare, se
considera formularea initiala a problemei
(A×x=l×x), care se înmulteste la stanga cu xT si se extrage apoi expresia valorii proprii:
Comparand relatiile se
observa imediat ca, atunci cand x este un vector propriu al matricei A, catul Rayleigh asociat coincide cu
valoarea proprie corespunzatoare. Prin urmare, utilizarea
expresiilor anterioare înlocuieste stabilirea aproximatiei initiale a valorii
proprii l cu cea a vectorului
propriu x asociat acesteia.
În loc sa se "ghiceasca" o singura valoare, adica l, se determina n
valori, adica cele n componente ale
vectorului propriu x, pe baza stationaritatii catului Rayleigh în vecinatatea vectorului propriu cautat.
Aceasta proprietate se traduce prin variatii "relativ slabe" ale
catului Rayleigh la variatii "relativ însemnate" ale vectorului x.
Prin urmare, pornind de la o aproximatie "grosiera" a
vectorului propriu x, catul Rayleigh
reprezinta , în general, o aproximatie
"excelenta" pentru valoarea proprie asociata. Acesta este de fapt raspunsul la paradoxul iteratiei inverse cu
decalaj spectral.
Algoritmul
3 – Metoda iterativa
inversa cu coeficient Rayleigh
1.
Definirea matricei A=[aij],
i,j=1,...,n si a preciziei Eps.
2.
Aproximatia initiala a vectorului propriu x1 si normalizarea acesteia.
3.
Calculul catului Rayleigh asociat aproximatiei
initiale:
R1 ¬
4.
Initializarea procesului iterativ: k ¬ 0.
5.
Aplicarea metodei iterative inverse cu decalaj
spectral:
5.1.
Trecerea la o noua iteratie: k ¬ k+1;
5.2.
Aplicarea decalajului spectral matricei A folosind catul Rayleigh:
As ¬ A - Rk × In.
5.3.
Calculul inversei matricei decalate As-1.
5.4.
Calculul noii aproximatii a vectorului propriu:
xk+1 ¬ As-1 × xk
5.5.
Normalizarea noii aproximatii:
5.6.
Calculul catului Rayleigh pentru noua aproximatie:
Rk+1 ¬
5.7.
Criteriul de oprire: daca çRk+1
- Rkú £ Eps sau k=Nmax procesul iterativ se întrerupe si
se trece la pasul 6. În caz contrar se revine la pasul 5.1.
6. Perechea valoare proprie-vector propriu cautata este (l,x) º ( Rk+1,xk+1).
Se
poate arata ca, daca aproximatia initiala x1
nu este ortogonala pe vectorul propriu cautat x, utilizarea catului Rayleigh ca aproximatie a valorii proprii l asigura o
convergenta patratica, adica úçxk+1
- xúç £ d ×úçxk+1
- xúç2 , unde d este un scalar
strict pozitiv. Mai mult chiar, daca matricea A este simetrica, procesul iterativ se caracterizeaza
printr-o convergenta cubica. Aceste proprietati excelente de convergenta sunt
însa compensate în buna masura de efortul marit de calcul determinat de
necesitatea recalcularii la fiecare iteratie a
inversei matricei decalate As. Aceasta reprezinta
o piedica serioasa în calea utilizarii pe scara larga a metodei iterative
inverse cu decalaj spectral.