Aranymetszés módszere

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.

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

A következő lépés egy új x érték kiértékelése, ami ${\displaystyle x_{4}}$ lesz. A legcélszerűbb az ${\displaystyle x_{4}}$ értékét a legnagyobb intervallumból választani, ami esetünkben az ${\displaystyle x_{2}}$ és az ${\displaystyle x_{3}}$ közötti. Az ábráról egyértelműen leolvasható, hogy ha az ${\displaystyle f_{4}a}$-ban nézzük, akkor az intervallum [${\displaystyle x_{1}}$,${\displaystyle x_{4}}$], de ha az ${\displaystyle f_{4}b}$ értékét nézzük, akkor az intervallumunk az ${\displaystyle x_{2}}$ és ${\displaystyle x_{3}}$ között lesz. Az első esetben az új hármaspont (${\displaystyle x_{1}}$,${\displaystyle x_{2}}$,${\displaystyle x_{4}}$), a másodikban (${\displaystyle x_{2}}$,${\displaystyle x_{4}}$,${\displaystyle x_{3}}$). Ezt a lépést újra és újra alkalmazva megkapjuk a minimumpontját egy függvénynek.

A fenti ábrán látjuk, hogy az új keresési intervallum az ${\displaystyle x_{1}}$ és az ${\displaystyle x_{4}}$ között van, amelynek hossza a+c, vagy pedig az ${\displaystyle x_{2}}$ és az ${\displaystyle 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 ${\displaystyle x_{4}}$-et, hogy teljesüljön a következő egyenlőség:${\displaystyle x_{4}}$=${\displaystyle x_{1}}$-${\displaystyle x_{2}}$+${\displaystyle x_{3}}$.

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

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

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

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

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

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

vagy

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

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

${\displaystyle \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.

Az algoritmusnak szüksége van egy leállási feltételre, ez a következő:

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

ahol ${\displaystyle \tau }$ az algoritmus tolerancia paramétere, és ${\displaystyle |x|}$ abszolút értéke az ${\displaystyle x}$-nek. A ${\displaystyle \tau }$ javasolt értéke ${\displaystyle \tau ={\sqrt {\epsilon }}}$ ahol ${\displaystyle \epsilon }$ a szükséges pontosság értéke.

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.

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