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

Метод Фибоначчи эффективнее метода дихотомии, так как разбиение отрезка производится таким образом, что на каждой итерации требуется вычислять не два значения f(x₁) и f(x₂), а лишь одно.

Метод Фибоначчи основан на использовании чисел Фибоначчи, задаваемых рекуррентным соотношением

F_n = F_n-1 + F_n-2 (n  2) (1.6)

с начальными значениями F₀ = 1, F₁ = 1.

Этот метод был предложен в 1953 г. Кифером.

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

n	0 1 2 3 4 5 6 7 8 9 10 11 …
Fn	1 1 2 3 5 8 13 21 34 55 89 144 …

Метод Фибоначчи состоит из n шагов.

Положим вначале a₀ = a, b₀ = b.

На k-ом шаге, k =0, 1, … , n – 1, определим точки x и x из условия

x = a_k + (b_k – a_k), x = a_k + (b_k – a_k). (1.7)

Формулы (1.7) являются основными расчетными формулами метода Фибоначчи

После этого так же, как и в методе дихотомии, определяют новый, меньший отрезок локализации [a_k+1, b_k+1] по тому же правилу:

если f(x )  f(x ), то a_k+1 = a_k, b_k+1 = x ;

если f(x ) > f(x ), то a_k+1 = x , b_k+1 = b_k.

Важно, что одна из пробных точек x , x станет пробной точкой на новом отрезке локализации, т. е. совпадет с одной из точек x , x .

Поэтому на каждой итерации достаточно определить только одно значение f(x), так как другое уже найдено на предыдущей итерации.

В конце вычислений можно взять в качестве приближенного значения x^* = x .

После выполнения n итераций погрешность удовлетворяет следующему неравенству:

_n = < . (1.8)

Следовательно, если задана требуемая точность , число итераций n определяется из условия <  или

F_{n +1} > . (1.9)

Заметим, что из (1.9) следует, что число итераций, необходимое для удовлетворения заданной точности  , зависит только от длины отрезка b – a и точности  и не зависит от вида функции f(x).

Алгоритм 1.3 (Алгоритм метода Фибоначчи).

Шаг 1. Ввести исходные данные: a, b, . Определить число итераций n из условия (1.9). Ввести числа Фибоначчи F₀, F₁, F₂, … , F_{n +1}.

Шаг 2. Положить k = 0 и определить x₁ и x₂ по формулам (1.7).

Шаг 3. Вычислить f(x₁) и f(x₂).

Шаг 4. Проверить критерий окончания вычислений: k = n . Если k < n, перейти к шагу 5, иначе – к шагу 6.

Шаг 5. Перейти к новому отрезку локализации и новым пробным точкам. Если f(x₁)  f(x₂), то положить b = x₂, x₂ = x₁, f(x₂) = f(x₁), x₁= a + (b – a) и вычислить f(x₁). Иначе положить a = x₁, x₁ = x₂, f(x₁) = f(x₂), x₂ = a + (b – a) и вычислить f(x₂).

Положить k = k +1 и перейти к шагу 4.

Шаг 6. Положить x^*  x₁. Вычислить f ^* f(x^*).

Пример 1.4.

Методом Фибоначчи решим задачу, рассмотренную ранее: f(x) = x⁴ + e ^–x  min, x  [0, 1],  = 0.1.

Условие (1.8) для нашей задачи имеет вид

F_{n +1} > = 5.

Первым среди чисел Фибоначчи, для которого выполняется это условие является число F₅ = 8, т.е. n +1 = 5, n = 4.

Результаты вычислений для четырех итераций приведены в табл. 1.5.

Таблица 1.5

k	a	b	b – a	x1	x2	f(x1)	f(x2)	Сравнение f(x1) и f(x2)
0 1 2 3	0 0.375 0.375 0.375	1 1.000 0.75 0.625	1 0.625 0.375 0.25	0.375 0.625 0.5 0.5	0.625 0.75 0.625 0.5	0.707 0.688 0.669 0.669	0.688 0.789 0.688 0.669	f(x1) > f(x2) f(x1) < f(x2) f(x1) < f(x2)

Таким образом, x^*  0.5 и f(x^*)  0.669.