Aranymetszés módszere

A Wikipédiából, a szabad enciklopédiából
Jump to navigation Jump to search
Az aranymetszés módszer alkalmazása


Az aranymetszés optimalizálási módszer egy technikája 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[szerkesztés]

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[szerkesztés]

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[szerkesztés]

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[szerkeszté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.

Külső hivatkozások[szerkesztés]

  1. Avriel, Mordecai & Wilde, Douglass J. (1966), "Optimality proof for the symmetric Fibonacci search technique", Fibonacci Quarterly 4: 265–269, MR0208812
  1. 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>
  1. 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