Метод Фибоначчи — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Описание)
м (rollbackEdits.php mass rollback)
 
(не показаны 4 промежуточные версии 3 участников)
Строка 10: Строка 10:
 
Предположим, что на <tex>k</tex>-й итерации интервал неопределенности равен <tex>[a_k, b_k]</tex>.  Рассмотрим две точки <tex>{\lambda}_k</tex> и <tex>{\mu}_k</tex>, определяемые следующим образом:
 
Предположим, что на <tex>k</tex>-й итерации интервал неопределенности равен <tex>[a_k, b_k]</tex>.  Рассмотрим две точки <tex>{\lambda}_k</tex> и <tex>{\mu}_k</tex>, определяемые следующим образом:
  
<tex>{\lambda}_k = a_k + \frac{F_{n-k-1}}{F_{n-k+1}}*(b_k - a_k)</tex>
+
<tex>{\lambda}_k = a_k + \dfrac{F_{n-k-1}}{F_{n-k+1}}*\left(b_k - a_k\right)</tex>
<tex>{\mu}_k = a_k + \frac{F_{n-k}}{F_{n-k+1}}*(b_k - a_k)</tex>,  
+
 
 +
<tex>{\mu}_k = a_k + \dfrac{F_{n-k}}{F_{n-k+1}}*\left(b_k - a_k\right)</tex>,  
 +
 
 
где <tex> k = 1, 2, \dots, n-1</tex> и <tex>n</tex> {{---}} заданное общее число вычислений функции.
 
где <tex> k = 1, 2, \dots, n-1</tex> и <tex>n</tex> {{---}} заданное общее число вычислений функции.
  
Новый интервал неопределенности <tex>[a_{k+1}, b_{k+1}]</tex> будет равен <tex> [{\lambda}_k, b_k]</tex>, если <tex> f({\lambda}_k) > f({\mu}_k)</tex> и <tex>[a_k, {\mu}_k]</tex>, если <tex> f({\lambda}_k) \le f({\mu}_k)</tex>. В первом случае, учитывая <tex>{\lambda}_k </tex> и полагая <tex>v = n - k</tex>, получим
+
Новый интервал неопределенности <tex>[a_{k+1}, b_{k+1}]</tex> будет равен <tex> [{\lambda}_k, b_k]</tex>, если <tex> f\left({\lambda}_k\right) > f\left({\mu}_k\right)</tex> и <tex>[a_k, {\mu}_k]</tex>, если <tex> f\left({\lambda}_k\right) \le f\left({\mu}_k\right)</tex>. В первом случае, учитывая <tex>{\lambda}_k </tex> и полагая <tex>v = n - k</tex>, получим
  
<tex>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)</tex>.  
+
<tex>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)</tex>.  
  
 
Во втором случае, учитывая <tex> {\mu}_k</tex>, получаем
 
Во втором случае, учитывая <tex> {\mu}_k</tex>, получаем
  
<tex> b_{k+1} - a_{k+1} = {\mu}_k - a_k = \frac{F_{n-k}}{F_{n-k+1}}*(b_k - a_k)</tex>.
+
<tex> b_{k+1} - a_{k+1} = {\mu}_k - a_k = \dfrac{F_{n-k}}{F_{n-k+1}}*\left(b_k - a_k\right)</tex>.
 +
 
 +
Таким образом, в обоих случаях длина интервала неопределенности сжимается с коэффициентом <tex>\dfrac{F_{n-k}}{F_{n-k+1}}</tex>. Покажем, что на <tex>k-</tex>той итерации либо <tex>{\lambda}_k = {\mu}_k</tex>, либо <tex>{\mu}_{k+1} = {\lambda}_k</tex>, так что требуется только одно новое вычисление функции. Предположим, что <tex> f\left({\lambda}_k\right) > f\left({\mu}_k\right)</tex>. Тогда <tex>a_{k+1} = {\lambda}_k, b_{k+1} = b_k</tex>. Таким образом, используя <tex> F_v = F_{v-1} + F_{v-2}, v = 1, 2, 3,\dots, F_0 = F_1 = 1 </tex> и заменив <tex>k</tex> на <tex>k+1</tex>, получаем <tex>{\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)</tex>.
 +
Подставив выражение для <tex>{\lambda}_k</tex> и заменив <tex>k</tex> на <tex>k + 1</tex>, получим <tex>{\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)</tex>.
 +
 
 +
<tex> 1 - \dfrac{F_{n-k-1}}{F_{n-k+1}} = \dfrac{F_{n-k}}{F_{n-k+1}}</tex>.
 +
 
 +
