Búsqueda de la sección dorada
La búsqueda (o método) de la sección dorada es una técnica para hallar el extremo (mínimo o máximo) de una función unimodal, mediante reducciones sucesivas del rango de valores en el cual se conoce que se encuentra el extremo.
La técnica debe su nombre al hecho de que el algoritmo mantiene los valores de la función en tríos de puntos cuyas distancias forman una proporción dorada.
El diagrama de arriba ilustra un paso en la técnica para hallar un mínimo.
están en el eje vertical y el horizontal es el parámetro
ha sido calculado ya para los tres puntos
, es evidente que el mínimo se encuentra dentro del intervalo desde
en algún lugar dentro del intervalo más grande, dígase entre
Por la figura, se puede notar que si
y el nuevo trío de puntos serán
, y el nuevo trío de puntos serán
De esta manera, en cualquier caso, es posible construir un nuevo intervalo de búsqueda más pequeño en el cual está garantizado que se encuentra el mínimo de la función.
Este método requiere que ambos intervalos sean de igual tamaño.
Si no lo son, es posible que una "mala suerte" pueda llevar a utilizar el intervalo más grande muchas veces, ralentizando así la convergencia del método.
Sin embargo, queda aún sin responder dónde debe ubicarse
Al mantener la misma proporción durante todo el algoritmo, se evita la situación en la cual
Matemáticamente, para asegurar que el espaciado después de evaluar
es proporcional al espaciado antes de la evaluación, si
y el nuevo trío de puntos es
y el nuevo trío de puntos es
, entonces se quiere: Eliminando c de este sistema de dos ecuaciones se obtiene: o donde
La dada en el libro "Numerical Recipes in C" se basa en los espacios entre
, terminando cuando se cumple la siguiente cota de precisión relativa: donde
es un parámetro de tolerancia del algoritmo y
La condición está basada en el tamaño del intervalo relativo a su valor central, porque el error relativo en
es aproximadamente proporcional al cuadrado del error absoluto en
Por esa misma razón, en "Numerical Recipes in C" se recomienda
, junto con un número ligeramente inferior de pasos, constituye la principal ventaja algorítmica de este método sobre la búsqueda ternaria.
Un algoritmo muy similar puede ser también usado para determinar el extremo (mínimo o máximo) de una secuencia de valores que tiene un único mínimo local o máximo local.
Por esta razón, la variante del método para secuencias es usualmente llamada búsqueda de Fibonacci.
La búsqueda de Fibonacci fue ideada por Kiefer (1953) como una búsqueda minimax para encontrar el máximo (mínimo) de una función unimodal en un intervalo.
