Методические указания к курсовой работе для студентов специальности «Управление и информатика в технических системах» (стр. 3 из 8)

4. С заданной величиной погрешности

в окрестностях найденной по п. 3 опорной точки менять значения переменной до тех пор, пока происходит убывание минимизируемой функции. Значение, обеспечивающее наименьшее значение функции, принять за фиксированное значение переменной и перейти к п. 2. После нахождения фиксированных значений всех переменных попробовать улучшить решение, выполняя заново п.п. 2-4. Если улучшить решение невозможно, то перейти к пункту 5.

5. За точку минимума принять точку, имеющую последние фиксированные значения всех переменных, минимум функции найдется как ее значение в этой точке.

3.2 Метод Хука – Дживса

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

Описание этой процедуры представлено ниже:

1.Задать погрешность определения местоположения точки минимума

(величина определяется содержанием решаемой задачи).

2.Задать значение базисной точки

.

3.Задать величину начального шага для каждой переменной

.

4.Вычислить

в базисной точки .

5.Каждая переменная по очереди изменяется прибавлением длины шага

.

Таким образом, мы вычисляем значение функции

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

6.Если

, т.е. уменьшение функции не было достигнуто, то исследование повторяется вокруг той же базисной точки , но с уменьшенной длиной шага. На практике удовлетворительным является уменьшение шага (шагов) в десять раз от начальной длины.

7.Если

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

Разумно двигаться из базисной точки

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

.

В общем случае

.

8.Затем исследование следует продолжать вокруг точки

, как описано в п. 5.

9.Если наименьшее значение в п.8 меньше значения в базисной точке

(в общем случае ), то получают новую базисную точку ( ), после чего следует перейти к п. 7. В противном случае не производить поиск по образцу из точки ( ) а продолжить исследования в точке ( ) – переход к п.5.

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

3.3 Метод полного перебора (метод сеток)

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

3.4 Градиентный метод.

1. Задать значение погрешности вычисления экстремума функции

.

2. Задать значение начальной пробной точки

.

3. Задать величину начального шага

4. Вычислить значения частных производных функции в пробной точке:

5. Проверить условие достижения заданной точности:

Если это условие выполняется по всем переменным, то поиск завершается и за точку минимума принимается точка

, для которой подсчитывается минимальное значение функции, иначе перейти к п.6.

6. Определить значение координат новой пробной точки

по формуле:

7. Вычислить значение функции в последней пробной точке

, проверить условие . Если соотношение выполняется, то за очередную пробную точку взять и перейти к п.4, иначе пробная точка остается прежней и перейти к п.8.

8. Положить

и перейти к п. 6.

3.5 Метод наискорейшего спуска многомерной функции

Выбор шага

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

1. Задать значение погрешности определения местоположения минимума функции

.

2. Задать значение начальной пробной точки

.

3. Вычислить значение частных производных функции в рассматриваемой пробной точке:

4. Проверить условие достижения заданной точности:

5. Если это условие выполняется по всем переменным, то переход к п. 8, иначе перейти к п. 6.

6. Определить наилучшие значения шага

по каждой координате. Определение значения шага осуществляется по следующим формулам: