курсовые,контрольные,дипломы,рефераты
Семинарская работа
Градиентный метод с дроблением шага и метод наискорейшего спуска
Выполнил
Студент группы МОС-22
Кравченко Александр
Градиентный метод с дроблением шага.
В этом варианте градиентного метода величина шага αn на каждой итерации выбирается из условия выполнения неравенства
|
f(xn+1) = f(xn - anf ¢(xn)) £ f(xn) - ean||f ¢(xn)||2, |
где e Î (0, 1) — некоторая заранее выбранная константа. Условие гарантирует (если, конечно, такие an удастся найти), что получающаяся последовательность будет релаксационной. Процедуру нахождения такого an обычно оформляют так.
Выбирается число d Î (0, 1) и некоторый начальный шаг a0. Теперь для каждого n полагают an = a0 и делают шаг градиентного метода. Если с таким an условие выполняется, то переходят к следующему n. Если же условие не выполняется, то умножают an на d ("дробят шаг") и повторяют эту процедуру до тех пор пока равенство
|
|
ò |
1 |
|
не будет выполняться. В условиях теоремы об условной сходимости градиентного метода с постоянным шагом эта процедура для каждого n за конечное число шагов приводит к нужному an.
Можно показать, что в условиях теоремы (о линейной сходимости градиентного метода с постоянным щагом) градиентный метод с дроблением шага линейно сходится. Описанный алгоритм избавляет нас от проблемы выбора a на каждом шаге, заменяя ее на проблему выбора параметров e, d и a0, к которым градиентный метод менее чувствителен. При этом, разумеется, объем вычислений возрастает (в связи с необходимостью процедуры дробления шага), впрочем, не очень сильно, поскольку в большинстве задач основные вычислительные затраты ложатся на вычисление градиента.
Метод наискорейшего спуска.
Этот вариант градиентного метода основывается на выборе шага из следующего соображения. Из точки xn будем двигаться в направлении антиградиента до тех пор пока не достигнем минимума функции f на этом направлении, т. е. на луче L = {x Î Rm: x = xn - af ¢(xn); a ³ 0}:
|
an = argminaÎ[0, ¥)f(xn - af ¢(xn)). |
Рис. 1
Другими словами, an выбирается так, чтобы следующая итерация была точкой минимума функции f на луче L (см. рис.1 ). Такой вариант градиентного метода называется методом наискорейшего спуска. Заметим, что в этом методе направления соседних шагов ортогональны. В самом деле, поскольку функция j: a ® f(xn - af ¢(xn)) достигает минимума при a = an, точка an является стационарной точкой функции j:
|
|
= (f ¢(xn - anf ¢(xn)), -f ¢(xn)) = -(f ¢(xn+1), f ¢(xn)). |
Метод наискорейшего спуска требует решения на каждом шаге задачи одномерной оптимизации. Практика показывает, что этот метод часто требует меньшего числа операций, чем градиентный метод с постоянным шагом.
В общей ситуации, тем не менее, теоретическая скорость сходимости метода наискорейшего спуска не выше скорости сходимости градиентного метода с постоянным (оптимальным) шагом.
Семинарская работа Градиентный метод с дроблением шага и метод наискорейшего спуска Выполнил Студент группы МОС-22 Кравченко Александр Градиентный метод с дроблением шага. В этом варианте градиентного метода величин
Закономерность распределения простых чисел в ряду натуральных чисел
Закономерность распределения простых чисел (дополнение)
Алгоритм решения Диофантовых уравнений
Теория вероятности
Переворот на Солнце
Трансплутоновые планеты (пояс Койпера)
Закон Брэгга
Меркурий
Принцип запрета Паули
Предел Чандрасекара
Copyright (c) 2025 Stud-Baza.ru Рефераты, контрольные, курсовые, дипломные работы.