Aranymetszés módszere

Az aranymetszés módszer alkalmazása

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(x)$ függvény már ki lett értékelve három pontban: $x_{1}$, $x_{2}$, $x_{3}$. Az $f_{2}$ értéke az $f_{1}$ és az $f_{3}$ értéke között helyezkedik el, tehát egyértelművé válik, hogy a minimumpont az $x_{1}$ és az $x_{3}$ között helyezkedik el.

A következő lépés egy új x érték kiértékelése, ami $x_{4}$ lesz. A legcélszerűbb az $x_{4}$ értékét a legnagyobb intervallumból választani, ami esetünkben az $x_{2}$ és az $x_{3}$ közötti. Az ábráról egyértelműen leolvasható, hogy ha az $f_{4}a$-ban nézzük, akkor az intervallum [$x_{1}$,$x_{4}$], de ha az $f_{4}b$ értékét nézzük, akkor az intervallumunk az $x_{2}$ és $x_{3}$ között lesz. Az első esetben az új hármaspont ($x_{1}$,$x_{2}$,$x_{4}$), a másodikban ($x_{2}$,$x_{4}$,$x_{3}$). 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 $x_{1}$ és az $x_{4}$ között van, amelynek hossza a+c, vagy pedig az $x_{2}$ és az $x_{3}$ 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 $x_{4}$-et, hogy teljesüljön a következő egyenlőség:$x_{4}$=$x_{1}$-$x_{2}$+$x_{3}$.

A kérdés meg mindig ugyanaz, hogy hol kell elhelyezkedjen az $x_{2}$ az $x_{1}$ és az $x_{3}$ 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 $f(x_{4})$ az $f(x_{4}a)$-ban van akkor:

${\frac {c}{a}}={\frac {a}{b}}.$

Ellenben, ha $f(x_{4})$ az $f(x_{4}b)$-ben van, akkor az arány a következőképpen néz ki:

${\frac {c}{(b-c)}}={\frac {a}{b}}.$

A "c" értéket kifejezzük és a két egyenletet egyenlővé tesszük:

$\left({\frac {b}{a}}\right)^{2}={\frac {b}{a}}+1$

vagy

${\frac {b}{a}}=\varphi$

ahol a φ  az aranyarány (a fi):

$\varphi ={\frac {1+{\sqrt {5}}}{2}}=1,618033988\ldots$

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ő:

$|x_{3}-x_{1}|<\tau (|x_{2}|+|x_{4}|)\,$

ahol $\tau$ az algoritmus tolerancia paramétere, és $|x|$ abszolút értéke az $x$-nek. A $\tau$ javasolt értéke $\tau ={\sqrt {\epsilon }}$ ahol $\epsilon$ 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

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