Метод Фибоначчи

В методе Фибоначчи точка деления интервала исследования определяется с каждым новым расчётом (в методе дихотомии необходимо на каждом шаге выполнять два расчёта). В интервал исследования попадет предыдущий расчёт и для продолжения поиска достаточно произвести расчёт симметрично имеющемуся.

Допустим, задано число расчётов (шагов) N. Необходимо их произвести так, чтобы интервал, в котором лежит оптимум, был минимальным. Числа Фибоначчи, используемые в этом методе, определяются следующим образом:

F_N=F_N-1+F_N-2

F₀=F₁=1

Алгоритм метода Фибоначчи состоит из следующих этапов:

1) Изменяют масштаб исходного интервала, в котором лежит оптимум. В качестве единицы измерения принимают 1=X₀/F_N, или если задана длина l, в котором лежит оптимум, находят его на исходном интервале длиной X₀. Для этого, разделив X₀ на 1, находят ближайшее большее число Фибоначчи F_N,
а по нему определяют N – число необходимых расчётов для определения интервала.

2) Расставляют первые две точки и на интервале исследования X₀ на расстоянии F_N-2 от конца b.

3) Вычисляют значение целевой функции в этих точках для сужения интервала исследования. Пусть > , тогда интервал [ , F_N] исключается из рассмотрения.

4) На новом интервале исследования снова расставляют две точки и , но в одной из них уже известно значение целевой функции = .

5) Переходят к этапу 3 и т.д., пока не достигают искомого интервала, в котором находится значение переменной, максимизирующее её целевую функцию.

На рис. 6 показан процесс сужения интервала исследования:

Рис. 6. Процесс сужения интервала исследования.

Последний N–й расчёт определяет интервал длиной l, в котором находится экстремум целевой функции.