Aranymetszés módszere
![](http://upload.wikimedia.org/wikipedia/commons/thumb/5/52/GoldenSectionSearch.png/325px-GoldenSectionSearch.png)
Az aranymetszés optimalizálási módszer egy technika az unimodális függvények szélsőértékpontjainak (minimum vagy maximum) a meghatározására, ha ismert az a szűk értéktartomány, amelyen belül megtalálhatók. Onnan kapta nevét, hogy az algoritmus tartalmazza azt azt a három függvényértéket, amelyek egymástól való távolságát pontosan az aranymetszés adja meg. Ez a módszer közel áll a Fibonacci-kereséshez és a bináris kereséshez.
Fő gondolat
A fenti ábra bemutatja egy lépését a minimum keresési technikának. Az f(x) funkcionális értékei szerepelnek a függőleges tengelyen, míg a vízszintesen az x megfelelő értékei. Az függvény már ki lett értékelve három pontban: , , . Az értéke az és az értéke között helyezkedik el, tehát egyértelművé válik, hogy a minimumpont az és az között helyezkedik el.
A következő lépés egy új x érték kiértékelése, ami lesz. A legcélszerűbb az értékét a legnagyobb intervallumból választani, ami esetünkben az és az közötti. Az ábráról egyértelműen leolvasható, hogy ha az -ban nézzük, akkor az intervallum [,], de ha az értékét nézzük, akkor az intervallumunk az és között lesz. Az első esetben az új hármaspont (,,), a másodikban (,,). Ezt a lépést újra és újra alkalmazva megkapjuk a minimumpontját egy függvénynek.
A próbapont megkeresése
A fenti ábrán látjuk, hogy az új keresési intervallum az és az között van, amelynek hossza a+c, vagy pedig az és az között van, amelynek hossza b. Az aranymetszés előírja, hogy ezek egyformák legyenek. Ha nem egyformák, akkor úgy kell megválasztani az -et, hogy teljesüljön a következő egyenlőség:=-+.
A kérdés meg mindig ugyanaz, hogy hol kell elhelyezkedjen az az és az között. Az aranymetszés keresési módszer olyan módon választja ki a pontokat, hogy a közöttük lévő távolságok aránya mindig egyenlő legyen. Matematikailag, ha az -ban van akkor:
Ellenben, ha az -ben van, akkor az arány a következőképpen néz ki:
A "c" értéket kifejezzük és a két egyenletet egyenlővé tesszük:
vagy
ahol a φ az aranyarány (a fi):
Onnan kapta ez az algoritmus a nevét, hogy a távolságok aránya az aranyarány az aranymetszésből.
Meghatározási feltétel
Az algoritmusnak szüksége van egy leállási feltételre, ez a következő:
ahol az algoritmus tolerancia paramétere, és abszolút értéke az -nek. A javasolt értéke ahol a szükséges pontosság értéke.
Fordítás
Ez a szócikk részben vagy egészben a Golden section search című angol Wikipédia-szócikk fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.
Külső hivatkozások
- Avriel, Mordecai & Wilde, Douglass J. (1966), "Optimality proof for the symmetric Fibonacci search technique", Fibonacci Quarterly 4: 265–269, MR0208812
- Kiefer, J. (1953), "Sequential minimax search for a maximum", Proceedings of the American Mathematical Society 4 (3): 502–506, MR0055639,, doi:10.2307/2032161, <http://jstor.org/stable/2032161>
- Press, W. H.; Teukolsky, S. A. & Vetterling, W. T. et al. (1999), Numerical Recipes in C, The Art of Scientific Computing (second ed.), Cambridge University Press, Cambridge, ISBN 0-521-43108-5