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

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

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

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 часов.

Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов (88‰).

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

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

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

Метод Фибоначчи [ править ]

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

Описание [ править ]

Метод основан на последовательности чисел Фибоначчи [math] [/math] , которая определяется следующим образом :

[math] F_v = F_ + F_, v = 1, 2, 3,dots, F_0 = F_1 = 1 [/math]

Таким образом, последовательность Фибоначчи имеет вид [math] 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …[/math] Предположим, что на [math]k[/math] -й итерации интервал неопределенности равен [math][a_k, b_k][/math] . Рассмотрим две точки [math]<lambda>_k[/math] и [math]<mu>_k[/math] , определяемые следующим образом:

где [math] k = 1, 2, dots, n-1[/math] и [math]n[/math] — заданное общее число вычислений функции.

Новый интервал неопределенности [math][a_, b_][/math] будет равен [math] [<lambda>_k, b_k][/math] , если [math] fleft(<lambda>_k
ight) gt fleft(<mu>_k
ight)[/math] и [math][a_k, <mu>_k][/math] , если [math] fleft(<lambda>_k
ight) le fleft(<mu>_k
ight)[/math] . В первом случае, учитывая [math]<lambda>_k [/math] и полагая [math]v = n — k[/math] , получим

[math]b_ — a_ = b_k — <lambda>_k = b_k — a_k — dfrac>>*left(b_k — a_k
ight) = dfrac>>*left(b_k — a_k
ight)[/math] .

Во втором случае, учитывая [math] <mu>_k[/math] , получаем

[math] b_ — a_ = <mu>_k — a_k = dfrac>>*left(b_k — a_k
ight)[/math] .

Таким образом, в обоих случаях длина интервала неопределенности сжимается с коэффициентом [math]dfrac>>[/math] . Покажем, что на [math]k-[/math] той итерации либо [math]<lambda>_k = <mu>_k[/math] , либо [math]<mu>_ = <lambda>_k[/math] , так что требуется только одно новое вычисление функции. Предположим, что [math] fleft(<lambda>_k
ight) gt fleft(<mu>_k
ight)[/math] . Тогда [math]a_ = <lambda>_k, b_ = b_k[/math] . Таким образом, используя [math] F_v = F_ + F_, v = 1, 2, 3,dots, F_0 = F_1 = 1 [/math] и заменив [math]k[/math] на [math]k+1[/math] , получаем [math]<lambda>_ = a_ + dfrac>>*left(b_ — a_
ight) = <lambda>_k + dfrac>>*left(b_k — <lambda>_k
ight)[/math] . Подставив выражение для [math]<lambda>_k[/math] и заменив [math]k[/math] на [math]k + 1[/math] , получим [math]<lambda>_ = a_k + dfrac>>*left(b_k — a_k
ight) + dfrac>>*left(1 — dfrac>>
ight)*left(b_k — a_k
ight)[/math] .

Читайте также:  Файл dng что это

Если [math]fleft(<lambda>_k
ight) le fleft(<mu>_k
ight)[/math] , то выполнив аналогичные преобразования, получим [math]<lambda>_ = <lambda>_k[/math] . Таким образом, в обоих случаях на [math]k + 1[/math] -й итерации требуется только одно вычисление функции. В отличие от метода золотого сечения в методе Фибоначчи требуется, чтобы общее число вычислений [math]n[/math] (или коэффициент сокращения исходного интервала) было задано заранее. Это объясняется тем, что точки, в которых производятся вычисления, зависят от [math]n[/math] . Длина интервала неопределенности на [math]k[/math] -той итерации сжимается с коэффициентом [math]dfrac>>[/math] . Следовательно, после [math] left(n-1
ight)[/math] итерации, где [math]n[/math] — заданное общее число вычислений функции [math]fleft(x
ight)[/math] , длина интервала неопределенности сократится от [math]left(b_1 — a_1
ight)[/math] до [math]dfrac[/math] .

Алгоритм [ править ]

Предварительный этап. Выбрать допустимую конечную длину интервала неопределенности [math]l gt 0[/math] и константу различимости [math]<epsilon>[/math] . Пусть задан начальный интервал неопределенности [math]left(b_1 — a_1
ight)[/math] . Выбрать общее число вычислений функции [math]n[/math] так, чтобы [math]F_n gt dfrac[/math] . Положить [math]<lambda>_1 = a_1 + dfrac>*left(b_1 — a_1
ight)[/math] , [math]<mu>_1 = a_1 + dfrac>
*left(b_1 — a_1
ight)[/math] .Вычислить [math]fleft(<lambda>_1
ight)[/math] , [math]fleft(<mu>_1
ight)[/math] , положить [math]k = 1[/math] и перейти к основному этапу.

Первый шаг. Если [math]fleft(<lambda>_k
ight) gt fleft(<mu>_k
ight)[/math] , то перейти ко второму шагу, в противном случае – к третьему шагу.

Второй шаг.Положить [math]a_ = <lambda>_k, b_ = b_k[/math] . Затем положить [math]<lambda>_ = <mu>_k[/math] , [math]<mu>_ = a_ + dfrac>>*left(b_ — a_
ight)[/math] . Если [math]k = n — 2[/math] , то перейти к пятому шагу, в противном случае вычислить [math]fleft(<mu>_
ight)[/math] и перейти к четвертому шагу.

Третий шаг. Положить [math]a_ = a_k[/math] , [math]b_ = <mu>_k[/math] , [math]<mu>_ = <lambda>_k[/math] , [math]<lambda>_ = a_ + dfrac>>*left(b_ — a_
ight)[/math] . Если [math]k = n — 2[/math] , то перейти к пятому шагу, в противном случае [math]fleft(<lambda>_
ight)[/math] и перейти к четвертому шагу.

Четвертый шаг. Заменить [math]k[/math] на [math]k + 1[/math] и перейти к первому шагу.

Пятый шаг. Положить [math]<lambda>_n = <lambda>_[/math] , [math]<mu>_n = <lambda>_n + <epsilon>[/math] . Если [math]fleft(<lambda>_n
ight) = fleft(<mu>_n
ight)[/math] , то положить [math]a_n = <lambda>_n, b_n = b_[/math] . В противном случае (если [math]fleft(<lambda>_n
ight) lt fleft(<mu>_n
ight)[/math] ), положить [math]a_n = a_, b_n = <mu>_n[/math] .

Конец: оптимальное решение содержится в интервале [math][a_n, b_n][/math] .

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

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

Алгоритм

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

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

  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) в которой каждое последующее число равно сумме двух… … Википедия

          Ссылка на основную публикацию
          Adblock detector