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

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

Метод Фибоначчи (англ. 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 + \frac{F_{n-k-1}}{F_{n-k+1}}*(b_k - a_k)[/math] [math]{\mu}_k = a_k + \frac{F_{n-k}}{F_{n-k+1}}*(b_k - a_k)[/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({\lambda}_k) \gt f({\mu}_k)[/math] и [math][a_k, {\mu}_k][/math], если [math] f({\lambda}_k) \le f({\mu}_k)[/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 - \frac{F_{n-k-1}}{F_{n-k+1}}*(b_k - a_k) = \frac{F_{n-k}}{F_{n-k+1}}*(b_k - a_k)[/math].

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

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

Таким образом, в обоих случаях длина интервала неопределенности сжимается с коэффициентом [math]\frac{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({\lambda}_k) \gt f({\mu}_k)[/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} + \frac{F_{n-k-1}}{F_{n-k}}*(b_{k+1} - a_{k+1}) = {\lambda}_k + \frac{F_{n-k-1}}{F_{n-k}}*(b_k - {\lambda}_k)[/math]. Подставив выражение для [math]{\lambda}_k[/math] и заменив [math]k[/math] на [math]k + 1[/math], получим [math]{\lambda}_{k+1} = a_k + \frac{F_{n-k-1}}{F_{n-k+1}}*(b_k - a_k) + \frac{F_{n-k-2}}{F_{n-k}}*\left(1 - \frac{F_{n-k-1}}{F_{n-k+1}}\right)*(b_k - a_k)[/math].

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

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

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