Федеральное государственное автономное
образовательное учреждение
высшего профессионального образования
«СИБИРСКИЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ»
Институт космических и информационных технологий
«Кафедра информатики»
ОТЧЕТ О ПРАКТИЧЕСКОЙ РАБОТЕ №1
"Численные методы многомерной оптимизации"
Преподаватель _________ Сергеева Н. А.
подпись, дата
Студент, КИ 09-08 _________ Банникова А.В.
подпись, дата
Красноярск 2012
1 Постановка задачи
Метод Хука – Дживса
Даны две двумерные функции:
Начальная точка, шаги по координатным
направлениям:
-
малое положительное число – условие
окончания поиска, коэффициент уменьшения
шага
,
задает пользователь.
Необходимо найти безусловный минимум
функции двух переменных, т. е. найти
такую точку
,
с помощью метода Хука-Дживса. Реализовать
и исследовать свойства данного метода
в программной среде С++.
2. Метод Ньютона
Даны двумерные функции:
Начальная точка, - малое положительное число – условие окончания поиска, задает пользователь.
Необходимо найти локальный минимум
функции двух переменных на множестве
допустимых решений, т. е. найти такую
точку
,
с помощью метода Ньютона.
Реализовать и исследовать свойства данных методов в программной среде С++.
2. Теоретические сведенья
2. 1 Метод конфигураций
Метод конфигураций, служит для поиска безусловного локального экстремума функции и относится к прямым методам, то есть опирается непосредственно на значения функции. Алгоритм делится на две фазы: исследующий поиск и поиск по образцу.
На начальном этапе задается стартовая точка (обозначим её h1) и шаги hi по координатам. Затем замораживаем значения всех координат кроме 1-й, вычисляем значения функции в точках x0+h0 и x0-h0 (где x0 — первая координата точки, а h0 — соответственно значение шага по этой координате) и переходим в точку с наименьшим значением функции. В этой точке замораживаем значения всех координат кроме 2-й, вычисляем значения функции в точках x1+h1 и x1-h1, переходим в точку с наименьшим значением функции и т. д. для всех координат. В случае, если для какой-нибудь координаты значение в исходной точке меньше, чем значения для обоих направлений шага, то шаг по этой координате уменьшается. Когда шаги по всем координатам hi станут меньше соответствующих значений ei, алгоритм завершается, и точка 1 признаётся точкой минимума.
Таким образом, проведя исследующий поиск по всем координатам, мы получим новую точку, с наименьшим значением функции в окрестности (обозначим ее 2). Теперь можно осуществлять переход ко 2 фазе алгоритма.
На этапе поиска по образцу откладывается точка 3 в направлении от 1 к 2 на том же расстоянии. Её координаты получаются по формуле, где xi — точка с номером i, λ — параметр алгоритма, обычно выбирающийся равным 2. Затем в новой точке 3 проводится исследующий поиск, как на 1 фазе алгоритма, за исключением того, что шаг на этой фазе не уменьшается. Если на этой фазе, в результате исследующего поиска, удалось получить точку 4, отличную от точки 3, то точку 2 переобозначим на 1, а 4 на 2 и повторим поиск по образцу. В случае если не удаётся найти точку 4, отличную от точки 3, то точку 2 переобозначим на точку 1 и повторим 1-ю фазу алгоритма — исследующий поиск.