Как работает метод золотого сечения в тернарном поиске?

Метод золотого сечения в тернарном поиске позволяет улучшить скорость работы алгоритма за счёт того, что на каждой итерации функция вычисляется только в одной точке (за исключением первой итерации, когда набор данных нужно разделить на три части). e-postulat.ru neerc.ifmo.ru

Алгоритм поиска состоит из следующих шагов: e-postulat.ru

1. Определение границ поиска l и r, а затем вычисление точек x1 и x2 по определённым формулам, где используется золотое число. e-postulat.ru
2. Вычисление значений функции в точках x1 и x2 и их сравнение. e-postulat.ru
3. Изменение границ поиска в зависимости от сравнения значений функции: e-postulat.ru

• Если f(x1) > f(x2), то левая граница сдвигается к x1, а после x2 вычисляется по той же формуле. e-postulat.ru
• Если же f(x1) < f(x2), то правая граница сдвигается к x2, а x1 вычисляется по формуле, которая указана в первом шаге. e-postulat.ru

На каждой итерации область поиска уменьшается в золотое число раз. e-postulat.ru Таким образом, поиск с помощью золотого сечения требует меньше приблизительно в 2,37 раз вычислений, чем в троичном поиске. e-postulat.ru