Метод Фибоначчи минимизации функции одной переменной

Размещено на http://www.allbest.ru/

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«ДОНСКОЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»

ДГТУ

Кафедра «Программное обеспечение вычислительной техники и автоматизированных систем»

«ПОВТ и АС»

Курсовая работа по дисциплине «Методы вычислений»

на тему: «Метод Фибоначчи минимизации функции одной переменной»

Автор курсовой работы:

Кузнецов Евгений Николаевич

Ростов-на-Дону

2014 г.

Содержание

1. Теоретический обзор

1.1 Классические методы поиска экстремума функции одной переменной

1.2 Метод Фибоначчи минимизации функции одной переменной

2. Постановка задачи

3. Программное конструирование

4. Результаты работы программного средства

4.1 Описание тестовых примеров

4.2 Нахождение минимума и максимума

Контрольный пример №1

Контрольный пример №2

Заключение

Список использованных источников

Введение

программный фибоначчи функция отрезок

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

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

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

В данном методе используются числа Фибоначчи. Они названы по имени средневекового математика Леонардо Пизанского (известного как Фибоначчи). Это числа, которые определяются по следующему алгоритму: нулевое и первое число равно нулю, а каждое следующее равно сумме двух предыдущих. Последовательность Фибоначчи была хорошо известна в древней Индии, где она применялась в метрических науках, намного раньше, чем она стала известна в Европе. Именно на этой последовательности основан изложенный в данной работе метод.

1. Теоретический обзор

1.1 Классические методы поиска экстремума функции одной переменной

Рассмотрим целевую функция. Данная функция является функцией одной переменной, которая имеет на интервале минимизации всего одну точку минимума (впадину).

Функция, заданная на интервале называется унимодальной на [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 отлична от нуля.

Если n-нечетное, то x*-точка перегиба.

Если n-четное, то x*-точка локального оптимума. Кроме того,

если эта производная положительная, то x*-точка локального минимума

если эта производная отрицательная, то x*-точка локального максимума[1]

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

f1(x) = -f(x)

1.2 Метод Фибоначчи минимизации функции одной переменной

Метод Фибоначчи обеспечивает максимальное сокращение интервала неопределённости при заданном количестве вычислений функции

Алгоритм поиска по методу Фибоначчи определяется по тем же правилам симметрии, что и алгоритм по методу золотого сечения. На первой итерации выбирается две точки, расположенные симметрично относительно середины отрезка [a, b]. На каждой последующей итерации точка очередного вычисления выбирается симметрично оставшейся точке. При заданном количестве вычислений n и заданной погрешности вычислении е, точки деления интервала неопределённости (где j=1,2,.., n-1) вычисляются по формулам:

здесь Fk - число Фибоначчи, определяемое следующим образом:

Следует отметить, что на итерации j > 1 вычисляется только та из точек, которая не была определена на предыдущем шаге. За оценку точки минимума принимается та из точек, которая осталась внутри итогового интервала (рис. 1).

Ориентировочное значение числа Фибоначчи, обеспечивающее достижение требуемой точности, выбирается из условия:

Алгоритм метода Фибоначчи описать следующим образом:

Задаются начальные границы отрезка [a, b] и точность, n - количество вычислений целевой функции, j=1, рассчитываются начальные точки деления: 

где Fk - число Фибоначчи; и значения в них целевой функции:.

Если, то :

Иначе:

Увеличиваем j на 1.

Если j ? n, то возвращаемся к шагу 2. Иначе, вывод результата RES. Конец вычислений. [2]

2. Постановка задачи

Цель курсовой работы: «разработать программный модуль для нахождения минимума целевой функции по методу Фибоначчи».

Для ознакомления с общими сведениями о минимизации функции и, конкретно, с методом Фибоначчи составить теоретический обзор.

Привести алгоритм метода, а также составить блок-схему метода.

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

Исследуемые на экстремум функции изобразить графически.

3. Программное конструирование

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

Входные параметры:

f - целевая функция;

a - левая граница минимизации;

b - правая граница минимизации;

n - количество вычислений целевой функции;

e - точность вычисления минимума.

Выходные параметры:

RES - точка минимума.

4. Результаты работы программного средства

4.1 Описание тестовых примеров

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

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

4.2 Нахождение минимума и максимума

Для проверки эффективности работы и точности вычисления программного модуля по методу Фибоначчи, было взято 3 функции различной сложности. Результаты вычислений были проверены функциями MathCad:

minimize(f, var1, var2,...) - возвращает значения переменных var1, var2,..., удовлетворяющие ограничениям в блоке решения и доставляющие наименьшее значение функции f;

maximize(f, var1, var2,...) - возвращает значения переменных var1, var2,..., удовлетворяющие ограничениям в блоке решения и доставляющие наибольшее значение функции f.

Контрольный пример №1

Контрольный пример №2

Заключение

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

Результатом анализа и разбора метода стало описание алгоритмов и механизмов работы программного модуля, которые были отражены в блок-схеме.

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

Список использованных источников

1. Пантелеев А.В. Методы оптимизации. Практический курс. - М.: Логос, 2011.

2. Соболь Б.В. Методы Оптимизации. Изд. 5_е. Ростов н/Д : Феникс, 2008.

3. Минимизация функции методом Фибоначчи [ЭЛЕКТРОННЫЙ РЕСУРС] - URL: http://dic.academic.ru/dic.nsf/ruwiki/1034656

Размещено на Allbest.ru