Метод Фибоначчи поиска экстремума. Метод фибоначчи


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

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

С помощью численной процедуры, описанной в данном учебном курсе, непосредственно ищется минимум функции в некотором интервале, в котором предположительно лежит этот минимум. При этом метод Фибоначчи относятся к методам исключения интервалов, на которых заведомо отсутствует оптимум исследуемой функции. Кроме того в данных методах предполагается, что оптимизируемая функция является унимодальной.

В процессе применения методов исключения интервалов можно выделить две фазы:

  • Фаза установления границ интервала, на котором реализуется процедура поиска. Это могут быть границы достаточного широкого интервала заведомо содержащего точку оптимума. В поисковых задачах оптимизации отрезок, на котором находится точка минимума, называют интервалом неопределённости.

  • Фаза уменьшения интервала, на котором реализуется конечная последовательность преобразований исходного интервала с тем, чтобы уменьшить его длину до заранее установленной величины (точности поиска экстремума).

На втором этапе, этапе уменьшения интервала, как раз и применяется метод Фибоначчи. В общем виде задача оптимизации ставится следующим образом: «Найти минимум унимодальной функции на замкнутом интервалепри заданном числе вычислений функции».

Краткое описание метода Фибоначчи

Предположим, что нужно определить минимум как можно точнее, т.е. с наименьшим интервалом неопределённости, но при этом можно выполнить только вычислений функции. Как следует расположить этиточек? Ясно, что надо сделать так, чтобы в последующих итерациях использовались точки, использованные на предыдущих итерациях. Предположим, что на интервалеизвестно значение функции в точке. Если можно вычислить значение функции только один раз (т.е.), то где поместить точку, для того чтобы получить наименьший интервал неопределённости после отбрасывания интервала, в котором оптимум не расположен?

Рассмотрим рисунок. Точки фиксированы. Предположим, что, а точкарасположена на интервале. Возможны два случая:

Поскольку не известно, какая ситуация справедлива, точку надо выбрать так, чтобы минимизировать наибольшую из длин:или. Достигнуть этого можно, сделав эти длины равными, т.е. поместивсимметрично относительно точки(в любом другом случае новый интервал будет большей величины).

Кроме того, при (прина последнем интервале) длина последнего интервала минимальна, если предпоследний интервал разделить пополам. Действительно, при этоми последний интервал неопределённости равен. Однако притрудно выбрать нужный интервал неопределённости, поскольку. Обычно точкииотстоят друг от друга на достаточном расстоянии, чтобы чётко зафиксировать, в какой точке интерваланаходится интервал неопределенности.

Предположим теперь, что можно вычислить значение функции раз. В этом случае стратегия поиска ясна с самого начала. Нужно поместить следующую точку внутри интервала симметрично относительно уже находящейся там точки. Парадоксально, но, чтобы понять, как следует начинать процедуру вычисления, необходимо разобраться в том, как следует кончать её.

Уже было показано, что на последнем -ом вычислении -ю точку (на поясняющем рисунке) следует поместить симметрично по отношению кточке (точке) на расстояниеиз условия различимостив этих точках.– это интервал нечувствительности на последней итерации, т.е. разница между аргументамиидвух экспериментов, при которых можно отличить значения функцийи.

Замечание: на первом этапе можно считать и точкурасположить в середине отрезка, а затем точкурасположить справа или слева от первой точки на достаточно малом расстояниине равном 0.

Из рисунка следует, что интервал неопределённости имеет длину . Тогда. На предыдущем этапе точкиидолжны быть смещены симметрично внутри интервалана расстояниеот концов. Следовательно,. Аналогично показывается, что. В общем случае, при. Таким образом:

В общем случае , где,- последовательность чисел Фибоначчи, определяемая как:для.

Если начальный интервал , то конечный:. Следовательно, произведявычислений функции, начальный интервалуменьшается враз (пренебрегая малой величиной). Это наилучший результат. Если поиск начат с начальным интервалом, то его несложно продолжить, используя правило симметрии: на отрезкенеобходимо найти положение первой точки, которая размещается на расстоянииот правого конца интервала(ближе к точке), а вторая точка (точка) – на таком же расстоянииот левого конца интервала (ближе к точке). Значениеравно.

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

studfiles.net

Алгоритм метода Фибоначчи

Шаг 1.

Задаётся точность и число вычислений функции.

Шаг 2.

Вычисляется длина начального интервала и число(– число вычислений функцииизменяется отдо).

Шаг 3.

Вычисляем , где- числа Фибоначчи. Вычисляемв начальной точке.

Если величина не задана, рекомендуется выбирать её из условия.

Шаг 4.

Находим и вычисляем.

Шаг 5.

5.1

