|
Метод сопряженных градиентов ⇐ ПредыдущаяСтр 7 из 7 Метод предназначен для решения задачи (5.1) и принадлежит классу методов первого порядка. Метод представляет собой модификацию метода наискорейшего спуска (подъема) и автоматически учитывает особенности целевой функции, ускоряя сходимость.
Описание алгоритма Шаг 0. Выбирается точка начального приближения Шаг k. На k -м шаге находится минимум (максимум) целевой функции
Формула (5.4) может быть переписана в эквивалентном виде
Алгоритм завершает свою работу, как только выполнится условие
Метод Ньютона Метод предназначен для решения задачи (5.1) и принадлежит классу методов второго порядка. В основе метода лежит разложение Тейлора целевой функции Действительно, пусть некоторая точка
Формулу (5.5) перепишем в матричной форме, учитывая при этом, что
где Предположим, что матрица Гессе
Формула (5.7) определяет алгоритм метода Ньютона: пересчет приближений на k -й итерации выполняется в соответствии с формулой
Алгоритм заканчивает свою работу, как только выполнится условие
где
Метод Ньютона-Рафсона Метод является методом первого порядка и предназначен для решения систем n нелинейных уравнений c n неизвестными:
В частности, этот метод может быть применен при поиске стационарных точек целевой функции задачи (5.1), когда необходимо решить систему уравнений из условия Пусть точка
откуда (по условию
где
Формула (5.12) определяет алгоритм метода Ньютона-Рафсона: пересчет приближений на k -й итерации выполняется в соответствии с формулой
В случае одной переменной, когда система (5.9) вырождается в единственное уравнение
где На рис. 5.2 показана схема реализации метода Ньютона-Рафсона при поиске решения уравнения
Рис. 5.2
Замечание 5.1. Сходимость численных методов, как правило, сильно зависит от начального приближения. Замечание 5.2. Методы Ньютона и Ньютона-Рафсона требуют большого объема вычислений (надо на каждом шаге вычислять и обращать матрицы Гессе и Якоби). Замечание 5.3. При использовании методов обязательно следует учитывать возможность наличия многих экстремумов у целевой функции (свойство мультимодальности).
ЛИТЕРАТУРА
1. Афанасьев М.Ю., Суворов Б.П. Исследование операций в экономике: Учебное пособие. – М.: Экономический факультет МГУ, ТЕИС, 2003 – 312 с. 2. Базара М, Шетти К. Нелинейное программирование. Теория и алгоритмы: Пер. с англ. – М.: Мир, 1982 – 583 с. 3. Берман Г. Н. Сборник задач по курсу математического анализа: Учебное пособие для вузов. – СПб: «Специальная Литература», 1998. – 446 с. 4. Вагнер Г. Основы исследования операций: В 3-х томах. Пер. с англ. – М.: Мир, 1972. – 336 с. 5. Вентцель Е. С. Исследование операций. Задачи, принципы, методология – М.: Наука, 1988. – 208 с. 6. Демидович Б.П. Сборник задач и упражнений по математическому анализу. – М.: Наука, 1977. – 528 с. 7. Дегтярев Ю.И. Исследование операций. – М.: Высш. шк., 1986. – 320 с. 8. Нуреев Р.М. Сборник задач по микроэкономике. – М.: НОРМА, 2006. – 432 с. 9. Солодовников А. С., Бабайцев В.А., Браилов А.В. Математика в экономике: Учебник: В 2-х ч. – М.:Финансы и статистика, 1999. – 224 с. 10. Таха Х. Введение в исследование операций, 6-е изд.: Пер. с англ. – М.: Издательский дом «Вильямс», 2001. – 912 с. 11. Химмельблау Д. Прикладное нелинейное программирование: Пер. с англ. – М.: Мир, 1975 – 534 с. 12. Шикин Е. В., Шикина Г.Е. Исследование операций: Учебник – М.: ТК Велби, Изд-во Проспект, 2006. – 280 с. 13. Исследование операций в экономике: Учебн. пособие для вузов/ Н.Ш.Кремер, Б.А.Путко, И.М.Тришин, М.Н.Фридман; Под ред. проф. Н.Ш.Кремера. – М.: Банки и биржи, ЮНИТИ, 1997. – 407 с. 14. Матрицы и векторы: Учебн. пособие/ Рюмкин В.И. – Томск: ТГУ, 1999. – 40 с. 15. Системы линейных уравнений: Учебн. пособие / Рюмкин В.И. – Томск: ТГУ, 2000. – 45 с.
ОГЛАВЛЕНИЕ
[1] Определения линейной и нелинейной функций см. в разделе 1.2 [2] Крейсерской скоростью называется скорость, при которой расход топлива на единицу пути минимален. [3] Выражение (5.1) означает «найти максимум (и (или) минимум) функции». ![]() ![]() ЧТО ТАКОЕ УВЕРЕННОЕ ПОВЕДЕНИЕ В МЕЖЛИЧНОСТНЫХ ОТНОШЕНИЯХ? Исторически существует три основных модели различий, существующих между... ![]() Конфликты в семейной жизни. Как это изменить? Редкий брак и взаимоотношения существуют без конфликтов и напряженности. Через это проходят все... ![]() ЧТО И КАК ПИСАЛИ О МОДЕ В ЖУРНАЛАХ НАЧАЛА XX ВЕКА Первый номер журнала «Аполлон» за 1909 г. начинался, по сути, с программного заявления редакции журнала... ![]() Что делает отдел по эксплуатации и сопровождению ИС? Отвечает за сохранность данных (расписания копирования, копирование и пр.)... Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:
|