Метод Фибоначчи
Обладая высокой эффективностью, метод «золотого сечения» не является оптимальным при заданном числе вычислений целевой функции. Если исследователю заранее известно, что он сможет использовать не более какого-то определенного числа значений целевой функции, то он, конечно, предпочтет метод дихотомии, который позволяет уменьшать интервал неопределенности сразу вдвое, а не в 1/0,618 раза, как метод «золотого сечения». Если же есть возможность в процессе поиска оптимума изменять расположение точек, в которых вычисляются значения целевой функции, то можно соединить преимущества симметричного расположения точек, о которых говорилось выше, с преимуществами метода дихотомии и построить оптимальный алгоритм поиска. Пусть ZN — длина интервала неопределенности после N-го шага. Условие симметрии имеет вид
а условие вычисления последнего значения целевой функции на полученном методом дихотомии интервале 5 записывается в виде ZN-1 = 2ZN-1 - ε.
Из этих двух соотношений, возвращаясь назад, можно найти требуемую величину любого промежуточного интервала неопределенности и тем самым найти точки, в которых вычисляется целевая функция. Например,
Общее выражение для произвольного интервала неопределенности имеет вид
В общем случае величину последнего интервала неопределенности можно выразить в виде
В пределе при ε → 0 нижняя граница определяется величиной наименьшего интервала неопределенности, которую можно получить при заданном числе вычислений целевой функции.
Используя метод Фибоначчи, прежде всего решают, сколько значений целевой функции N может быть использовано. Затем, зная величину интервала неопределенности, распределяют в нем значения N. Так как Z1=Z0=1, то сначала вычисляют целевую функцию в точках, расположенных на расстояниях Z2 от противоположных концов исходного интервала. В этом случае
На следующем шаге выбирают величину смещений Z3 относительно Z2. В дальнейшем сохраняют подходящее значение интервала и повторяют процесс до тех пор, пока не будет вычислено N-e значение целевой функции.