Método de la sección áurea

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 18 de febrero de 2018; las comprobaciones requieren 10 ediciones .

El método de la sección áurea es un método para encontrar el extremo de una función real de una variable en un intervalo dado. El método se basa en el principio de división en segmentos en las proporciones de la sección áurea . Es uno de los métodos computacionales más simples para resolver problemas de optimización . Presentado por primera vez por Jack Kiefer en 1953.

Descripción del método

Sea dada una función . Entonces, para encontrar el valor indeterminado de esta función en un segmento dado que cumpla con el criterio de búsqueda (que sea un mínimo ), el segmento en consideración se divide en proporción a la sección áurea en ambas direcciones, es decir, dos puntos son seleccionados y tales que: $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

, donde es la proporción de la sección áurea .

\Fi

De este modo:

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

Es decir, el punto divide el segmento en relación con la proporción áurea. Del mismo modo divide el segmento en la misma proporción. Esta propiedad se utiliza para construir un proceso iterativo. $x_{1}$ ${\ estilo de visualización [a, \; x_ {2}]}$ $x_{2}$ ${\ estilo de visualización [x_{1}, \; b]}$

Algoritmo

En la primera iteración, el segmento dado se divide por dos puntos que son simétricos con respecto a su centro, y se calculan los valores en estos puntos.
A continuación, se descarta uno de los extremos del segmento al que, entre los dos nuevos puntos fijados, resultó estar más próximo el de valor máximo (para el caso de buscar el mínimo ).
En la siguiente iteración, debido a la propiedad de la sección áurea que se muestra arriba, ya es necesario buscar solo un punto nuevo.
El procedimiento continúa hasta que se alcanza la precisión especificada.

Formalización

Paso 1. Se establecen los límites iniciales del segmento y la precisión . $a,\;b$ $\varepsilon$
Paso 2. Calcular los puntos iniciales de división: y los valores en ellos de la función objetivo : . $x_{1}=b-{\frac {(ba)}{\Phi )),\quad x_{2}=a+{\frac {(ba)}{\Phi }}$ $y_{1}=f(x_{1}),\;y_{2}=f(x_{2})$
- Si (para buscar max cambia la desigualdad a ), entonces $y_{1}\geq y_{2}$ $y_{1}\leq y_{2}$ ${\ estilo de visualización a = x_ {1}}$
- De lo contrario ${\ estilo de visualización b = x_ {2}}$
Paso 3
- Si , entonces deténgase. ${\ estilo de visualización | ba | <\ varepsilon}$ $x={\frac{a+b}{2))$
- De lo contrario, regrese al paso 2.

El algoritmo está tomado del libro Numerical Methods de Matthews y Fink. Usando MATLAB.

La implementación de este algoritmo en F# , en el que se reutilizan los valores de la función objetivo:

Sea phi = 0 . 5 * ( 1 . 0 + sqrt 5 . 0 ) let minimice f eps a b = let rec min_rec f eps a b fx1 fx2 = si b - a < eps entonces 0 . 5 * ( a + b ) más sea t = ( b - a ) / phi sea x1 , x2 = b - t , a + t sea fx1 = haga coincidir fx1 con Some v -> v | Ninguno -> f x1 let fx2 = hacer coincidir fx2 con Some v -> v | Ninguno -> f x2 si fx1 >= fx2 entonces min_rec f eps x1 b ( Algunos fx2 ) Ninguno más min_rec f eps a x2 Ninguno ( Algunos fx1 ) min_rec f eps ( min a b ) ( max a b ) Ninguno Ninguno // Ejemplos de llamadas: minimizar cos 1 e - 6 0 . 0 6 . 28 |> printfn "%.10g" // = 3.141592794; la función f se llama 34 veces. minimizar ( divertido x -> ( x - 1 . 0 )** 2 . 0 ) 1 e - 6 0 . 0 10 . 0 |> printfn "%.10g" // = 1.000000145; la función f se llama 35 veces.

Método del número de Fibonacci

Debido a que en asintótica , el método de la sección áurea se puede transformar en el llamado método del número de Fibonacci . Sin embargo, debido a las propiedades de los números de Fibonacci, el número de iteraciones está estrictamente limitado. Esto es conveniente si el número de posibles llamadas a la función se establece inmediatamente. $\Phi =\lim _{n\to \infty }{\frac {F_{n+1}}{F_{n}}}$

Algoritmo

Paso 1. Se establecen los límites iniciales del segmento y el número de iteraciones , se calculan los puntos de división iniciales: y los valores de la función objetivo en ellos : . $a,\;b$ $norte$ $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})$
Paso 2. . ${\ estilo de visualización n = n-1}$
- Si , entonces . $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})$
- De lo contrario $b=x_{2},\;x_{2}=x_{1},\;x_{1}=a+(b-x_{2}),\;y_{2}=y_{1} ,\;y_{1}=f(x_{1})$
Paso 3
- Si , entonces deténgase. $n=1$ $x={\frac{x_{1}+x_{2}}{2}}$
- De lo contrario, regrese al paso 2.

Literatura

Akulich I. L. Programación matemática en ejemplos y tareas: Proc. Subsidio para la economía de los estudiantes. especialista. universidades - M. : Superior. escuela, 1986.
Gill F., Murray W., Wright M. Optimización práctica. Por. De inglés. — M .: Mir, 1985.
Korshunov Yu. M. Fundamentos matemáticos de la cibernética. — M .: Energoatomizdat, 1972.
Maksimov Yu. A., Filippovskaya EA Algoritmos para resolver problemas de programación no lineal. — M. : MEPHI, 1982.
Maksimov Yu. A. Algoritmos de programación lineal y discreta. — M. : MEPhI, 1980.
Korn G., Korn T. Manual de matemáticas para científicos e ingenieros. - M. : Nauka, 1970. - S. 575-576.
Korn G., Korn T. Un manual de matemáticas para investigadores e ingenieros . - M. : Nauka, 1973. - S. 832 con ilustraciones ..
John G. Matthews, Curtis D. Fink. Métodos numéricos. Usando MATLAB. — 3ra edición. - M., San Petersburgo: Williams, 2001. - S. 716.

Véase también

Métodos de optimización
unidimensional	método de la sección áurea Dicotomía método de parábola búsqueda de cuadrícula Método de búsqueda de bloque uniforme método fibonacci búsqueda ternaria método Piyavsky Método Strongin
orden cero	método de Gauss Método Nelder-Mead Método Hook-Jeeves método de Rosenbrock metodo powell
Primer orden	descenso de gradiente método Zeutendijk Descenso coordinado método de gradiente conjugado Métodos Cuasi-Newtonianos Algoritmo de Levenberg-Marquardt
segundo orden	método de newton Método de Newton-Raphson Algoritmo de Broyden-Fletcher-Goldfarb-Shanno (BFGS)
estocástico	Método de Montecarlo recocido simulado Algoritmos evolutivos evolución diferencial Algoritmo de hormiga método de enjambre de partículas Algoritmo de colonia de abejas Método de paseo aleatorio
Métodos de programación lineal	método símplex algoritmo de gomori método elipsoide método potencial
Métodos de programación no lineal	Programación cuadrática secuencial

proporción áurea
Figuras "doradas"	rectángulo dorado triangulo Dorado rombo dorado elipse dorada triángulo de Kepler esquina dorada espiral dorada gnomon dorado
Otras secciones	Súper proporción áurea sección de plata sección de bronce
Otro	números de Fibonacci Regla de los tercios método de la sección áurea La proporción áurea en el pentagrama