Лекция: Метод Фибоначчи
Является предельным случаем «Золотого сечения». В отличие от метода золотого сечения тем, что меняется интервал неопределенности от итерации к итерации.
Является один из наиболее эффективных методов поиска минимума функции одной переменной. На первой итерации вычисляются два значения функции, на следующих по одному. В методе используется последовательность чисел Фибоначчи, заданная с помощью рекуррентой формулы:
В силу свойств чисел Фибоначчи количество итераций строго ограничено. Это удобно, если сразу задано количество возможных обращений к функции.
Пошаговое описание алгоритма:
1) Произвести предварительный расчет количества итераций по формуле:
2) Найти x1 и x2, по формулам:
Вычислить f(x1) иf(x2).
Вычислить текущую погрешность. Принимаем k = 1.
3) Проверка на окончание поиска: если >, то принимаем k = k+1 и переходим к шагу 3, если k = N-2 переходим к шагу 4.
4) Переход к новому отрезку и новым пробным точкам. Если f(x1)<f(x2), то положить b = x2, x2 = x1, f(x2) = f(x1),
x1 = и вычислить f(x1), иначе — a = x1, x1 = x2, f(x1) = f(x2), x2 = и вычислить f(x2). Вычислить и перейти к шагу 2.
5) Окончание поиска:
Если f(x2) f(x1), то принимаем b = x1, иначе a =x1.
Тогда точка минимума будет равна
Плюсы:позволяет получить наименьший интервал неопределённости, количество итераций ограничено.
Минусы: надо знать Nколичество итераций, при большом N–число Фибоначчи большое.