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

[Alexey1]

Скажите, если необходимо сделать 2 вычисления для поиска интервала с минимумом функции по методу Фибоначи, каким будет этот интервал. Используя формулу метода Фибоначи $x_1=a+\frac {F_{n-1}} {F_n} L_0$, $x_2=b-\frac {F_{n-1}} {F_n} L_0$, где $[a,b]$ первоначальный интервал, $[x_1,x_2]$ искомый интервал, $L_0=x_2-x_1$, получается, что $x_1=x_2$ совпадают.

[gris]

При двух вычислениях будет выполнена одна итерация и получен результат -середина отрезка.


Обычно используют формулу $x_1=a+F_{n-2}/F_n}\cdot L_0;\, x_2=a+F_{n-1}/F_n}\cdot L_0$, а у Вас $x_1$ будет всегда больше $x_2$, хотя это не существенно, разумеется.
Ну и $L_0=b-a$
И, наконец, $(x_1;x_2)$ не будет искомым интервалом.

[Alexey1]

То есть на случай двух вычислений общая формула не работает.

[gris]

Работает. Правда при двух вычислениях, то есть одной итерации, мы, собственно, сам метод и не используем.
На $F_0=1; F_1=1;F_2=2;F процесс итерирования обычно заканчивается, а тут мы его даже не начинали.

[Alexey1]

Как это для двух вычислений $n=3$? Разве не $n=2$? Вот здесь дан алгоритм http://www.matmetod.ru/fibonacci_algorithm

[gris]

Я поправил предыдущие посты, где усомнился было в правильности применения метода Фибоначчи при двух вычислениях. Но я вовремя одумался.
немного погодя изложу свои соображения.

[ewert]

Лучше вообще использовать метод золотого сечения -- он алгоритмически гораздо проще, а эффект примерно тот же самый.

[gris]

Метод Фибоначчи и метод золотого сечения призваны обеспечить заданную точность нахождения экстремума унимодальной функции.
В методе Фибоначчи мы заранее определяем число вычислений значения функции в определяемых по формуле точках. Число итераций на единицу меньше числа вычислений. В результате мы получаем точку экстремума с заданной заранее точностью. Идея метода в том, что при очередной итерации мы просчитываем только одну точку, а вторая у нас уже есть.
Что нас может заставить выбрать два вычисления? Только точность в половину длины первоначального отрезка. В этом случае мы будем производить одну итерацию и сразу же получим ответ - середина отрезка. Экстремум находится в середине отрезка плюс-минус половина его длины. Ну или если хотите, интервал нахождения точки эктремума совпадает с первоначальным.
Результат практически бесполезный, но формально правильный, так как требуемая точность обеспечена.
Так что Фибоначчи рулит

[ewert]

gris в сообщении #196580 писал(а):

В методе Фибоначчи мы заранее определяем число вычислений значения функции в определяемых по формуле точках. Число итераций на единицу меньше числа вычислений. В результате мы получаем точку экстремума с заданной заранее точностью. Идея метода в том, что при очередной итерации мы просчитываем только одну точку, а вторая у нас уже есть.

Ровно то же самое относится к методу золотого сечения, с тем лишь приятным отличием, что не надо заранее вычислять сами числа Фибоначчи, да, кстати, и требуемое число итераций.

-----------------------------------------------------------------------------
Да, а ещё удобнее тупо делить на три равных части. Логика ещё более упрощается, скорость же уменьшается совсем ненамного -- раза в полтора, что ли (объём каждой итерации вдвое больше, но зато сама итерация раза в полтора точнее).