1. МЕТОДЫ ОДНОМЕРНОЙ ОПТИМИЗАЦИИ

1.4. Метод поиска с использованием чисел Фибоначчи [1,3-6]

Последовательность чисел Фибоначчи определяется соотношением:

(8)

и имеет вид:

i	0	2	2	3	4	5	6	7	8	9	10	11	12
Fi	1	1	2	3	5	8	13	21	34	55	89	144	233	и т.д.

Подобно методу золотого сечения процедура поиска с использованием чисел Фибоначчи требует два вычисления функции на первом шаге, а на каждом последующем - только по одному. Однако, в отличие от метода золотого сечения, в этой процедуре общее число S вычисления функции должно быть выбрано заранее. Кроме того, сокращение интервала неопределенности не остается постоянным, а меняется от шага к шагу: на k-ом шаге длина интервала неопределенности сжимается с коэффициентом

Первые два вычисления проводятся в точках:

расположенных симметрично относительно середины отрезка [a,b]. Если f(x₁)<f(x₂), то новым отрезком локализации минимума является [a, x₂], в случае f(x₁)≥f(x₂)-[x₁, b]. Каждая следующая точка выбирается симметрично относительно середины полученного отрезка к лежащей внутри этого отрезка точке уже проведенного вычисления (x₁ или x₂). При этом любая внутренняя точка делит отрезок локализации в отношении, двух последовательных чисел Фибоначчи.

Взаимное расположение точек первых трех вычислений в случае f(x₁)<f(x₂) показано на рис. 7.

Первый шаг
Второй шаг

Рис. 7.

После (S-1)-го шага точка проведенного вычисления оказывается в середине отрезка локализации. Точка последнего, S-го, шага выбирается на расстоянии δ от середины этого отрезка, где δ - заранее фиксированное малое положительное число (константа различимости).

После S вычислений функции длина отрезка локализации составляет (с точностью до δ):

(9)

Сравнение (9) и (7) показывает, что при одном и том же S метод Фибоначчи дает меньший интервал неопределенности, чем метод золотого сечения, т.е. является более эффективным. Однако для достаточно больших S значение стремится к (0,618)^S-1 , так что эти методы становятся почти идентичными.

В том случае; когда при использовании метода Фибоначчи задан .конечный интервал неопределенности ε, число S можно определить из условия:

(10)

Алгоритм минимизации функции f(x) с использование, чисел Фибоначчи.

1. По заданной точности рассчитывается вспомогательное число

2. Для полученного значения N находится такое число Фибоначчи F_S, для которого выполняется неравенство:

3.

4. По формуле (9) определяется длина конечного интервала неопределенности l.

5. Вычисляются значения x₁=a+l∙F_S-2, x₂=b-l∙F_S-2.

6. В зависимости от соотношения f(x₁) и f(x₂) выбирается новый интервал локализации минимума.

7. Внутри полученного интервала находится новая точка (x₁ или x₂), симметричная к уже имеющейся точке и отстоящая от конца интервала на величину l∙F_S-1-k , где k - номер шага. В этой точке рассчитывается значение f(x). Затем вычисления повторяются, начиная с пункта 5, до тех пор, пока k не станет равно S-1. Тогда переходят к пункту 7.

8. Полагают x₂=x₁+δ, находят f(x₂). Если f(x₂)>f(x₁)то минимум реализуется на интервале (a, x₁), в противном случае - на интервале (x₁ , b).

Блок-схема описанного алгоритма приведена на рис.8.

Рис. 8. Блок – схема алгоритма поиска минимума функции f(x) использованием чисел Фибоначчи

Пример.

С помощью метода Фибоначчи найти минимум функции f(x)=x²+2x на интервале (-3,5). Длина конечного интервала неопределенности не должна превосходить 0,2.

Решение.

Примем δ=0,01.

Найдем необходимое число вычислений функции:

F8<40<F9

Итак, S =9.

Первый шаг. a=-3; b=5.

x₁=a+l∙F₇= 0.0555; f(x₁) =0,1141;

x₂ = b-l∙F₇=1,9445; f(x₂) =7,6701;

f(x₁)<f(x₂). Новый отрезок [-3; 1,9445].

Второй шаг. a=-3; b=5.

x₁=a+l∙F₆= -1.1085; f(x₁) =-0,9882;

x₂ =0,0555; f(x₂) =0,1141;

f(x₁)<f(x₂). Новый отрезок [-3; 0,0555].

Дальнейшие расчеты приведены в таблице 2. Значения f(x) вычисленные на каждом шаге, помечены звездочкой.

Таблица 2
№ шага	a	b	b-a	x1	x2	f(x1)	f(x2)
1	-3,000	5,000	8,000	0,0555	1,9445	0,1141^*	7,6701^*
2	-3,000	1,9445	4,9445	-1,1085	0,0555	-0,9882^*	0,1141
3	-3,000	0,0555	3,0555	-1,8360	-1,1085	-0,3011^*	-0,9882
4	-1,8360	0,0555	1,8915	-1,1085	-0,6720	-0,9882	-0,8924^*
5	-1,8360	-0,6720	1,1640	-1,3995	-1,1085	-0,8404^*	-0,9882
6	-1,3995	-0,6720	0,7275	-1,1085	-0,9630	-0,9882	-0,9986^*
7	-1,1085	-0,6720	0,4365	-0,9630	-0,8175	-0,9986	-0,9667^*
8	-1,1085	-0,8175	0,2910	-0,9630	-0,9630	-0,9986	-0,9986
9	-1,1085	-0,9630	0,1455	-0,9630	-0,9530	-0,9986	-0,9978^*

Поскольку для k = 9 f(x₁)<f(x₂), конечный интервал неопределённости равен (-1,1085; -0,9630), длина его составляет 0,1455. В качестве приближенного значения точки минимума выберем середину этого отрезка -1,0358; f(-1,0358) = -0,9987. Напомним, что при использовании, метода золотого сечения при S = 9 длина интервала неопределенности была равна 0,176.