Decizia este luată în format Word.
Metoda gradientului conjugat formează direcții de căutare care sunt mai potrivite geometriei funcției minimizate.
Definiția. Două n -dimensional vector x și y se numesc conjugate în raport cu matricea A (sau A-conjugat) dacă produsul interior (x, Au) = 0. Aici, A - simetrică matrice pozitiv definită de dimensiune n x n.
Diagrama algoritmului metodei gradientului conjugat
Pune k = 0.
1 Fie x 0 punctul inițial; .
d0 = -g0; k = 0.
Definiți x k +1 = x k + λk dk. unde
.
Apoi dk + 1 = -gk + 1 + βk dk,
,
βk se constată din condiția dk + 1 Adk = 0 (conjugat față de matricea A).
Sh. 3 Introduceți k = k + 1 → Sh. 2.
Criteriul pentru oprirea unei căutări unidimensionale de-a lungul fiecărei direcții dk este scris ca :.
Valorile sunt alese astfel încât direcția lui dk este A-conjugată cu toate direcțiile construite anterior.
Metoda Fletcher-Reeves
Strategia metodei Fletcher-Reeves este de a construi o secvență de puncte, k = 0, 1, 2. astfel încât f (x k + 1)
x k + 1 = x k -tk dk. k = 0, 1, 2, ...
dk = (X k) + bk-1 F (x k-1)
Mărimea pasului este aleasă dintre condiția minimă a funcției f (x) în raport cu t în direcția mișcării, adică, ca rezultat al rezolvării problemei de minimizare unidimensională:
f (x k -tk dk) → min (tk> 0)
În cazul unei funcții patratice f (x) = (x, Hx) + (b, x) + a unei direcții dk. dk-1 va fi H-conjugat; (dk, Hdk-1) = 0
În punctele secvenței, gradientele funcției f (x) sunt reciproc perpendiculare, adică (X, k), f (x k + 1), # 9661; f (x k)) = 0, k = 0, 1, 2 ...
Atunci când se minimizează funcțiile non-patrate, metoda Fletcher-Reeves nu este finită. Pentru funcțiile ne-patrate, se folosește următoarea modificare a metodei Fletcher-Reeves (metoda Polac-Ribiera) atunci când valoarea bk-1 se calculează după cum urmează:
Există set index I-: .. I =, adică metoda Polak-Ribiere implică utilizarea iterare mai abrupte coborâre cu gradient după fiecare n pași prin înlocuirea x cu 0 la x n + 1.
Construcția secvenței se termină la un punct pentru care | # 9661; f (x k) |<ε.
Semnificația geometrică a metodei de gradienți conjugați este după cum urmează. Din punctul inițial dat x 0, o coborâre în direcția d0 = (X 0) În punctul x 1, vectorul de gradient Deoarece x 1 este punctul minim al funcției în direcția d0. atunci f (x1) este ortogonal la vectorul d0. Apoi se caută vectorul d1. H-conjugat la d0. Mai mult, se caută un minim de funcție de-a lungul direcției d1 și așa mai departe.
Algoritm Fletcher-Reeves
Etapa inițială.
Setați x la 0. # 949;> 0.
Găsiți gradientul unei funcții într-un punct arbitrar
k = 0.
Etapa principală
Pasul 1. Calculați (Xk)
Pasul 2. Verificați executarea criteriului de stop | # 9661; f (x k) |<ε
a) dacă criteriul este îndeplinit, calculul este finalizat, x * = x k
b) dacă criteriul nu este îndeplinit, treceți la pasul 3 dacă k = 0, altfel la pasul 4.
Pasul 3. Determinați d0 = F (x 0)
Pasul 4. Determinați, sau în cazul unei funcții non-patrate
Pasul 5. Definiți dk = (X k) + bk-1 F (x k-1)
Pasul 6. Calculați mărimea treptei tk din condiția f (xk - tk dk) → min (tk> 0)
Pasul 7. Calculați x k + 1 = x k -kk dk
Pasul 8. Puneți k = k + 1 și mergeți la pasul 1.
Convergența metodei
Teorema 1. Dacă funcția patratică f (x) = (x, Hx) + (b, x) + a cu o matrice non-negativă definită H atinge valoarea minimă pe R n. atunci metoda Fletcher-Reeves asigură că punctul minim se găsește nu mai mult de n pași.
Teorema 2. Fie funcția f (x) diferențiată și limitată mai jos de R m. și gradientul său satisface condiția Lipschitz. Apoi, pentru un punct inițial arbitrar pentru metoda Polac-Ribiera, avem
Teorema 2 garantează convergența secvenței cu punctul staționar x *. unde (X *) = 0. Prin urmare, punctul x * găsit necesită investigații suplimentare pentru clasificarea sa. Metoda Polac-Ribiera garantează că secvența converge la un punct minim doar pentru funcții puternic convexe.
O estimare a ratei de convergență se obține numai pentru funcțiile puternic convexe. în acest caz, secvența converge la punctul minim al funcției f (x) cu viteza: | x k + n - x * | ≤ C | x k - x * |, k =
Un exemplu. Găsiți funcția minimă prin metoda gradientelor conjugate: f (X) = 2x1 2 + 2x2 2 + 2x1 x2 + 20x1 + 10x2 +10.
Soluția. Ca direcție a căutării, selectăm vectorul de gradient la punctul curent: