Метод покоординатного спуска | это... Что такое Метод покоординатного спуска? (original) (raw)
Метод покоординатного спуска
Метод покоординатного спуска
Содержание
- 1 Постановка задачи решения системы уравнений в терминах методов оптимизации
- 2 Градиентные методы
- 3 Литература
- 4 Ссылки
- 5 Внешние ссылки
- 6 См. также
Постановка задачи решения системы уравнений в терминах методов оптимизации
Задача решения системы уравнений:
(1)
с n эквивалентна задаче минимизации функции
(2)
или какой-либо другой возрастающей функции от абсолютных величин | f i | невязок (ошибок) , . Задача отыскания минимума (или максимума) функции n переменных и сама по себе имеет большое практическое значение.
Для решения этой задачи итерационными методами начинают с произвольных значений и строят последовательные приближения:
или покоординатно:
(3)
которые сходятся к некоторому решению при .
Различные методы отличаются выбором «направления» для очередного шага, т.е. выбором отношений
.
Величина шага (расстояние, на которое надо передвинуться в заданном направлении в поисках экстремума) определяется значением параметра λ[_j_], минимизирующим величину как функцию от λ[_j_]. Эту функцию обычно аппроксимируют её тейлоровским разложением или интерполяционным многочленом по трем-пяти выбранным значениям λ[_j_]. Последний метод применим для отыскания max и min таблично заданной функции F(_x_1,_x_2,...,x n).
Градиентные методы
Основная идея методов заключается в том, чтобы идти в направлении наискорейшего спуска, а это направление задаётся антиградиентом :
где λ[_j_] выбирается
- постоянной, в этом случае метод может расходиться;
- дробным шагом, т.е. длина шага в процессе спуска делится на некое число;
- наискорейшим спуском:
Метод наискорейшего спуска (метод градиента)
Выбирают , где все производные вычисляются при , и уменьшают длину шага λ[_j_] по мере приближения к минимуму функции F.
Для аналитических функций F и малых значений f i тейлоровское разложение F(λ[j]) позволяет выбрать оптимальную величину шага
(5)
где все производные вычисляются при . Параболическая интерполяция функции F(λ[_j_]) может оказаться более удобной.
Алгоритм
- Задаются начальное приближение и точность расчёта
- Рассчитывают , где
- Проверяют условие останова:
Метод покоординатного спуска (Гаусса—Зейделя)
Улучшает предыдущий метод за счёт того, что на очередной итерации спуск осуществляется постепенно вдоль каждой из координат, однако теперь необходимо вычислять новые раз за один шаг.
Алгоритм
- Задаются начальное приближение и точность расчёта
- Рассчитывают , где
- Проверяют условие останова:
Метод сопряжённых градиентов
Метод сопряженных градиентов основывается на понятиях прямого метода многомерной оптимизации — метода сопряжённых направлений.
Применение метода к квадратичным функциям в определяет минимум за n шагов.
Алгоритм
- Задаются начальным приближением и погрешностью:
- Рассчитывают начальное направление:
Литература
- Акулич И.Л. Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. спец. вузов. — М.: Высш. шк., 1986.
- Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. Пер. с англ. — М.: Мир, 1985.
- Коршунов Ю.М., Коршунов Ю.М. Математические основы кибернетики. — М.: Энергоатомиздат, 1972.
- Максимов Ю.А.,Филлиповская Е.А. Алгоритмы решения задач нелинейного программирования. — М.: МИФИ, 1982.
- Максимов Ю.А. Алгоритмы линейного и дискретного программирования. — М.: МИФИ, 1980.
- Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. — М.: Наука, 1970. — С. 575-576.
Ссылки
- Интерполяционные формулы
- Математическое программирование
- Метод градиента
- Метод сопряжённых градиентов
- Прямые методы
- Формула Тейлора
Внешние ссылки
См. также
Wikimedia Foundation.2010.
Полезное
Смотреть что такое "Метод покоординатного спуска" в других словарях:
- Метод градиентного спуска — Градиентный спуск метод нахождения локального минимума (максимума) функции с помощью движения вдоль градиента. Для минимизации функции в направлении градиента используются методы одномерной оптимизации, например, метод золотого сечения. Также… … Википедия
- Метод наискорейшего спуска — Градиентный спуск метод нахождения локального минимума (максимума) функции с помощью движения вдоль градиента. Для минимизации функции в направлении градиента используются методы одномерной оптимизации, например, метод золотого сечения. Также… … Википедия
- ПОКООРДИНАТНОГО СПУСКА МЕТОД — один из методов минимизации функций многих переменных, использующий лишь значения минимизируемой функции. П. с. м. применяется в тех случаях, когда минимизируемая функция недифференцируема или вычисление ее производных требует большого объема… … Математическая энциклопедия
- Метод Гаусса — Зейделя — У этого термина существуют и другие значения, см. метод покоординатного спуска. Метод Гаусса Зейделя[1] является классическим итерационным методом решения системы линейных уравнений. Содержание 1 Постановка задачи 2 Метод … Википедия
- Метод Нелдера — Мида — Последовательные симплексы в методе Нелдера Мида для функции Розенброка (англ.) (вв … Википедия
- Метод Гаусса-Зейделя — Метод Гаусса Зейделя[1] является классическим итерационным методом решения системы линейных уравнений. Содержание 1 Постановка задачи 2 Метод 3 Условие сходимости … Википедия
- Метод Гаусса—Зейделя — Метод Гаусса Зейделя[1] является классическим итерационным методом решения системы линейных уравнений. Содержание 1 Постановка задачи 2 Метод 3 Условие сходимости … Википедия
- Метод Зейделя — Метод Гаусса Зейделя[1] является классическим итерационным методом решения системы линейных уравнений. Содержание 1 Постановка задачи 2 Метод 3 Условие сходимости … Википедия
- Метод сопряженных градиентов — метод нахождения локального минимума функции на основе информации о её значениях и её градиенте. В случае квадратичной функции в минимум находится за n шагов. Содержание 1 Основные понятия 2 Обосновани … Википедия
- Метод сопряжённых направлений — Метод сопряженных градиентов метод нахождения локального минимума функции на основе информации о её значениях и её градиенте. В случае квадратичной функции в минимум находится за n шагов. Содержание 1 Основные понятия 2 Обосновани … Википедия