|
X |
аА(х
|
X |
= (Е~аА)(хк По свойству норм имеем
*-1
Оценка сверху для нормы матрицы дает [lis -аА§<q~ max Jl-al\,|lЗависимость qfa) представлена на рис.5.1, из которого следует, что при ae(0; 2/L) величина q<l. Кроме того, из неравенств
Рис 5.1. Зависимость оценки знаменателя геометрической прогрессии от величины шага а градиентного метода
Из рис.5.1 следует, что величина q принимает минимальное значение q = fL l)/(L + I) при a = a = VflAl). Поэтому от соотношения между L и / существенно зависит число итераций градиентного метода при минимизации выпуклой квадратичной функции. Проиллюстрируем это на примере квадратичной функции двух переменных. При L = / > 0 точка минимума ffx) находится за один шаг.
Пример 5.1. Решить задачу f(x) = х2 + х\ -> min градиент-ным методом из начальной точки х = (1,1), приняв а - а .
В данном случае матрица А квадратичной функции
(2 ОЛ
А = \ Очевидно, / 1 = 2. Поэтому а - 21 (L + I) - 1/2 и
\0 2,
х1 - х° - \/2f'(x) = (0,0). Легко проверить, чтох1 = х.
При / - L линии уровня целевой функции ffx) - это концентрические окружности, поэтому направление антиградиента указывает на центр этих окружностей, т.е. на точку глобального минимума ffx).
Если L » I > 0, то линиями уровня являются эллипсы, полуоси которых сильно различаются. Поэтому направление антиградиента в некоторой точке может сильно отличаться от направления к точке глобального минимума.
Пример 5.2. Из начальной точки х° = (1, 1) выполнить несколько итераций поиска точки минимума функции f(x) - х2 +100x2 градиентным методом, полагая а - а.
Собственные значения матрицы А этой квадратичной функции равны: / 2, L - 200. Линиями уровня ffx) являются эллипсы, сильно вытянутые вдоль оси 0х]. Поэтому в точке х° направление вектора антиградиента ffx) - (-2, -200) сильно отличается от направления к точке глобального минимума х* - х° - (-1, -1). Приняв в формуле (5.5) а = а = 2/(1 + L) = 1/101, получим с учетом выражения для градиента ffx) - (2х\, 200л'2) следующую зависимость изменения координат точек минимизирующей последовательности:
Jff+,=jc*-99/101;;с2А+, = -х^ 99/101.
Из этой зависимости следует, что последовательность {х} сходится к точке глобального минимума медленно и траектория сходимости имеет ярко выраженный зигзагообразный характер.
В курсе линейной алгебры для симметрической положительно определенной матрицы вводится число обусловленности матрицы р L / I - отношение наибольшего к наименьшему собственному значению. В задаче минимизации произвольной (не обязательно квадратичной) сильно выпуклой функции ffx) эта величина для матрицы ее вторых производных (гессиана) 32 характеризует степень вытянутости линий (поверхностей) уровня ffx) = с. Очевидно, что всегда р > I. Если р велико, то линии (поверхности) уровня сильно вытянуты и говорят, что функция имеет овражный характер, т.е. резко меняется по одним направлениям и слабо - по другим. В подобных случаях задачу минимизации называют плохо обусловченной (см. пример 5.2). Если же р близко к единице, то линии (поверхности) уровня близки к окружностям (сферам) и задача минимизации является хорошо обусловленной (см. пример 5.1).
5.2. Метод наискорейшего спуска
В этом варианте градиентного метода также полагают pk = -f(xk) и величина шага ак находится в результате решения задачи одномерной минимизации
Фк(а)-> mm, (5.9)
где Фк(а)= f{xk-of{xk)\a > 0, т.е. на каждой итерации в направлении антиградиента - fix*) совершается исчерпывающий спуск.
Опишем алгоритм метода. Шаг 0. Задать параметр точности е > 0 , выбрать х е Еп. Шаг 1. Вычислить f(x) и проверить условие достижения точности: ||/'(х)| < я. Если оно выполнено, то принять х*=х,
f* = f(x) и поиск завершить, иначе - перейти к шагу 2.
Шаг 2. Решить задачу одномерной минимизации (5.9) для
хк -х, т.е. найти а . Принять х = х - a *f(x) и перейти к
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.