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

Метод Фибоначчи является наилучшим (в смысле максимального уменьшения длины отрезка локализации) среди активных мето­дов поиска.

Согласно методу Фибоначчи, на первом шаге (первой ите­рации) проводятся два вычисления значений в точках и (причем расположенных симметрично относи­тельно середины отрезка . По результатам вычислений одна из частей отрезка ( либо ) отбрасывается, при этом одна из точек (соответственно либо ) уже проведен­ных вычислений остается внутри отрезка . На каждом последующем шаге (последующей итерации) точка очередного вычисления выбирается симметрично оставшейся точки. Таким образом, на первой итерации проводятся два вычисления значе­ний , на каждой последующей - одно вычисление. Поэтому при заданном количестве вычислений N будет выполнено шагов (итераций).

При вычислении и , , используются числа Фибоначчи, определяемые следующим образом:

Условием окончания вычислений является выполнение за­данного количества вычислений N.

Недостатком метода Фибоначчи является то, что должно быть задано количество вычислений N.