next up previous contents
Next: Convergence considerations Up: The section search Previous: Fibonacci Search   Contents

The golden section search

Given a triplet $ (a,b,c)$ that brackets the minimum, we choose a new point x that defines a new bracketing triplet $ (a,x,b)$ or $ (b,x,c)$ according to the rule:

$\displaystyle \frac{x-b}{c-a} = 1 - 2\frac{b-a}{c-a}$    

This implies that $ \vert b-a\vert=\vert x-c\vert$, and that at each iteration the interval is scaled of the same ratio $ \lambda$.
Then we repeat the process with the new triplet. So the interval $ (a,c)$ is divided in two parts, a smaller and a larger, and the ratio between the whole interval and the larger is the same between the larger and the smaller, or in other words:

$\displaystyle \frac{1}{\lambda} = \frac{\lambda}{1-\lambda},$    

giving for $ \lambda$ the positive solution

$\displaystyle \lambda = \frac{\sqrt{5}-1}{2}.$    

This fraction is known as the golden-mean or golden-section, whose aesthetic properties come from ancient Pythagoreans.


next up previous contents
Next: Convergence considerations Up: The section search Previous: Fibonacci Search   Contents
marco+site@equars.com