Método de
Fibonacci
Ejemplo [Link]ón del Método de Fibonacci
Minimizar la función 𝑓 𝑥 = (𝑥 − 4)2 haciendo una búsqueda en el intervalo
0,9 . Usar 2 iteraciones.
Solución
Para n-2 iteraciones se requiere de n-4 evaluaciones de función. Sabemos
que 𝜏𝑛−2 = 𝜏2 = 1Τ2 a partir de lo cual se construye la secuencia de valores de
𝜏𝑖 que se van a usar en cada iteración i:
𝐹𝑛−1
𝐹0 = 0 𝜏0 = 𝜏𝑛−𝑛 =
𝐹1 = 1 𝐹𝑛 3
𝐹4−1 𝐹3
𝐹2 = 2 ൗ𝐹 =
𝜏0 = 𝜏4−4 = 4 5
𝐹3 = 3 𝐹4
𝐹3
𝐹4 = 5 𝜏0 = 𝜏0 =
4
𝐹𝑛−2
𝜏1 = 𝜏𝑛−(𝑛−1) = 2
𝐹𝑛−1 𝐹3
ൗ𝐹 =
𝐹4−2 4 3
𝜏1 = 𝜏4−(4−1) =
𝐹4−1
𝐹2
𝜏1 = 𝜏4−3 =
𝐹0 = 0 𝐹3
𝐹1 = 1
𝐹𝑛−3
𝐹2 = 2 𝜏2 = 𝜏𝑛−(𝑛−2) =
𝐹3 = 3 𝐹𝑛−2
𝐹4−3 𝐹1 1
𝐹4 = 5 𝜏2 = 𝜏4−(4−2) = ൗ𝐹 =
𝐹4−2 2 2
𝐹1
𝜏2 = 𝜏4−2 =
𝐹2
Iteración i: 0 1 2
𝜏𝑖 3ൗ 2ൗ 1ൗ
5 3 2
Iteración 0
Se colocan los puntos iniciales
𝜏0 = 3ൗ5 𝑏0 = 9
“ 𝑎0 , 𝑏0 = 0,9 ;
𝑙0 = 𝑏0 − 𝜏0 𝑏0 − 𝑎0 = 9 − 3ൗ5 9 − 0 = 3.6
𝜏0 𝑟0 = 𝑎0 + 𝜏0 𝑏0 − 𝑎0 = 0 + 3ൗ5 9 − 0 = 5.4
𝑏0 = 9 = 3ൗ5
La evaluación de la función en estos puntos resulta en 𝑓 𝑥 = (𝑥 − 4)2
𝑎0 = 0 𝑎0 = 0 𝑓 𝑙0 = (3.6 − 4)2 = 0.16
𝑓 𝑟0 = (5.4 − 4)2 = 1.96
Suponiendo que la función es unimodal, rechazamos
la región comprendida al lado derecho del punto 𝑟0 ,
como se muestra esquemáticamente
𝑎0 = 𝑙0 = 𝑟0 = 𝑏0 =
Iteración 1
◉El intervalo reducido y el ◉El punto que quedo sin ◉El nuevo punto izquierdo es
valor de 𝜏 a usarse en esta eliminar en la iteración
iteración son: anterior, que era punto
izquierdo, se transforma
en el punto derecho para 𝑙1 = 𝑏1 − 𝜏1 𝑏1 − 𝑎1
𝑎1 , 𝑏1 = 0,5.4 : esta iteración 2
= 5.4 − 5.4 − 0
3
𝜏1 = 2ൗ3 = 1.8
𝑙0 ⟹ 𝑟1 = 3.6
◉El siguiente esquema muestra
el resultado para esta iteración:
◉Y la función en este punto es
𝑓 𝑙1 = (1.8 − 4)2 = 4.48
Iteración 2
Esta es la última iteración que se
ha fijado, en la cual el intervalo
remanente es:
Con
𝑎2 , 𝑏2 = 1.8, 5.4 : 𝑟1 ⟹ 𝐼2 = 3.6
Como se trata de la última iteración, el nuevo punto de colocación r2 debe coincidir con el
punto I2, por la forma en que el método de Fibonacci está diseñado:
𝑟2 = 𝑎2 + 𝜏2 𝑏2 − 𝑎2 = 1.8 + 1ൗ2 5.4 − 1.8 = 3.6
En esta última iteración podemos eliminar la mitad de la región remanente evaluando la
función con el punto 𝑙2 + 𝜀, donde 𝜀 es un número suficientemente pequeño. Tomando
𝜀 =0.001
𝑓 3.61 = (3.61 − 4)2 = 0.1521
Debido a que la función hacia el lado derecho del punto final y tenemos
un problema de minimización, entonces se rechaza la región del lado
izquierdo de ese punto
Conclusión
La aplicación del método de Fibonacci con 2
iteraciones termina con una aproximación del
óptimo 𝑥 ∗ = 3.6. Se detecta que el óptimo esa
comprendido entre 3.6 y 5.4. La solución
exacta implica 𝑥 ∗ = 4.
