Aranymetszet módszer

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt hozzászólók, és jelentősen eltérhet a 2018. február 18-án felülvizsgált verziótól ; az ellenőrzésekhez 10 szerkesztés szükséges .

Az aranymetszet módszere egy változó valós függvényének szélsőértékének meghatározására szolgáló módszer egy adott intervallumon. A módszer az aranymetszet arányaiban történő szegmensosztás elvén alapul . Ez az egyik legegyszerűbb számítási módszer az optimalizálási problémák megoldására . Először Jack Kiefer mutatta be 1953-ban.

A módszer leírása

Legyen adott függvény . Ezután annak érdekében, hogy egy adott, a keresési feltételnek megfelelő szegmensen megtaláljuk ennek a függvénynek a határozatlan értékét (legyen ez minimum ), a vizsgált szegmenst mindkét irányban az aranymetszet arányában elosztjuk, azaz két pont. úgy vannak kiválasztva , hogy: $f(x):\;[a,\;b]\to \mathbb {R} ,\;f(x)\in \mathrm {C} ([a,\;b])$ $x_{1}$ $x_{2}$

{\frac {ba}{b-x_{1}}}={\frac {ba}{x_{2}-a}}=\Phi ={\frac {1+{\sqrt {5} }}{2}}=1,618\lpont

, ahol az aranymetszet aránya .

\Phi

Ilyen módon:

{\begin{array}{ccc}x_{1}&=&b-{\frac {(ba)}{\Phi }}\\x_{2}&=&a+{\frac {(ba)} {\Phi ))\end{array))

Vagyis a pont osztja a szakaszt az aranymetszés viszonylatában. Hasonló módon osztja fel a szegmenst ugyanolyan arányban. Ez a tulajdonság egy iteratív folyamat felépítésére szolgál. $x_{1}$ $[a,\;x_{2}]$ $x_{2}$ $[x_{1},\;b]$

Algoritmus

Az első iterációnál az adott szakaszt elosztjuk két, a középpontjára szimmetrikus ponttal, és ezekben a pontokban kiszámítjuk az értékeket.
Ezt követően a szegmens egyik végét, amelyhez a két újonnan beállított pont közül a maximum értékű (a minimum keresése esetén ) közelebbinek bizonyult, eldobjuk.
A következő iterációnál az aranymetszet fentebb bemutatott tulajdonsága miatt már csak egy új pontot kell keresni.
Az eljárás a megadott pontosság eléréséig folytatódik.

Formalizálás

1. lépés: A szakasz kezdeti határai és a pontosság beállítása . $a,\;b$ $\varepsilon$
2. lépés : Számítsa ki a kezdeti osztási pontokat: és a bennük lévő célfüggvény értékeit : . $x_{1}=b-{\frac {(ba)}{\Phi )),\quad x_{2}=a+{\frac {(ba)}{\Phi }}$ $y_{1}=f(x_{1}),\;y_{2}=f(x_{2})$
- Ha (a max kereséséhez módosítsa az egyenlőtlenséget értékre ), akkor $y_{1}\geq y_{2}$ $y_{1}\leq y_{2}$ $a=x_{1}$
- Különben . ${\displaystyle b=x_{2))$
3. lépés
- Ha , akkor hagyja abba. $|ba|<\varepsilon$ $x={\frac {a+b}{2))$
- Ellenkező esetben térjen vissza a 2. lépéshez.

Az algoritmus Matthews és Fink Numerical Methods című könyvéből származik. MATLAB használata.

Ennek az algoritmusnak az F# -ban való megvalósítása, amelyben a célfüggvény értékeit újra felhasználják:

legyen phi = 0 . 5 * ( 1. 0 + sqrt 5. 0 ) legyen f eps minimalizálása a b = legyen rec min_rec f eps a b fx1 fx2 = ha b - a < eps , akkor 0 . _ 5 * ( a + b ) else legyen t = ( b - a ) / phi legyen x1 , x2 = b - t , a + t legyen fx1 = párosítsa az fx1 - t a Some v - > v - vel | Nincs -> f x1 legyen fx2 = párosítsa az fx2 -t a Some v -> v | -vel Nincs -> f x2 if fx1 >= fx2 then min_rec f eps x1 b ( Some fx2 ) Nincs más min_rec f eps a x2 Nincs ( Some fx1 ) min_rec f eps ( min a b ) ( max a b ) Nincs Nincs // Hívási példák: minimalize cos 1 e - 6 0 . 0 6 . 28 |> printfn "%.10g" // = 3,141592794; f függvényt 34-szer hívjuk meg. minimalizálni ( szórakozás x -> ( x - 1 . 0 )** 2 . 0 ) 1 e - 6 0 . 0 10 . 0 |> printfn "%.10g" // = 1,000000145; f függvényt 35-ször hívjuk meg.

