Российская Федерация

Министерство образования и науки Российской Федерации

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

«Брянский государственный университет имени академика И.Г. Петровского»

Естественно-научный институт

Физико-математический факультет

Кафедра информатики и прикладной математики

«ПОИСКОВЫЙ МЕТОД МИНИМИЗАЦИИ МУЛЬТИМОДАЛЬНОЙ ФУНКЦИИ ОДНОЙ ПЕРЕМЕННОЙ НА ОСНОВЕ ДАУХЗВЕННОЙ СХЕМЫ ОТБОРА ИНТЕРВАЛОВ ПЕРВОГО ПОРЯДКА»

Реферат для поступления в магистратуру

«Математика»

профиль «Комплексный анализ и алгебра»

Подготовила:

Дембовская Нина Витальевна

Оценка за защиту реферата:

______________________________________________

Члены магистерской комиссии:

________________________ _________________

^{ФИО экзаменатора подпись}

________________________ _________________

^{ФИО экзаменатора подпись}

«__» ______________ 2014 г.

Брянск – 2014

Содержание

Введение 3

Исследование поискового метода минимизации мультимодальной функции одной переменной на основе двухзвенной схемы отбора интервалов первого порядка 6

Метод последовательного перебора 6

Поисковый метод минимизации мультимодальной функции одной переменной на основе двухзвенной схемы отбора интервалов первого порядка 11

Реализация поискового метода минимизации мультимодальной функции одной переменной на основе двухзвенной схемы отбора интервалов первого порядка и метода последовательного перебора 17

Сравнительное исследование эффективности методов 30

Заключение 43

Список литературы 44

Приложение 46

Введение

Экстремальные задачи нередко возникают в различных отраслях современной науки, таких, как информатика, кибернетика, экономика, космонавтика, физика, вычислительная математика, технические науки и многие другие. В большинстве случаев экстремальные задачи не поддаются аналитическому исследованию и для их решения используются численные методы, ориентированные на применение компьютера. Численные методы минимизации функций многих переменных обычно сводят решение многомерной экстремальной задачи к итерационному процессу на каждом шаге которого решается задача одномерной минимизации (задача определения минимума функции одной переменной). Существующие методы одномерной минимизации, в свою очередь, принято подразделять на методы локальной и глобальной минимизации. Первые применяются в основном для определения минимума унимодальных функций [20]. Применение методов локальной минимизации к функциям, имеющим несколько локальных минимумов, приводит обычно к определению одного из локальных минимумов, не обязательно совпадающего с минимумом глобальным. К наиболее распространённым методам локальной минимизации относятся такие методы, как метод половинного деления, метод золотого сечения, метод парабол. Методы глобальной минимизации работают намного медленнее, зачастую требуют хранения больших наборов данных, но зато позволяют во многих случаях найти глобальный минимум функции, которая не является унимодальной. К наиболее известным методам глобальной минимизации относятся метод равномерного перебора и метод ломаных [2].

Работы, посвященные новым методам минимизации функций одной переменной, продолжают появляться на страницах математических книги журналов [2], [4], [16]. К настоящему времени не существует общепринятого универсального численного метода, который позволял бы получать оптимальное решение для любой задачи нелинейной оптимизации. При решении каждой задачи минимизации, может требоваться применение нескольких методов, поэтому эффективное решение задачи минимизации зависит от набора алгоритмов минимизации, которыми владеет исследователь.

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

Целью данной работы является исследование и программная реализация нового поискового метода минимизации мультимодальной функции одной переменной на основе двухзвенной схемы отбора интервалов первого порядка [20].

Для достижения цели решались задачи:

1. Создание обзора методов минимизации функций и функционалов.

2. Реализация метода последовательного перебора средствами Borland Delphi.

3. Реализация поискового метода минимизации мультимодальной функции одной переменной на основе двухзвенной схемы интервалов первого порядка средствами Borland Delphi.

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

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