Методы Оптимизации Систем Автоматизированного Проектирования

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

Постановка задачи.

Тебуется найти безусловный минимум функции f(x) одной переменной, т.е. такую точку , что .

В методе Фибоначчи реализована стратегия, обеспечивающая максимальное гарантированное сокращение интервала неопределенности при заданном количестве вычислений функции. Эта стратегия опирается на числа Фибоначчи.

Определение. Числа Фибоначчи определяются следующим образом:
.
Последовательность чисел Фибоначчи имеет вид 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233,… .

Стратегия поиска.

Метод относится к последовательным стратегиям. Задается начальный интервал неопределенности и количество N вычислений функции. Алгоритм основан на анализе величин функции в двух точках. Точки вычисления функции находятся с использованием последовательности из N+1 чисел Фибоначчи. Как и в методе золотого сечения, на первой итерации требуется два вычисления функции, а на каждой последующей итерации, требуется только одно новое вычисление функции. Поиск заканчивается, когда длина текущего интервала неопределенности оказывается меньше установленной величины.

Алгоритм.

Задать начальный интервал неопределенности , ], допустимую длину конечного интервала l > 0 и константу различимости .

Найти количество N вячислений функции как наименьшее целое число, при котором удовлетворяется условие , и числа Фибоначчи .

Вычислить значения :
.

Вычислить , .
Шаг 6. Сравнить с
а) если , положить

Перейти к шагу 7;

Стр.: ..., 2, 3, 4