Метод Фибоначчи — различия между версиями
(→Описание) |
|||
Строка 33: | Строка 33: | ||
Если <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>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>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>. |
Версия 00:45, 28 января 2016
Метод Фибоначчи
Метод Фибоначчи (англ. Fibonacci method) — это улучшение реализации поиска с помощью золотого сечения, служащего для нахождения минимума/максимума функции. Подобно методу золотого сечения, он требует двух вычислений функции на первой итерации, а на каждой последующей только по одному. Однако этот метод отличается от метода золотого сечения тем, что коэффициент сокращения интервала неопределенности меняется от итерации к итерации.
Описание
Метод основан на последовательности чисел Фибоначчи
, которая определяется следующим образом :
Таким образом, последовательность Фибоначчи имеет вид
Предположим, что на -й итерации интервал неопределенности равен . Рассмотрим две точки и , определяемые следующим образом:
,
где
и — заданное общее число вычислений функции.Новый интервал неопределенности
будет равен , если и , если . В первом случае, учитывая и полагая , получим.
Во втором случае, учитывая
, получаем.
Таким образом, в обоих случаях длина интервала неопределенности сжимается с коэффициентом
. Покажем, что на той итерации либо , либо , так что требуется только одно новое вычисление функции. Предположим, что . Тогда . Таким образом, используя и заменив на , получаем . Подставив выражение для и заменив на , получим ..
.
Если золотого сечения в методе Фибоначчи требуется, чтобы общее число вычислений (или коэффициент сокращения исходного интервала) было задано заранее. Это объясняется тем, что точки, в которых производятся вычисления, зависят от . Длина интервала неопределенности на -той итерации сжимается с коэффициентом . Следовательно, после итерации, где — заданное общее число вычислений функции , длина интервала неопределенности сократится от до .
, то выполнив аналогичные преобразования, получим . Таким образом, в обоих случаях на -й итерации требуется только одно вычисление функции. В отличие от методаАлгоритм
Предварительный этап. Выбрать допустимую конечную длину интервала неопределенности
и константу различимости . Пусть задан начальный интервал неопределенности . Выбрать общее число вычислений функции так, чтобы . Положить , .