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

Является предельным случаем «Золотого сечения». В отличие от метода золотого сечения тем, что меняется интервал неопределенности от итерации к итерации.

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

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

Пошаговое описание алгоритма:

1) Произвести предварительный расчет количества итераций по формуле:

2) Найти x₁ и x₂, по формулам:

Вычислить f(x₁) и f(x₂).

Вычислить текущую погрешность . Принимаем k = 1.

3) Проверка на окончание поиска: если > , то принимаем k = k+1 и переходим к шагу 3, если k = N-2 переходим к шагу 4.

4) Переход к новому отрезку и новым пробным точкам. Если f(x₁)<f(x₂), то положить b = x₂, x­₂ = x₁, f(x₂) = f(x₁),

x₁ = и вычислить f(x₁), иначе - a = x₁, x­₁ = x₂, f(x₁) = f(x₂), x₂ = и вычислить f(x₂). Вычислить и перейти к шагу 2.

5) Окончание поиска:

Если f(x₂) f(x₁), то принимаем b = x₁, иначе a =x₁.

Тогда точка минимума будет равна

Плюсы: позволяет получить наименьший интервал неопределённости, количество итераций ограничено.

Минусы: надо знать Nколичество итераций, при большом N–число Фибоначчи большое.