Автор работы: Пользователь скрыл имя, 10 Ноября 2014 в 22:10, курсовая работа
С задачами поиска минимума функции приходится сталкиваться во многих областях науки, а также в практической деятельности. Дело в том, что многие технические, экономические и т.д. процессы моделируются функцией или несколькими функциями, которые зависят от переменных – факторов, влияющих на состояние моделируемого явления. Требуется найти экстремумы таких функций для того, чтобы определить оптимальное состояние, управление процессом.
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
«ДОНСКОЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»
ДГТУ
Кафедра «Программное обеспечение вычислительной техники и автоматизированных систем»
«ПОВТ и АС»
Курсовая работа по дисциплине «Методы вычислений»
на тему: «Метод Фибоначчи минимизации функции одной переменной»
Автор курсовой работы: Кузнецов Евгений Николаевич
Группа:
Специальность: 010500 «Математическое обеспечение и администрирование информационных систем»
Руководитель работы:
Ростов-на-Дону
2014 г.
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
«ДОНСКОЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»
ДГТУ
Кафедра «Программное обеспечение вычислительной техники и автоматизированных систем»
«ПОВТ и АС»
УТВЕРЖДАЮ
Зав. каф. Нейдорф Р.А.
«__» _______ 2014 г.
ЗАДАНИЕ
на курсовую работу по дисциплине «Методы вычислений»
Студент: Кузнецов Е. Н. Группа
Тема: «Метод Фибоначчи минимизации функции одной переменной»
Срок представления работы к защите “__” _______ 2014 г.
Исходные данные для курсовой работы: конспект лекций по методам вычислений, кн. Практикум по высшей математике Соболь Б.В.
Содержание пояснительной записки:
Введение: Описание экстремумов.
Разделы основной части: 1 ТЕОРЕТИЧЕСКИЙ ОБЗОР, 2 АЛГОРИТМИЧЕСКОЕ КОНСТРУИРОВАНИЕ, 3 ПРОГРАММНОЕ КОНСТРУИРОВАНИЕ, 4 РЕЗУЛЬТАТЫ РАБОТЫ ПРОГРАММНОГО СРЕДСТВА.
Руководитель работы:
РЕФЕРАТ
Отчет содержит: страниц-17, рисунков- 5,блок-схем-1, источников- 3.
Ключевые слова: МИНИМУМ ФУНКЦИИ, ПОИСК ЭКСТРЕМУМОВ, МЕТОД ФИБОНАЧЧИ.
В данной курсовой работе разработан программный модуль, ориентированный на нахождения минимума целевой функции по методу Фибоначчи на заданном отрезке, с заданным количеством вычислений и точностью. Результаты работы программного средства тестируются с помощью нескольких функций и сравниваются со встроенными функциями системы компьютерной математики MathCad.
СОДЕРЖАНИЕ
С задачами поиска минимума функции приходится сталкиваться во многих областях науки, а также в практической деятельности. Дело в том, что многие технические, экономические и т.д. процессы моделируются функцией или несколькими функциями, которые зависят от переменных – факторов, влияющих на состояние моделируемого явления. Требуется найти экстремумы таких функций для того, чтобы определить оптимальное состояние, управление процессом.
Ещё в XX в. потребности техники, в частности космической, выдвинули серию задач, которые не поддавались средствам вариационного исчисления. В экономике также существовал ряд проблем, например, минимизация издержек или максимизация прибыли, для которых требовалось создание эффективных методов оптимизации. Всё это привело к тому, что теория экстремальных задач получила новый мощный толчок к дальнейшим исследованиям.
Существует множество различных способов определения минимума функции с разным количеством итераций и уровнем определения точности. Также возможно комбинировать некоторые способы для достижения большей эффективности алгоритма. В этой работе будет рассмотрен метод Фибоначчи для нахождения минимума целевой функции на заданном интервале.
В данном методе используются числа Фибоначчи. Они названы по имени средневекового математика Леонардо Пизанского (известного как Фибоначчи). Это числа, которые определяются по следующему алгоритму: нулевое и первое число равно нулю, а каждое следующее равно сумме двух предыдущих.
Последовательность Фибоначчи была хорошо известна в древней Индии, где она применялась в метрических науках, намного раньше, чем она стала известна в Европе. Именно на этой последовательности основан изложенный в данной работе метод.
Рассмотрим целевую функция . Данная функция является функцией одной переменной, которая имеет на интервале минимизации всего одну точку минимума (впадину).
Функция , заданная на интервале называется унимодальной на [a,b], если существует единственная точка x* минимума , т.е. {на } если для любых двух точек x1,x2 принадлежащих [a,b] выполняется соотношение:
-из неравенств следует >;
-из неравенств следует >.
Необходимое условие минимума (максимума) функции в точке . Необходимые условия того, что x* является точкой локального минимума (максимума) дважды дифференцируемой функции f(x) на открытом интервале (a,b) выражаются следующими соотношениями:
1) fx|x=x* =0, 2) fxx|x=x* => 0 (<=0)
Определение: стационарной точкой называется точка x*, в которой fx|x=x* =0. Если стационарная точка не соответствует локальному оптимуму (минимуму или максимуму), то она называется точкой перегиба.
Достаточные условия экстремума. Пусть в точке x* первые (n-1) производные функции обращаются в нуль, а производная порядка n отлична от нуля.
Также можно отметить, что если имеется алгоритм нахождения минимума функции, то возможно с его помощью находить максимум функции. Для этого необходимо воспользоваться существующим алгоритмом, использовав при этом в качестве функции исходную, но взятую с противоположным знаком:
f1(x) = -f(x)
Метод Фибоначчи обеспечивает максимальное сокращение интервала неопределённости при заданном количестве вычислений функции
Алгоритм поиска по методу Фибоначчи определяется по тем же правилам симметрии, что и алгоритм по методу золотого сечения. На первой итерации выберается две точки , расположенные симметрично относительно середины отрезка [a, b]. На каждой последующей итерации точка очередного вычисления выбирается симметрично оставшейся точке. При заданном количестве вычислений n и заданной погрешности вычислении ε, точки деления интервала неопределённости (где j=1,2, .. , n-1) вычисляются по формулам:
здесь Fk – число Фибоначчи, определяемое следующим образом:
.
Следует отметить, что на итерации j > 1 вычисляется только та из точек , которая не была определена на предыдущем шаге. За оценку точки минимума принимается та из точек , которая осталась внутри итогового интервала (рис. 1).
Ориентировочное значение числа Фибоначчи , обеспечивающее достижение требуемой точности, выбирается из условия:
Рисунок 1 - Уменьшение интервала неопределенности
Алгоритм метода Фибоначчи описать следующим образом:
где Fk – число Фибоначчи; и значения в них целевой функции: .
.
Иначе:
.
Увеличиваем j на 1.
Цель курсовой работы: «разработать программный модуль для нахождения минимума целевой функции по методу Фибоначчи».
Для ознакомления с общими сведениями о минимизации функции и, конкретно, с методом Фибоначчи составить теоретический обзор.
Привести алгоритм метода, а также составить блок-схему метода.
Для проверки корректности работы программы и правильности результатов вычислений привести ряд тестовых испытаний с последующим сравнением с результатами встроенной функции MathCad.
Исследуемые на экстремум функции изобразить графически.
Рисунок 2 – Блок-схема алгоритма минимизации функции по методу Фибоначчи
Программный модуль метода Фибоначчи по нахождения минимума целевой функции. Подробное описание и пошаговая инструкция представлена в теоретическом обзоре пункт 2.2.
Входные параметры:
Выходные параметры:
В ходе выполнения данной курсовой работы была разработана программа, полностью соответствующая условиям задания, позволяющая производить поиск минимума целевой функции на заданном пользователем отрезке.
Также была реализована возможность находить максимум функции. Для этого используется функция, равная исходной, но с противоположным знаком, у которой находится минимум. Он же будет максимумом исходной функции.
Для проверки эффективности работы и точности вычисления программного модуля по методу Фибоначчи, было взято 3 функции различной сложности. Результаты вычислений были проверены функциями MathCad:
minimize(f, var1, var2, ...) - возвращает значения переменных var1, var2, ..., удовлетворяющие ограничениям в блоке решения и доставляющие наименьшее значение функции f;
maximize(f, var1, var2, ...) - возвращает значения переменных var1, var2, ..., удовлетворяющие ограничениям в блоке решения и доставляющие наибольшее значение функции f.
5.2.1 Контрольный пример №1
5.2.2 Контрольный пример №2
5.2.3 Контрольный пример №3
В ходе выполнения курсового работы были рассмотрены методы нахождения экстремума, а так же детально проанализирован метод Фибоначчи по минимизации целевой функции.
Результатом анализа и разбора метода стало описание алгоритмов и механизмов работы программного модуля, которые были отражены в блок-схеме.
В конечном итоге разработан программный модуль, полностью соответствующий требованиям, сформулированным в постановке задачи. Данный модуль был протестирован на ряде функций и показал высокие результаты скорости работы и точности расчетов.
Информация о работе Метод Фибоначчи минимизации функции одной переменной