No Image

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

СОДЕРЖАНИЕ
2 043 просмотров
10 марта 2020

Алгоритм поиска минимума функции сводится к выполнению следующих этапов.

1 этап. Задается начальный интервал неопределенности , – допустимая длина конечного интервала, – константа различимости.

2 этап. Найти количество вычислений функции как наименьшее целое число, при котором удовлетворяется условие и числа Фибоначчи .

3 этап. Задать .

4 этап. Вычислить .

5 этап. Вычислить .

6 этап. Если , то принять и . Перейти к этапу 7.

Если , принять и .

7 этап. Если , то принять и перейти к этапу 5.

Если , то всегда , то есть отсутствует точка нового вычисления функции. В этом случае следует принять . В точках вычисляются значения функции и находятся границы конечного интервала неопределенности:

– если , то принять ;

– если , то принять .

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

Характеристика относительного уменьшения начального интервала неопределенности , где количество вычислений функции.

Метод квадратичной интерполяции

(метод Пауэлла)

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

Алгоритм поиска точки минимума с квадратичной интерполяцией

Алгоритм поиска минимума функции сводится к выполнению следующих этапов.

1 этап. Задать начальную точку , величину шага , – малые положительные числа, характеризующие точность.

2 этап. Вычислить .

3 этап. Вычислить .

4 этап. Если , то принять .

Если , то принять .

5 этап. Вычислить .

6 этап. Найти .

7 этап. Вычислить точку минимума интерполяционного полинома, построенного по трем точкам:

и величину . Если знаменатель в формуле для на некоторой итерации обращается в нуль, то результатом интерполяции является прямая линия. В этом случае рекомендуется принять и перейти к шагу 2.

8 этап. Проверить выполнение условий окончания

.

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

Если хотя бы одно из условий не выполнено и , выбрать наилучшую точку ( или ) и две точки по обе стороны от нее. Переобозначить эти точки в порядке возрастания и перейти к этапу 6.

Если хотя бы одно из условий не выполнено и , то принять и перейти к этапу 2.

Варианты заданий

Варианты заданий приведены в таблице.

Таблица. Варианты заданий

F(X) = Тип экстремума Исходный интервал Погрешность
max [4; 9] 0.02
min [-1; 0] 0.005
max [4; 9] 0.02
min [-1; 0] 0.005
min [0.5; 1] 0.001
min [-2; 0] 0.01
min [-1.5; 3] 0.01
min [1.3; 3.0] 0.01
max [0; 3] 0.02
min [0; 2.5] 0.02
max [0.8; 2.0] 0.008
min [0; 1.5] 0.01
min [1; 3] 0.012
max [0; 3] 0.02
max [-1; 0.5] 0.005
min [0; 2] 0.01
min [0; 2] 0.01
min [-1; 0] 0.002
min [0; 1] 0.005
min [-1; 1] 0.01
max [2; 6] 0.02
min [0; 2] 0.01
min [0.5; 2] 0.01
min [0; 1.5] 0.01
min [0.5; 2] 0.005
min [0; 2] 0.005

Задание

1. Составить блок-схемы алгоритмов поиска точки экстремума заданной функции.

2. Построить график функции для выбора границ первоначального интервала.

3. По разработанным алгоритмам составить программы поиска минимума функции.

4. Найти координаты и значение функции в точке минимума всеми методами.

5. Найти точное значение координаты точки минимума, используя необходимые и достаточные условия экстремума.

6. Проанализировать полученные результаты и сделать выводы по достигнутой точности и количеству вычислений функции.

7. Дать письменные ответы на контрольные вопросы.

Контрольные вопросы

1. В чем состоит необходимое и достаточное условие экстремума одномерной функции?

2. В чем заключается условие унимодальности функции и как это условие используется?

3. Понятие выпуклой функции.

4. Как найти экстремум функции?

5. Как ведет себя производная в области точки экстремума?

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

7. Как ведет себя касательная к выпуклой функции? Поведение ее в области экстремума?

8. Можно считать, что глобальный минимум является локальным? А наоборот?

9. В чем различие между пассивным и последовательным поиском?

10. Что называют интервалом неопределенности в задачах одномерной оптимизации?

Читайте также:  Как отследить машины яндекс такси

11. В чем состоит метод дихотомии?

12. Какие трудности возникают в методе квадратичной аппроксимации?

13. Каким образом сравнивают эффективность методов прямого поиска?

Содержание отчета

2. Формулировка задачи.

3. Блок-схемы алгоритмов поиска минимума.

4. Графическое представление функции.

5. Листинги программ.

6. Результаты вычислений.

7. Сравнительная характеристика методов.

ЛИТЕРАТУРА

1. Лесин В.В., Лисовец Ю.П. Основы методов оптимизации: Учебное пособие. – СПб.: Издательство «Лань», 2011. – 352 с.

2. Пантелеев А.В., Летова Т.А. Методы оптимизации в примерах и задачах: Учебное пособие. – М.: Высшая школа, 2002.- 544 с.

Временной ресурс:

– аудиторные занятия – 4 часа;

– самостоятельная работа – 16 часов.

Общие условия выбора системы дренажа: Система дренажа выбирается в зависимости от характера защищаемого.

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

Опора деревянной одностоечной и способы укрепление угловых опор: Опоры ВЛ – конструкции, предназначен­ные для поддерживания проводов на необходимой высоте над землей, водой.

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

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

Алгоритм

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

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

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

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

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

      Алгоритм

      1. Шаг 1. Задаются начальными границами отрезка и числом итераций , рассчитывают начальные точки деления: и значения в них целевой функции: .
      2. Шаг 2..
        • Если , то .
        • Иначе .
        • Шаг 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) в которой каждое последующее число равно сумме двух… … Википедия

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

          Значительная часть прикладных задач связана с методами оптимизации. Оптимизация применяется с различной целью, в зависимости от той цели, которую поставила данная отрасль.

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

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

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

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

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

          Объем и структура курсовой работы. Работа состоит из введения, пяти глав, содержит 18 страниц, в том числе 3 рисунка, 2 таблицы. Список литературы включает 3 наименования.

          Метод Фибоначчи очень тесно связан с числами, названными в честь великого математика Фибоначчи, настоящее имя которого Леонардо Пизанский. Стоит уделить некоторое место в данной работе, биографии ученого, с чьим именем непосредственно связан описываемый метод.

          Леонардо Пизанский (около 1170 – около 1250) являлся первым крупным математиком средневековой Европы. Фибоначчи – это прозвище, которое переводится с итальянского как “Хороший сын родился” .Отец его был торговец, поэтому часто разъезжал по разным странам. Чаще всего его отец бывал в Алжире, где юный Леонардо обучался математике у арабских учителей. Он изучал труды исламских математиков, по переводам ознакомился с трудами античных и индийских математиков. Фибоначчи написал ряд математических трактатов на основе усвоенных им знаний. Самый известный труд ученого называется “Книга абака”. В этой книге были изложены все арифметические и алгебраические сведения того времени с неимоверной ясностью и глубиной. В отдельной главе, посвященной арифметической и геометрической прогрессии, ряда квадрата, впервые описана последовательность чисел Фибоначчи [3].

          Читайте также:  Gta san andreas дата выхода

          Числа Фибоначчи – элементы числовой последовательности, в которой каждое последующие число равно сумме двух предыдущих. Их можно определить по формуле:

          В итоге получаем некоторую последовательность чисел:

          Помимо числовой последовательности Леонардо Пизанский сделал ряд открытий :

          – сформулировал правило для нахождения суммы членов произвольной –

          – рассмотрел возвратную последовательность, в которой каждое число,

          начиная с третьего, равно сумме двух предшествующих ему чисел;

          – ввел термин «частное» для обозначения результата деления;

          – описал способ приведения дробей к общему знаменателю с помощью

          нахождения наименьшего общего кратного знаменателя (более

          рациональный чем использовали арабские математики).

          Кроме этого, он разработал свои методы решения различных задач.

          Леонардо Пизанский внес большой вклад в математику средневековой Европы.

          Метод Фибоначчи применяется для численного поиска безусловного экстремума. Требуется найти x для f ( x ) на интервале [ a ; b ] , где существует экстремум данной функции, x должен соответствовать точке экстремума.

          Наша задача сводится к поиску, а задача поиска имеет три важных аспекта:

          1. Пусть мы имеем право совершить n последовательных определений значения f , выбирая каждый раз точку определения по своему усмотрению. То возникают вопросы, в каких точках следует определять значения функций, чтобы точка x определялась с наибольшой точностью, и какова эта точность?

          2.Если мы хотим определить минимизирующую функцию f в точке x с заданной точностью e . Сколько определений значений функции f для этого неоходмо произвести и как эти определения организовать?

          3. В каких условиях данные возможности достаточны для достижения поставленной цели? Т.е. неоходимо решение нескольких задач.

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

          Как правило метод Фибоначчи применяется для унимодальных функций. Это класс функций, которые достигают своего экстремума x * на интервале [ a 0 ; b 0 ] , причем этот экстремум единственный. При этом функция слева от x * убывает, а справа возрастает.

          Если a 0 ≤ z x * , то f ( y )> f ( z ) , но если x * y z ≤ 0 , то f ( y ) f ( z ) (рис1.а).

          Можно отметить следующий факт: что непрерывная строго выпуклая вниз функция является унимодальной. Однако определению удовлетворяют функции не являющиеся непрерывными и унимодальными(рис.1б).

          Еще раз сформулируем поставленную задачу. У нас есть функция f ( x ) которая имеет экстремум на заданном интервале [ a 0 ; b 0 ] , необходимо найти экстремум этой функции x * на этом интервале не более чем за N шагов.

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

          Методы одномерной минимизации возникают при вариации параметра x , который является скалярным.

          Существует различное количество методов минимизации, такие как оптимальный пассивный поиск, метод деления пополам, метод Фибоначчи и золотого сечения, которые основаны на сравнении значений функции f ( x ) вычисляемых в точках x 1 , x 2 , … , x n . Это методы так называемого прямого поиска, в котором точки x являются пробными.

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

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

          В качества сравнения преимуществ и недостатков метода Фибоначчи над остальными методами прямого поиска приведем таблицу 1[2], которая сравнивает методы по выше описанным критериям. Как видно из таблицы совсем не эффективен метод оптимального пассивного поиска. Метод Фибоначчи по эффективности превосходит метод деления пополам и почти одинаков с методом золотого сечения.

          Комментировать
          2 043 просмотров
          Комментариев нет, будьте первым кто его оставит

          Это интересно
          Adblock
          detector