<tex>{\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</tex>.
 +
 
 +
Если <tex>f\left({\lambda}_k\right) \le f\left({\mu}_k\right)</tex>, то выполнив аналогичные преобразования, получим <tex>{\lambda}_{k+1} = {\lambda}_k</tex>. Таким образом, в обоих случаях на <tex>k + 1</tex>-й итерации требуется только одно вычисление функции.
 +
В отличие от метода [[Поиск с помощью золотого сечения|золотого сечения]] в методе Фибоначчи требуется, чтобы общее число вычислений <tex>n</tex> (или коэффициент сокращения исходного интервала) было задано заранее. Это объясняется тем, что точки, в которых производятся вычисления, зависят от <tex>n</tex>. Длина интервала неопределенности на <tex>k</tex>-той итерации сжимается с коэффициентом <tex>\dfrac{F_{n-k}}{F_{n-k+1}}</tex>. Следовательно, после <tex> \left(n-1\right)</tex> итерации, где <tex>n</tex> {{---}} заданное общее число вычислений функции <tex>f\left(x\right)</tex>, длина интервала неопределенности сократится от <tex>\left(b_1 - a_1\right)</tex> до <tex>\dfrac{b_1 - a_1}{F_n}</tex>.
 +
 
 +
==Алгоритм==
 +
'''Предварительный этап.'''
 +
Выбрать допустимую конечную длину интервала неопределенности <tex>l > 0</tex> и константу различимости <tex>{\epsilon}</tex>. Пусть задан начальный интервал неопределенности <tex>\left(b_1 - a_1\right)</tex>. Выбрать общее число вычислений функции <tex>n</tex> так, чтобы <tex>F_n > \dfrac{b_1 - a_1}{l}</tex>. Положить <tex>{\lambda}_1 = a_1 + \dfrac{F_{n-2}}{F_n}*\left(b_1 - a_1\right)</tex>, <tex>{\mu}_1 = a_1 + \dfrac{F_{n-1}}{F_n}*\left(b_1 - a_1\right)</tex>.Вычислить <tex>f\left({\lambda}_1\right)</tex>, <tex>f\left({\mu}_1\right)</tex>, положить <tex>k = 1</tex> и перейти к основному этапу.
 +
 
 +
'''Основной этап.'''
 +
 
 +
''Первый шаг.'' Если <tex>f\left({\lambda}_k\right) > f\left({\mu}_k\right)</tex>, то перейти ко второму шагу, в противном случае – к третьему шагу.
 +
 
 +
''Второй шаг.''Положить <tex>a_{k+1} = {\lambda}_k, b_{k+1} = b_k</tex>. Затем положить <tex>{\lambda}_{k+1} = {\mu}_k</tex>, <tex>{\mu}_{k+1} = a_{k+1} + \dfrac{F_{n-k-1}}{F_{n-k}}*\left(b_{k+1} - a_{k+1}\right)</tex>. Если <tex>k = n - 2</tex>, то перейти к пятому шагу, в противном случае вычислить <tex>f\left({\mu}_{k+1}\right)</tex> и перейти к четвертому шагу.
  
Таким образом, в обоих случаях длина интервала неопределенности сжимается с коэффициентом <tex>\frac{F_{n-k}}{F_{n-k+1}}</tex>. Покажем, что на <tex>k-</tex>той итерации либо <tex>{\lambda}_k = {\mu}_k</tex>, либо <tex>{\mu}_{k+1} = {\lambda}_k</tex>, так что требуется только одно новое вычисление функции. Предположим, что <tex> f({\lambda}_k) > f({\mu}_k)</tex>. Тогда <tex>a_{k+1} = {\lambda}_k, b_{k+1} = b_k</tex>. Таким образом, используя <tex> F_v = F_{v-1} + F_{v-2}, v = 1, 2, 3,\dots, F_0 = F_1 = 1 </tex> и заменив <tex>k</tex> на <tex>k+1</tex>, получаем <tex>{\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)</tex>.  
+
''Третий шаг.'' Положить <tex>a_{k+1} = a_k</tex>, <tex>b_{k+1} = {\mu}_k</tex>, <tex>{\mu}_{k+1} = {\lambda}_k</tex>, <tex>{\lambda}_{k+1} = a_{k+1} + \dfrac{F_{n-k-2}}{F_{n-k}}*\left(b_{k+1} - a_{k+1}\right)</tex>. Если <tex>k = n - 2</tex>, то перейти к пятому шагу, в противном случае <tex>f\left({\lambda}_{k+1}\right)</tex> и перейти к четвертому шагу.
Подставив выражение для <tex>{\lambda}_k</tex> и заменив <tex>k</tex> на <tex>k + 1</tex>, получим <tex>{\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)</tex>.
 
  
<tex> 1 - \frac{F_{n-k-1}}{F_{n-k+1}} = \frac{F_{n-k}}{F_{n-k+1}}</tex>.
+
''Четвертый шаг.'' Заменить <tex>k</tex> на <tex>k + 1</tex> и перейти к первому шагу.
  
<tex>{\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</tex>.
+
''Пятый шаг.'' Положить <tex>{\lambda}_n = {\lambda}_{n-1}</tex>, <tex>{\mu}_n = {\lambda}_n + {\epsilon}</tex>. Если <tex>f\left({\lambda}_n\right) = f\left({\mu}_n\right)</tex>, то положить <tex>a_n = {\lambda}_n, b_n = b_{n-1}</tex>. В противном случае (если <tex>f\left({\lambda}_n\right) < f\left({\mu}_n\right)</tex>), положить <tex>a_n = a_{n-1}, b_n = {\mu}_n</tex>.
  
Если <tex>f({\lambda}_k) \le f({\mu}_k)</tex>, то выполнив аналогичные преобразования, получим <tex>{\lambda}_{k+1} = {\lambda}_k</tex>. Таким образом, в обоих случаях на <tex>k + 1</tex>-й итерации требуется только одно вычисление функции.
+
'''Конец''': оптимальное решение содержится в интервале <tex>[a_n, b_n]</tex>.
В отличие от метода [[Поиск с помощью золотого сечения|золотого сечения]] в методе Фибоначчи требуется, чтобы общее число вычислений <tex>n</tex> (или коэффициент сокращения исходного интервала) было задано заранее. Это объясняется тем, что точки, в которых производятся вычисления, зависят от <tex>n</tex>. Длина интервала неопределенности на <tex>k</tex>-той итерации сжимается с коэффициентом <tex>\frac{F_{n-k}}{F_{n-k+1}}</tex>. Следовательно, после <tex> (n-1)</tex> итерации, где <tex>n</tex> {{---}} заданное общее число вычислений функции <tex>f(x)</tex>, длина интервала неопределенности сократится от <tex>(b_1 - a_1)</tex> до <tex>\frac{b_1 - a_1}{F_n}</tex>.
 

Текущая версия на 19:29, 4 сентября 2022

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

Метод Фибоначчи (англ. 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].