Если и, то исключается интервал, а остаётся интервал. Полагаем. Если условие 5.1 выполнено, переходим к шагу 6.

5.2

Если и, то исключается интервал, а остаётся интервал. Полагаем. Переходим к шагу 6.

5.3

Если и, то остаётся интервал. Полагаем. Переходим к шагу 6.

5.4

Если и, то остаётся интервал. Полагаем. Переходим к шагу 6.

Шаг 6.

Увеличиваем и проверяем условия 6.1 и 6.2

6.1

Если , то переходим к шагу 4.

6.2

Если , то работа окончена и последний интервал, где расположен оптимум, найден. Переход к шагу 7.

Шаг 7.

Интервал неопределённости . В качестве оптимального значенияможно принять:

Пример

Методом Фибоначчи минимизировать функцию на интервалеприи.

Поскольку из таблицы чисел Фибоначчи выбереми.

Итерация 1

Шаг 1.

Шаг 2.

Шаг 3.

Вычисляем .

Шаг 4.

Находим

Шаг 5.

Сравнение . Следовательно, выполняется пункт 5.1 и надо исключить интервал. Оставляем интервал. Переприсвоение:.

Шаг 6.

Увеличиваем . Проверяем условие. Т.к.переходим ко второй итерации и делаем шаг 4.

Итерация 2

Шаг 4.

Находим .

Шаг 5.

Сравниваем . Согласно шагу 5.1 остаётся интервал. Переприсвоение:.

Шаг 6.

. Сравниваем. Переходим к итерации 3.

Итерация 3

Шаг 4.

Находим .

Шаг 5.

Сравниваем и. Согласно шагу 5.3 остаётся интервал. Переприсвоение:. Переходим к шагу 6.

Шаг 6.

Сравниваем, поэтому переходим к шагу 7.

Шаг 7.

Найденный интервал неопределённости . В качестве оптимального значенияможно принять, например, середину интервала неопределённости:. Точное значение аргумента, при котором достигается минимум, равно.

Метод дихотомии

Методы поиска, которые позволяют определить оптимум функции одной переменной путём последовательного исключения подинтервалов и, следовательно, путём уменьшения интервала поиска, носят название методов исключения интервалов. Метод дихотомии – один из методов исключения интервалов. В процессе применения методов исключения интервалов можно выделить две фазы:

  • Фаза установления границ интервала, на котором реализуется процедура поиска. Это могут быть границы достаточного широкого интервала заведомо содержащего точку оптимума. В поисковых задачах оптимизации отрезок, на котором находится точка минимума, называют интервалом неопределённости.

  • Фаза уменьшения интервала, на котором реализуется конечная последовательность преобразований исходного интервала с тем, чтобы уменьшить его длину до заранее установленной величины (точности поиска экстремума).

Первый этап может отсутствовать, если интервал, заведомо содержащий экстремум функции, уже задан. Вторая фаза, фаза установления интервала, реализуется различными методами уменьшения интервала:

  • Методом дихотомии

  • Методом золотого сечения

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

Суть метода дихотомии состоит в последовательном разбиении интервала, содержащего экстремум (его называют интервалом поиска), на подинтервалы и исключении одного из них, заведомо не содержащего экстремум. Величина подинтервала, исключаемого на каждом шаге, зависит от расположения пробных точек ивнутри интервала поиска. Поскольку местонахождение точки оптимума заранее не известно, целесообразно предположить, что размещение пробных точек должно обеспечивать уменьшение интервала в одном и том же отношении на каждом шаге. В методе дихотомии это отношение равно, т.е. интервал неопределённости делится на каждом шаге пополам и отбрасывается часть, где минимум заведомо быть не может.

studfiles.net

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

В основу метода чисел Фибоначчи положены два соотношения:

Lq-2 = Lq-1+ Lq , q=;

LN = (LN-1 + )/2.

Первое из этих двух соотношений определяет связь трех соседних интервалов неопределенности. Второе соотношение требует, чтобы в завершении эксперимента две последние точки находились симметрично на интервале неопределенности LN-1. Здесь  - минимальный размер интервала неопределенности LN, вычисляемый перед N–м шагом.

Расчеты показывают, что в диапазоне реальных значений N (от 4-5 до 25-30) метод чисел Фибоначчи эффективнее метода дихотомии на 20-30%. Это объясняется тем, что сокращение длины очередного интервала Lq требует здесь проведения одно­го нового эксперимента, тогда как в схеме дихотомии их тре­бовалось два.

Так как второе граничное условие связывает LN и LN-1, то схему поиска следует строить от конца к началу. В итоге обнаруживается зависимость длин интервалов неопределенности, вычисляемых на каждом шаге и координат точек, в которых следует вычислять значения целевой функции, от значений N и , заданных при планировании поиска. Необходимо помнить, значение  не должно быть больше, чем LN.

Для разрешения этой проблемы заранее рассчитаны коэффи­циенты при LN и  c целью определения различных значений Lq, названные числами Фибоначчи FN в честь итальянского ма­тематика XIII века Леонарда Пизанского (Фибоначчи):

Lq= FN-q+1 LN– FN-q-1.

Если же в результате вычисления по приведенной выше формуле значение LN окажется меньше, чем значение , то следует уменьшать либо минимальный размер интервала неопределенности , либо количество шагов N. Иначе при вычислении LN-1 будет получаться не логичное неравенство: LN-1 < LN.

В табл. 2 приведены значения FN для малых значений N.

Нетрудно видеть, что эти числа определяются соотношениями

F0 = F1 =1; Fk = Fk-1 + Fk-2; k=2, 3, ….

Таблица 2. Числа Фибоначчи

N

FN

N

FN

N

FN

0

1

6

13

12

233

1

1

7

21

13

377

2

2

8

34

14

610

3

3

9

55

15

987

4

5

10

89

16

1597

5

8

11

144

17

2584

На рис. 3.5.4. приведена геометрическая иллюстрация схемы поиска экстремума методом чисел Фибоначчи. Из нее видно, что LN-3 = LN-1+ LN-2. Если считать, что исходный интервал L1=1, то L2 + L3 =1, а также 1=1– L2, 2= L2. При этом точки 1 и 2 расположенысимметрично относительно центра единичного интервала L1=1.

Рис. 3.5.4. Геометрическая иллюстрация задачи поиска экстремума методом чисел Фибоначчи

Решим предыдущую задачу поиска экстремума методом чисел Фибоначчи.

Как было указано ранее N = 6 ,  = 0,05. Тогда, приняв q=1 и L1=1, воспользуемся формулой

Lq= FN-q+1 LN– FN-q-1.

Получим L1=F6-1+1L6–F6-1-1=F6L6 – F4=13L6–50,05=13L6 – 0,25=1;  L6=. Остальные длины интервалов неопределенности определим, воспользовавшись формулойLN-3 = LN-1+ LN-2.

Тогда L4 = L6 + L5  L5 + 0,1;

L3 = L5 + L4  L5 + L5 + 0,1 2L5 + 0,1;

L2 = L4 + L3  L5 + 0,1+ 2L5 + 0,1 3L5 + 0,2;

L1 = L3 + L2  2L5 + 0,1+ 3L5 + 0,2 5L5 + 0,3 = 1.

Следовательно, L5=;L4 =L5 + 0,1=0,24; L3 =2L5 + 0,1=0,38;

L2 =3L5 + 0,2=0,62;  1 = 1 – 0,62 =0,38; 2 = 0,62; L1 = 5L5 + 0,3 = 1, что и было предположено.

До начала решения задачи исходный интервал неопределенности [0; 1] длины L1 = 1. После измерений значений целевой функции в точках 1,2 и сравнения их выявляем, что большее значение целевая функция принимает в точке 2 =0,62, поэтому новый интервал неопределенности [0,38; 1] длины L2 = 0,62.

Нам уже известно, что длина третьего интервала неопределенности L3 = 0,38. Заметим, что расстояние от 1 до 0,62 как раз и составляет 0,38, поэтому первая точка нового второго шага нам уже известна. Это точка 3=2=0,62. Осталось найти вторую точку второго шага такую, которая отстояла бы вправо по шкале на 0,38 от левой границы интервала неопределенности L2 – от точки 1=0,38. Тогда 4=0,38+0,38=0,76. Процесс решения этой задачи приведен на рис.3.5.5 и в таблице 3.

0L1 = 1

1

0,62

2

1

L2 = 0,62

0,38

3

4

L3 = 0,38

5

6

0,76

L4 = 0,24

0,48

7

8

L5 = 0,14

9

10

0,52

L6 = 0,10

0,42

11

12

L7=0, 067

0,46

L7 = 0, 067

Рис. 3.5.5. Шаги поиска экстремума при стратегии чисел Фибоначчи

Таблица 3. Шаги поиска экстремума W() при стратегии чисел Фибоначчи

i

2i-1

2i

Li

W(2i-1)

W(2i)

1

0,38

0,62

1

3,14

3,24

2

0,62

0,76

0,62

3,24

2,96

3

0,52

0,62

0,38

3,44

3,24

4

0,48

0,52

0,24

4,22

3,44

5

0,42

0,48

0,14

3,53

4,22

6

0,46

0,48

0,10

3,97

4,22

Таким образом, *[0,46; 0,52]. Это с допустимой точ­ностью совпадает с результатами, полученными методом дихото­мии. Однако потребовалось меньшее число экспериментов, так как (это видно из таблицы и рисунка) на каждом шаге поиска требуется только одно новое измерение целевой функции, т. к. одна из точек предыдущего интервала неопределенности Li переходит на очередной интервал Li+1.

В качестве недостатка метода чисел Фибоначчи следует отметить то, что для того, чтобы найти первое число 1 = f(N, ) нужно знать значения аргументов функции f, что не всегда возможно. Изменение N в ходе экспериментов в метод чисел Фибоначчи невозможно. Т. е. метод чисел Фибоначчи является итеративным методом поиска экстремума целевой функции, использующим пассивную стратегию. Лишен данного недостатка рассматриваемый далее метод золо­того сечения, хотя его эффективность несколько меньше (при­мерно в 1,17 раза при N > 4), чем эффективность метода чи­сел Фибоначчи.

Как мы видим, для определения L6=0,1 методом чисел Фибоначчи нам потребовалось измерить значения целевой функции всего в шести точках. При решении данной задачи методом дихотомии после шести измерений интервал неопределенности был равен L4=0,17, после восьми измерений – L5=0,11, после десяти – L6=0,08, а после двенадцати – L7=0,065. Для сравнения, методом чисел Фибоначчи после одиннадцати измерений интервал неопределенности (при N = 10) будет равен

L1=F10-1+1L10–F10-1-1= F10L10–F8=89L10–1,7=1;  L10=.

Аналогично находим интервал неопределенности после 12 (при =0,01) L11=и после 13 (при=0,006) измерений L12=.

studfiles.net

Метод Фибоначчи поиска экстремума - это... Что такое Метод Фибоначчи поиска экстремума?

 Метод Фибоначчи поиска экстремума

Метод золотого сечения — метод поиска значений действительно-значной функции на заданном отрезке. В основе метода лежит принцип деления в пропорциях золотого сечения. Наиболее широко известен как метод поиска экстремума в решении задач оптимизации.

Описание метода

Пусть задана функция . Тогда для того, чтобы найти определённое значение этой функции на заданном отрезке, отвечающее критерию поиска (пусть это будет минимум), рассматриваемый отрезок делится в пропорции золотого сечения в обоих направлениях, то есть выбираются две точки и такие, что:

Иллюстрация выбора промежуточных точек метода золотого сечения.

, где — пропорция золотого сечения.

Таким образом:

То есть точка делит отрезок в отношении золотого сечения. Аналогично делит отрезок в той же пропорции. Это свойство и используется для построения итеративного процесса.

Алгоритм

На первой итерации заданный отрезок делится двумя симметричными относительно его центра, точками и рассчитываются значения в этих точках. После чего тот из концов отрезка, к которому среди двух вновь поставленных точек ближе оказалась та, значение в которой максимально (для случая поиска минимума), отбрасывают. На следующей итерации в силу показанного выше свойства золотого сечения уже надо искать всего одну новую точку. Процедура продолжается до тех пор, пока не будет достигнута заданная точность.

Формализация

  1. Шаг 1. Задаются начальные границы отрезка и точность , рассчитывают начальные точки деления: и значения в них целевой функции: .
  2. Шаг 2.
    • Если , то .
    • Иначе .
  3. Шаг 3.
    • Если , то и останов.
    • Иначе возврат к шагу 2.

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

В силу того, что в асимптотике , метод золотого сечения может быть трансформирован в так называемый метод чисел Фибоначчи. Однако при этом в силу свойств чисел Фибоначчи количество итерации строго ограничено. Это удобно, если сразу задано количество возможных обращений к функции.

Алгоритм

  1. Шаг 1. Задаются начальными границами отрезка и числом итераций , рассчитывают начальные точки деления: и значения в них целевой функции: .
  2. Шаг 2. .
    • Если , то .
    • Иначе .
  3. Шаг 3.
    • Если , то и останов.
    • Иначе возврат к шагу 2.

Литература

  1. Акулич И.Л. Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. пец. вузов. — М.: Высш. шк., 1986.
  2. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. Пер. с англ. — М.: Мир, 1985.
  3. Коршунов Ю.М., Коршунов Ю.М. Математические основы кибернетики. — М.: Энергоатомиздат, 1972.
  4. Максимов Ю.А.,Филлиповская Е.А. Алгоритмы решения задач нелинейного программирования. — М.: МИФИ, 1982.
  5. Максимов Ю.А. Алгоритмы линейного и дискретного программирования. — М.: МИФИ, 1980.
  6. Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. — М.: Наука, 1970. — С. 575-576.

См. также

Wikimedia Foundation. 2010.

  • Метод Симпсона
  • Метод Фоля

