Fibonacci Search Algorithm Can someone show me an example of using this method for 'find the minimum of $$F(x) = x^2 - 6x + 2 \; \text{ on } [0,10] $$' ? 
I'm trying to follow the algorithm detailed above, but I don't understand it. How do they know at what $k$ to stop at? Why are they stopping at $k = 2$?
 A: Notice in the algorithm they specified, they have:
$$\Delta = \dfrac{\lambda_{k-2}}{\lambda_k}(b-a)$$
where $\lambda$ is the $n^{th}$ Fibonacci number.
What happens when $k = 2$? We have:
$$\Delta = \dfrac{\lambda_{2-2}}{\lambda_2}(b-a) = \dfrac{\lambda_{0}}{\lambda_2}(b-a) = \dfrac{1}{2}(b-a)$$
Thus, we have gotten to the last $\Delta$ evaluation we can do, so we are left with doing one last function evaluation to choose our last range which contains the minimum value of $f$ at $\hat x$.
The way they wrote this algorithm is a bit difficult to read and other authors use a different approach for the number of iterations.
I rewrote the algorithm to one that is easier to follow (I hope):


*

*Step 1: Choose $f(x), a, b$

*Step 2: Choose a desired accuracy $\epsilon$ and calculate the number of steps $n = \dfrac{b-a}{\epsilon}$

*Step 3: $k = n$

*Step 4: $\Delta = \dfrac{\lambda_{k-2}}{\lambda_k}(b-a)$

*Step 5: Set $ap = a + \Delta$ and $bp = b - \Delta$

*Step 6: If $f(ap) \ge f(bp)$, set $a = ap, b = b$, else set $a = a, b = bp$.

*Step 7: $k = k - 1$

*Step 8: If $k > 2$, repeat from Step 4 through Step 7.

*Step 9: Since $k = 2$, If $f(a) \ge f(b)$, set $ap = \dfrac{1}{2}(a+b) - \epsilon, a = ap$, else set $bp = \dfrac{1}{2}(a+b) + \epsilon, b = bp$

*Step 10: Print $(a, b)$

*Step 11: Set the minimum point as $\hat x = \dfrac{1}{2}(a + b)$


For the example you gave, you should find $\hat x = 3 ~\pm ~\epsilon$
Update Note that a better approach to calculating the number of iterations is to find $k$ such that:
$$\lambda_{k+1} < \dfrac{b-a}{\epsilon}$$
Set $n = k$.
