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}=\phi$

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

$\phi =\frac{1+\sqrt{5}}{2}=1,618033988\dots$

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{ϵ}$ ahol $ϵ$ a szükséges pontosság értéke.

További információk

1. Sablon:Citation

1. Sablon:Citation

1. Sablon:Citation