Konjugált gradiens módszer Online
A határozat Word formátumban.
A konjugált gradiens módszer generál egy keresési irányban nagyobb mértékben felel meg a funkciót, hogy minimalizált geometria.
Definíció. Két n dimenziós vektort x és y nevezzük konjugátum képest az A mátrix (vagy A-val konjugált), ha a belső terméket (x, Au) = 0. Itt, A - szimmetrikus pozitív definit méretű mátrix N x N-.
Rajz módszert konjugátum gradiensek
Put k = 0.
S. Legyen x 1 0 - kiindulási pont; .
d0 = -g0; k = 0.
Sh 2 Határozzuk meg x k + 1 = xk + λk dk. ahol
.
Ezután dk + 1 = -gk + 1 + βk dk,
,
βk a feltételt dk + 1 ADK = 0 (viszonyítva konjugátum A) mátrixban.
Put 3 Sh k = k + 1 → 2 Sh.
Criterion dimenziós keresés megáll mentén az egyes irányok dk írhatjuk :.
Az értékeket úgy választjuk meg, hogy az az irány a-DK társult valamennyi korábban megszerkesztett irányban.
Módszer Fletcher-Reeves
Módszer Fletcher-Reeves stratégia az, hogy össze egy pontsorozat, k = 0, 1, 2, úgy, hogy f (x k +1)
xk + 1 = xk -tk dk. k = 0, 1, 2, ...
dk = # 9661; f (x k) + bk-1 # 9661; f (x k-1)
A lépés érték van kiválasztva minimalizálásával az f (x) T a menetirányban, azaz a probléma megoldásának dimenziós minimalizálás ..:
f (x k -tk dk) → min (tk> 0)
Abban az esetben, egy másodfokú f (x) = (X, Hx) + (b, x) + egy irányba dk. dk-1 H-konjugátum, azaz (Dk. Hdk-1) = 0
Ezen a ponton a szekvenciája gradiensek f (x) kölcsönösen merőleges, azaz a (# 9661; f (x k +1), # 9661; f (x k)) = 0, k = 0, 1, 2 ...
Miközben minimálisra csökkenti a nem kvadratikus függvények Fletcher-Reeves módszer nem véges. A nem-másodfokú függvény a következő módosított módszerével Fletcher-Reeves (Polak-Ribiere módszer), ahol bk-1, az érték a következőképpen számítjuk ki:
Ott I- index halmaz: .. I =, azaz a Polak-Ribiere módszer használatával jár iteráció legmeredekebb gradiens csökkenési után minden n lépéseket helyett x 0 és x n + 1.
Építőipari folyamat véget ér a pont, amelyre | # 9661; f (x k) |<ε.
A geometriai jelentését konjugált gradiens módszer a következő. Egy adott kiindulási pont x 0 végezzük irányába származású d0 = # 9661; f (x 0) .A pont x 1 határozza meg a gradiens vektor # 9661; f (x 1) x .Poskolku 1 egy minimális pont funkció irányában d0. A # 9661; f (x 1) ortogonális a vektor d0. Ezután kérte vektor d1. H-konjugátum d0. Következő van keresett függvény minimuma iránya mentén D1 és t. D.
Az algoritmus a módszer Fletcher-Reeves
A kezdeti szakaszban.
Kérdezd x 0. # 949> 0.
Keresse meg a gradiens tetszőleges pont
k = 0.
A nagyszínpad
1. lépés: Számítsuk # 9661; f (x k)
2. lépés: a végrehajtása állj feltétel | # 9661; f (x k) |<ε
a) ha a feltétel teljesül, a számítás több mint, x * = x k
b) ha a kritérium nem teljesül, folytassa a 3. lépéssel, ha k = 0, egyébként a 4. lépéshez.
3. lépés: Határozzuk meg a d0 = # 9661; f (x 0)
4. lépés határozza meg, vagy abban az esetben, a nem kvadratikus függvény
5. lépés: Határozza dk = # 9661; f (x k) + bk-1 # 9661; f (x k-1)
6. lépés Compute a nagysága a pályán állapot tk f (x k - tk dk) → min (tk> 0)
7. lépés Számítsuk x k + 1 = xk -tk dk
8. lépés: Put k = k + 1 és menjen az 1. lépésre.
konvergenciája
Tétel 1. Ha a másodfokú függvény f (x) = (X, Hx) + (b, x) + pozitív félig határozott mátrix H eléri a minimális értéket R n. a Fletcher-Reeves módszer lehetővé teszi a meghatározását a minimális pontját nem több, mint N lépésben.
2. Tétel Tegyük fel, hogy az f (x) differenciálható, és alulról korlátos R m. és gradiens kielégíti a Lipschitz feltételt. Ezután, egy tetszőleges kiindulási pont a módszer Polak-Ribiere van
Tétel 2 garanciák konvergencia a fix pont szekvenciát x *. ahol # 9661; f (x *) = 0. Ezért találtam pont x * további vizsgálatot igényel annak besorolását. Módszer Polak-Ribiere biztosítja konvergenciáját a szekvencia a minimális pont csak erősen domború funkciók.
A konvergencia sebessége kapunk csak erősen domború funkciók. Ebben az esetben, a szekvenciát konvergál a minimális pontját az f (x) sebességgel: | x k + n - X * | ≤ C | x k - x * |, k =
Példa. Keresse meg a minimum a módszer konjugátum gradiensek: f (X) = 2x1 2 + 2x2 2 + 2x1 x2 + 20x1 + 10x2 +10.
Határozat. Mivel a keresési irányt választunk egy vektor gradiens az aktuális pont: