Gyllene snittmetoden

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 18 februari 2018; kontroller kräver 10 redigeringar .

Gyllene snittmetoden är en metod för att hitta extremumet för en reell funktion av en variabel på ett givet intervall. Metoden bygger på principen om segmentindelning i proportionerna av det gyllene snittet . Det är en av de enklaste beräkningsmetoderna för att lösa optimeringsproblem . Först introducerades av Jack Kiefer 1953.

Beskrivning av metoden

Låt en funktion ges . Sedan, för att hitta det obestämda värdet av denna funktion på ett givet segment som uppfyller sökkriteriet (låt det vara ett minimum ), delas segmentet i fråga i proportion till det gyllene snittet i båda riktningarna, det vill säga två punkter är valda och sådana att: $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

, var är andelen av det gyllene snittet .

\Phi

På det här sättet:

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

Det vill säga att punkten delar segmentet i förhållande till det gyllene snittet. Delar segmentet i samma proportion. Denna egenskap används för att bygga en iterativ process. $x_{1}$ $[a,\;x_{2}]$ $x_{2}$ $[x_{1},\;b]$

Algoritm

Vid den första iterationen delas det givna segmentet med två punkter som är symmetriska kring dess centrum, och värdena vid dessa punkter beräknas.
Därefter kasseras en av ändarna av segmentet, till vilket, bland de två nyinställda punkterna, den med maximalt värde (för fallet med sökning efter minimum ) visade sig vara närmare.
Vid nästa iteration, på grund av egenskapen hos det gyllene snittet som visas ovan, är det redan nödvändigt att leta efter bara en ny punkt.
Proceduren fortsätter tills den specificerade noggrannheten uppnås.

Formalisering

Steg 1. De initiala gränserna för segmentet och noggrannheten ställs in . $a,\;b$ $\varepsilon$
Steg 2. Beräkna de initiala divisionspunkterna: och värdena i dem för målfunktionen : . $x_{1}=b-{\frac {(ba)}{\Phi )),\quad x_{2}=a+{\frac {(ba)}{\Phi }}$ $y_{1}=f(x_{1}),\;y_{2}=f(x_{2})$
- Om (för att söka efter max ändra olikheten till ), då $y_{1}\geq y_{2}$ $y_{1}\leq y_{2}$ $a=x_{1}$
- Annars . $b=x_{2}$
Steg 3
- Om , sluta då. $|ba|<\varepsilon$ $x={\frac {a+b}{2))$
- Annars går du tillbaka till steg 2.

Algoritmen är hämtad från Matthews och Finks bok Numerical Methods. Använder MATLAB.

Implementeringen av denna algoritm i F# , där målfunktionens värden återanvänds:

låt phi = 0 . 5 * ( 1 . 0 + sqrt 5 . 0 ) låt minimera f eps a b = let rec min_rec f eps a b fx1 fx2 = om b - a < eps så 0 . 5 * ( a + b ) annars låt t = ( b - a ) / phi låt x1 , x2 = b - t , a + t låt fx1 = matcha fx1 med Some v -> v | Ingen -> f x1 låt fx2 = matcha fx2 med Vissa v -> v | Ingen -> f x2 om fx1 >= fx2 då min_rec f eps x1 b ( Vissa fx2 ) Inga andra min_rec f eps a x2 Ingen ( Vissa fx1 ) min_rec f eps ( min a b ) ( max a b ) Ingen Ingen // Anropsexempel: minimera cos 1 e - 6 0 . 0 6 . 28 |> printfn "%.10g" // = 3,141592794; funktion f anropas 34 gånger. minimera ( kul x -> ( x - 1 . 0 )** 2 . 0 ) 1 e - 6 0 . 0 10 . 0 |> printfn "%.10g" // = 1,000000145; funktion f kallas 35 gånger.

Fibonacci-talmetoden

På grund av det faktum att inom asymptotik kan gyllene snittmetoden omvandlas till den så kallade Fibonacci -talmetoden . Men på grund av egenskaperna hos Fibonacci-tal är antalet iterationer strikt begränsat. Detta är praktiskt om antalet möjliga anrop till funktionen omedelbart ställs in. $\Phi =\lim _{n\to \infty }{\frac {F_{n+1}}{F_{n}}}$

Algoritm

Steg 1. De initiala gränserna för segmentet och antalet iterationer ställs in , de initiala divisionspunkterna beräknas: och målfunktionens värden i dem : . $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})$
Steg 2. . $n=n-1$
- Om , då . $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})$
- Annars . $b=x_{2},\;x_{2}=x_{1},\;x_{1}=a+(b-x_{2}),\;y_{2}=y_{1} ,\;y_{1}=f(x_{1})$
Steg 3
- Om , sluta då. $n=1$ $x={\frac {x_{1}+x_{2}}{2}}$
- Annars går du tillbaka till steg 2.

Litteratur

Akulich I. L. Matematisk programmering i exempel och uppgifter: Proc. bidrag för studenters ekonomi. specialist. universitet. - M . : Högre. skola, 1986.
Gill F., Murray W., Wright M. Praktisk optimering. Per. från engelska. — M .: Mir, 1985.
Korshunov Yu. M. Matematiska grunder för cybernetik. — M .: Energoatomizdat, 1972.
Maksimov Yu. A., Filippovskaya EA Algoritmer för att lösa olinjära programmeringsproblem. — M .: MEPhI, 1982.
Maksimov Yu. A. Linjära och diskreta programmeringsalgoritmer. — M .: MEPhI, 1980.
Korn G., Korn T. Handbok i matematik för vetenskapsmän och ingenjörer. - M . : Nauka, 1970. - S. 575-576.
Korn G., Korn T. En handbok i matematik för forskare och ingenjörer . - M . : Nauka, 1973. - S. 832 med illustrationer ..
John G. Matthews, Curtis D. Fink. Numeriska metoder. Använder MATLAB. — 3:e upplagan. - M., St. Petersburg: Williams, 2001. - S. 716.

Se även

Optimeringsmetoder _
En-dimensionell	gyllene snittmetoden Dikotomi Parabolmetoden Rutnätssökning Enhetlig blocksökningsmetod Fibonacci-metoden Ternär sökning Piyavsky-metoden Strongin metod
Noll ordning	Gauss metod Nelder-Mead metod Hook-Jeeves metod Rosenbrock-metoden Powell metod
Första beställning	lutning nedstigning Zeutendijk-metoden Koordinera nedstigning Konjugerad gradientmetod Kvasi-newtonska metoder Levenberg-Marquardts algoritm
andra beställning	Newtons metod Newton-Raphson-metoden Broyden-Fletcher-Goldfarb-Shanno-algoritm (BFGS)
Stokastisk	Monte Carlo metoden Simulerad glödgning Evolutionära algoritmer differentiell evolution Myralgoritm Partikelsvärmmetod Algoritm för bikoloni Random walk-metod
Linjära programmeringsmetoder _	Enkel metod Gomoris algoritm Ellipsoid metod Potentiell metod
Icke -linjära programmeringsmetoder	Sekventiell kvadratisk programmering

gyllene snittet
"Gyllene" figurer	gyllene rektangel gyllene triangeln gyllene romb gyllene ellips Kepler triangel gyllene hörnet gyllene spiral gyllene gnomon
Andra avsnitt	Super gyllene snitt silversektion brons sektion
Övrig	Fibonacci-siffror Tredjeregel gyllene snittmetoden Det gyllene snittet i pentagrammet