Метод сопряженных градиентов
- Метод сопряженных градиентов
-
Метод сопряженных градиентов — метод нахождения локального минимума функции на основе информации о её значениях и её градиенте. В случае квадратичной функции в минимум находится за n шагов.
Основные понятия
Определим терминологию:
Пусть .
Введём на целевую функцию .
Вектора называются сопряжёнными, если:
где — матрица Гессе .
|
Теорема (о существовании).
Существует хотя бы одна система сопряжённых направлений для матрицы , т.к. сама матрица (её собственные вектора) представляет собой такую систему. |
|
Обоснование метода
Нулевая итерация
Иллюстрация последовательных приближений метода сопряжённых градиентов к точке
экстремума. Картинка наглядно показывает, что каждое последующее сопряжённое направление перпендикулярно предыдущему.
Пусть
Тогда .
Определим направление так, чтобы оно было сопряжено с :
Разложим в окрестности и подставим :
Транспонируем полученное выражение и домножаем на справа:
В силу непрерывности вторых частных производных . Тогда:
Подставим полученное выражение в (3):
Тогда, воспользовавшись (1) и (2):
Если , то градиент в точке перпендикулярен градиенту в точке , тогда по правилам скалярного произведения векторов:
Приняв во внимание последнее, получим из выражения (4) окончательную формулу для вычисления :
К-я итерация
На k-й итерации имеем набор.
Тогда следующее направление вычисляется по формуле:
где непосредственно рассчитывается на k-й итерации, а все остальные уже были рассчитаны на предыдущих.
Это выражение может быть переписано в более удобном итеративном виде:
Алгоритм
- Пусть — начальная точка, — направление антиградиента и мы пытаемся найти минимум функции . Положим и найдем минимум вдоль направления . Обозначим точку минимума .
- Пусть на некотором шаге мы находимся в точке , и — направление антиградиента. Положим , где выбирают либо (стандартный алгоритм), либо (алгоритм Полака–Райбера). После чего найдем минимум в направлении и обозначим точку минимума . Если в вычисленном направлении функция не уменьшается, то нужно забыть предыдущее направление, положив и повторив шаг.
Формализация
- Задаются начальным приближением и погрешностью:
- Рассчитывают начальное направление:
-
- Если или , то и останов.
- Иначе
- если , то и переход к 3;
- иначе и переход к 2.
Случай квадратичной функции
|
Теорема.
Если сопряжённые направления используются для поиска минимума квадратичной функции, то эта функция может быть минимизирована за n шагов, по одному в каждом направлении, причём порядок несущественен. |
|
Литература
- Акулич И.Л. Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. спец. вузов. — М.: Высш. шк., 1986.
- Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. Пер. с англ. — М.: Мир, 1985.
- Коршунов Ю.М., Коршунов Ю.М. Математические основы кибернетики. — М.: Энергоатомиздат, 1972.
- Максимов Ю.А.,Филлиповская Е.А. Алгоритмы решения задач нелинейного программирования. — М.: МИФИ, 1982.
- Максимов Ю.А. Алгоритмы линейного и дискретного программирования. — М.: МИФИ, 1980.
- Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. — М.: Наука, 1970. — С. 575-576.
См. также
Градиентные методы:
Ссылки
Поиск глобального оптимума для задач оптимального проектирования систем или определения оптимальных законов управления.
Wikimedia Foundation.
2010.
Полезное
Смотреть что такое "Метод сопряженных градиентов" в других словарях:
СОПРЯЖЕННЫХ ГРАДИЕНТОВ МЕТОД — метод решения системы линейных алгебраич. уравнений Ах=b с положительно определенной матрицей А. Это прямой и итерационный метод одновременно: при любом начальном приближении он сходится за конечное число итераций, давая точное решение. В С. г. м … Математическая энциклопедия
Метод сопряжённых градиентов — Метод сопряженных градиентов метод нахождения локального минимума функции на основе информации о её значениях и её градиенте. В случае квадратичной функции в минимум находится за шагов. Содержание 1 Основные понятия … Википедия
Метод сопряжённых направлений — Метод сопряженных градиентов метод нахождения локального минимума функции на основе информации о её значениях и её градиенте. В случае квадратичной функции в минимум находится за n шагов. Содержание 1 Основные понятия 2 Обосновани … Википедия
Метод покоординатного спуска — Содержание 1 Постановка задачи решения системы уравнений в терминах методов оптимизации 2 Градиентные методы … Википедия
ТЯЖЕЛОГО ШАРИКА МЕТОД — метод решения задачи минимизации дифференцируемой функции f(x)на евклидовом пространстве Е п. Метод основан на рассмотрении системы дифференциальных уравнений к рая описывает движение материальной точки по поверхности y=f(x)в поле тяжести,… … Математическая энциклопедия
ЧЕБЫШЕВСКИЙ ИТЕРАЦИОННЫЙ МЕТОД — итерационный алгоритм нахождения решения линейного уравнения учитывающий информацию о принадлежности Sр(A) спектра оператора А нек рому множеству и использующий свойства и параметры многочленов, наименее отклоняющихся от нуля на множестве и… … Математическая энциклопедия
Система уравнений и экстремальные задачи. Градиентные методы. — Система уравнений и экстремальные задачи. Градиентные методы. Содержание 1 Постановка задачи решения системы уравнений в терминах методов оптимизации … Википедия
Градиентные методы — численные методы решения с помощью градиента задач, сводящихся к нахождению экстремумов функции. Содержание 1 Постановка задачи решения системы уравнений в терминах методов о … Википедия
НЕЛИНЕЙНОЕ УРАВНЕНИЕ — численные методы решения итерационные методы решения нелинейных уравнений. Под нелинейными уравнениями понимаются (см. [1] [3]) алгебраические и трансцендентные уравнения вида где х действительное число, нелинейная функция, а под системой… … Математическая энциклопедия
МАКСИМИЗАЦИЯ И МИНИМИЗАЦИЯ ФУНКЦИЙ — конечного числа переменных задача поиска экстремума функции под этой задачей понимается: 1) нахождение 2) отыскание точек максимума или минимума, если достигаются на допустимом множестве (см. Максимум и минимум функции). 3) построение… … Математическая энциклопедия