Градиентные методы.

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

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

Различают градиентные методы I и II порядков. Градиент функции в некоторой точке это вектор, показывающий направление наибольшей скорости увеличения функции. Антиградиент –убывание функции (т.е. противоположно градиенту).

Grad Если спроектировать его на ортогональные оси.

вектор сторка

проекции градиента.

Антиградиент - т.е. -

3. Метод наискорейшего спуска. (1-го порядка)

где М откр.

Алгоритм любого метода поиска отражается следующей поисковой формулой.

или

К –номер итерации;

S- направление, в котором осуществляется поиск;

- величина шага.

Знак ±

Ели движение по градиенту, то

-градиент - антиградиент часто пользуется

Пример.

Начальная точка к=0

1 шаг

Определяем в начальной точке проекции градиента

4)

По направлению антигр. построим плоскость П₂, перпендикулярную горизонтальной плоскости . Это плоскость пройдет через точку А⁰ и пересчет экстремальную поверхность по экстремальной линии

Уравнение этой линии с учетом выражения (2) (ибо вдоль неё мы и должны сделать 1-ую итерацию) имеет вид

где

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

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

И так

После этого найдем координаты экстремума рассматриваемой кривой т.е. координаты точки А¹, по формуле (2)

Это сделана одна итерация

2 шаг Принимаем точку А¹ за начальную и все повторим

По направлению антиградиента строим вертикальную площадь П₂, которая пересечет горизонтальную площадь по линии L₂, а экстремум поверхность по экстремальной линии, уравнение которой запишем или

или

Найдем оптимальное значение

Тогда координаты экстремальной точки А² в плоскости П₂ по формуле (2) будут

3 шаг Принимаем точку А² за начальную и проводимую 3-ую итерацию и т.д.

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

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

Нанесем на наш чертеж рис. 1

x₂

L_{2 т.е.} -

рис. 1

линии равного уровня. Поскольку в нашем случае - квадратичная функция (сепарабельная), то оси фигур линии равного уровня (т.е. главные оси эллипсов) будут параллельны осям координат.

Мы уже знакомы с методом «Г-З», поэтому нас не должен удивлять тот факт, что частные экстремумы, т.е. точки А¹, А² и т.д. расположены в точках касания направлений градиентов L₁, L₂ с линией равного уравнения. Но что характерно для метода наискорейшего спуска, так тот факт, что если выбираются оптимальным образом, то углы между L₁ и L₂, L₂ и L₃ и т.д. получаются прямыми. Отметим, что это только в случае, когда выбрано оптимальным. Возникает вопрос нельзя ли формализовать метод наискорейшего спуска, хотя бы для квадратичных функций? Оказывается можно.

Пусть задано уравнение поверхности 2²⁰порядка в общем виде.

Проекции градиента на координате оси легко получить: