Алгоритм работы программы




Теоретические сведенья

Метод конфигураций

 

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

На начальном этапе задается стартовая точка (обозначим её 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-ю фазу алгоритма — исследующий поиск.

Метод Ньютона

Метод Ньютона - это итерационный численный метод нахождения корня (нуля) заданной функции. Метод был впервые предложен английским физиком, математиком и астрономом Исааком Ньютоном (1643—1727). Поиск решения осуществляется путём построения последовательных приближений и основан на принципах простой итерации. Метод обладает квадратичной сходимостью. Улучшением метода является метод хорд и касательных. Метод Ньютона в основном используется для решения задач оптимизации, в которых требуется определить нуль первой производной либо градиента в случае многомерного пространства.

Стратегия метода Ньютона состоит в построении последовательности точек, таких, что значение функции в предыдущей точки больше, чем в последующей. Точки последовательности выбираются по правилу: . Начальная точка задается пользователем, а направление спуска определяется по формуле , где Н(х) – матрица Гессе, - градиент исходной функции.

 

Алгоритм работы программы

Шаг 1. Пользователь выбирает метод нахождения минимума функции, и вид данной функции из предложенных.

а) При выборе метода Хука – Дживса:

1. Задаем функцию зависимости от двух аргументов.

Пользователь задает начальные значения: начальную точку, шаги по координатным направлениям: , ошибку , коэффициент уменьшения шага .

2. Осуществляем следующий поиск по выбранному координатному направлению:

а) если: , то шаг считается удачным. В этом случае следует положить и переходим к шагу 3;

б) если в п. а шаг неудачный, то делается шаг в противоположное направление. Если , то положим и перейдем к шагу 3.

3. Проверим условие: если , то перейдем к шагу 4, иначе, к шагу 5.

4. Провести поиск по образцу. Положить , и перейти к шагу 2.

а) если все шаги по координатным направлениям меньше числа , то поиск закончен

б) для тех i, для которых больше , уменьшить величину шага на a перейти к шагу 2.

б) При выборе метода Ньютона

1. Задаем значения нулевой точки, ошибку .

2. Находим матрицу Гессе Н(х) и градиент.

3. Положим к = 0, и вычислим градиент в точке .

4. Проверить выполнение критерия окончания

а) Если неравенство выполнено, то расчет окончен и

б) Если нет, то перейти к пункту 5.

5. Вычислить матрицу .

6. Вычислить матрицу .

7. Проверить выполнения условия > 0

а) если да, то перейти к шагу 9

б) если нет, то перейти к шагу 10, положив

8. Определить

9. Найти точку , t=1, если >0, иначе выбрать t из дополнительных условий.

10. Если условие выполняется , поиск окончен, в противном случае положить к = к + 1, и перейти к пункту 3.

Шаг 2. Выводим полученные значения точек, и значения функции в этих точках.

Шаг 3. Нарисовать линии уровней заданной функции и итерационную процедуру поиска минимума.




Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2017-12-29 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: