Исследование мультимодальной функции в математике
Исследование поискового метода минимизации мультимодальной функции одной переменной на основе двухзвенной схемы отбора интервалов первого порядка. Поисковый метод ее минимизации. Сравнительное исследование эффективности методов, их плюсы и минусы.
| Рубрика | Математика |
| Вид | контрольная работа |
| Язык | русский |
| Дата добавления | 27.07.2014 |
| Размер файла | 603,5 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Введение
мультимодальный двухзвенный математика
Экстремальные задачи нередко возникают в различных отраслях современной науки, таких, как информатика, кибернетика, экономика, космонавтика, физика, вычислительная математика, технические науки и многие другие. В большинстве случаев экстремальные задачи не поддаются аналитическому исследованию и для их решения используются численные методы, ориентированные на применение компьютера. Численные методы минимизации функций многих переменных обычно сводят решение многомерной экстремальной задачи к итерационному процессу на каждом шаге которого решается задача одномерной минимизации (задача определения минимума функции одной переменной). Существующие методы одномерной минимизации, в свою очередь, принято подразделять на методы локальной и глобальной минимизации. Первые применяются в основном для определения минимума унимодальных функций [20]. Применение методов локальной минимизации к функциям, имеющим несколько локальных минимумов, приводит обычно к определению одного из локальных минимумов, не обязательно совпадающего с минимумом глобальным. К наиболее распространённым методам локальной минимизации относятся такие методы, как метод половинного деления, метод золотого сечения, метод парабол. Методы глобальной минимизации работают намного медленнее, зачастую требуют хранения больших наборов данных, но зато позволяют во многих случаях найти глобальный минимум функции, которая не является унимодальной. К наиболее известным методам глобальной минимизации относятся метод равномерного перебора и метод ломаных [2].
Работы, посвященные новым методам минимизации функций одной переменной, продолжают появляться на страницах математических книги журналов [2], [4], [16]. К настоящему времени не существует общепринятого универсального численного метода, который позволял бы получать оптимальное решение для любой задачи нелинейной оптимизации. При решении каждой задачи минимизации, может требоваться применение нескольких методов, поэтому эффективное решение задачи минимизации зависит от набора алгоритмов минимизации, которыми владеет исследователь.
Вряд ли можно создать численный метод, способный определять сколь угодно узкие локальные минимумы. Важно лишь, чтобы были параметры, способные увеличивать чувствительность метода к узким локальным минимумам. К сожалению, повышение чувствительности всегда достигается за счёт сгущения сетки точек и существенного увеличения объёмов вычислительной работы [20], поэтому задача минимизации функций, а также составление новых методов минимизации мультимодальной функции одной переменной в наше время является актуальной.
Целью данной работы является исследование и программная реализация нового поискового метода минимизации мультимодальной функции одной переменной на основе двухзвенной схемы отбора интервалов первого порядка [20].
Для достижения цели решались задачи:
1. Создание обзора методов минимизации функций и функционалов.
2. Реализация метода последовательного перебора средствами Borland Delphi.
3. Реализация поискового метода минимизации мультимодальной функции одной переменной на основе двухзвенной схемы интервалов первого порядка средствами Borland Delphi.
4. Постановка, проведение и анализ результатов сравнительного экспериментального исследования метода последовательного перебора, метода ломаных, монотонного алгоритма Стронгина, поискового метода минимизации мультимодальной функции одной переменной на основе двухзвенной схемы отбора интервалов первого порядка, поискового метода минимизации мультимодальной функции одной переменной на основе трехзвенной схемы отбора интервалов первого порядка и поискового метода минимизации мультимодальной функции одной переменной на основе трехзвенной схемы отбора интервалов второго порядка.
1. Исследование поискового метода минимизации мультимодальной функции одной переменной на основе двухзвенной схемы отбора интервалов первого порядка
Метод последовательного перебора
Обозначим через класс функций, удовлетворяющих условию Липшица на отрезке , с одной и той же для всех функций этого класса константой . Для функции будем рассматривать задачу минимизации первого типа, когда ищется величина .
На классе можно предложить простой и эффективный последовательный метод перебора, когда выбор точки при каждом производится с учетом вычислений значения функции в предыдущих точках и задачу: как выбрать число и метод , чтобы
(1)
удается решить за меньшее количество вычислений значений функции. Положим
(2)
где , , , а число определяется условием .
Теорема 1.
Метод последовательного перебора (2) решает задачу (1) на классе .
Описание метода
Пусть функция удовлетворяет условию Липшица на с известной константой . Тогда, согласно следствия из теоремы 4.5, будет существовать минимум и хотя бы одна из точек минимума функции на . Будем искать приближения для минимума и какой-нибудь точки минимума функции на () с погрешностями, не превышающими заданного положительного числа .
Для решения поставленной задачи разобьем на отрезков , , ; . Вычислим значения функции () в очках разбиения и найдем . Далее сравним полученное значение с величиной , чтобы не выйти за границы отрезка, на котором ищется минимум функции. Если выполняется условие , то переходим к следующему шагу поиска минимума функции. Как только это условие перестанет выполняться, возьмем в качестве последней проверяемой точки . После этого выберем в качестве приближений для точного значения точки минимума и точного значения минимума функции значения и , где значение выбирается соответствующим номеру шага, на котором найдено приближенное минимальное значение точки минимума [2].
Заметим, что метод (1) выгодно отличается простотой реализации и не требует большой машинной памяти. Недостатком метода (1), как и метода ломаных, является необходимость априорного знания константы из условия Липшица.
Метод последовательного перебора, аналогичный методу (2), можно предложить и для некоторых других классов функций. Остановимся на классе функций, дважды. дифференцируемых на отрезке, у которых , где - некоторая фиксированная константа. Обозначим этот класс функций через . Заметим, что если , то , и следовательно, монотонно убывает на . Это значит, что тогда функция достигает своей нижней грани при или . Таким образом, задача минимизации функций из класса в случае решается просто. Поэтому имеет смысл рассматривать класс при .
Тогда для решения задачи минимизации первого типа на классе функций можно предложить следующий метод последовательного перебора
(2)
где, , , а число определяется условием [2].
Теорема2.2.
Применяя метод (2.2), задачу минимизации первого типа для любой функции можно решить с заданной точностью , т.е.
. (2.4)
В худшем случае (например, если ) может оказаться, что , , и тогда метод (2.3) переходит в метод равномерного перебора с шагом . Если же при некоторых (например, для ), то методом (3) удается получить неравенство (4), вообще говоря, при меньшем , чем методом равномерного перебора. Недостатком метода (3) является требование знания константы .
Поисковый метод минимизации мультимодальной функции одной переменной на основе двухзвенной схемы отбора интервалов первого порядка
Вряд ли можно создать численный метод, способный определять сколь угодно узкие локальные минимумы. Важно лишь, чтобы были параметры, способные увеличивать чувствительность метода к узким локальным минимумам. К сожалению, повышение чувствительности всегда достигается за счёт сгущения сетки точек и существенного увеличения объёмов вычислительной работы.
В данном параграфе рассматривается новый численный метод глобальной одномерной минимизации [20]. Он не требуют априорного знания константы Липшица или её приближённого вычисления. В нем предусмотрены параметры, позволяющие увеличивать их чувствительность к узким локальным минимумам, которая ограничивается только быстродействием компьютера.
Рассматривается следующая экстремальная задача. Функция определена и непрерывна на заданном . Предполагается, что на располагается конечное число отрезков , на которых функция является унимодальной и имеет локальный минимум . Глобальный минимум функции на совпадает с одним из локальных минимумов . Локальный минимум может достигаться не в одной точке . Только в случае строгой унимодальности функции на точка локального минимума () будет единственной на этом отрезке. Локальный и глобальный минимум могут достигаться и на концах . Точек глобального минимума () также может быть множество, но в любом случае одна из них будет совпадать с одной из точек локального минимума .
Ищется значение , а также приближенные значения локальных минимумов и глобального минимума с погрешностями, не превышающими заданного положительного числа . Ищутся также приближенные значения точек локального минимума и точки глобального минимума с погрешностями, не превышающими заданного положительного числа . Если на имеется множество точек локального минимума, то нам годится любая из них. То же относится и к точке глобального минимума [20].
При решении сформулированной экстремальной задачи отрезок разбивается на равные части. Далее используются простые и легко проверяемые условия, позволяющие выделить отрезки разбиения, на которых функция , предположительно, является унимодальной. Эти условия являются необходимыми (но, вообще говоря, не достаточными) для унимодальности непрерывной функции на выделяемых отрезках. Далее на каждом из выделенных отрезков применяется метод локальной минимизации, с помощью которого определяются приближения для локального минимума и точки локального минимума, вычисляется приближения для глобального минимума и точки глобального минимума.
После этого разбиение измельчается в несколько раз и описанная выше процедура повторяется. Если значения приближений глобального минимума, полученные на двух последних разбиениях, совпадают с заданной точностью, то процесс измельчения завершается и последние результаты принимаются за окончательные. В противном случае описанный процесс измельчения и вычислений минимумов продолжается.
Начальное количество отрезков разбиения связывается с границей погрешности точек минимума, что позволяет использовать эту границу для регулирования чувствительности метода к тонким минимумам.
Описанный подход позволяет построить множество численных методов глобальной минимизации, которые отличаются схемами выделения отрезков предположительной унимодальности минимизируемой функции и используемыми методами локальной минимизации. Рассмотрим подробно один из таких методов.
Теперь рассмотрим сам поисковый метод минимизации мультимодальной функции одной переменной на основе двухзвенной схемы отбора интервалов первого порядка
Для минимизации функции на отрезках предположительной унимодальности будем использовать метод золотого сечения. Он обеспечивает вычисление с заданной точностью локального минимума и точки локального минимума на отрезке унимодальности функции.
Для решения сформулированной выше экстремальной задачи строится последовательность сгущающихся равномерных сеток на . Число отрезков разбиения очередной сетки . При каждом сгущении сетки
, . (5)
Таким образом, при каждом сгущении сетки число увеличивается в 3 раза. Узлы очередной сетки вычисляются по обычным формулам:
, , (6)
где - шаг разбиения. В этих узлах вычисляются значения функции . Эти значения используются для выбора отрезков, на которых функция , предположительно, является унимодальной. Проверяются подряд отрезки , , , ,…, , , (рис. 1).
Будем считать, что на функция предположительно является унимодальной, если
. (6)
Считается, что на отрезках функция предположительно является унимодальной, если
( и ) или ( и ) или
( и ). (7)
Будем считать, что на функция предположительно является унимодальной, если
. (8)
Условия (6) и (8) получаются из необходимых для унимодальности функции на отрезках и условий:
,
.
Условия (7) получаются из необходимых для унимодальности функции на отрезке условий:
,
.
Здесь использованы полиномиальные формулы численного дифференцирования 1 порядка точности. В условиях (8) требуется, чтобы хотя бы одно из неравенств было строгим. Это необходимо, чтобы исключить отрезки на которых функция является постоянной. При формулировке условий (8) фигурируют два отрезка. Поэтому условия предположительной унимодальности функции (6) - (8) будем называть двухзвенными условиями первого порядка.
При нахождении очередного (-го) отрезка, на котором выполняются условия (6) или (7) или (8), на нём применяется модифицированный метод золотого сечения, с помощью которого определяются приближенное значение точки локального минимума функции и приближенное значение локального минимума этой функции с погрешностями, не превышающими и, соответственно. Условия (6) - (8) позволяют выявить все окрестности внутренних точек локального минимума функции на отрезке , ширина которых не меньше , а также окрестности граничных точек локального минимума функции , ширина которых не меньше . С ростом значения и уменьшением , условия (6) - (8) будут выявлять окрестности всё более и более узких локальных минимумов и при достаточно большом значении (маленьком значении ) будут выявлены окрестности всех точек локального минимума функции , на которых функция является унимодальной. А далее методом золотого сечения получатся приближенные значения точек локального минимума и локальных минимумов с погрешностями и , соответственно. Параллельно вычисляются количество обнаруженных локальных минимумов , приближенные значения глобального минимума и точка глобального минимума ().
Точка совпадает с одной из приближенных точек локального минимума , а совпадает с одним из приближенных локальных минимумов . Поэтому, если , то погрешности и также не будут превышать и , соответственно. В заключение заметим, что хранить значения и нет смысла [20].
Для завершения описания метода решения экстремальной задачи осталось сформулировать условия окончания итераций и условия выбора начального значения величины . Процесс сгущения сеток будем заканчивать, когда значение глобального минимума перестаёт уменьшаться при сгущении сетки (с учётом заданной точности его определения методом золотого сечения ).
Чтобы сформулировать условия выбора начального значения заметим, что если
, (9)
то заданное условие в методе золотого сечения будет выполнено. Если при этом второе условие выполняется, то это значит, что функция имеет узкие минимумы, ширина которых меньше . В этом случае нужно уменьшить . Решая неравенство (2.9) относительно получим следующее условие
, (10)
при выполнении которого следует выдать сообщение о необходимости уменьшения значения . Здесь - целая часть вещественного числа. Начальное значение будем выбирать меньшим, чем и таким, чтобы после третьего сгущения сетки значение ещё не достигало , а после четвёртого сгущения значение становилось больше :
. (11)
При таком выборе начального значения величина границы погрешности становится параметром, влияющим на чувствительность метода к узким локальным минимумам. Для повышения чувствительности метода следует уменьшать [20].
2. Реализация поискового метода минимизации мультимодальной функции одной переменной на основе двухзвенной схемы отбора интервалов первого порядка и метода последовательного перебора
Описанные методы были реализованы в системе Delphi 7. Текст программы приведен в приложении.
Delphi - это интегрированная среда разработки, в которой используется язык программирования Object Pascal. Delphi является средой RAD (rapid application development - быстрая разработка приложений). Начиная со среды разработки Delphi 7.0, в официальных документах Borland стала использовать название Delphi для обозначения языка Object Pascal. Начиная с 2007 года уже язык Delphi (производный от Object Pascal) начал жить своей самостоятельной жизнью и претерпевал различные изменения связанные с современными тенденциями (например, с развитием платформы.net) развития языков программирования: появились class helpers, перегрузки операторов и д.р.
Программа тестировалась на модельных задачах. Для хранения значений параметров приближенного решения использовались одномерные массивы. Исходными данными для программы являются концы отрезка, на котором ищется минимум функции и , значения погрешности точки минимума и погрешности значения функции в точке минимума, а также значения и для четвертой модельной задачи. Результатами работы программы являются приближенное значение точки , в которой находится минимум функции, а также приближенное значение минимума функции в точке .
Руководство пользователя
Открываем файл Project2 в среде разработки Borland Delphi 7.0. В коде программы пишется новая функция, аналогичная функции TForm1.f4 (x:real):real. Затем находится функция TForm1. VyborFunction (z1:real):real, в которой осуществляется условие перевода данных в введенную функцию. Ввод функции производится с клавиатуры, поддерживаются цифры 0-9, арифметические операции, ^ - (степень числа), тригонометрические функции (sin, cos, tan, asin, acos, atan, sh, ch, th, cth), также функции (abs, exp, lg, ln, sqrt).После этого программа по нажатию F9 запускается на выполнение. При запуске программы появляется окно, в котором необходимо ввести начальные данные.
При запуске программы появляется окно, в котором необходимо ввести начальные данные. На рис. 2 изображено окно программы.
Главное окно программы
При нажатии на кнопку «Выберите уравнение» программа открывает окно (см. рис. 3) с набором функций, которые может выбрать пользователь.
Окно выбора модельной задачи
После выбора функции пользователь определяет, с каким методом он будет работать, выбрав между поисковым методом и методом последовательного перебора (см. рис. 4 (a)).
Окно программы для выбора метода минимизации
После выбора функции при нажатии на кнопку «Задать параметры» программа открывает окно (см. рис. 2.4. (b)), в котором пользователь может задать начало и конец отрезка минимизации функции, а также погрешность вычисления точки глобального минимума и погрешность вычисления функции в точке глобального минимума .
Окно для задания параметров функции
При нажатии на кнопку «Посчитать значения» программа ищет точку глобального минимума функции и ее значение в этой точке с заданными погрешностями и выводит полученные результаты в новом окне (см. рис. 2.5).
Окно результатов работы программы
При нажатии на кнопку «График» программа открывает новое окно, в котором пользователь может выбрать погрешность с которой программа построит график выбранной ранее функции и выведет его в области слева при нажатии на кнопку «Построить».
Окно программы, отображающей график выбранной модельной задачи
При нажатии на кнопку «Очистить параметры», появляющуюся после заполнения параметров функции, все ранее заданные параметры удаляются (кроме значения, определяющего функцию, выбранную пользователем). При нажатии на кнопку «Крестик» программа производит полную очистку всех выбранных ранее параметров и заданных значений.
Руководство программиста
Трансляцию функции, выбираемой пользователем, выполняет функция TForm1. VyborFunction(). Основные вычисления производятся в процедуре TForm1. Button4Click (Sender: TObject), где Sender - передаваемые в процедуру TForm1. Button4Click параметры функции. Результат работы выводится на форму с полем Form4. Memo1.
Ввод данных (промежуток поиска минимума , точность), производится процедурой ParametersForMemo(), которая передает данные в процедуру TForm1. Button4Click(), а значения в процедуру processgrid2 (ap, bp:real). EpsX - погрешность точки минимума, EpsY - погрешность функции в точке минимума. Ввод константы Липшица производится с помощью процедуры TForm3. Button1Click().kkl - константа Липшица.
Поиск минимума: выбор функции, с которой будет работать пользователь осуществляется функцией TForm1. VyborFunction (z1:real). Она возвращает номер выбранной функции. Выбор метода, с которым придется работать в дальнейшем осуществляется с помощью переключателей sRadioButton1, sRadioButton2. Начальный шаг разбиения определяется как Shag (Fa, Fb, EpsX), куда передаются значения начала и конца отрезка, а также значение погрешности точки минимума. Процедура processgrid2 () выполняет проверку отрезка на унимодальность и дальнейшее его разбиение на малые отрезки для поиска минимума методом золотого сечения в процедуре localMinimum(). Параметры xa, ag, xb, bg, xd, dg, xe, eg являются результатом работы процедуры processgrid2 () и исходными данными для процедуры localMinimum(). Результат работы (найденные локальные минимумы) процедуры localMinimum() записывается в поле Form4. Memo1. Программа завершает работу после того, как перестанут выполняться условия: (Abs (ygpr-ygsl)>2*EpsY) and (Mmax-M>0.5) - для поискового метода, u [i-1]<(b - (h/2)) - для метода последовательного перебора.
Рисование графика функции производит процедура TForm5. Button1Click(). Результат работы программа выводит на форму.
Используемые в программе глобальные переменные:
1. yb - одномерный массив вещественных чисел, используемый для выбора пользователем погрешности значения точки глобального минимума функции;
2. yy (вещественное число) - погрешность значения функции в точке глобального минимума;
3. numf (целое число) - номер функции, выбранной пользователем;
4. k1, k2, k3, k4, k5, k6 (целые числа) - счетчики в циклах;
5. tmstart (вещественное число) - переменная, хранящая время начала работы программы для поиска точки минимума и минимума функции;
6. tmfinish (вещественное число) - переменная, хранящая время окончания работы программы для поиска точки минимума и минимума функции;
7. tmout (вещественное число) - переменная, хранящая время работы программы для поиска точки минимума и минимума функции;
8. timeRR - двумерный массив, хранящий сведения о времени работы программы в таблице;
9. XL, YL - одномерные массивы вещественных чисел, хранящие промежуточные значения точки локального минимума и значения функции в этой точке;
10. alpha (вещественное число) - переменная хранящая значение константы, используемой в методе золотого сечения;
11. u0, u1, u2, u3, u5 (вещественные числа) - переменные, хранящие значения точек при поиске точки минимума методом золотого сечения;
12. KP (целое число) - переменная, хранящая общее число локальных минимумов, найденных программой;
13. st (целое число) - переменная, необходимая для возведения в степень для выбранной функции;
14. izm (переменная типа boolean) - переменная, показывающая, когда на форме были произведены изменения;
15. xgpr, ygpr, xgsl, ygsl (вещественные переменные) - переменные, хранящие промежуточные значения при поиске точки глобального минимума и значения функции в этой точке;
16. XG (вещественное число) - точка глобального минимума;
17. YG (вещественное число) - глобальный минимум функции;
18. rnr, r1r, r2r, res (вещественные числа) - переменные, необходимые для задания функций;
19. hp (вещественное число) - длина отрезка, на котором исследуется функция;
20. ffpr, ffsl, x0p, x1p, x2p, x1pp, x2pp, x3p, f0p, f1p, f2p, f1pp, f2pp, f3p (вещественные числа) - переменные для ранения промежуточных значений при поиске точки глобального минимума и точки глобального минимума методом золотого сечения;
21. Fa (вещественное число) - начало отрезка, на котором исследуется функция;
22. Fb (вещественное число) - конец отрезка, на котором исследуется функция;
23. w, g (вещественные числа) - числа в показателях степеней для четверной функции;
24. ad, bd, cd (вещественные числа) - промежуточные значения, для определения точек в методе золотого сечения;
25. hg (вещественное число) - шаг сетки;
26. n (вещественное число) - число отрезков разбиения на сетке;
27. fgm (вещественное число) - промежуточный глобальный минимум;
28. xgm (вещественное число) - промежуточное значение точки глобального минимума;
29. EpsX (вещественное число) - погрешность точки минимума;
30. EpsY (вещественное число) - погрешность функции;
31. xx (вещественное число) - переменная, необходимая для возведения в степень;
32. m (вещественное число) - параметр, через который вычисляется число отрезков разбиения на сетке;
33. Dt, Tm, mas (строковые переменные) - переменные, необходимые для вывода таймера.
Используемые в программе процедуры и функции:
1. procedure TForm1. Button1Click (Sender: TObject)
Процедура выбора уравнения с которым в дальнейшем будет работать программа.
2. procedure TForm1. BitBtn1Click (Sender: TObject)
Процедура очистки выбранных ранее параметров. Процедура TForm1. BitBtn1Click начинает работать после нажатия на кнопку «Очистить параметры».
3. procedure TForm1. FormCreate (Sender: TObject)
Процедура слежения за текущим временем и датой, которые отображаются внизу окна программы.
4. procedure ParametersForMemo()
Процедура для задания параметров при нажатии на кнопку «Задать параметры».
5. procedure TForm1. Timer1Timer (Sender: TObject)
Процедура таймера. Форма обновляется с интервалом в 1 мс.
6. function TimeMmSs (timeMS:real):string
Функция возвращает строку времени в минутах, секундах и миллисекундах.
7. function stepen (x:real; step:integer):real
Функция stepen позволяет возводить в степень число step раз.
8. function TForm1. Shag (a, b, y:real):real
Функция считает число отрезков разбиения на сетке.
9. function TForm1.f1 (x:real):real
Функция для описания первого модельного примера.
10. function TForm1.f2 (x:real):real
Функция для описания второго модельного примера.
11. function TForm1.f3 (x:real):real
Функция для описания третьего модельного примера.
12. function TForm1.f4 (x:real):real
Функция для описания четверного модельного примера.
13. procedure TForm1. Button3Click (Sender: TObject)
Процедура очищает поля с ранее заданными параметрами при нажатии на кнопку «Очистить параметры».
14. function TForm1. VyborFunction (z1:real):real
Функция непосредственного выбора функции с которой будет работать пользователь и дальнейшее подстановка заданных параметров в выбранную функцию.
15. function Unimodal (zn1, zn2:real; zn3:real=0):boolean
Функция проверки выбранного отрезка на унимодальность. Начальные данные определяются процедурой processgrid2. Результат представляет собой логическую переменную.
16. procedure localMinimum (xa, ag, xb, bg, xd, dg, xe, eg:real)
Процедура поиска локального минимума. Начальные данные определяются процедурой processgrid2. Результаты заносятся в два одномерных массива, хранящие полученные значения точки локального минимума и сам минимум.
17. procedure processgrid2 (ap, bp:real)
Процедура проверки отрезка на унимодальность и дальнейшее разбиение этого отрезка по методу золотого сечения. Начальные данные хранятся в переменных ap, bp - начало и конец отрезка. Результат передается в процедуру localMinimum.
18. procedure TForm1. Button4Click (Sender: TObject)
Основная процедура программы. Содержит в себе модифицированный метод золотого сечения, позволяющий найти локальный минимум на выбранном отрезке сетки с заданной погрешностью. Результаты записываются в таблицу, открывающуюся по нажатию на кнопку «Посчитать значения».
Тестирование программы, реализующей метод последовательного перебора
Для проведения тестирования выберем задачу минимизации функции на отрезке , для которой можно легко найти единственный глобальный и локальный минимум. Он достигается в точке и равен .
Результат работы программы зафиксируем в таблице. Для этого введем следующие обозначения:
- точное значение точки глобального минимума функции;
- приближенное значение точки глобального минимума функции, полученное с помощью программы;
- точное значение глобального минимума функции в точке ;
- приближенное значение глобального минимума функции в точке , полученное с помощью программы.
Введем следующие величины, для более точного сравнения полученных результатов: , . Зафиксируем погрешность вычисления значения функции .
|
- |
- |
Смысл тестирования заключается в том, что заданная точность должна достигаться, т.е. при любых допустимых значениях должно выполняться . Если слишком мало, то погрешности вычисления значения функций будет больше чем и такая точность принципиально не достижима.
Из таблицы результатов работы программы, реализующей метод последовательного перебора, можно сделать вывод, что заданная точность была достигнута для всех заданных значений .
Тестирование программы, реализующей поисковый метод на основе двухзвенной схемы отбора интервалов первого порядка
Для проведения тестирования выберем задачу минимизации функции на отрезке , для которой можно легко найти единственный глобальный и локальный минимум. Он достигается в точке и равен .
Результат работы программы, реализующей поисковый метод на основе двухзвенной схемы отбора интервалов первого порядка зафиксируем в таблице. Для этого введем следующие обозначения:
- точное значение точки глобального минимума функции;
- приближенное значение точки глобального минимума функции, полученное с помощью программы;
- точное значение глобального минимума функции в точке ;
- приближенное значение глобального минимума функции в точке , полученное с помощью программы.
Введем следующие величины, для более точного сравнения полученных результатов: , . Зафиксируем погрешность вычисления значения функции .
|
- |
- |
Из таблицы результатов работы программы, реализующей поисковый метод на основе двухзвенной схемы отбора интервалов первого порядка, можно сделать вывод, что заданная точность была достигнута для всех заданных значений .
3. Сравнительное исследование эффективности методов
В этом параграфе проводится сравнительное исследование поисковых методов минимизации мультимодальной функции одной переменной на основе схем отбора интервалов, метода последовательного перебора, монотонного алгоритма глобального поиска Стронгина и метода ломаных. В качестве параметра эффективности метода выберем количество вычисления значений функций для достижения заданной точности.
Подобный метод определения эффективности численных методов используется многими другими авторами, например Стронгиным [17]. В таблицах 4-9 представлены результаты вычисления этого параметра эффективности для перечисленных методов. Результаты для метода ломаных и поискового метода на основе трехзвенной схемы отбора интервалов первого порядка были взяты из работы [9]. Результаты для монотонного алгоритма глобального поиска Стронгина и поискового метода на основе трёхзвенной схемы отбора интервалов второго порядка были взяты из работы [14]. Под точностью будем понимать абсолютную погрешность значения точки глобального минимума , где - точное значение точки глобального минимума, - приближенное значение точки глобального минимума, вычисленное с помощью программы. Для достижения нужной точности используется параметр, который есть в каждом методе и при устремлении его к нулю, заданная точность должна быть достигнута. Для всех поисковых методов, метода последовательного перебора, метода ломаных и монотонного алгоритма глобального поиска Стронгина таким параметром является - оценка погрешности приближенного значения точки глобального минимума. Этот параметр используется и вводится непосредственно в программе. Т.о. при его последовательном уменьшении абсолютная погрешность точки глобального минимума также будет уменьшаться.
В первой колонке задается значение , такое что и приблизительно равное . Фиксируем значение и уменьшаем значение параметра соответствующего метода до тех пор, пока значение погрешности не станет меньше или равным и в то же время близким к . Для последнего случая фиксируем количество вычислений значения функции и помещаем его в таблицу.
Для некоторых задач точное значение глобального минимума аналитически найти невозможно. В этих случаях это значение находится с помощью численного метода. Для получения значения параметра воспользуемся поисковым методом на основе двухзвенной схемы отбора интервалов первого порядка. С его помощью найдем значение точки глобального минимума с высокой точностью, т.е. при . Полученное значение используем как точное значение точки глобального минимума исследуемой функции при вычислении погрешности.
Характерной особенностью всех методов, кроме поисковых, является использование в качестве исходного данного константы Липшица для функции на .В простейших случаях константа Липшица вычисляется аналитически. Аналитический метод вычисления константы Липшица заключается в том, что находится производная функции и вычисляется ее максимум на том отрезке, для которого ищется минимум функции. Таким образом, на отрезке вычисляется производная исследуемой функции равное . Константа Липшица выбирается равной .Часто константу Липшица аналитически вычислить очень сложно, например, если исследуемая функция не является элементарной или если метод одномерной минимизации используется в качестве вспомогательного метода в решении задач много мерной минимизации. Поэтому методы, использующие ее для своих вычислений, сопровождаются дополнительной программой вычисления константы Липшица.
Вычисление константы Липшица обычно производится сеточным методом. На отрезке строится сетка из точек, таким образом получена последовательность точек , где , , . Затем производится вычисление значений - значения функции в точках , .
Обычно заранее невозможно определить значение при котором будет достаточно близка к значению . Поэтому для получения приближенного значения с заданной точностью используется итерационный процесс.
Зададим последовательность для каждой пары вычисляются значения и .Вычисляем , где - значения функции в соседних узлах сетки. Затем вычисляем значение , где и сравниваем по модулю разность значений и . Если меньше заданного некоторого , то константа Липшица считается найденной и равной с погрешностью , иначе удваиваем значение и вычисляем новые значения и . Погрешность значения зависит от значения и припогрешность .
Данный метод можно оптимизировать, если вместо использовать . Данная оптимизация ускоряет вычисление константы Липшица в и более раз, но при этом необходимо отдельно рассмотреть случай, при котором Это происходит в том случае, если функция является постоянной (константой), в этом случае значение константы Липшица берется равным .
В случае программного поиска константы Липшица общее количество вычислений функции является суммой значений количества вычислений функции, необходимого для получения константы Липшица и количества вычислений функции, необходимого для нахождения приближенного значения точки глобального минимума одним из методов, использующих константу Липшица.
Если константа Липшица вычисляется аналитически, трудоемкость методов будет существенно разной, поэтому все выводы делаются в каждом случае отдельно.
В таблицах 4-9 используются следующие обозначения:
- заданная точность искомого приближенного значения точки глобального минимума;
sL - Число вычислений функции для определения константы Липшица, найденное при определении константы Липшица сеточным методом;
sML1 - Число вычислений функции для метода ломаных с вычисленной константой Липшица;
sML2 - Число вычислений функции для метода ломаных с найденной константой Липшица используя максимум производной функции;
sSL1 - Число вычислений функции для АГП (алгоритм глобального поиска) Стронгина с вычисленной константой Липшица;
sSL2 - Число вычислений функции для АГП Стронгина с найденной константой Липшица используя максимум производной функции;
sPL1 - Число вычислений функции для метода последовательного перебора с вычисленной константой Липшица;
sPL2 - Число вычислений функции для метода последовательного перебора с найденной константой Липшица используя максимум производной функции;
s3z1 - Число вычислений функции для метода на основе трёхзвенной схемы отбора интервалов первого порядка;
s3z2 - Число вычислений функции для метода на основе трёхзвенной схемы отбора интервалов второго порядка;
s2z1 - Число вычислений функции для метода на основе двухзвенной схемы отбора интервалов первого порядка.
Модельная задача 1. Ищется минимум функции на отрезке (рис. 4). Вычисленное значение константы Липшица = 35452. Точное значение точки минимума функции = 1,54978592608382.
График функции
Функция характеризуется большим количеством узких локальных минимумов. Данная модельная задача проверяет эффективность работы исследуемых методов в случаях, когда функция имеет множество локальных минимумов одинаковой ширины, один из которых является глобальным.
|
sL |
sML1 |
sML2 |
sSL1 |
sSL2 |
||
|
10-2 |
1048574 |
64 |
64 |
190 |
190 |
|
|
10-3 |
1048574 |
512 |
512 |
6767 |
8765 |
|
|
10-4 |
1048574 |
8192 |
8192 |
39111 |
59181 |
|
|
10-5 |
1048574 |
19146 |
34451 |
611564 |
1110472 |
|
|
10-6 |
1048574 |
30797 |
63900 |
640772 |
1329008 |
|
sPL1 |
sPL2 |
s3z1 |
s3z2 |
s2z1 |
||
|
10-2 |
2120 |
2120 |
282 |
83 |
964 |
|
|
10-3 |
6060 |
6060 |
2053 |
2707 |
9096 |
|
|
10-4 |
78257 |
78257 |
13684 |
6629 |
13264 |
|
|
10-5 |
733560 |
733560 |
29796 |
160938 |
146712 |
|
|
10-6 |
961392 |
1613920 |
53814 |
237323 |
358651 |
Заключение
К основным результатам выпускной квалификационной работы можно отнести:
1. Обзор литературы, связанной с методами минимизации функций и функционалов.
2. Программная реализация поискового метода минимизации мультимодальной функции одной переменной на основе двухзвенной схемы отбора интервалов первого порядка.
3. Программная реализация метода последовательного перебора.
4. Постановка, проведение и анализ результатов сравнительного экспериментального исследования метода последовательного перебора, метода ломаных, монотонного алгоритма Стронгина, поискового метода минимизации мультимодальной функции одной переменной на основе двухзвенной схемы отбора интервалов первого порядка, поискового метода минимизации мультимодальной функции одной переменной на основе трехзвенной схемы отбора интервалов первого порядка и поискового метода минимизации мультимодальной функции одной переменной на основе трехзвенной схемы отбора интервалов второго порядка.
Список литературы
1. Васильев Ф.П. Численные методы решения экстремальных задач. / Ф.П. Васильев - М.: изд. Наука, 1988, 552 с.
2. Васильев Ф.П. Численные методы решения экстремальных задач./ Ф.П. Васильев - М.: изд. Наука 1980,510 с.
3. Введение в математическое моделирование: учеб. пособие / под ред. П.В. Трусова. - М.: Университетская книга, Логос, 2007, 440 с.
4. Зубанов А.М. О построении линейно неявных схем, -эквивалентных неявным схемам Рунге-Кутты. / А.М. Зубанов, Н.Н. Кутрухин, П.Д. Ширков // Компьютерные исследования и моделирование, Т.4. Математические основы и численные методы моделирования. - 2012. №3. - С. 483-496.
5. Зуев Е.А. Язык программирования TurboPascal 6.0, 7.0. / Е.А. Зуев - М: изд. Веста, Радио и связь, 1993, 384 с.
6. Ильин В.А. Основы математического анализа. Часть I. / В.А. Ильин, Э.Г. Позняк - М.: Физматлит, 7-е изд., 2005, 648 с.
7. Ильин В.А., Позняк Э.Г. Основы математического анализа. Часть II. / В.А. Ильин, Э.Г. Позняк - М.: Физматлит, 4-е изд., 2002, 464 с.
8. Калиткин Н.Н. Численные методы. / Н.Н. Калиткин - М.: изд. Наука, 1978, 512 с.
9. Карташов В.Г. Поисковый метод минимизации мультимодальной функции одной переменной на основе трехзвенной схемы отбора интервалов первого порядка: выпускная квалификационная работа /В.Г. Карташов (рукопись)
10. Кудрявцев Л.Д. Курс математического анализа. (В 3-х томах). // М.: Дрофа, т. 1 - 2003, 704 с., т. 2 - 2004, 720 с., т. 3 - 2006, 351 с.
11. Онлайн учебник по Delphi 7 [Электронный ресурс]. - http://delphi.support.uz/
12. Пантелеев А.В. Методы оптимизации в примерах и задачах: уч. пособие / А.В. Пантелеев, Т.А. Летова - 2-е изд. - М: изд. Высшая школа, 2005,544 с.
13. Полак Э. Численные методы оптимизации. Единый подход. / Э. Полак - М.: изд. Мир, 1974, 376 с.
14. Полоник Н.А. Поисковый метод минимизации мультимодальной функции одной переменной на основе трехзвенной схемы отбора интервалов первого порядка: выпускная квалификационная работа /Н.А. Полоник (рукопись)
15. Рейзлин В.И. Численные методы оптимизации: учебное пособие. / В.И. Рейзлин. Томский политехнический университет - Томск: изд-во Томского политехнического университета, 2011, 105 с.
16. Сорокин П.Н. Сравнение двух семейств метода простой итерации. / П.Н. Сорокин, Н.Н. Ченцова // Компьютерные исследования и моделирование, Т.4. - 2012. - №1.С. 5-29.
17. Стронгин Р.Г. Численные методы в многоэкстремальных задачах. / Р.Г. Стронгин - М.: изд. Наука, 1978, 240 с.
18. Тейксейра. BorlandDelphi 6. Руководство разработчика.: [пер. с англ.] / Тейксейра, Стив, Пачеко, Ксавье. - M.: Вильямс, 2002, 1120 с.
19. Трубников С.В. Компьютерное моделирование: уч. пособие для студ. вузов / С.В. Трубников - Брянск, изд-во БГУ, 2004, 336 с.
20. Трубников С.В. Поисковые методы минимизации мультимодальной функции одной переменной на основе схем отбора отрезков унимодальности / С.В. Трубников (рукопись)
21. Трубников С.В. Численные методы минимизации [Электронный ресурс]. - Учебное пособие по численным методам минимизации (15,8 МБ)
Размещено на Allbest.ru
...Подобные документы
Определение МДНФ логической функции устройства различными методами (Квайна, Петрика, неопределенных коэффициентов и др.). Составление алгоритма метода минимизации функции и разработка его рабочих программ. Выполнение синтеза схемы логического устройства.
курсовая работа [60,2 K], добавлен 21.11.2010Понятие генетического алгоритма и механизм минимизации функции многих переменных. Построение графика функции и ее оптимизация. Исследование зависимости решения от вида функции отбора родителей для кроссинговера и мутации потомков, анализ результатов.
контрольная работа [404,7 K], добавлен 04.05.2015Исследование функции на непрерывность. Определение производных показательной функции первого и второго порядков. Определение скорости и ускорения материальной точки, движущейся прямолинейно по закону. Построение графиков функций, интервалов выпуклости.
контрольная работа [180,3 K], добавлен 25.03.2014Математическая задача оптимизации. Минимум функции одной и многих переменных. Унимодальные и выпуклые функции. Прямые методы безусловной оптимизации и минимизации, их практическое применение. Методы деления отрезка пополам (дихотомия) и золотого сечения.
курсовая работа [2,0 M], добавлен 26.08.2009Расчет частных производных первого порядка. Поиск и построение области определения функции. Расчет полного дифференциала. Исследование функции на экстремум. Поиск наибольшего и наименьшего значения функции в замкнутой области. Производные второго порядка.
контрольная работа [204,5 K], добавлен 06.05.2012Методы условной и безусловной нелинейной оптимизации. Исследование функции на безусловный экстремум. Численные методы минимизации функции. Минимизация со смешанными ограничениями. Седловые точки функции Лагранжа. Использование пакетов MS Excel и Matlab.
лабораторная работа [600,0 K], добавлен 06.07.2009Нахождение частной производной первого порядка. Определение области определения функции. Расчет производной от функции, заданной неявно. Полный дифференциал функции двух переменных. Исследование функции на экстремум, ее наименьшее и наибольшее значения.
контрольная работа [1,1 M], добавлен 12.11.2014Исследование функции на четность и периодичность. Нахождение вертикальных, горизонтальных (или наклонных) асимптот, а также экстремумов и интервалов монотонности. Определение интервалов выпуклости и точки перегиба. Построение графика исследуемой функции.
презентация [134,7 K], добавлен 21.09.2013Свойства множества Кантора. Исследование заданной функции на непрерывность. Выражение множества B (кладбище Серпинского) и D (гребёнка Кантора) через множество Кантора. Свойства и построение всюду непрерывной, но нигде не дифференцируемой функции.
курсовая работа [1,1 M], добавлен 24.06.2015Вычисление производной функции и ее критических точек. Определение знака производной на каждом из интервалов методом частных значений. Нахождение промежутков монотонности и экстремумов функции. Разложение подынтегральной функции на простейшие дроби.
контрольная работа [134,7 K], добавлен 09.04.2015Способы построения искусственного базиса задачи. Выражение искусственной целевой функции. Математическая модель задачи в стандартной форме. Получение симплекс-таблиц. Минимизации (сведения к нулю) целевой функции. Формы преобразования в задаче равенства.
задача [86,0 K], добавлен 21.08.2010Методика и основные этапы нахождения производной функции. Исследование методами дифференциального исчисления и построение графика функции. Порядок определения экстремумов функции. Вычисление неопределенных и определенных интегралов заменой переменной.
контрольная работа [84,3 K], добавлен 01.05.2010Сокращенные, тупиковые дизъюнктивные нормальные формы. Полные системы булевых функций. Алгоритм Квайна, Мак-Класки минимизации булевой функции. Геометрическое представление логических функций. Геометрический метод минимизации булевых функций. Карты Карно.
курсовая работа [278,1 K], добавлен 21.02.2009Основные определения и теоремы производной, дифференциала функции; техника дифференцирования. Применение производных к вычислению пределов. Исследование функции на монотонность и точки локального экстремума. Полное исследование функции, асимптоты графика.
контрольная работа [539,8 K], добавлен 20.03.2016Область определения и свойства функции (четность, нечетность, периодичность). Точки пересечения функции с осями координат. Непрерывность функции. Характер точек разрыва. Асимптоты. Экстремумы функции. Исследование функции на монотонность. Точки перегиба.
презентация [298,3 K], добавлен 11.09.2011Метод интервалов как один из важнейших методов математической деятельности, связанный с вопросами нахождения нулей функции или промежутков ее знак постоянства для неравенства. Алгоритм решения дробно-рационального неравенства методом интервалов.
курсовая работа [630,7 K], добавлен 12.04.2015Исследование числовых рядов на сходимость. Область сходимости для разных степенных рядов. Разложение функции в ряд Тейлора. Нормы сеточной функции. Исследование устойчивости разностной схемы для однородного уравнения. Совокупность разностных уравнений.
курсовая работа [586,9 K], добавлен 19.04.2011Поиск нулей функции - исследование и построение различных функций зависимостей. Исследование непрерывных процессов. Метод простой итерации. Итерационный процесс Ньютона, аналитическое задание системы уравнений и локализация области нахождения корня.
реферат [54,1 K], добавлен 08.08.2009Методы исследования операций для количественного анализа сложных целенаправленных процессов. Решение задач методом полного перебора и оптимальной вставки (определение всевозможных расписаний, их очередности, выбор оптимального). Генератор исходных данных.
курсовая работа [476,3 K], добавлен 01.05.2011Логика - наука о законах и формах мышления, а основное понятие алгебры логики - высказывание. Основные понятия и тождества булевой алгебры. Изучение методов минимизации булевых функций. Метод Квайна, основанный на применении двух основных соотношений.
контрольная работа [178,2 K], добавлен 20.01.2011
