Постановка задачи. Метод Фибоначчи применяется для численного поиска безусловного экстремума

Метод Фибоначчи применяется для численного поиска безусловного экстремума. Требуется найти x для f(x) на интервале [a;b], где существует экстремум данной функции, x должен соответствовать точке экстремума.

Чтобы построить метод одномерной минимизации, который должен работать по принципу последовательного сокращения интервала неопределенности, нужно задать правило выбора двух внутренних точек на каждом интервале. Для более эффективного решения поставленной задачи необходимо, чтобы одна из двух точек являлась внутренней для следующего интервала. При выполнении этого условия количество вычислений функции сократиться вдвое, в результате одна итерация потребует расчета только одного нового значения функции. Метод Фибоначчи позволяет сокращать интервал неопределенности при заданном количестве вычислений функций. Сокращение интервалов опирается на числа Фибоначчи.

Как правило метод Фибоначчи применяется для унимодальных функций. Это класс функций, которые достигают своего экстремума x* на интервале [a0;b0], причем этот экстремум единственный. При этом функция слева от x* убывает, а справа возрастает.

Если a0<y<z<x*, то f(y)>f(z), но если x*<y<z<b0, то f(y)<f(z) (рис1.а).

Рис1.Функция унимодальная.

Можно отметить следующий факт: что непрерывная строго выпуклая вниз функция является унимодальной. Однако определению удовлетворяют функции не являющиеся непрерывными и унимодальными(рис.1б).

Еще раз сформулируем поставленную задачу. У нас есть функция f(x) которая имеет экстремум на заданном интервале [a0;b0], необходимо найти экстремум этой функции x* на этом интервале не более чем за N шагов.

________________________________________________________________