где f: Rm ® R, укладываются в следующую схему. Начиная с некоторого x0 Î Rm, строится последовательность {xn} Ì Rm такая, что

Внимание!

Если вам нужна помощь с работой, то рекомендуем обратиться к профессионалам. Более 70 000 экспертов готовы помочь вам прямо сейчас.

Подробнее Гарантии Отзывы

при всех n Î N. Такие последовательности иногда называют релаксационными, а методы построения релаксационных последовательностей — итерационными методами или методами спуска. Последовательность, удовлетворяющую (2), строят в надежде, что уменьшая на каждом шаге (переходе от xn к xn+1) значение функции, мы приближаемся к минимуму (по крайней мере, локальному).

Будем говорить, что метод, начиная с данного x0 Î Rm,

а) условно сходится, если последовательность {xn} релаксационна и

б) сходится, если

в) линейно сходится (или сходится со скоростью геометрической прогрессии, или имеет первый порядок сходимости), если при некоторых C > 0 и q Î [0, 1)

г) сверхлинейно сходится, если для любого q Î (0, 1) и некоторого (зависящего от q) C выполнено неравенство (3);

д) квадратично сходится (или имеет второй порядок сходимости), если при некоторых C > 0 и q Î [0, 1) и всех n Î N

Выше уже отмечалось, что если x не является точкой локального минимума функции f, то двигаясь из x в направлении, противоположном градиенту (еще говорят, в направлении антиградиента), мы можем локально уменьшить значение функции. Этот факт позволяет надеяться, что последовательность {xn}, рекуррентно определяемая формулой

Нужна работа? Есть решение!

Более 70 000 экспертов: преподавателей и доцентов вузов готовы помочь вам в написании работы прямо сейчас.

Подробнее Гарантии Отзывы

где a — некоторое положительное число, будет релаксационной.

К этой же формуле приводит и следующее рассуждение. Пусть у нас есть некоторое приближение xn. Заменим в шаре B(xn, e) с центром в точке xn функцию f ее линейным (вернее, афинным) приближением:

(функция j аппроксимирует f в окрестности точки xn с точностью o(x — xn). Разумеется, (линейная) безусловная задача j(x) ® min неразрешима, если f ¢(xn) ¹ Q. В окрестности же B(xn, e) функция j имеет точку минимума. Эту точку естественно взять за следующее приближение xn+1.

2. Градиентный метод с постоянным шагом.

В общем случае число a в формуле (4) может на каждом шаге (т. е. для каждого n) выбираться заново:

Именно методы, задаваемые формулой (5), называются градентными. Если an = a при всех n, то получающийся метод называется градиентным методом с постоянным шагом (с шагом a.)

Поясним геометрическую суть градиентного метода. Для этого выберем способ изображения функции с помощью линий уровня. Линией уровня функции f (изолинией) называется любое множество вида {x Î Rm: f(x) = c}. Каждому значению c отвечает своя линия уровня (см. рис. 1).

Рис. 1.

Геометрическая интерпретация градиентного метода с постоянным шагом изображена на рис. 2. На каждом шаге сдвигаемся по вектору антиградиента, «уменьшенному в a раз».

Рис. 2.

где p > 1 (случай p £ 1 не рассматриваем, поскольку тогда функция f не будет гладкой, а мы такой случай не исследуем). Очевидно, задача (1) с такой функцией f имеет единственное решение x* = 0. Для этой функции приближения xn градиентного метода имеют вид:

Закажите работу от 200 рублей

Если вам нужна помощь с работой, то рекомендуем обратиться к профессионалам. Более 70 000 экспертов готовы помочь вам прямо сейчас.

Подробнее Гарантии Отзывы

Пределом этой последовательности может быть только 0. Действительно, если x** = limn®¥ xn ¹ 0, то, переходя к пределу в (6) при n ® ¥, получаем противоречащее предположению x** ¹ 0 равенство

откуда x** = 0. Очевидно также, что если x0 = 0, то и xn = 0 при всех  n.

Покажем, что если p < 2, то при любом шаге a > 0 и любом начальном приближении x0 (за исключением не более чем счетного числа точек) приближения (6) не являются сходящимися. Для этого заметим, что если 0 < |xn| < (2/ap)1/2(2-p), то

Поэтому, если xn не обращается в нуль, то она не может сходиться к нулю и, следовательно, не может сходиться вообще.

Таким образом, осталось доказать (7). В силу (6)

Остается заметить, что если 0 < |xn| < (2/ap)1/(2-p), то  |1 — ap|xn|p-2·sign  xn| > 1, что и требовалось доказать.

Если p = 2, т. е. f(x) = x2, то (6) имеет  вид

Поэтому, если a Î (0, 1), то |1 — 2a| < 1, а следовательно,

Если же a ³ 1, то

и последовательность {xn}, начинающаяся из ненулевой начальной точки, расходится.

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

Нужна работа? Есть решение!

Более 70 000 экспертов: преподавателей и доцентов вузов готовы помочь вам в написании работы прямо сейчас.

Подробнее Гарантии Отзывы

3. Теорема об условной сходимости градиентного метода с постоянным шагом.

Пусть в задаче (1) функция f ограничена снизу, непрерывно дифференцируема и, более того, f ¢ удовлетворяет условию Липшица:

Тогда при a Î (0, 2/L) градиентный метод с постоянным шагом условно сходится.

Д о к а з а т е л ь с т в о.  Положим zn = -af ¢(xn) и обозначим f(xn + tzn) через j(t).

Тогда

и поэтому по формуле Ньютона — Лейбница для функции j

 

 

 

 

Учитывая условие Липшица для f ¢, эту цепочку можно продолжить:

Поскольку 1 — La/2 > 0, последовательность {f(xn)} не возрастает и, следовательно, релаксационность {xn} доказана. А так как в силу условий теоремы f еще и ограничена снизу, последовательность {f(xn)} сходится. Поэтому, в частности, f(xn+1) — f(xn) ® 0 при n ® ¥. Отсюда и из (8) получаем

æ
è

1 –

La

2

ö
ø

–1

[f(xn) — f(xn+1)] ® 0 при n ® ¥.

 

Подчеркнем, что теорема не гарантирует сходимости метода, но лишь его условную сходимость, причем, локальную.