Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике § 10.3. Градиентный методРассмотрим задачу безусловной минимизации дифференцируемой функции многих переменных
Существуют различные способы выбора шага 1. Метод наискорейшего спуска.Рассмотрим функцию
Этот метод, предложенный в 1845 г. О. Коши, принято теперь называть методом наискорейшего спуска.
Рис. 10.5 На рис. 10.5 изображена геометрическая иллюстрация этого метода для минимизации функции двух переменных. Из начальной точки Отметим, что на каждой итерации выбор шага Применим метод наискорейшего спуска для минимизации квадратичной функции
с симметричной положительно определенной матрицей А. Согласно формуле (10.8), в этом случае
Заметим, что
Эта функция является квадратичной функцией параметра а и достигает минимума при таком значении
Таким образом, применительно к минимизации квадратичной функции (10.24) метод наискорейшего спуска эквивалентен расчету по формуле (10.25), где
Замечание 1. Поскольку точка минимума функции (10.24) совпадает с решением системы Замечание 2. Отметим, что Пример 10.1. Применим метод наискорейшего спуска для минимизации квадратичной функции Заметим, что Возьмем начальное приближение I итерация. II итерация. Можно показать, что для всех
Заметим, что последовательность На рис. 10.5 изображена именно та траектория спуска, которая была получена в данном примере. Для случая минимизации квадратичной функции справедлив следующий общий результат Теорема 10.1. Пусть А — симметричная положительно определенная матрица и минимизируется квадратичная функция (10.24). Тогда при любом выборе начальною приближения метод наискорейшею спуска (10.25), (10.26) сходится и верна следующая оценка погрешности:
Здесь Отметим, что этот метод сходится со скоростью геометрической прогрессии, знаменатель которой Пример 10.2. Применение метода наискорейшего спуска для минимизации квадратичной функции
Рис. 10.6 Последовательность чем в предыдущем примерю. Так как здесь Замечание 1. Мы сформулировали теорему о сходимости метода наискорейшего спуска в случае, когда целевая функция является квадратичной. В общем случае, если минимизируемая функция строго выпуклая и имеет точку минимума х, то также независимо от выбора начального приближения полученная указанным методом последовательность Замечание 2. Для квадратичной целевой функции (10.24) решение задачи одномерной минимизации (10.23) удается найти в виде простой явной формулы (10.26). Однако для большинства других нелинейных функций этого сделать нельзя и для вычисления 2. Проблема "оврагов".Из проведенного выше обсуждения следует, что градиентный метод сходится достаточно быстро, если для минимизируемой функции поверхности уровня близки к сферам (при
Рис. 10.7. Если начальная точка Для ускорения сходимости градиентного метода при минимизации овражных функций разработан ряд специальных "овражных" методов. Дадим представление об одном из простейших приемов. Из двух близких начальных точек
Рис. 10.8 Более подробную информацию о проблеме "оврагов" и "овражных" методах можно найти, например, в [9], [18]. 3. Другие подходы к определению шага спуска.Как нетрудно понять, на каждой итерации было бы желательно выбирать направление спуска В одном из простейших алгоритмов (типа дробления шага) такого выбора шага
Однако при таком выборе
Здесь Пример 10.3. Продемонстрируем применение градиентного метода с дроблением шага к задаче минимизации квадратичной функции Выберем начальное приближение I итерация. Вычисляем Вычисляем Вычисляем Вычисляем Положим Далее вычисления следует продолжить до выполнения какого-либо принятого критерия окончания итераций. 4. Влияние погрешности вычислений.Один из существенных недостатков градиентного метода связан с его чувствительностью к погрешностям вычислений. Особенно сильно этот недостаток сказывается в малой окрестности точки минимума, где антиградиент, задающий направление поиска, мал по модулю. Поэтому эффективность градиентного метода на завершающей стадии поиска существенно ниже, чем на начальной стадии.
|
1 |
Оглавление
|