Fibonacci számmódszer

Tekintettel arra, hogy az aszimptotikában az aranymetszet módszer átalakítható az úgynevezett Fibonacci -számmódszerré . A Fibonacci-számok tulajdonságai miatt azonban az iterációk száma szigorúan korlátozott. Ez akkor kényelmes, ha azonnal beállítja a funkció lehetséges hívásainak számát. $\Phi =\lim _{n\to \infty }{\frac {F_{n+1}}{F_{n}}}$

Algoritmus

1. lépés: A szakasz kezdeti határait és az iterációk számát meghatározzuk , a kezdeti osztási pontokat kiszámítjuk: és a bennük lévő célfüggvény értékeit : . $a,\;b$ $n$ $x_{1}=a+(ba){\frac {F_{n-2}}{F_{n}}},\quad x_{2}=a+(ba){\frac {F_{n- 1}}{F_{n}}}$ $y_{1}=f(x_{1}),\;y_{2}=f(x_{2})$
2. lépés . $n=n-1$
- Ha , akkor . $y_{1}>y_{2}$ $a=x_{1},\;x_{1}=x_{2},\;x_{2}=b-(x_{1}-a),\;y_{1}=y_{2 },\;y_{2}=f(x_{2})$
- Különben . $b=x_{2},\;x_{2}=x_{1},\;x_{1}=a+(b-x_{2}),\;y_{2}=y_{1} ,\;y_{1}=f(x_{1})$
3. lépés
- Ha , akkor hagyja abba. $n=1$ $x={\frac {x_{1}+x_{2}}{2}}$
- Ellenkező esetben térjen vissza a 2. lépéshez.

Irodalom

Akulich I. L. Matematikai programozás példákban és feladatokban: Proc. diákgazdasági juttatás. szakember. egyetemek. - M . : Feljebb. iskola, 1986.
Gill F., Murray W., Wright M. Gyakorlati optimalizálás. Per. angolról. - M .: Mir, 1985.
Korshunov Yu. M. A kibernetika matematikai alapjai. - M .: Energoatomizdat, 1972.
Maksimov Yu. A., Filippovskaya EA Algoritmusok nemlineáris programozási problémák megoldására. — M. : MEPhI, 1982.
Maksimov Yu. A. Lineáris és diszkrét programozási algoritmusok. — M. : MEPhI, 1980.
Korn G., Korn T. Matematikai kézikönyv tudósok és mérnökök számára. - M . : Nauka, 1970. - S. 575-576.
Korn G., Korn T. A matematika kézikönyve kutatóknak és mérnököknek . - M . : Nauka, 1973. - S. 832 illusztrációkkal ..
John G. Matthews, Curtis D. Fink. Numerikus módszerek. MATLAB használata. — 3. kiadás. - M., St. Petersburg: Williams, 2001. - S. 716.

Lásd még

Optimalizálási módszerek
Egydimenziós	aranymetszet módszer Kettősség Parabola módszer Rács keresés Egységes blokkkeresési módszer Fibonacci módszer Háromszoros keresés Piyavsky módszer Strongin módszer
Nulla sorrend	Gauss módszer Nelder-Mead módszer Hook-Jeeves módszer Rosenbrock módszer Powell-módszer
Első rendelés	gradiens süllyedés Zeutendijk módszer Koordináta süllyedés Konjugált gradiens módszer Kvázi-Newtoni módszerek Levenberg-Marquardt algoritmus
másodrendű	Newton módszere Newton-Raphson módszer Broyden-Fletcher-Goldfarb-Shanno algoritmus (BFGS)
Sztochasztikus	Monte Carlo módszer Szimulált lágyítás Evolúciós algoritmusok differenciális evolúció Hangya algoritmus Részecskeraj módszer Méhtelep algoritmus Véletlenszerű séta módszer
Lineáris programozási módszerek	Simplex módszer Gomori algoritmusa Ellipszoid módszer Potenciális módszer
Nemlineáris programozási módszerek	Szekvenciális kvadratikus programozás

aranymetszés
"Arany" figurák	arany téglalap Arany háromszög arany rombusz arany ellipszis Kepler háromszög arany sarok arany spirál arany gnomon
Egyéb szakaszok	Szuper aranymetszés ezüst rész bronz szakasz
Egyéb	Fibonacci számok A harmad szabálya aranymetszet módszer Az aranymetszés a pentagramban