double arrow
Алгоритм

3

1) На начальном этапе выбирается отрезок [a,b] , на котором ищется минимум.

2) Внутри отрезка выбирается точка c, делящая его в золотом отношении, то есть так, что отношение большей части отрезка к меньшей равно отношению всего отрезка к его большей части:

с = a + (b-a)/ φ

3) Определяется положение дополнительной точки x, которая расположена симметрично точке c относительно центра отрезка:

x = a + b - c

4) Вычисляются значения функции f(a), f(b), f(c), f(x).

5) Значения функции сравниваются и определяется новое положение интервала поиска (см. рис 3):

a. Если c>x:

i. Если f(x) < f(c), то новый отрезок: [a, c]

ii. Иначе новый отрезок: [x, b]

b. Если c<x: (эта ситуация может возникнуть на втором шаге и далее)

i. Если f(x) < f(c), то новый отрезок: [c, b]

ii. Иначе новый отрезок: [a, x]

6) Если длина отрезка стала меньше заранее заданной точности, алгоритм завершается, иначе итерация повторяется с шага 2.

Рис. 3. Метод Фибоначчи. Показан случай, когда f(x)<f(c).

Особенностью метода Фибоначчи, позволяющей экономить дорогостоящие вычисления целевой функции f(x), является то, что, начиная со второго шага, значение функции в точке c известно с предыдущего шага, остаётся вычислить только значение в отражённой точке x.

Например, на рис.3 f(x)<f(c), поэтому новым интервалом поиска становится интервал [a,c]. Точка x в этом случае оказывается внутри нового интервала и делит его в золотом отношении, то есть она становится новой точкой c.

Длина интервала поиска на следующем шаге всегда в φ = 1,68… раз меньше длины на предыдущем шаге. Таким образом, за одно вычисление целевой функции метод Фибоначчи увеличивает точность в 1,68… раз, что больше чем соответствующий показатель метода дихотомии (1.41…).

3





Сейчас читают про: