Оптимизация функций. Метод золотого сечения. Метод дихотомии

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

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

«Томский государственный университет систем управления и радиоэлектроники» (ТУСУР)

Кафедра автоматизации обработки информации (АОИ)

Оптимизация функций. Метод золотого сечения. Метод дихотомии.

Курсовая работа по дисциплине: «Информатика и программирование»

Работу выполнил

Студент гр.408

_________  Д.П.Васильева

«____»______________ 2019 г.

Руководитель:

  _________  Н.В.Пермякова

«____»______________ 2019 г.

Томск 2019

Введение

1. Численные методы …

 1.1. Общая часть

1.2. Математическое описание метода 1

1.3. Математическое описание метода 2

2. Программная реализация

2.1. Функциональная структура программы

  2.2.Руководство пользователя

2.3. Результаты тестирования метода 1

 2.4. Результаты тестирования метода 2

3. Сравнительный анализ методов

Заключение

Список использованной литературы.

Введение

Оптимизация – это выбор, нахождение лучшего «оптимального» решения из всех возможных вариантов. Теорию и методы решения задачи оптимизации изучает математическое программирование.

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

Методы оптимизации - это раздел вычислительной математики, объединяющий методы и алгоритмы решения задач оптимизации функций, а также обосновывающие применение этих методов теоретические результаты. Линейное программирование дисциплина, посвящённая теории и методам решения экстремальных задач на множествах n-мерного векторного пространства, задаваемых системами линейных уравнений и неравенств. Одним из обобщений линейного программирования является дробно-линейное программирование. Оптимизационные методы одни из важнейших пунктов в процессе в линейном программировании. И количество методов великое множество и практика порождает все новые и все наиболее сложные методы. Но универсального метода, который подходит для поиска экстремума абсолютно любой функции не существует.

Целью курсовой работы является изучение и рассмотрение двух из них – метода золотого сечения и метода дихотомии.

Задачи курсовой работы:

- Изучение методов золотого сечения и дихотомии;

- Программная реализация методов, получение практического опыта;

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

Численные методы оптимизации

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

Численные методы классифицируются на:

• Методы направленного поиска экстремума
• Методы случайного поиска экстремума

Также методы направленного поиска экстремума подразделятся на:

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

Суть численных алгоритмов оптимизации при отыскании минимума функции f(x) состоит в построении минимизирующей последовательности[pic 1]

где где  – начальные значения; – направление поиска минимума на k -м шаге;  – величина шага в указанном направлении. Если для всех k выполняется условие  и минимум функции существует, то последовательность значений  сходится к решению задачи минимизации  . На практике добиваются достаточно малой заданной величины разницы между значениями аргументов и (или) значений функций на двух последовательных итерациях.[pic 2][pic 3][pic 4][pic 5][pic 6][pic 7]