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

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

Метод Фибоначчи (англ. Fibonacci method) — это улучшение реализации поиска с помощью золотого сечения, служащего для нахождения минимума/максимума функции. Подобно методу золотого сечения, он требует двух вычислений функции на первой итерации, а на каждой последующей только по одному. Однако этот метод отличается от метода золотого сечения тем, что коэффициент сокращения интервала неопределенности меняется от итерации к итерации.

Описание

Метод основан на последовательности чисел Фибоначчи [math] {F_v} [/math], которая определяется следующим образом :

[math] F_v = F_{v-1} + F_{v-2}, v = 1, 2, 3,\dots, F_0 = F_1 = 1 [/math]

Таким образом, последовательность Фибоначчи имеет вид [math] 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …[/math] Предположим, что на [math]k[/math]-й итерации интервал неопределенности равен [math][a_k, b_k][/math]. Рассмотрим две точки [math]{\lambda}_k[/math] и [math]{\mu}_k[/math], определяемые следующим образом:

[math]{\lambda}_k = a_k + \dfrac{F_{n-k-1}}{F_{n-k+1}}*\left(b_k - a_k\right)[/math]

[math]{\mu}_k = a_k + \dfrac{F_{n-k}}{F_{n-k+1}}*\left(b_k - a_k\right)[/math],

где [math] k = 1, 2, \dots, n-1[/math] и [math]n[/math] — заданное общее число вычислений функции.

Новый интервал неопределенности [math][a_{k+1}, b_{k+1}][/math] будет равен [math] [{\lambda}_k, b_k][/math], если [math] f\left({\lambda}_k\right) \gt f\left({\mu}_k\right)[/math] и [math][a_k, {\mu}_k][/math], если [math] f\left({\lambda}_k\right) \le f\left({\mu}_k\right)[/math]. В первом случае, учитывая [math]{\lambda}_k [/math] и полагая [math]v = n - k[/math], получим

[math]b_{k+1} - a_{k+1} = b_k - {\lambda}_k = b_k - a_k - \dfrac{F_{n-k-1}}{F_{n-k+1}}*\left(b_k - a_k\right) = \dfrac{F_{n-k}}{F_{n-k+1}}*\left(b_k - a_k\right)[/math].

Во втором случае, учитывая [math] {\mu}_k[/math], получаем

[math] b_{k+1} - a_{k+1} = {\mu}_k - a_k = \dfrac{F_{n-k}}{F_{n-k+1}}*\left(b_k - a_k\right)[/math].

Таким образом, в обоих случаях длина интервала неопределенности сжимается с коэффициентом [math]\dfrac{F_{n-k}}{F_{n-k+1}}[/math]. Покажем, что на [math]k-[/math]той итерации либо [math]{\lambda}_k = {\mu}_k[/math], либо [math]{\mu}_{k+1} = {\lambda}_k[/math], так что требуется только одно новое вычисление функции. Предположим, что [math] f\left({\lambda}_k\right) \gt f\left({\mu}_k\right)[/math]. Тогда [math]a_{k+1} = {\lambda}_k, b_{k+1} = b_k[/math]. Таким образом, используя [math] F_v = F_{v-1} + F_{v-2}, v = 1, 2, 3,\dots, F_0 = F_1 = 1 [/math] и заменив [math]k[/math] на [math]k+1[/math], получаем [math]{\lambda}_{k+1} = a_{k+1} + \dfrac{F_{n-k-1}}{F_{n-k}}*\left(b_{k+1} - a_{k+1}\right) = {\lambda}_k + \dfrac{F_{n-k-1}}{F_{n-k}}*\left(b_k - {\lambda}_k\right)[/math]. Подставив выражение для [math]{\lambda}_k[/math] и заменив [math]k[/math] на [math]k + 1[/math], получим [math]{\lambda}_{k+1} = a_k + \dfrac{F_{n-k-1}}{F_{n-k+1}}*\left(b_k - a_k\right) + \dfrac{F_{n-k-2}}{F_{n-k}}*\left(1 - \dfrac{F_{n-k-1}}{F_{n-k+1}}\right)*\left(b_k - a_k\right)[/math].

[math] 1 - \dfrac{F_{n-k-1}}{F_{n-k+1}} = \dfrac{F_{n-k}}{F_{n-k+1}}[/math].