Смотреть что такое "Метод Фибоначчи поиска экстремума" в других словарях:

  • Фибоначчи числа — Числа Фибоначчи  элементы числовой последовательности 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597 … (последовательность A000045 в OEIS) в которой каждое последующее число равно сумме двух предыдущих чисел. Название по… …   Википедия

  • Метод золотого сечения — метод поиска значений действительно значной функции на заданном отрезке. В основе метода лежит принцип деления в пропорциях золотого сечения. Наиболее широко известен как метод поиска экстремума в решении задач оптимизации Содержание 1 Описание… …   Википедия

  • Метод чисел Фибоначчи — Метод золотого сечения метод поиска значений действительно значной функции на заданном отрезке. В основе метода лежит принцип деления в пропорциях золотого сечения. Наиболее широко известен как метод поиска экстремума в решении задач оптимизации …   Википедия

  • Метод Нелдера — Мида — Последовательные симплексы в методе Нелдера Мида для функции Розенброка (англ.) (вв …   Википедия

  • Метод Хука — Дживса (англ. Hooke  Jeeves), также как и алгоритм Нелдера Мида, служит для поиска безусловного локального экстремума функции и относится к прямым методам, то есть опирается непосредственно на значения функции. Алгоритм делится на две… …   Википедия

  • Метод сопряжённых градиентов — Метод сопряженных градиентов метод нахождения локального минимума функции на основе информации о её значениях и её градиенте. В случае квадратичной функции в минимум находится за шагов. Содержание 1 Основные понятия …   Википедия

  • ФИБОНАЧЧИ МЕТОД — разновидность одномерного поиска экстремума функции путем последовательного сужения интервала неопределенности. Единственное ограничение, налагаемое на исследуемую функцию требование строгой унимодальности на заданном интервале. При… …   Математическая энциклопедия

  • Метод Нелдера-Мида — Последовательные симплексы в методе Нелдера Мида для функции Розенброка (англ.) (вверху) и функции Химмельблау (англ.) (внизу) Не путать с «симплекс методом» из линейного программирования  методом оптимизации линейной системы с ограничениями.… …   Википедия

  • Метод деформируемого многогранника — Последовательные симплексы в методе Нелдера Мида для функции Розенброка (англ.) (вверху) и функции Химмельблау (англ.) (внизу) Не путать с «симплекс методом» из линейного программирования  методом оптимизации линейной системы с ограничениями.… …   Википедия

  • Числа Фибоначчи — Числа Фибоначчи  элементы числовой последовательности 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, … (последовательность A000045 в OEIS) в которой каждое последующее число равно сумме двух… …   Википедия

dic.academic.ru

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

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

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

Как и в методе дихотомии, процедура будет заключаться в последовательном уменьшении отрезка неопределенности на основании анализа значений функции в двух внутренних точках отрезка с существенным отличием от предыдущего, состоящего в том, что одна из внутренних точек последующего отрезка неопределенности совпадет с одной из двух внутренних точек предыдущего отрезка неопределенности.

Определение.

Последовательность чисел

называется последовательностью Фибоначчи.

Зададимся некоторым и выпишем последовательность чисел Фибоначчи.

Итак, необходимо найти минимум на отрезке с точностью.

Опишем 1-й шаг метода Фибоначчи.

Как и в предыдущем методе найдем на отрезке:

;

Из формул видно, что симметричны относительно середины отрезка.

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

В силу свойств последовательности Фибоначчи, на каждом шаге, кроме 1-го и предпоследнего, вычисляется одно новое значение функции, другое значение используется из предыдущего шага. Только на 1-м шаге значение вычисляется дважды, а на предпоследнем, когда совпадает с, известно из предыдущего шага. Можно показать, что на -м шагесовпадут, этим завершится процедура деления отрезка неопределенности. Для получения окончательного результата необходимо вычислить и , где - малая величина, параметр метода.

Если , то полагают, что, в противном случае.

Посмотрим, как уменьшается отрезок неопределенности

;

....................................................................................

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

Необходимо заметить, что для решения задачи минимизации с заданной точностью необходимо решить неравенствоотносительно , получить последовательность чисел Фибоначчи и использовать ее с конца.

Замечание 1.

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

Замечание 2.

Поскольку определяется сначала как функция от, алгоритм не позволяет получить более точный результат путем продолжения счета. Для обеспечения другой точности необходимо реализовать новую вычислительную процедуру.

Рисунок 3.3.11

Блок-схема метода Фибоначчи.

Пример.

Найти минимум на отрезке c

Начнем с определения :

Для решения поставленной задачи потребуется 9 шагов по методу Фибоначчи, при этом понадобится 9 раз вычислять . Заметим, что для решения этой же задачи методом дихотомии мы проделали 7 шагов, то есть вычисляли 14 раз.

1-й шаг.

;

.

2-й шаг.

.

3-й шаг.

;

.

4-й шаг.

;

.

5-й шаг.

;

.

6-й шаг.

;

.

7-й шаг.

.

8-й шаг.

;

.

9-й шаг.

;

.

Замечание.

Вычисления проводились с 5 знаками после запятой, поэтому точки последующего и предыдущего шага совпадают не полностью.

studfiles.net

Метод чисел Фибоначчи - это... Что такое Метод чисел Фибоначчи?

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

Метод золотого сечения — метод поиска значений действительно-значной функции на заданном отрезке. В основе метода лежит принцип деления в пропорциях золотого сечения. Наиболее широко известен как метод поиска экстремума в решении задач оптимизации.

Описание метода

Пусть задана функция . Тогда для того, чтобы найти определённое значение этой функции на заданном отрезке, отвечающее критерию поиска (пусть это будет минимум), рассматриваемый отрезок делится в пропорции золотого сечения в обоих направлениях, то есть выбираются две точки и такие, что:

Иллюстрация выбора промежуточных точек метода золотого сечения.

, где — пропорция золотого сечения.

Таким образом:

То есть точка делит отрезок в отношении золотого сечения. Аналогично делит отрезок в той же пропорции. Это свойство и используется для построения итеративного процесса.

Алгоритм

На первой итерации заданный отрезок делится двумя симметричными относительно его центра, точками и рассчитываются значения в этих точках. После чего тот из концов отрезка, к которому среди двух вновь поставленных точек ближе оказалась та, значение в которой максимально (для случая поиска минимума), отбрасывают. На следующей итерации в силу показанного выше свойства золотого сечения уже надо искать всего одну новую точку. Процедура продолжается до тех пор, пока не будет достигнута заданная точность.

Формализация

  1. Шаг 1. Задаются начальные границы отрезка и точность , рассчитывают начальные точки деления: и значения в них целевой функции: .
  2. Шаг 2.
    • Если , то .
    • Иначе .
  3. Шаг 3.
    • Если , то и останов.
    • Иначе возврат к шагу 2.

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

В силу того, что в асимптотике , метод золотого сечения может быть трансформирован в так называемый метод чисел Фибоначчи. Однако при этом в силу свойств чисел Фибоначчи количество итерации строго ограничено. Это удобно, если сразу задано количество возможных обращений к функции.

Алгоритм

  1. Шаг 1. Задаются начальными границами отрезка и числом итераций , рассчитывают начальные точки деления: и значения в них целевой функции: .
  2. Шаг 2. .
    • Если , то .
    • Иначе .
  3. Шаг 3.
    • Если , то и останов.
    • Иначе возврат к шагу 2.

Литература

  1. Акулич И.Л. Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. пец. вузов. — М.: Высш. шк., 1986.
  2. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. Пер. с англ. — М.: Мир, 1985.
  3. Коршунов Ю.М., Коршунов Ю.М. Математические основы кибернетики. — М.: Энергоатомиздат, 1972.
  4. Максимов Ю.А.,Филлиповская Е.А. Алгоритмы решения задач нелинейного программирования. — М.: МИФИ, 1982.
  5. Максимов Ю.А. Алгоритмы линейного и дискретного программирования. — М.: МИФИ, 1980.
  6. Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. — М.: Наука, 1970. — С. 575-576.

См. также

Wikimedia Foundation. 2010.

  • Метод функционала плотности
  • Методи Андонов-Ченто

Смотреть что такое "Метод чисел Фибоначчи" в других словарях:

  • Метод золотого сечения — метод поиска значений действительно значной функции на заданном отрезке. В основе метода лежит принцип деления в пропорциях золотого сечения. Наиболее широко известен как метод поиска экстремума в решении задач оптимизации Содержание 1 Описание… …   Википедия

  • Метод Фибоначчи поиска экстремума — Метод золотого сечения метод поиска значений действительно значной функции на заданном отрезке. В основе метода лежит принцип деления в пропорциях золотого сечения. Наиболее широко известен как метод поиска экстремума в решении задач оптимизации …   Википедия

  • Метод Нелдера-Мида — Последовательные симплексы в методе Нелдера Мида для функции Розенброка (англ.) (вверху) и функции Химмельблау (англ.) (внизу) Не путать с «симплекс методом» из линейного программирования  методом оптимизации линейной системы с ограничениями.… …   Википедия

  • Метод деформируемого многогранника — Последовательные симплексы в методе Нелдера Мида для функции Розенброка (англ.) (вверху) и функции Химмельблау (англ.) (внизу) Не путать с «симплекс методом» из линейного программирования  методом оптимизации линейной системы с ограничениями.… …   Википедия

  • Фибоначчи — (Fibonacci) Фибоначчи первый крупный математик средневековой Европы Десятичная система счисления, арабские цифры, числа, последовательность, уровни, ряд, линии и спираль Фибоначчи Содержание >>>>>>>>> …   Энциклопедия инвестора

  • Фибоначчи числа — Числа Фибоначчи  элементы числовой последовательности 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597 … (последовательность A000045 в OEIS) в которой каждое последующее число равно сумме двух предыдущих чисел. Название по… …   Википедия

  • Метод Фибоначчи с запаздываниями — (Lagged Fibonacci generator) один из методов генерации псевдослучайных чисел. Особенности распределения случайных чисел, генерируемых линейным конгруэнтным алгоритмом, делают невозможным их использование в статистических алгоритмах, требующих… …   Википедия

  • Метод Ньютона — Метод Ньютона, алгоритм Ньютона (также известный как метод касательных)  это итерационный численный метод нахождения корня (нуля) заданной функции. Метод был впервые предложен английским физиком, математиком и астрономом Исааком Ньютоном… …   Википедия

  • Чисел теория — Теория чисел, или высшая арифметика, раздел математики, изучающий целые числа и сходные объекты. В зависимости от используемых методов теорию чисел подразделяют на несколько подтеорий. Содержание 1 Элементарная теория чисел 2 Аналитическая теория …   Википедия

  • Числа Фибоначчи — Числа Фибоначчи  элементы числовой последовательности 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, … (последовательность A000045 в OEIS) в которой каждое последующее число равно сумме двух… …   Википедия

dic.academic.ru

реализация и сравнение / Хабр

Введение
Программистам числа Фибоначчи должны уже поднадоесть. Примеры их вычисления используются везде. Всё от того, что эти числа предоставляют простейший пример рекурсии. А ещё они являются хорошим примером динамического программирования. Но надо ли вычислять их так в реальном проекте? Не надо. Ни рекурсия, ни динамическое программирование не являются идеальными вариантами. И не замкнутая формула, использующая числа с плавающей запятой. Сейчас я расскажу, как правильно. Но сначала пройдёмся по всем известным вариантам решения.

Код предназначен для Python 3, хотя должен идти и на Python 2.

Для начала – напомню определение:

Fn= Fn-1+ Fn-2

и F1= F2=1.

Замкнутая формула
Пропустим детали, но желающие могут ознакомиться с выводом формулы. Идея в том, чтобы предположить, что есть некий x, для которого Fn = xn, а затем найти x.

что означает

сокращаем xn-2

Решаем квадратное уравнение:

Откуда и растёт «золотое сечение» ϕ=(1+√5)/2. Подставив исходные значения и проделав ещё вычисления, мы получаем:

что и используем для вычисления Fn.

from __future__ import division import math def fib(n): SQRT5 = math.sqrt(5) PHI = (SQRT5 + 1) / 2 return int(PHI ** n / SQRT5 + 0.5)

Хорошее: Быстро и просто для малых n Плохое: Требуются операции с плавающей запятой. Для больших n потребуется большая точность. Злое: Использование комплексных чисел для вычисления Fn красиво с математической точки зрения, но уродливо — с компьютерной.

Рекурсия
Самое очевидное решение, которое вы уже много раз видели – скорее всего, в качестве примера того, что такое рекурсия. Повторю его ещё раз, для полноты. В Python её можно записать в одну строку:fib = lambda n: fib(n - 1) + fib(n - 2) if n > 2 else 1

Хорошее: Очень простая реализация, повторяющая математическое определение Плохое: Экспоненциальное время выполнения. Для больших n очень медленно Злое: Переполнение стека

Запоминание
У решения с рекурсией есть большая проблема: пересекающиеся вычисления. Когда вызывается fib(n), то подсчитываются fib(n-1) и fib(n-2). Но когда считается fib(n-1), она снова независимо подсчитает fib(n-2) – то есть, fib(n-2) подсчитается дважды. Если продолжить рассуждения, будет видно, что fib(n-3) будет подсчитана трижды, и т.д. Слишком много пересечений.

Поэтому надо просто запоминать результаты, чтобы не подсчитывать их снова. Время и память у этого решения расходуются линейным образом. В решении я использую словарь, но можно было бы использовать и простой массив.

M = {0: 0, 1: 1} def fib(n): if n in M: return M[n] M[n] = fib(n - 1) + fib(n - 2) return M[n]

(В Python это можно также сделать при помощи декоратора, functools.lru_cache.)

Хорошее: Просто превратить рекурсию в решение с запоминанием. Превращает экспоненциальное время выполнение в линейное, для чего тратит больше памяти. Плохое: Тратит много памяти Злое: Возможно переполнение стека, как и у рекурсии

Динамическое программирование
После решения с запоминанием становится понятно, что нам нужны не все предыдущие результаты, а только два последних. Кроме этого, вместо того, чтобы начинать с fib(n) и идти назад, можно начать с fib(0) и идти вперёд. У следующего кода линейное время выполнение, а использование памяти – фиксированное. На практике скорость решения будет ещё выше, поскольку тут отсутствуют рекурсивные вызовы функций и связанная с этим работа. И код выглядит проще.

Это решение часто приводится в качестве примера динамического программирования.

def fib(n): a = 0 b = 1 for __ in range(n): a, b = b, a + b return a

Хорошее: Быстро работает для малых n, простой код Плохое: Всё ещё линейное время выполнения Злое: Да особо ничего.

Матричная алгебра
И, наконец, наименее освещаемое, но наиболее правильное решение, грамотно использующее как время, так и память. Его также можно расширить на любую гомогенную линейную последовательность. Идея в использовании матриц. Достаточно просто видеть, что

А обобщение этого говорит о том, что

Два значения для x, полученных нами ранее, из которых одно представляло собою золотое сечение, являются собственными значениями матрицы. Поэтому, ещё одним способом вывода замкнутой формулы является использование матричного уравнения и линейной алгебры.

Так чем же полезна такая формулировка? Тем, что возведение в степень можно произвести за логарифмическое время. Это делается через возведения в квадрат. Суть в том, что

где первое выражение используется для чётных A, второе для нечётных. Осталось только организовать перемножения матриц, и всё готово. Получается следующий код. Я организовал рекурсивную реализацию pow, поскольку её проще понять. Итеративную версию смотрите тут.

def pow(x, n, I, mult): """ Возвращает x в степени n. Предполагает, что I – это единичная матрица, которая перемножается с mult, а n – положительное целое """ if n == 0: return I elif n == 1: return x else: y = pow(x, n // 2, I, mult) y = mult(y, y) if n % 2: y = mult(x, y) return y def identity_matrix(n): """Возвращает единичную матрицу n на n""" r = list(range(n)) return [[1 if i == j else 0 for i in r] for j in r] def matrix_multiply(A, B): BT = list(zip(*B)) return [[sum(a * b for a, b in zip(row_a, col_b)) for col_b in BT] for row_a in A] def fib(n): F = pow([[1, 1], [1, 0]], n, identity_matrix(2), matrix_multiply) return F[0][1]

Хорошее: Фиксированный объём памяти, логарифмическое время Плохое: Код посложнее Злое: Приходится работать с матрицами, хотя они не так уж и плохи

Сравнение быстродействия
Сравнивать стоит только вариант динамического программирования и матрицы. Если сравнивать их по количеству знаков в числе n, то получится, что матричное решение линейно, а решение с динамическим программированием – экспоненциально. Практический пример – вычисление fib(10 ** 6), числа, у которого будет больше двухсот тысяч знаков.

n = 10 ** 6 Вычисляем fib_matrix: у fib(n) всего 208988 цифр, расчёт занял 0.24993 секунд. Вычисляем fib_dynamic: у fib(n) всего 208988 цифр, расчёт занял 11.83377 секунд.

Теоретические замечания
Не напрямую касаясь приведённого выше кода, данное замечание всё-таки имеет определённый интерес. Рассмотрим следующий граф:

Подсчитаем количество путей длины n от A до B. Например, для n = 1 у нас есть один путь, 1. Для n = 2 у нас опять есть один путь, 01. Для n = 3 у нас есть два пути, 001 и 101. Довольно просто можно показать, что количество путей длины n от А до В равно в точности Fn. Записав матрицу смежности для графа, мы получим такую же матрицу, которая была описана выше. Это известный результат из теории графов, что при заданной матрице смежности А, вхождения в Аn — это количество путей длины n в графе (одна из задач, упоминавшихся в фильме «Умница Уилл Хантинг»).

Почему на рёбрах стоят такие обозначения? Оказывается, что при рассмотрении бесконечной последовательности символов на бесконечной в обе стороны последовательности путей на графе, вы получите нечто под названием "подсдвиги конечного типа", представляющее собой тип системы символической динамики. Конкретно этот подсдвиг конечного типа известен, как «сдвиг золотого сечения», и задаётся набором «запрещённых слов» {11}. Иными словами, мы получим бесконечные в обе стороны двоичные последовательности и никакие пары из них не будут смежными. Топологическая энтропия этой динамической системы равна золотому сечению ϕ. Интересно, как это число периодически появляется в разных областях математики.

habr.com