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

Ме́тод Фибона́ччи, разновидность одномерного поиска экстремума функции путём последовательного сужения интервала неопределённости. Единственное ограничение, налагаемое на исследуемую функцию

${\displaystyle f(x)\left(x\in \left(a_{0},b_{0}\right)\subset \mathbb {R} ^{\mathbf {1} }\right),}$

– требование строгой унимодальности на заданном интервале.

При последовательном сужении значения ${\displaystyle f(x)}$ вычисляются (или замеряются) в заранее ограниченном числе ${\displaystyle n}$ пробных точек. В результате получается последовательность сужающихся интервалов неопределённости, содержащих искомый экстремум:

${\displaystyle \left(a_{0},b_{0}\right)\supset \left(a_{1},b_{1}\right)\supset \ldots \supset \left(a_{n},b_{n}\right)}$.

Чтобы сузить интервал неопределённости для произвольной строго унимодальной функции, нужно знать не менее двух её пробных значений. В метод Фибоначчи внутри каждого текущего интервала неопределённости ${\displaystyle (a_{i},b_{i})}$ подбираются ровно две пробные точки симметрично от середины интервала. Далее, от одной из пробных точек отбрасывается конец интервала с наихудшими значениями ${\displaystyle f(x)}$. Получается ${\displaystyle (a_{i+1},b_{i+1})}$, где в дополнение к оставшейся старой пробной точке симметрично строится новая. Отсюда для длин интервалов

${\displaystyle \Delta _{i}=b_{i}-a_{i}}$

следует рекуррентное уравнение

${\displaystyle \Delta _{i}=\Delta _{i+1}+\Delta _{i+2}}$.

(Помимо прочего выше предполагалось, что выполнено условие перекрывания ${\displaystyle \Delta _{1}<2/3\cdot \Delta _{0}}$.)

Решение уравнения при условии ${\displaystyle \Delta _{n+1}=\Delta _{n+2}}$ даёт

${\displaystyle \Delta _{i}={\frac {F_{n+3-i}}{F_{n+2}}}\Delta _{0},\quad i=2,\ldots ,n,}$

где ${\displaystyle F_{(.)}}$ – числа Фибоначчи.

Точка экстремума ${\displaystyle x_{\text{opt}}\approx \left(a_{n}+b_{n}\right)/2}$.

В простейшем варианте метод Фибоначчи (когда предполагается, что пробные точки и пробные значения ${\displaystyle f(x)}$ определяются абсолютно точно), чтобы сузить исходный интервал неопределённости с ${\displaystyle \Delta }$ до ${\displaystyle \varepsilon }$, надо взять число ${\displaystyle n}$ пробных точек из неравенства ${\displaystyle 2\Delta /\varepsilon \leqslant F_{n+2}}$. С учётом поправок на точность определения значений функции вышеприведённая оценка несколько усложняется.

Существует предел

${\displaystyle \tau =\lim _{n\rightarrow \infty }{\frac {F_{n}}{F_{n+1}}}={\frac {{\sqrt {5}}-1}{2}}=0,618033989\ldots \!{\text{.}}}$

Это даёт основание ввести метод золотого сечения – такой вариант метода Фибоначчи, где ${\displaystyle \forall _{i}\Delta _{i+1}=\tau \Delta _{i}}$, то есть пробные точки осуществляют золотое сечение текущего интервала. Преимущество последнего метода заключается в том, что число пробных точек заранее не планируется.

Разработаны модификации метода Фибоначчи для нефинитных функций, для сокращения вычислений при равенстве ${\displaystyle f(x)}$ в двух пробных точках, для повышения устойчивости счёта и др.

Метод Фибоначчи значительно превосходит по эффективности дихотомию (см. в статье Метод половинного деления). Однако для оптимизации дифференцируемых функций метод Фибоначчи малоцелесообразен (см. в статьях Метод спуска, Максимизация и минимизация функций).