Изменения
Новая страница: «==Метод Фибоначчи== '''Метод Фибоначчи''' (англ. ''Fibonacci method'') {{---}} это улучшение реализации [[П...»
==Метод Фибоначчи==
'''Метод Фибоначчи''' (англ. ''Fibonacci method'') {{---}} это улучшение реализации [[Поиск с помощью золотого сечения|поиска с помощью золотого сечения]], служащего для нахождения минимума/максимума функции. Подобно методу золотого сечения, он требует двух вычислений функции на первой итерации, а на каждой последующей только по одному. Однако этот метод отличается от метода золотого сечения тем, что коэффициент сокращения интервала неопределенности меняется от итерации к итерации.
==Описание==
Метод основан на последовательности чисел Фибоначчи <tex> {F_v} </tex>, которая определяется следующим образом :
<tex> F_v = F_{v-1} + F_{v-2}, v = 1, 2, 3, …, F_0 = F_1 = 1 </tex>
Таким образом, последовательность Фибоначчи имеет вид <tex> 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …</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>{\mu}_k = a_k + \frac{F_{n-k}}{F_{n-k+1}}*(b_k - a_k)</tex>,
где <tex> k = 1, 2, …, n-1</tex> и <tex>n {{---}}</tex> заданное общее число вычислений функции.
Новый интервал неопределенности <tex>[a_{k+1}, b_{k+1}]</tex> будет равен <tex> [{\lambda}_k, b_k], если <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>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> {\mu}</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>\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, …, 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>{\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>{\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>f({\lambda}_k) \le f({\mu}_k)</tex>, то выполнив аналогичные преобразования, получим <tex>{\lambda}_{k+1} = {\lambda}_k</tex>. Таким образом, в обоих случаях на <tex>k + 1</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>.
'''Метод Фибоначчи''' (англ. ''Fibonacci method'') {{---}} это улучшение реализации [[Поиск с помощью золотого сечения|поиска с помощью золотого сечения]], служащего для нахождения минимума/максимума функции. Подобно методу золотого сечения, он требует двух вычислений функции на первой итерации, а на каждой последующей только по одному. Однако этот метод отличается от метода золотого сечения тем, что коэффициент сокращения интервала неопределенности меняется от итерации к итерации.
==Описание==
Метод основан на последовательности чисел Фибоначчи <tex> {F_v} </tex>, которая определяется следующим образом :
<tex> F_v = F_{v-1} + F_{v-2}, v = 1, 2, 3, …, F_0 = F_1 = 1 </tex>
Таким образом, последовательность Фибоначчи имеет вид <tex> 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …</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>{\mu}_k = a_k + \frac{F_{n-k}}{F_{n-k+1}}*(b_k - a_k)</tex>,
где <tex> k = 1, 2, …, n-1</tex> и <tex>n {{---}}</tex> заданное общее число вычислений функции.
Новый интервал неопределенности <tex>[a_{k+1}, b_{k+1}]</tex> будет равен <tex> [{\lambda}_k, b_k], если <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>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> {\mu}</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>\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, …, 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>{\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>{\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>f({\lambda}_k) \le f({\mu}_k)</tex>, то выполнив аналогичные преобразования, получим <tex>{\lambda}_{k+1} = {\lambda}_k</tex>. Таким образом, в обоих случаях на <tex>k + 1</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>.
