Метод наискорейшего спуска для системы уравнений

3.8. Метод скорейшего спуска (градиента) для случая . системы линейных алгебраических уравнений

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

Представим систему линейных уравнений в следующем виде:

(3.38)

Запишем выражение (3.38) в операторной форме:

(3.39)

Здесь приняты следующие обозначения:

; ; . (3.40)

В методе скорейшего спуска решение ищут в виде

, (3.41)

Где и — векторы неизвестных на P и P+1 шагах итераций; вектор невязок на P-ом шаге определяется выражением

, (3.42)

А (3.43)

В формуле (3.43) используется скалярное произведение двух векторов, которое определяется следующей формулой:

(3.44)

В формуле (3.43) — транспонированная матрица Якоби, вычисленная на P-ом шаге. Матрица Якоби вектор – функции F(X) определяется как

(3.45)

Нетрудно убедиться, что для системы (3.39) матрица Якоби равна

(3.46)

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

· Как видно из выражения (3.45), матрица Якоби не зависит от шага итерации.

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

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

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

· Итерационный процесс можно прервать на любом K–ом шаге и продолжить позднее, введя в качестве нулевого шага значения X(K).

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

Пример 3.7. Методом скорейшего спуска решим систему уравнений

Так как диагональные элементы матрицы являются преобладающими, то в качестве начального приближения выберем:

Следовательно, вектор невязок на нулевом шаге равен

Далее последовательно вычисляем

Отсюда

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

Вопросы для самопроверки

· Назовите известные вам методы решения СЛАУ.

· Чем точные методы отличаются от приближенных?

· Что такое прямой и обратный ход в методе Гаусса?

· Нужен ли обратный ход при вычислении методом Гаусса а) обратной матрицы; б) определителя?

· Что такое невязка?

· Сравните достоинства и недостатки точных и приближенных методов.

· Что такое матрица Якоби?

· Надо ли пересчитывать матрицу Якоби на каждом шаге итерации в методе градиента?

· Исходная СЛАУ решается независимо тремя методами – методом Якоби, методом Зейделя и методом градиента. Будут ли равны значения

А) начального приближения (нулевой итерации);

Б) первой итерации?

· При решении СЛАУ (n > 100) итерационными методами решение расходится. Как найти начальное приближение?

Безусловная оптимизация. Метод наискорейшего спуска

Безусловная оптимизация. Метод наискорейшего спуска

Метод наискорейшего спуска (в англ. литературе «method of steepest descent») — это итерационный численный метод (первого порядка) решения оптимизационных задач, который позволяет определить экстремум (минимум или максимум) целевой функции:

— это значения аргумента функции (управляемые параметры) на вещественной области.

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

где i, j,…, n — единичные векторы, параллельные координатным осям.

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

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

где знак «+» используется для поиска максимума функции, а знак «-» используется для поиска минимума функции;

— единичный вектор направления, который определяется по формуле:

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

— константа, определяющая размеры шага и одинаковая для всех i-х направлений.

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

Другими словами, величину шага определяют при решении данного уравнения:

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

В случае функции двух переменных данный метод имеет следующую геометрическую интерпретацию: направление движения из точки касается линии уровня в точке . Траектория спуска зигзагообразная, причем соседние звенья зигзага ортогональны друг другу. Условие ортогональности векторов направлений спуска в соседних точках записывается следующим выражением:

Рис.1. Траектория движения к точке экстремума при использовании метода наискорейшего спуска, изображенная на графике линии равного уровня функции f(x)

Поиск оптимального решения завершается в случае, когда на итерационном шаге расчета (несколько критериев):

— траектория поиска остается в малой окрестности текущей точки поиска:

— приращение целевой функции не меняется:

— градиент целевой функции в точке локального минимума обращается в нуль:

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

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

Методика расчета

• 1 шаг: Определение аналитические выражения (в символьном виде) для вычисления градиента функции

• 2 шаг: Задаем начальное приближение

Далее выполняется итерационный процесс.

• 3 шаг: Определяется необходимость рестарта алгоритмической процедуры для обнуления последнего направления поиска. В результате рестарта поиск осуществляется заново в направлении скорейшего спуска.

• 4 шаг: Вычисление координат единичного вектора по представленным формулам

• 5 шаг: определяем шаг расчета из условия поиска экстремума для следующей функции (решения задачи одномерной оптимизации).

• 6 шаг: Определяем новые значения аргументов функции после выполнения k-го шага расчета:

где знак «+» используется для поиска максимума функции, а знак «-» используется для поиска минимума функции;

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

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

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

На этом занятии мы с вами рассмотрим довольно популярный алгоритм под названием «метод градиентного спуска» или, еще говорят «метод наискорейшего спуска». Идея метода довольно проста. Предположим, имеется дифференцируемая функция с точкой экстремума x*. Нам нужно найти эту точку. Для простоты восприятия информации, предположим, что это парабола с точкой экстремума x*. Конечно, для такого простого случая эту точку можно очень легко определить из уравнения:

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

Итак, из рисунка мы хорошо видим, что справа от точки экстремума x* производная положительна, а слева – отрицательна. И это общее математическое правило для точек локального минимума. Предположим, что мы выбираем произвольную начальную точку на оси абсцисс. Теперь, смотрите, чтобы из двигаться в сторону x*, нам нужно в области положительных производных ее уменьшать, а в области отрицательных – увеличивать. Математически это можно записать так:

Здесь n – номер итерации работы алгоритма. Но, вы можете спросить: а где же тут градиент? В действительности, мы его уже учли чисто интуитивно, когда определяли перемещение вдоль оси абсцисс для поиска оптимальной точки x*. Но математика не терпит такой вульгарности, в ней все должно быть прописано и точно определено. Как раз для этого нужно брать не просто производную, а еще и определять направление движения, используя единичные векторы декартовой системы координат:

И градиент функции можно записать как

то есть, это будет уже направление вдоль оси ординат и направлен в сторону наибольшего увеличения функции. Соответственно, двигаясь в противоположную сторону, будем перемещаться к точке минимума x*.

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

Однако у такой формулы есть один существенный недостаток: значение производной может быть очень большим и мы попросту «перескочим» через значение x* и уйдем далеко влево или вправо. Чтобы этого не происходило, производную дополнительно умножают на некоторое небольшое число λ:

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

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

и ее производную:

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

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

Отображаем начальный график:

Запускаем алгоритм градиентного поиска:

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

После запуска увидим скатывание точки к экстремуму функции. Установим значение

Увидим «перескоки» оптимального значение, то есть, неравномерную сходимость к точки минимума. А вот, если поставить параметр

то скатывания совсем не будет, т.к. аргумент x будет «перескакивать» точку минимума и никогда ее не достигать. Вот так параметр λ влияет на работу алгоритма градиентного спуска.

Выбор шага сходимости

Важно правильно его подбирать в каждой конкретной решаемой задаче. Обычно, это делается с позиции «здравого смысла» и опыта разработчика, но общие рекомендации такие: начинать со значения 0,1 и уменьшать каждый раз на порядок для выбора лучшего,

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

Функция min здесь выбирает наименьшее из двух аргументов и использует его в знаменателе дроби. Это необходимо, чтобы величина шага при больших n не становилась слишком маленькой и ограничивалась величиной

где mn – некоторое заданное ограничивающее значение.

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

приводится к единичной норме:

И уже он используется в алгоритме наискорейшего спуска:

В одномерном случае нашего примера, это, фактически означает, что вместо действительного значения градиента, берутся числа ±1:

И алгоритм в Python примет вид:

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

Результат выглядит уже лучше и при этом, мы не привязаны к значению градиента.

Локальный минимум

Еще одной особенностью работы этого алгоритма является попадание в область локального минимума функции. Например, если взять вот такой график:

То при начальном значении x=0 получим один минимум, а, например, при x=2,5 – другой. В этом легко убедиться, если в нашей программе переписать функции:

(последняя – это производная: ). Увеличим диапазон отображения графика:

и запустим программу. Теперь, установим начальное значение xx=2,5, снова запустим и увидим уже другую точку локального минимума.

Это, наверное, основной недостаток данного алгоритма – попадание в локальный минимум. Чтобы решить эту проблему перебирают несколько разных начальных значений и смотрят: при котором был достигнуто наименьшее значение. Его и отбирают в качестве результата. Такой ход не дает нам гарантии, что действительно был найден глобальный минимум функции (иногда он может не существовать, как, например, с нашей синусоидой), но, тем не менее, это повышает наш шанс найти лучшее решение. Вот базовая теория и практика применения метода наискорейшего спуска.

Видео по теме

#1: Метод наименьших квадратов

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

#3: Метод градиентного спуска для двух параметров

#4: Марковские процессы в дискретном времени

#5: Фильтр Калмана дискретного времени

#6: Фильтр Калмана для авторегрессионого уравнения

#7: Векторный фильтр Калмана

#8: Фильтр Винера

#9: Байесовское построение оценок, метод максимального правдоподобия

#10: Байесовский классификатор, отношение правдоподобия

© 2022 Частичное или полное копирование информации с данного сайта для распространения на других ресурсах, в том числе и бумажных, строго запрещено. Все тексты и изображения являются собственностью сайта