2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Метод Фибоначи
Сообщение18.03.2009, 01:52 
Скажите, если необходимо сделать 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$ совпадают.

 
 
 
 
Сообщение18.03.2009, 10:53 
Аватара пользователя
При двух вычислениях будет выполнена одна итерация и получен результат -середина отрезка.


Обычно используют формулу $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)$ не будет искомым интервалом.

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

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

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

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

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

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

 
 
 
 
Сообщение19.03.2009, 13:27 
gris в сообщении #196580 писал(а):
В методе Фибоначчи мы заранее определяем число вычислений значения функции в определяемых по формуле точках. Число итераций на единицу меньше числа вычислений. В результате мы получаем точку экстремума с заданной заранее точностью. Идея метода в том, что при очередной итерации мы просчитываем только одну точку, а вторая у нас уже есть.

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

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

 
 
 [ Сообщений: 9 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group