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

Прежде чем изложить метод введем определение чисел Фибоначчи [11].

Определение 2. Числа Фибоначчи определяются по формуле

Последовательность чисел Фибоначчи имеет следующий вид:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …..

Метод Фибоначчи относится к последовательным стратегиям. Задается начальный интервал неопределенности и количество N вычислений функции. Алгоритм уменьшения интервала опирается на анализ значений функции в двух точках. Точки вычисления функции находятся с использованием последовательности из N+1 чисел Фибоначчи. Как в методе «золотого» сечения на первой итерации требуются два вычисления функции, а на каждой последующей – только по одному. Условия окончания процесса поиска стандартные: поиск заканчивается, когда длина текущего интервала неопределенности оказывается меньше установленной величины.

Алгоритм метода Фибоначчи [8].

Шаг 1. Задать начальный интервал неопределенности ,  - допустимую длину конечного интервала,  - константа различимости.

Шаг 2. Найти количество вычислений функции , как наименьшее целое число, при котором удовлетворяется условие; и числа Фибоначчи , ,...., .

Шаг 3. Положить .

Шаг 4. Вычислить

, 

Шаг 5. Вычислить J(y_k), J(z_k).

Шаг 6. Сравнить J(y_k) c J(z_k):

а) если J(y_k) £  J(z_k), положить

, , ,

.

Перейти к шагу 7;

б) если J(y_k) > J(z_k), положить

, , ,

Перейти к шагу 7.

Шаг 7. Проверить условие окончания и в случае необходимости сделать заключительное N-е вычисление функции для получения решения:

а) если , то положить   и перейти к шагу 5;

б) если , то всегда , т.е. отсутствует точка нового вычисления функции.

Следует положить: , . В точках ,  вычисляются значения функции и находятся границы конечного интервала неопределенности:

- если , положить

, ;

- если , положить

, .

Процесс поиска завершается и . В качестве приближенного решения можно взять любую точку последнего интервала, например, его середину .

Сходимость. Для метода Фибоначчи характеристика относительного уменьшения начального интервала неопределенности находится по формуле

,

где N - количество вычислений функции.

Замечания.

1. При заданном количестве вычислений функции N метод Фибоначчи обеспечивает минимальную величину конечного интервала неопределенности по сравнению с методами, рассмотренными ранее (метод перебора, метод деления отрезка пополам, метод «золотого» сечения).

2. На k-ой итерации длина интервала неопределенности сокращается по правилу .

Пример 3. Найти минимум функции

методом Фибоначчи.

Решение.

1. Зададим начальный интервал .

Пусть 

2. Найдем числа Фибоначчи:

Так как

.

3. Положим k = 0.

4⁰. Вычислим

5⁰. Вычислим 

6⁰. Сравним  ;

7⁰. Проверим условие окончания: k = 0 ¹ N - 3 = 6 - 3 = 3; L₂ = [0; 6,154]. Положим k = 1 и перейдем к шагу 5.

5¹. Вычислим значения  (уже было вычислено на шаге 5⁰).

6¹. Сравним ;

7¹. Проверим условие окончания: k = 1 ¹ N - 3 = 3; L₂ = [0; 3,846]. Положим

k = 2 и перейдем к шагу 5.

5². Вычислим значения    (уже было вычислено на шаге 5¹).

6². Сравним ;

7². Проверим условие окончания: k = 2 ¹ N - 3 = 3; L₄ = [1,538; 3,846]. Положим k = 3 и перейдем к шагу 5.

5³. Вычислим значения  .

6³. Сравним ;

7³. Проверим условие окончания: k  = 3 ¹ N - 3 = 3; L₅ = [2,308; 3,846]. Положим          

Вычислим  (было вычислено на шаге 5³);

. Так как

Поэтому 

Заметим, что

.

В качестве приближенного решения возьмем середину интервала  L₆: