Последовательный поиск. Метод Фибоначчи

Числа Фибоначчи: , , , . Последовательность чисел Фибоначчи: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …

Метод Фибоначчи, как и метод половинного деления, состоит в построении множества (N -1) вложенных отрезков локализации, пробные точки делят предыдущий отрезок в отношении, которое определяется числами Фибоначчи:

, , , , ,

если , то и ,

если же , то и .

Здесь важно, что на очередном шаге итераций точка совпадает с или с . Поэтому на очередном шаге достаточно вычислить значение функции только в одной недостающей точке.

При этом через (N -1) шаг и . Определив из этого условия значение N, выполняем последовательный поиск методом Фибоначчи. Заметим, что в методе Фибоначчи на каждом очередном шаге отрезок локализации уменьшается в : или , т.е. .

За (N -1) шаг отрезок локализации уменьшится в раз, и приближенное значение точки минимума — середина последнего отрезка локализации. Действительно,

.

Эффективность методов прямого поиска можно сравнивать по тому, на сколько уменьшается отрезок локализации на одном шаге, по количеству вычислений функции за N шагов, по величине гарантированной погрешности:

Название	Длина отрезка локализации	Гарантированная погрешность
Оптимальный пассивный поиск
Половинное деление
Фибоначчи
Золотое сечение

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

Название
Оптимальный пассивный поиск
Половинное деление
Фибоначчи
Золотое сечение

Дата добавления: 2014-01-07