Kultaisen leikkauksen menetelmä

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 18. helmikuuta 2018 tarkistetusta versiosta . tarkastukset vaativat 10 muokkausta .

Kultaleikkausmenetelmä on menetelmä, jolla löydetään yhden muuttujan reaalifunktion ääriarvo tietyltä väliltä. Menetelmä perustuu segmentin jaon periaatteeseen kultaisen leikkauksen suhteissa . Se on yksi yksinkertaisimmista laskennallisista menetelmistä optimointiongelmien ratkaisemiseksi . Ensimmäisen kerran Jack Kiefer esitteli vuonna 1953.

Menetelmän kuvaus

Olkoon funktio annettu . Tämän jälkeen tämän funktion määrittelemättömän arvon löytämiseksi tietystä segmentistä, joka täyttää hakukriteerit (olkoon se vähintään ), tarkasteltava segmentti jaetaan suhteessa kultaiseen leikkaukseen molempiin suuntiin, eli kahteen pisteeseen valitaan ja siten, että: $f(x):\;[a,\;b]\to \mathbb {R} ,\;f(x)\in \mathrm {C} ([a,\;b])$ $x_{1}$ $x_{2}$

{\frac {ba}{b-x_{1}}}={\frac {ba}{x_{2}-a}}=\Phi ={\frac {1+{\sqrt {5} }}{2}}=1,618\ldots

, missä on kultaisen leikkauksen osuus .

\Phi

Tällä tavalla:

{\begin{array}{ccc}x_{1}&=&b-{\frac {(ba)}{\Phi }}\\x_{2}&=&a+{\frac {(ba)} {\Phi ))\end{array))

Eli piste jakaa segmentin suhteessa kultaiseen leikkaukseen. Samalla tavalla jakaa segmentin samassa suhteessa. Tätä ominaisuutta käytetään iteratiivisen prosessin rakentamiseen. $x_{1}$ $[a,\;x_{2}]$ $x_{2}$ $[x_{1},\;b]$

Algoritmi

Ensimmäisessä iteraatiossa annettu segmentti jaetaan kahdella pisteellä, jotka ovat symmetrisiä sen keskipisteen suhteen, ja arvot näissä kohdissa lasketaan.
Sen jälkeen hylätään toinen segmentin päistä, jolle kahden uuden asetetun pisteen joukosta suurin arvo ( minimihaun tapauksessa ) osoittautui olevan lähempänä.
Seuraavassa iteraatiossa edellä esitetyn kultaisen leikkauksen ominaisuuden vuoksi on jo tarpeen etsiä vain yksi uusi piste.
Toimenpide jatkuu, kunnes määritetty tarkkuus on saavutettu.

Formalisointi

Vaihe 1. Janan alkurajat ja tarkkuus asetetaan . $a,\;b$ $\varepsilon$
Vaihe 2. Laske alkujakopisteet: ja niissä olevat tavoitefunktion arvot : . $x_{1}=b-{\frac {(ba)}{\Phi )),\quad x_{2}=a+{\frac {(ba)}{\Phi }}$ $y_{1}=f(x_{1}),\;y_{2}=f(x_{2})$
- Jos (jos haluat etsiä max, muuta epäyhtälö arvoon ), sitten $y_{1}\geq y_{2}$ $y_{1}\leq y_{2}$ $a=x_{1}$
- Muuten . $b=x_{2}$
Vaihe 3
- Jos , niin lopeta. $|ba|<\varepsilon$ $x={\frac {a+b}{2))$
- Muussa tapauksessa palaa vaiheeseen 2.

Algoritmi on otettu Matthewsin ja Finkin kirjasta Numerical Methods. MATLABin käyttö.

Tämän algoritmin toteutus F# :ssa, jossa tavoitefunktion arvoja käytetään uudelleen:

olkoon phi = 0 . 5 * ( 1. 0 + sqrt 5. 0 ) minimoi f eps a b = anna rec min_rec f eps a b fx1 fx2 = jos b - a < eps niin 0 . _ _ _ 5 * ( a + b ) muuten olkoon t = ( b - a ) / phi let x1 , x2 = b - t , a + t anna fx1 = vastaa fx1 kanssa Jotkut v -> v | Ei mitään -> f x1 anna fx2 = sovittaa fx2 kanssa Jotkut v -> v | Ei mitään -> f x2 jos fx1 >= fx2 sitten min_rec f eps x1 b ( Jotkut fx2 ) Ei mitään muuta min_rec f eps a x2 Ei mitään ( Jotkut fx1 ) min_rec f eps ( min a b ) ( max a b ) Ei mitään Ei mitään // Kutsuesimerkkejä: minimoi cos 1 e - 6 0 . 0 6 . 28 |> printfn "%.10g" // = 3,141592794; funktiota f kutsutaan 34 kertaa. minimoida ( hauska x -> ( x - 1 . 0 )** 2 . 0 ) 1 e - 6 0 . 0 10 . 0 |> printfn "%.10g" // = 1,000000145; funktiota f kutsutaan 35 kertaa.

Fibonacci-lukumenetelmä

Johtuen siitä, että asymptotiikassa kultaleikkausmenetelmä voidaan muuntaa ns. Fibonacci -lukumenetelmäksi . Fibonacci-lukujen ominaisuuksien vuoksi iteraatioiden määrä on kuitenkin tiukasti rajoitettu. Tämä on kätevää, jos toiminnon mahdollisten kutsujen määrä asetetaan välittömästi. $\Phi =\lim _{n\to \infty }{\frac {F_{n+1}}{F_{n}}}$

Algoritmi

Vaihe 1. Janan alkurajat ja iteraatioiden määrä asetetaan , lasketaan alkujakopisteet: ja niissä tavoitefunktion arvot : . $a,\;b$ $n$ $x_{1}=a+(ba){\frac {F_{n-2}}{F_{n}}},\quad x_{2}=a+(ba){\frac {F_{n- 1}}{F_{n}}}$ $y_{1}=f(x_{1}),\;y_{2}=f(x_{2})$
Vaihe 2 . ${\näyttötyyli n=n-1}$
- Jos , niin . $y_{1}>y_{2}$ $a=x_{1},\;x_{1}=x_{2},\;x_{2}=b-(x_{1}-a),\;y_{1}=y_{2 },\;y_{2}=f(x_{2})$
- Muuten . $b=x_{2},\;x_{2}=x_{1},\;x_{1}=a+(b-x_{2}),\;y_{2}=y_{1} ,\;y_{1}=f(x_{1})$
Vaihe 3
- Jos , niin lopeta. $n = 1$ $x={\frac {x_{1}+x_{2}}{2}}$
- Muussa tapauksessa palaa vaiheeseen 2.

Kirjallisuus

Akulich I. L. Matemaattinen ohjelmointi esimerkeissä ja tehtävissä: Proc. opiskelijatalouden tuki. asiantuntija. yliopistot. - M . : Korkeampi. koulu, 1986.
Gill F., Murray W., Wright M. Käytännön optimointi. Per. englannista. - M .: Mir, 1985.
Korshunov Yu. M. Kybernetiikan matemaattiset perusteet. - M .: Energoatomizdat, 1972.
Maksimov Yu. A., Filippovskaya EA Algoritmit epälineaaristen ohjelmointiongelmien ratkaisemiseen. - M .: MEPhI, 1982.
Maksimov Yu. A. Lineaariset ja diskreetit ohjelmointialgoritmit. - M .: MEPhI, 1980.
Korn G., Korn T. Matematiikan käsikirja tutkijoille ja insinööreille. - M .: Nauka, 1970. - S. 575-576.
Korn G., Korn T. Matematiikan käsikirja tutkijoille ja insinööreille . - M . : Nauka, 1973. - S. 832 kuvituksella ..
John G. Matthews, Curtis D. Fink. Numeeriset menetelmät. MATLABin käyttö. – 3. painos. - M., St. Petersburg: Williams, 2001. - S. 716.

Katso myös

Optimointimenetelmät _
Yksiulotteinen	kultaisen leikkauksen menetelmä Dikotomia Paraabeli menetelmä Verkkohaku Yhtenäinen lohkohakumenetelmä Fibonaccin menetelmä Kolminkertainen haku Piyavsky menetelmä Vahva menetelmä
Nolla järjestys	Gaussin menetelmä Nelder-Meadin menetelmä Hook-Jeeves -menetelmä Rosenbrockin menetelmä Powellin menetelmä
Ensimmäinen tilaus	gradienttilasku Zeutendijkin menetelmä Koordinaattilasku Konjugaattigradienttimenetelmä Kvasi-Newtonilaiset menetelmät Levenberg-Marquardt-algoritmi
toinen tilaus	Newtonin menetelmä Newton-Raphsonin menetelmä Broyden-Fletcher-Goldfarb-Shanno-algoritmi (BFGS)
Stokastinen	Monte Carlon menetelmä Simuloitu hehkutus Evoluutioalgoritmit differentiaalinen evoluutio Ant algoritmi Hiukkasparvimenetelmä Mehiläisyhdyskunnan algoritmi Satunnainen kävelymenetelmä
Lineaariset ohjelmointimenetelmät _	Yksinkertainen menetelmä Gomorin algoritmi Ellipsoidi menetelmä Potentiaalinen menetelmä
Epälineaariset ohjelmointimenetelmät	Jaksottainen neliöllinen ohjelmointi

kultainen leikkaus
"Kultaiset" hahmot	kultainen suorakulmio Kultainen kolmio kultainen rombi kultainen ellipsi Keplerin kolmio kultainen nurkka kultainen spiraali kultainen gnomoni
Muut osiot	Super kultainen suhde hopeinen osa pronssinen osa
Muut	Fibonaccin numerot Kolmannesten sääntö kultaisen leikkauksen menetelmä Kultainen leikkaus pentagrammissa