Изменения

<tex> F_v = F_{v-1} + F_{v-2}, v = 1, 2, 3, …\dots, F_0 = F_1 = 1 </tex>

<tex>{\lambda}_k = a_k + \fracdfrac{F_{n-k-1}}{F_{n-k+1}}*\left(b_k - a_k)</tex><tex>{\mu}_k = a_k + \frac{F_{n-k}}{F_{n-k+1}}*(b_k - a_kright)</tex>, где <tex> k = 1, 2, …, n-1</tex> и <tex>n {{---}}</tex> заданное общее число вычислений функции.

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

где <tex>b_{k+1} - a_{k+= 1} = b_k - {, 2, \lambda}_k = b_k - a_k - \frac{F_{dots, n-k-1}}</tex> и <tex>n</tex> {F_{n-k+1}}*(b_k - a_k) = \frac{F_{n-k}}{F_{n-k+1}}*(b_k - a_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> {\mulambda}_k </tex> и полагая <tex>v = n - k</tex>, получаемполучим

<tex> b_{k+1} - a_{k+1} = b_k - {\mulambda}_k = b_k - a_k - \dfrac{F_{n-k-1}}{F_{n-k+1}}*\left(b_k - a_k\right) = \fracdfrac{F_{n-k}}{F_{n-k+1}}*\left(b_k - a_k\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, …, 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_b_{n-k-+1}}{F_- a_{n-k+1}= {\mu} _k - a_k = \fracdfrac{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 a_{k+1} + \fracdfrac{F_{n-k-1} }{F_{n-k}}*\left(b_{k+1} - a_{k+ 1}\right) = {\lambda}_k + \dfrac{F_{n-k-21}}{F_{n-k+1}}*\left(b_k - a_k{\lambda}_k\right) </tex>. Подставив выражение для <tex>{\lambda}_k</tex> и заменив <tex>k</tex> на <tex>k + 1</tex>, получим <tex>{\lambda}_{k+1} = a_k + \fracdfrac{F_{n-k-1}}{F_{n-k+1}}*\left(b_k - a_k\right) = + \dfrac{F_{n-k-2}}{F_{n-k}}*\left(1 - \mudfrac{F_{n-k-1}}{F_{n-k+1}}_k\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>\fracdfrac{F_{n-k}}{F_{n-k+1}}</tex>. Следовательно, после <tex> \left(n-1\right)</tex> итерации, где <tex>n </tex> {{---}}</tex> заданное общее число вычислений функции <tex>f\left(x\right)</tex>, длина интервала неопределенности сократится от <tex>\left(b_1 - a_1\right)</tex> до <tex>\fracdfrac{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>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>k</tex> на <tex>k + 1</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>[a_n, b_n]</tex>.