2.1.5. Метод Фибоначчи.
В отличие от рассмотренных поисковых процедур в методе Фибоначчи используется числовая последовательность, поэтому общее число n вычислений функции заранее задается. Это объясняется тем, что точки, в которых производятся вычисления, определяются по зависящим от n формулам
xk
= ak
+ 
(bk - ak),
k = 1, …, n - 1;
yk
= ak
+ 
(bk - ak),
k = 1, …, n - 1.
где Fj =Fj-1 + Fj-2, j = 3, 4, …; F0=F1=1 называется последовательностью чисел Фибоначчи (1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233,...). В этом методе длина интервала неопределенности на k-й итерации сократится от b1 - a1 до (b1 - a1)/Fn. Поэтому для требуемой точности можно заранее рассчитать величину Fn и количество вычислений функции.
Алгоритм метода Фибоначчи.
Начальный этап. Задается конечная длина интервала l > 0 и константа различимости > 0, начальный интервал [a1, b1]. Выбрать число вычислений функции n так, чтобы Fn > (b1 - a1)/l. Вычислить x1 = a1 + (Fn-2/Fn)(b1 - a1), y1 = a1+(Fn-1/Fn)(b1-a1); f(x1); f(y1) . Принять k = 1 и перейти к основному этапу.
Основной этап. Шаг 1. Если f(xk) > f(yk), то перейти к шагу 2, если f(xk) f(yk), то к шагу 3.
Шаг 2. Принять ak+1 = xk; bk+1 = bk. Затем вычислить xk+1 = yk, yk+1 = ak+1 + (Fn-k-1/Fn-k)(bk+1 - ak+1). Если k = n - 2, то перейти к шагу 4.
Шаг 3. Принять ak+1 = ak; bk+1 = yk; xk+1 =ak+1 + (Fn-k-2/Fn-k)(bk+1 - ak+1). Если k = n - 2, то перейти к шагу 5, иначе вычислить f(xk+1) и перейти к шагу 4.
Шаг 4. Присвоить k = k + 1 и перейти к шагу 1.
Шаг 5. Принять xn = xn-1 и yn = xn+ . Если f(xn) > f(yn) , то an = xn и bn = bn‑1. При f(xn) f(yn) вычислить an = an-1 и bn = уn и остановиться.
Оптимальное решение содержится в интервале [an, bn].
Пример расчета экстремума функции методом Фибоначчи
Постановка задачи. Минимизировать f(x) = x2 - 5x+8 на интервале [-5, 5] с точностью l =0,25.
Результаты расчетов представлены в таблице 2.5.
Таблица 2.5
Расчет минимума функции f(x) = x2 - 5x+8 методом Фибоначчи.
№ |
аk |
bk |
xk |
yk |
f(xk) |
f(yk) |
|b-a| |
Критерий |
1 |
-5.000 |
5.000 |
-1.182 |
1.182 |
15.306 |
3.488 |
10.000 |
не достигнут |
2 |
-1.182 |
5.000 |
1.182 |
2.636 |
3.488 |
1.769 |
6.182 |
не достигнут |
3 |
1.182 |
5.000 |
2.636 |
3.545 |
1.769 |
2.843 |
3.818 |
не достигнут |
4 |
1.182 |
3.545 |
2.091 |
2.636 |
1.917 |
1.769 |
2.364 |
не достигнут |
5 |
2.091 |
3.545 |
2.636 |
3.000 |
1.769 |
2.000 |
1.455 |
не достигнут |
6 |
2.091 |
3.000 |
2.455 |
2.636 |
1.752 |
1.769 |
0.909 |
не достигнут |
7 |
2.091 |
2.636 |
2.273 |
2.455 |
1.802 |
1.752 |
0.545 |
не достигнут |
8 |
2.273 |
2.636 |
2.455 |
2.455 |
1.752 |
1.752 |
0.364 |
не достигнут |
9 |
2.455 |
2.636 |
2.455 |
2.636 |
1.752 |
1.769 |
0.182 |
достигнут |
Конечный интервал неопределенности равен [2,455; 2,636], длина которого l = 0,182. Середина интервала равна 2,545. Точка минимума х*=2,5.