Название: Информатика - Алгоритмы и программы (Н.В. Усольцев)

Жанр: Информатика

Просмотров: 1276

3.1. методы нулевого порядка

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

.

В методе прямого перебора осуществляется сканирование по всем узлам сетки и поиск мин/макс значения  точно также, как и в одномерном случае.

В методе покоординатного изменения сначала ищется мин/макс при изменении первого аргумента, потом второго, потом третьего и т.д., затем снова изменятся первый, второй – до выхода в точку мин/макс.

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

Градиентные методы используют при поиске мин/макс информацию о градиенте – векторе, указывающем в пространстве  направление ее наибольшего возрастания. Следует двигаться по линии градиента, при поиске максимума по его направлению, при поиске минимума  - против.

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

где  - единичные векторы (орты) координатных осей.

Для вычисления компонентов вектора-градиента обычно используется численное дифференцирование, например, с использованием двухточечной или трехточечной формул:

Направление градиента образует с осями координат углы:

                        ,

где   - модуль вектора-градиента:    .

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

или                             .

Удобно, чтобы величина шага  была пропорциональна величине градиента

                        .

В этом случае, при приближении к экстремуму шаги станут автоматически уменьшаться, и в точке экстремума движение остановится.

                        .

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

                                   .