3. Наискорейший спуск.

Спускаться можно не только параллельно осям координат. Вдоль любой прямой функция зависит только от одной переменной, и минимум на этой прямой находится описанными в § 1 методами.

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

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

Если функция является положительно определенной квадратичной функцией

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

(23)

Из уравнения легко находим ее минимум

дающий нам следующую точку спуска:

Направление наискорейшего спуска определяется градиентом квадратичной функции (22):

Подставляя это значение в формулы (24)-(25), получим окончательные выражения для вычисления последовательных спусков.

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

здесь — собственные значения положительно определенной матрицы А (они вещественны и положительны). Если что соответствует сильно вытянутым эллипсам — линиям уровня, то и сходимость может быть очень медленной. Есть такие начальные приближения (рис. 39), когда точно реализуется наихудшая возможная оценка, т. е. в (27) имеет место равенство.

Рис. 39.

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

Для улучшения метода наискорейшего спуска предлагают «кухонные» поправки к алгоритму — например, совершают по каждому направлению спуск не точно до минимума. Наиболее любопытным представляется такое видоизменение алгоритма. Будем делать по направлению, противоположному градиенту, только бесконечно малый шаг и после него вновь уточнять направление спуска. Это приводит к движению по кривой являющейся решением системы обыкновенных дифференциальных уравнений:

Вдоль этой кривой т. е. функция убывает, и мы движемся к минимуму при

Уравнение (28) моделирует безынерционное движение материальной точки вниз по линии градиента. Можно построить и другие уравнения — например, дифференциальное уравнение второго порядка, моделирующее движение точки при наличии вязкого трения.

Однако от идеи метода еще далеко до надежного алгоритма. Фактически систему дифференциальных уравнений (28) надо численно интегрировать (см. главу VIII). Если интегрировать с большим шагом, то численное решение будет заметно отклоняться от линии градиента. А при интегрировании малым шагом сильно возрастает объем расчетов. Кроме того, если рельеф имеет извилистые овраги, то трудно ожидать хорошей сходимости этого метода.

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