1. Notiuni teoretice

Fiind date n perechi de valori (x_i, y_ei), cu ajutorul algoritmului Hooke-Jeeves se realizeaza determinarea unei functii de regresie y(x) astfel incat sa se minimizeze suma patratelor diferentelor dintre valorile initiale y_ei si valorile y_i ale functiei de regresie in puctele x_i:

Algoritmul este folosit cu precadere atunci cand nu se poate aplica metoda celor mai mici patrate datorita faptului ca sistemul de ecuatii obtinut prin egalarea cu zero a derivatelor partiale nu este liniar si nici nu poate fi liniarizat prin logaritmare.

Desfasurarea algoritmului Hooke-Jeeves poate fi comparata cu deplasarea unui 'vector de cautare', intr-un spatiu k-dimensional, pe directia pe care este minima valoarea expresiei

Printre datele initiale ale algoritmului trebuie sa se afle o estimare a formei functiei de regresie y(x), aceasta fiind caracterizata prin parametrii c_j, j = 1...k ale caror valori vor fi modificate de la o iteratie la alta in scopul obtinerii expresiei optime a functiei y(x).

Utilizarea algoritmului presupune de asemenea furnizarea ca date initiale a urmatoarelor valori:

Dc : valoarea initiala a incrementului cu care vor fi modificati parametrii c_j;

e : limita inferioara a valorii sumei H(x) la care va avea loc oprirea algoritmului;

e : limita inferioara a valorii incrementului Dc, la care va avea loc oprirea algoritmului.

In prima iteratie, atat originea cat si varful vectorului de cautare se afla in punctul ale carui coordonate sunt reprezentate de estimatiile initiale c_j, j = 1...k. Se noteaza cu b_j, j = 1...k, coordonatele originii si cu v_j, j = 1...k, coordonatele varfului vectorului de cautare. Evident, la prima iteratie (pasul 0):

si se calculeaza valorile

Tot la prima iteratie, se considera ca directia de cautare este paralela cu prima axa de coordonate a spatiului k-dimensional (d=

Pasul 1: Se deplaseaza varful vectorului de cautare, cu distanta Dc, in sensul negativ al directiei de cautare:

si se recalculeaza valoarea H(v) in noua pozitie:

Daca nu este indeplinita conditia

se trece la pasul 2, daca da, se recalculeaza valoarea V = H(v) si se trece la pasul 4.

Pasul 2: Se efectueaza o deplasare a varfului vectorului de cautare, cu aceeasi marime, in sensul pozitiv al directiei de cautare:

si se recalculeaza

Daca nici in aceasta noua pozitie a varfului vectorului de cautare nu este indeplinita conditia

se trece la pasul 3, daca da, se recalculeaza valoarea V = H(v) si se trece la pasul 4.

Pasul 3: Se revine la punctul de pornire:

Pasul 4: Se defineste drept directie de cautare urmatoarea dimensiune a spatiului k-dimensional:

Daca s-a depasit numarul de dimensiuni al spatiului de cautare:

se trece la pasul 5, daca nu, se revine la pasul 1.

Pasul 5: Daca valoarea functiei H este mai mica in varful v al vectorului de cautare decat in baza b a acestuia:

se trece la pasul 6, daca nu, se trece la pasul 7.

Pasul 6: Daca valoarea V este inferioara limitei e reprezentand precizia necesara pentru calculul sumei H, rezulta ca valorile

sunt valorile optime cautate ale coeficientilor functiei de regresie y(x), iar algoritmul se opreste.

Daca nu este indeplinita conditia V e , atunci vectorul de cautare este translatat pe suportul sau, astfel incat baza sa ajunga in locul varfului:

si se revine la pasul 0.

Pasul 7: Se retrage varful vectorului de cautare in baza acestuia:

si se injumatateste valoarea incrementului de cautare:

Daca noua valoare Dc este mai mica decat limita de precizie a cautarii e , se considera ca valorile (c_j = b_j), j=1...k sunt valorile optime cautate ale coeficientilor functiei de regresie y(x), iar algoritmul se opreste. Daca nu este indeplinita conditia

se revine la pasul 0.

Pentru o mai buna intelegere a algoritmului, organigrama acestuia este prezentata in figura A.3.1.

2. Exemplu de calcul

Pentru datele din tabelul A.3.1, se doreste determinarea coeficientilor unei functii de regresie de forma

Tabelul A.3.1

Pornind de la o estimatie initiala a coeficientilor

si de la o valoare a incrementului

in tabelul A.3.2 pot fi urmarite valorile calculate pe parcursul iteratiilor succesive, pana la realizarea conditiei de precizie

In iteratia 2 poate fi urmarita efectuarea pasului 1 pe prima directie de cautare, in sens negativ (deplasarea din v₁ = 3 in v₁ = 2,9), iar in iteratia 3 efectuarea aceluiasi pas pe cea de-a doua directie, dar in sens pozitiv (deplasarea din v₂ = 3 in v₂ = 3,1). Aceleasi operatii au fost efectuate si in perechiile de iteratii 5-6, 8-9, 11-12 etc.

Figura A.3.1: Organigrama algoritmului Hooke - Jeeves

In iteratia 4 poate fi urmarita deplasarea bazei vectorului de cautare in punctul (2,9; 3,1) si a varfului acestuia in punctul (2,8; 3,2), conform pasului 6 al algoritmului. Operatii analoage sunt efectuate si in iteratiile 7, 10, 13 etc.

In iteratia 24, deoarece valorile V = H(v) calculate in iteratiile 21, 22 si 23 au fost mai mici decat valoarea B = H(b), marimea incrementului de cautare a fost injumatatita (pasul 7).

Tabelul A.3.2