Convergence considerations

All the three previous methods have a linear convergence, since at each iteration the ratio between the interval containing $\mathbf{x}^\star$ and the new smaller interval is:

$$0 \leq \frac{I_{k+1}}{I_k} \leq 1.$$

The asymptotic convergence rate is defined as

$$\lim_{k\rightarrow\infty}\frac{I_{k+1}}{I_k}.$$

For the dicotomic search, since $2I_{k+1} = I_k + \epsilon$, taking $\epsilon = 0$ we have

$$\lim_{k\rightarrow\infty}\frac{I_{k+1}}{I_k} = \frac{1}{2}.$$

For the Fibonacci search, first we must write the generic number of the Fibonacci sequence in a closed form:

$$f_k = \frac{1}{\sqrt{5}}\biggl[\left(\frac{1+\sqrt{5}}{2}\right)^{k+1}- \left(\frac{1-\sqrt{5}}{2}\right)^{k+1}\biggr].$$

then it can be proved that, taking $\epsilon = 0$:

$$\lim_{k\rightarrow\infty}\frac{I_{k+1}}{I_k} = \lim_{k\rightarrow\infty}\frac{f_{k+1}}{f_k} = \frac{\sqrt{5}-1}{2}$$

For the golden section search, as previously said $\frac{I_{k+1}}{I_k} = \lambda$, so

$$\lim_{k\rightarrow\infty}\frac{I_{k+1}}{I_k} = \lambda = \frac{\sqrt{5}-1}{2}.$$

Thus the convergence rate of the Fibonacci and the golden-section search are identical.