f (x) = a + (x, b) + 1 (x, H x). (10)
cu o matrice pozitivă definită n · n. Se pare că funcția patratică (10) poate fi minimizată prin metoda direcțiilor conjugate în nu mai mult de n trepte.
Pentru a utiliza această metodă de minimizare a funcției patratice (10), trebuie să cunoaștem direcțiile n - conjugate reciproc S0. S 1, ..., S n-1. Eficacitatea acestor domenii este o problemă independentă. Există multe direcții conjugate reciproc S0. S 1, ..., S n-1 și modalități de construcție a acestora. Metoda de gradienți Fletcher-Reeves conjugat este descrisă mai jos, în care alegerea direcțiilor conjugate H este realizată împreună cu minimizarea unidimensională a f (x) prin # 945; ..
1.2.2 Metoda Fletcher-Reeves.
Această metodă utilizează o secvență de direcții de căutare, fiecare dintre acestea fiind o combinație liniară a anti-agentului la punctul curent și direcția precedentă de coborâre. Metoda este transformată într-o funcție obiectivă triunghiulară
f (x) = a + (x, b) + 1 (x, H x).
Atunci când se minimizează prin metoda Fletcher-Reeves, vectorii Sk sunt calculați din formule
Valorile # 946; k-1 sunt alese astfel încât direcțiile S k. Sk-1 au fost H-conjugat.
Punctul x k-1 este determinat ca rezultat al minimizării funcției f (x) în direcția S k. ieșind din punctul x k. și anume
unde # 945; k oferă un minim de # 945; k al funcției f (x k. # 945; · S k).
Astfel, procedura propusă pentru minimizarea funcției f (x) este după cum urmează. La un anumit punct x0, se calculează antigraful
S0 = - f '(x 0). Se efectuează o minimizare unidimensională în această direcție și se determină punctul x 1. La punctul x 1, antigradientul -f '(x 1) este calculat din nou. Deoarece acest punct oferă funcția minimă f (x) de-a lungul direcției S0 = - f '(x 0), vectorul f' (x 1) este ortogonal la f '(x 0). Apoi, în conformitate cu valoarea cunoscută f '(x1), conform formulei (11), se calculează vectorul S1. # 946; 0 va fi H-conjugat la S 0. Apoi, vom căuta minimul funcției f (x) de-a lungul direcției S 1, și așa mai departe.
Pentru k = 0, introducem aproximația inițială x0. Calculul antigradientului S0 = - f '(x0).
Soluție minimizare dimensională a unei funcții f (xk + a · Sk), prin care a determinat valoarea etapa ak și punctul xk + 1 = xk + ak · Sk.
Dacă f '(xk + 1) = 0, atunci xk + 1 este soluția problemei. În caz contrar, definim o nouă direcție de căutare: Sk + 1 din relație. Sk + 1 = - f '(xk + 1) + · Sk Apoi r = r + 1 și mergeți la pasul 2.
Aceasta este forma finală a algoritmului Fletcher-Reeves. Așa cum am menționat mai devreme, el va găsi minimul funcției patrate în nu mai mult de n pași.
1.2.3 Minimizarea funcției obiectiv non-patrate.
Metoda Fletcher-Reeves poate fi folosită pentru a minimiza funcțiile ne-patrate. Este o metodă de ordinul întâi și, în același timp, rata convergenței sale este patratică. Desigur, dacă funcția obiectiv nu este patratică, metoda nu va mai fi finită. Prin urmare, după iterația (n + 1), procedura se repetă cu x0 înlocuită cu xn + 1. și numărătoarea se termină atunci când || f '(xk + 1) || £ # 949; unde # 949; Este un număr dat. Atunci când se minimizează funcțiile non-patrate, se aplică de obicei următoarea modificare a metodei Fletcher-Reeves.
Schema algoritmului pentru funcțiile obiective non-patrate.
Pentru k = 0, aproximația inițială x0 și condițiile de oprire # 949; 3. Calculul antigradientului S0 = - f '(x0).
Soluție minimizare dimensională a unei funcții f (xk + a · Sk), prin care a determinat valoarea etapa ak și punctul xk + 1 = xk + ak · Sk.