[math]{\lambda}_{k+1} = a_k + \dfrac{F_{n-k-1} + F_{n-k-2}}{F_{n-k+1}}*\left(b_k - a_k\right) = a_k + \dfrac{F_{n-k}}{F_{n-k+1}}*\left(b_k - a_k\right) = {\mu}_k[/math].

Если [math]f\left({\lambda}_k\right) \le f\left({\mu}_k\right)[/math], то выполнив аналогичные преобразования, получим [math]{\lambda}_{k+1} = {\lambda}_k[/math]. Таким образом, в обоих случаях на [math]k + 1[/math]-й итерации требуется только одно вычисление функции. В отличие от метода золотого сечения в методе Фибоначчи требуется, чтобы общее число вычислений [math]n[/math] (или коэффициент сокращения исходного интервала) было задано заранее. Это объясняется тем, что точки, в которых производятся вычисления, зависят от [math]n[/math]. Длина интервала неопределенности на [math]k[/math]-той итерации сжимается с коэффициентом [math]\dfrac{F_{n-k}}{F_{n-k+1}}[/math]. Следовательно, после [math] \left(n-1\right)[/math] итерации, где [math]n[/math] — заданное общее число вычислений функции [math]f\left(x\right)[/math], длина интервала неопределенности сократится от [math]\left(b_1 - a_1\right)[/math] до [math]\dfrac{b_1 - a_1}{F_n}[/math].

Алгоритм

Предварительный этап. Выбрать допустимую конечную длину интервала неопределенности [math]l \gt 0[/math] и константу различимости [math]{\epsilon}[/math]. Пусть задан начальный интервал неопределенности [math]\left(b_1 - a_1\right)[/math]. Выбрать общее число вычислений функции [math]n[/math] так, чтобы [math]F_n \gt \dfrac{b_1 - a_1}{l}[/math]. Положить [math]{\lambda}_1 = a_1 + \dfrac{F_{n-2}}{F_n}*\left(b_1 - a_1\right)[/math], [math]{\mu}_1 = a_1 + \dfrac{F_{n-1}}{F_n}*\left(b_1 - a_1\right)[/math].Вычислить [math]f\left({\lambda}_1\right)[/math], [math]f\left({\mu}_1\right)[/math], положить [math]k = 1[/math] и перейти к основному этапу.

Основной этап.

Первый шаг. Если [math]f\left({\lambda}_k\right) \gt f\left({\mu}_k\right)[/math], то перейти ко второму шагу, в противном случае – к третьему шагу.

Второй шаг.Положить [math]a_{k+1} = {\lambda}_k, b_{k+1} = b_k[/math]. Затем положить [math]{\lambda}_{k+1} = {\mu}_k[/math], [math]{\mu}_{k+1} = a_{k+1} + \dfrac{F_{n-k-1}}{F_{n-k}}*\left(b_{k+1} - a_{k+1}\right)[/math]. Если [math]k = n - 2[/math], то перейти к пятому шагу, в противном случае вычислить [math]f\left({\mu}_{k+1}\right)[/math] и перейти к четвертому шагу.

Третий шаг. Положить [math]a_{k+1} = a_k[/math], [math]b_{k+1} = {\mu}_k[/math], [math]{\mu}_{k+1} = {\lambda}_k[/math], [math]{\lambda}_{k+1} = a_{k+1} + \dfrac{F_{n-k-2}}{F_{n-k}}*\left(b_{k+1} - a_{k+1}\right)[/math]. Если [math]k = n - 2[/math], то перейти к пятому шагу, в противном случае [math]f\left({\lambda}_{k+1}\right)[/math] и перейти к четвертому шагу.

Четвертый шаг. Заменить [math]k[/math] на [math]k + 1[/math] и перейти к первому шагу.

Пятый шаг. Положить [math]{\lambda}_n = {\lambda}_{n-1}[/math], [math]{\mu}_n = {\lambda}_n + {\epsilon}[/math]. Если [math]f\left({\lambda}_n\right) = f\left({\mu}_n\right)[/math], то положить [math]a_n = {\lambda}_n, b_n = b_{n-1}[/math]. В противном случае (если [math]f\left({\lambda}_n\right) \lt f\left({\mu}_n\right)[/math]), положить [math]a_n = a_{n-1}, b_n = {\mu}_n[/math].

Конец: оптимальное решение содержится в интервале [math][a_n, b_n][/math].