Алгоритм

1) На начальном этапе выбирается отрезок [ a, b ], на котором ищется минимум.

2) Внутри отрезка выбирается точка c, делящая его в золотом отношении, то есть так, что отношение большей части отрезка к меньшей равно отношению всего отрезка к его большей части:

с = a + (b - a)/ φ

3) Определяется положение дополнительной точки x, которая расположена симметрично точке c относительно центра отрезка:

x = a + b - c

4) Вычисляются значения функции f(a), f(b), f(c), f(x).

5) Значения функции сравниваются и определяется новое положение интервала поиска (см. рис 3):

a. Если c > x:

i. Если f(x) < f(c), то новый отрезок: [ a, c ]

ii. Иначе новый отрезок: [ x, b ]

b. Если c < x: (эта ситуация может возникнуть на втором шаге и далее)

i. Если f(x) < f(c), то новый отрезок: [ c, b ]

ii. Иначе новый отрезок: [ a, x ]

6) Если длина отрезка стала меньше заранее заданной точности, алгоритм завершается, иначе итерация повторяется с шага 2.

Рис. 3. Метод Фибоначчи. Показан случай, когда f(x)<f(c).

Особенностью метода Фибоначчи, позволяющей экономить дорогостоящие вычисления целевой функции f(x), является то, что, начиная со второго шага, значение функции в точке c известно с предыдущего шага, остаётся вычислить только значение в отражённой точке x.

Например, на рис.3 f(x)<f(c), поэтому новым интервалом поиска становится интервал [ a, c ]. Точка x в этом случае оказывается внутри нового интервала и делит его в золотом отношении, то есть она становится новой точкой c.

Длина интервала поиска на следующем шаге всегда в φ = 1,68… раз меньше длины на предыдущем шаге. Таким образом, за одно вычисление целевой функции метод Фибоначчи увеличивает точность в 1,68… раз, что больше чем соответствующий показатель метода дихотомии (1.41…).