Universitatea “Politehnica” Bucureşti

Facultatea de Electronică, Telecomunicaţii şi Tehnologia Informaţiei

Tema 2 TOP

Metoda linara a gradientilor conjugati

Studentii: Paraschiv Radu

Vulpe Florian

Grupa: 443A

2012-2013

1)Introducere

Metodele de gradient conjugat au fost proiectate de Magnus Hestenes siEduard Stiefel in lucrarea Methods of conjugate gradients for solving linear systems,J. Research 1952 in care au prezentat un algoritm pentru rezolvarea sistemeloralgebrice liniare, cu matricea simetrica si pozitiv definita. In 1964, metoda a fostextinsa de Fletcher si Reeves la probleme de optimizare neliniara fara restrictii. Deatunci, 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, totusiacestia continua sa fie de un considerabil interes in particular datorita proprietatilorlor de convergenta si eficientei in rezolvarea problemelor de optimizare de maridimensiuni.

Metodele de gradient conjugat au ca si scop obtinerea minimului uneiforme patratice in n iteratii. Aceasta metoda necesita calculul derivatelorpartiale de ordinul intai si are convergenta superliniara. Spre deosebirea de altemetode similare, aceasta metoda nu necesita memorarea unei matrice.

Consideram un sistem liniar de ecuatii: Ax = b. Presupunem ca A este omatrice patratica, simetrica si pozitiv definita. Rezolvarea sistemelor de ecuatiiliniare folosind metode de optimizare

Metodele de optimizare pot fi aplicate cu succes pentru rezolvareasistemelor de ecuatii liniare, indeosebi pentru sisteme mari, atunci candmetodele directe nu mai sunt eficiente. Deoarece numarul de variabile estemare, ın astfel de situatii sunt preferate metodele de gradient conjugat.

Metodele directiilor conjugate sunt motivate de dorinta de a accelera viteza deconvergenta a metodelor clasice iterative pentru aceasta clasa de probleme.

Aceste metode sunt, de fapt, aplicabile si pentru probleme de optimizarenoncuadratice. Pentru astfel de probleme, in general, se termina procesul dupa unnumar finit de iteratii, dar, atunci cand sunt aplicate in mod corespunzator, auconvergenta atractiva si rata de convergenta convenabila.

2)Principiul de baza

Putem spune ca doi vectori u si v se numesc conjugati daca uTAv=0, unde Aeste o matrice de dimensiune nxn cunoscuta.

Definim functia θ = − strict convexa cu un x* solutie unica aproblemei min(θ(x)).

Alegem ca si punct initial x0=0 cu care incepem cautarea in spatiul functiei θ.Pentru a determina daca ne apropiem de solutia optima avem nevoie de un reziduu.

Primul pas pentru o functie f(x) x∈ ,este de a alege vectorul de cautare p1

astfel incat acesta sa fie negativul gradientului functiei f(x0). Prin urmare p1= b-Ax0,iar cel de-al doilea vector de cautare va fi conjugatul acestuia.

Notam cu rk=b-Axk reziduul in punctul k, si acesta reprezinta gradientul negatival functiei patratice in punctul xk.

Prin urmare, pasul urmator este calculat prin :

= +Iar directia catre urmatorul optim este data de:= +∝unde : =

3)Algoritmul

Pasul 1. Initializare. Selectam punctul initial x0 si calculam r0 = b−Ax0,p0=r0, k=0.

Pasul 2. Se testeaza un criteriu de oprire a iteratiilor. De exemplu daca reziduul| rk|≤ ε ,unde ε ˃ 0 este o toleranta suficeint de mica; daca inecuatia se verificaatunci stopatunci stop;

Pasul 3. Se calculeaza αk=rkTzk/(pk

TApk).

Pasul 4. Se actualizeaza variabilele si reziduul: xk+1=xk+ αkpk , rk+1=rk- αkApk.

Pasul 5. Se calculeaza: βk= rk+1Trk+1/ rkTrk si directiile pk+1= rk+1+ βkpk . Se

incrementeaza k si se reia algoritmul de la pasul 2.

