Calcul Paralel - Metoda de Gradient Conjugat

Extras din referat Cum descarc?

Introducere
Metodele de optimizare sunt in general metode de descrestere, ce determina minimul unei functii U de n variabile reale care se numeste functie scop sau functie obiectiv. De aici si denumirea lor de metode de minimizare a functiilor de mai multe variabile. Evident, problema gasirii maximului revine la minimizarea functiei cu semn schimbat. Metodele de descrestere au convergenta globala, adica permit gasirea solutiei chiar daca punctul de plecare este indepartat de solutie.
Metodele de optimizare au un domeniu de aplicabilitate foarte larg. Pe de o parte, majoritatea fenomenelor naturii sau economice reprezinta compromisuri intre cauze contradictorii, si ca atare multe din problemele ingineriei, economiei, matematicii, statisticii, medicinei, dar mai cu seama procesele decizionale se pot formula ca probleme de optimizare. Pe de alta parte, majoritatea metodelor numerice pot fi reformulate ca probleme de optimizare. Aceste reformulari duc uneori la obtinerea unor metode performante, cum ar fi cele pentru rezolvarea sistemelor de ecuatii liniare, si cele pentru rezolvarea sistemelor de ecuatii neliniare 
Metodele de gradient conjugat reprezinta o contributie importanta in panoplia metodelor de optimizare fara restrictii de mari dimensiuni. Algoritmii asociati acestor metode sunt caracterizati de cerinte modeste de memorie si au proprietati foarte bune de convergenta globala. Popularitatea lor este datorata in parte simplitatii expresiei lor algebrice, implementarii foarte rapide si usoare in programe de calcul, precum si eficientei lor in rezolvarea problemelor cu un numar mare de variabile. 
Metodele de gradient conjugat au fost proiectate de Magnus Hestenes (1906-1991) si Eduard Stiefel (1909-1978) in lucrarea Methods of conjugate gradients for solving linear systems, J. Research Nat. Bur. Standards Sec. B. 48, 409-436 (1952) in care au prezentat un algoritm pentru rezolvarea sistemelor algebrice liniare, cu matricea simetrica si pozitiv definita. In 1964, metoda a fost extinsa de Fletcher si Reeves la probleme de optimizare neliniara fara restrictii. De atunci, un numar foarte mare de algoritmi de gradient conjugat au fost elaborati. Chiar daca algoritmii de gradient conjugat au peste 50 de ani de existenta, totusi acestia continua sa fie de un considerabil interes in particular datorita proprietatilor lor de convergenta si eficientei in rezolvarea problemelor de optimizare de mari dimensiuni. 
Metodele de gradient conjugat nu se deosebesc esential de metodele cvasi-Newton din punct de vedere al scopului, si anume obtinerea minimului unei forme patratice in n iteratii. Ambele clase de metode necesita calculul derivatelor partiale de ordinul intai si au aceeasi convergenta superliniara. Deosebirea esentiala consta in faptul ca metodele de gradient conjugat nu necesita memorarea unei matrice.
Consideratii teoretice
Metodele de gradient. 
Aceste metode sunt tipic de ordinul I si sunt caracterizate prin alegerea in fiecare punct curent vk a unei directii de deplasare dk opusa gradientului local:
dk = -gk (1)
Dezvoltand in serie Taylor functia in vecinatatea punctului vk si retinand doar termenii de ordinul intai, se obtine:
(2)
Insa,
(3)
egalitatea avand loc numai in cazul (1). Prin urmare, pentru orice pas sk >0 alegerea directiei de cautare conform relatiei (1) asigura local descresterea maxima posibila a functiei obiectiv f.
Algoritmul de calcul al punctului de minim prin metoda gradientului este prezentat in cele ce urmeaza:
0. Se alege un punct initial astfel incat multimea 
sa fie marginita.
1. Se initializeaza k = 0.
2. Se calculeaza gk = f v (vk ) .
Daca || g k ||= 0 , atunci si algoritmul este oprit.
Altfel, se alege directia dk = -gk si se trece la pasul 3.
3. Se determina pasul sk .
4. Se calculeaza vk+1 = vk + sk dk , se actualizeaza k prin inlocuirea lui k cu k+1 si se revine la pasul 2.


Fisiere in arhiva (1):

  • Calcul Paralel - Metoda de Gradient Conjugat.doc

Imagini din acest proiect Cum descarc?

Promoție: 1+1 gratis

După plată vei primi prin email un cod de download pentru a descărca gratis oricare alt referat de pe site.Vezi detalii.


Descarcă aceast referat cu doar 4 € (1+1 gratis)

Simplu și rapid în doar 2 pași: completezi adresa de email și plătești. După descărcarea primului referat vei primi prin email un alt cod pentru a descărca orice alt referat.

1. Numele, Prenumele si adresa de email:

Pe adresa de email specificata vei primi link-ul de descarcare, nr. comenzii si factura (la plata cu cardul). Daca nu gasesti email-ul, verifica si directoarele spam, junk sau toate mesajele.

2. Alege modalitatea de plata preferata:


* La pretul afisat se adauga 19% TVA, platibil in momentul achitarii abonamentului / incarcarii cartelei.

Hopa sus!