Основы научных исследований. Анкудинов И.Г - 44 стр.

UptoLike

ВУЗ: 

СЗТУ | Санкт-Петербург

Составители: 

Рубрика: 

Метод градиентного спуска. Этот метод целесообразно применять при
численном решении систем уравнений. Рассмотрим систему двух уравнений
с двумя неизвестными
0),(
0),(
2
1
=
=
yxf
yxf
(3.7)
Введем вспомогательную неотрицательную функцию U в виде суммы
квадратов исходных функций
⎧
⎨
0),(),(),(
2
2
2
1
≥+= yxfyxfyxU
. (3.8)
Функция U обращается в ноль только при значениях неизвестных x,y,
являющихся решением системы (3.7). Поскольку значение U =0 является
также и минимумом функции, чтобы решить систему (3.7) достаточно найти
минимум функции U в (3.8). Оказывается, что существует удобный
итерационный процесс поиска этого минимума.
Для выяснения сути этого процесса воспользуемся следующей аналогией.
Представим себе функцию
z=U(x,y) в трехмерной декартовой системе
координат как некий "горный рельеф", который в одной или нескольких
точках касается плоскости xoy – "уровня мирового океана". Решение
начинается из некоторой точки этой "горной местности" с координатами x
0
,
y
0
, z
0
=U(x
0
,y
0
). Для этой точки определяется направление наиболее быстрого
уменьшения функции – направление, противоположное вектору градиента
функции (в нашей аналогии – направление самого крутого склона). В
выбранном направлении производится перемещение – "спуск с горы". При
этом величина шага в выбранном должна быть небольшой, иначе можно "по
инерции въехать на еще более крутой противоположный склон". Таким
образом, мы попадаем в новую точку "горной местности" с координатами
x
1
, y
1
, z
1
=U(x
1
,y
1
), причем U(x
1
,y
1
) < U(x
0
,y
0
). Далее описанная процедура
повторяется, пока не будет достигнут уровень U=0.
Итерационная формула, реализующая описанный алгоритм, имеет вид
),(
),(
1
1
nnynn
nnxnn
yxUgradyy
yxUgradxx
λ
λ
−=
−=
+
+
, (3.9)
где
λ
- нормирующий множитель амплитуды шага, grad
x
U и grad
y
U -
проекции единичного вектора градиента функции U.
Для системы уравнений, содержащей m неизвестных, спуск происходит в
(m+1) -мерном пространстве.
⎧
⎨
Основные проблемы при использовании метода градиентного спуска:
относительно медленная сходимость к корню и опасность попадания в
ненулевой минимум функции U.
Пример 3.4. Применим метод градиентного спуска для решения системы
уравнений
0=23
3
2
2
+−
=−+
xyx
yxy 0
(3.10)
Выберем в качестве начального приближения точку с координатами x
0
= 3, y
0
= 3. Вычислим в этой точке значение функции U и ее частных производных
U
x
′
и U
y
′
⎧
⎨
⎩

Страницы