4)Codul sursa

#include<stdio.h>#include<conio.h>#include<stdlib.h>#include<math.h>

int main(){double x[2],b[2],a[2][2];int i,j,k,iteratie;for(i=0;i<2;i++) {

x[i]=0.0;}//citirea datelorprintf("Citire vector de start : \n");for(i=0;i<2;i++){

printf("x[%d]:",i);scanf("%lf",&x[i]);

}printf("\nCitire matrice B : \n");for(i=0;i<2;i++){

printf("x[%d]:",i);scanf("%lf",&b[i]);

}printf("\nCitire matrice A : \n");for(i=0;i<2;i++){

for(j=0;j<2;j++){printf("x[%d][%d]:",i,j);scanf("%lf",&a[i][j]);

}}//initializari//r reziduu , d directie de cautaredouble r[2],d[2];double aux,aux1,rsold;for(i=0;i<2;i++){

aux=0.0;for(j=0;j<2;j++){

aux+=a[i][j]*x[j];}

r[i]=b[i]-aux;d[i]=r[i];

}rsold=0.0;for (i=0;i<2;i++) rsold+=r[i]*r[i];double Ap[2],alpha,rsnew;iteratie=0; alpha=0.0; rsnew=0.0;

//calcul propriu-zis

for(k=0;k<2;k++){printf("\n\n iteratie %d",k);for(i=0;i<2;i++){

aux=0.0;for(j=0;j<2;j++){

aux+=a[i][j]*d[j];}Ap[i]=aux;

}printf("\nmatricea ap");for(i=0;i<10;i++) printf("%f ",Ap[i]);aux1=0.0;for (i=0;i<2;i++) aux1+=d[i]*Ap[i];alpha=rsold/aux1;for(i=0;i<2;i++){

x[i]=x[i]+alpha*d[i];r[i]=r[i]-alpha*Ap[i];

}printf("\nmatricea x");for(i=0;i<2;i++) printf("%.9f ",x[i]);printf("\nmatricea r");for(i=0;i<2;i++) printf("%.9f ",r[i]);

for (i=0;i<2;i++) rsnew+=r[i]*r[i];printf("\n rsnew %f ",rsnew);printf("\n rsold %f ",rsold);if(sqrt(rsnew)<1e-10) k=11;for (i=0;i<2;i++){

d[i]=r[i]+(rsnew/rsold)*d[i];}iteratie++;rsold=rsnew;rsnew=0.0;

}

printf("\niteratii : %d",iteratie);printf("\n Optimul se afla la coordonatele :");for (i=0;i<2;i++) printf("\n%f",x[i]);return 1;

}

5)Exemplu de rulare

Pentru functia: = 2 + 1.5 + − − 2Rezultat practic

Reprezentare grafica

5)Exemplu de rulare

Pentru functia: = 2 + 1.5 + − − 2Rezultat practic

Reprezentare grafica

5)Exemplu de rulare

Pentru functia: = 2 + 1.5 + − − 2Rezultat practic

Reprezentare grafica

Pentru functia: = 0.5 + 2.5Rezultat practic

Reprezentare grafica

Pentru functia: = 0.5 + 2.5Rezultat practic

Reprezentare grafica

Pentru functia: = 0.5 + 2.5Rezultat practic

Reprezentare grafica

6)Concluzii

Cu exceptia situatiei in care solutia s-a obtinut in mai putin de n pasi gradientuleste intotdeauna nenul si liniar independent in raport cu directiileprecedente(gradientul este ortogonal pe subspatiul generat de d0, d1, ... dk-1).

Formula deosebit de simpla pentru generarea noii directii, facand metoda doarputin mai complicata decat metoda celei mai abrupte pante.

Procesul de cautare progreseaza satisfactor si uniform inspre solutie la fiecarepas deoarece directiile sunt bazate pe gradienti (spre deosebire de multe metode dedirectii conjugate cu directii generate arbitrar si in care progresul poate fi lent pana laultimii cativa pasi). Acest lucru nu este important pentru functii patratice ci pentrugeneralizarile la functii nepatratice.