§ 8. Метод наискорейшего градиентного спуска

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

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

В этом случае рассматриваемый метод называют методом наискорейшего градиентного спуска или просто методом наискорейшего спуска.

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

и

Обозначим через , т.е. положим

Пусть . Вспоминая, что , вычислим . Имеем

откуда

На рис. 6.8.1 изображены последовательные приближения метода наискорейшего спуска и линии уровня функции F. Итерационный процесс (3), (4) называют методом наискорейшего спуска решения рассматриваемой системы линейных уравнений.

Рис. 6.8.1

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

Теорема. Приближения метода наискорейшего спуска удовлетворяют соотношению

Доказательство. При произведем одну итерацию оптимального одношагового итерационного процесса

Погрешности итераций связаны соотношением

Пусть - ортонормированная система собственных векторов матрицы . Поскольку , то при всех выполняются соотношения

и, таким образом,

Пусть . Справедливы соотношения

С учетом (7) получаем

Поскольку , то это означает, что

Приближение можно записать в виде (1)

Так как на достигается минимум среди всех приближений вида (1), то . Отсюда следует оценка

а поэтому и справедливость утверждения теоремы. Аналогично (7.9) можно получить неравенство

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

Однако есть принципиальное различие в этих методах. Для написания итерационного процесса (6) требуется информация о границах спектра . В случае метода (3), (4), такой информации не требуется.

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

У метода наискорейшего спуска (3), (4), однако, есть следующий недостаток по сравнению с простейшим процессом (6). При нахождении каждого следующего приближения он требует не одной, а двух трудоемких операций умножения матрицы на вектор.

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

Вектор называется невязки. Умножая (8) слева на А и вычитая , получим

Формулу (4) для определения можно записать в виде

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

В итерационном процессе накопление вычислительной погрешности носит более сложный характер.

Задача 1. Получить оценку скорости сходимости метода наискорейшего спуска

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

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

Иначе обстоит дело в случае метода наискорейшего спуска. Пусть, например, — единичная матрица. Тогда

и метод наискорейшего спуска сходится за одну итерацию (доказать!). Произведем замену масштабов . Матрица системы А в данном случае будет диагональной с элементами на диагонали, равными . Тогда минимизируется функционал

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