# Golden search

## 1 Idea

The idea is quite similar to the dichotomy method. There are two golden points on the line segment (left and right) and the insightful idea is, that on the next iteration one of the points will remain the golden point.

## 2 Algorithm

```
def golden_search(f, a, b, epsilon):
= (sqrt(5) + 1) / 2
tau = a + (b - a) / tau**2
y = a + (b - a) / tau
z while b - a > epsilon:
if f(y) <= f(z):
= z
b = y
z = a + (b - a) / tau**2
y else:
= y
a = z
y = a + (b - a) / tau
z return (a + b) / 2
```

## 3 Bounds

|x_{k+1} - x_*| \leq b_{k+1} - a_{k+1} = \left( \frac{1}{\tau} \right)^{N-1} (b - a) \approx 0.618^k(b-a),

where \tau = \frac{\sqrt{5} + 1}{2}.

- The geometric progression constant
**more**than the dichotomy method - 0.618 worse than 0.5 - The number of function calls
**is less**than for the dichotomy method - 0.707 worse than 0.618 - (for each iteration of the dichotomy method, except for the first one, the function is calculated no more than 2 times, and for the gold method - no more than one)