Метод градиентного спуска

Рассмотрим СЛАУ (1). Пусть матрица является симметричной и положительно определенной. Поставим в соответствие СЛАУ (1) многочлен:

, (11)

который называется функционалом энергии.

Утверждение 1. Если матрица является симметричной и положительно определенной, то многочлен (11) имеет единственный минимум.

Существует определенная связь между двумя задачами: задачей решения СЛАУ (1) и задачей минимизации функционала (11).

Теорема 4. Если в некоторой точке n -мерного векторного пространства многочлен (11) имеет минимум, то координаты этой точки являются решением СЛАУ (1).

Теорема 5. Если - решение СЛАУ (1), то многочлен (11) принимает в этой точке свой абсолютный минимум по всему n -мерному пространству.

Из теорем 4,5 вытекает, что задача решения СЛАУ (1) для симметричной и положительно определенной матрицы эквивалентна задаче минимизации функционала (11).

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

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

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

, (12)

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

. (13)

Остановиться нужно при таком , в котором функция достигает своего минимума. Это произойдет там, где (см.матем.анализ – условия локального экстремума функции одной переменной). Пусть определяется по формуле (11). В этом случае

. (14)

Формула (14) получается путем непосредственного вычисления координат вектора и сравненя их значений с соответствующими элементами вектора :

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

Тогда функция (13) может быть записана в виде:

где

. (15)

Вычислим :

;

Тогда

Приравнивая , получаем стационарную точку функции:

. (16)

Алгоритм метода наискорейшего (градиентного) спуска

Пусть - заданная точность (погрешность), с которой нужно получить решение поставленной задачи.

Шаг 1. Задается начальное приближение .

Шаг 2. По формуле (16) вычисляется коэффициент .

Шаг 3. По формуле (15) вычисляет очередное приближение к решению : .

Шаг 4 (проверка). Если , то требуемая точность достигнута, итерационный процесс завершен, в качестве приближенного значения решения СЛАУ (1) берется , полученный на шаге 3; иначе полагается равным , переход на шаг 2.

Замечание 4 (вычислительная сложность метода градиентного спуска). Основные расчетные формулы метода градиентного спуска – это формулы (16) и (15), которые определяет действия данного алгоритма на каждой итерации. Проверьте, что каждая итерация метода градиентного спуска требует операций, тогда в целом количество арифметических операций, необходимых для решения СЛАУ методом градиентного спуска, определиться как