ОПТИМИЗАЦИЯ ПСЕВДООБРАЩЕНИЕ ИТЕРАЦИИ И РЕКУРСИИ УЧЕБНОЕ ПОСОБИЕ Липецк Липецкий государственный технический университет 2015 Министерство образования и науки Российский Федерации Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Липецкий государственный технический университет» ОПТИМИЗАЦИЯ ПСЕВДООБРАЩЕНИЕ ИТЕРАЦИИ И РЕКУРСИИ Учебное пособие Липецк Липецкий государственный технический университет 2015 УДК 519.863 П433 Авторы: А.К. Погодаев, С.Л. Блюмин, С.П. Миловидов, А.С. Сысоев Рецензенты: кафедра «Информационные системы и защита информации» Тамбовского государственного технического университета (зав. кафедрой д-р техн. наук, проф. <...> ); Рубан А.И., д-р техн. наук, проф., заслуженный деятель науки РФ, зав. кафедрой информатики Института космических и информационных технологий Сибирского федерального университета Погодаев, А. <...> ISBN 978-5-88247-741-6 В пособии систематически описаны элементы теории математического программирования, определение, примеры, свойства и алгоритмы псевдообращения, а также постановка и решение нелинейной задачи о наименьших квадратах, что приводит к рекуррентноитерационным алгоритмам. <...> Пример численного решения задачи многомерной нелинейной оптимизации. <...> Системы линейных уравнений и метод наименьших квадратов . <...> Название пособия как бы разделяет его на три основные части: введение в понятия оптимизации, понятие и алгоритмы псевдообращения матриц и рекуррентно-итерационные процедуры решения задач о наименьших квадратах. <...> Она начинается с постановки задачи оптимизации и подробно расcматривает решение её в линейном виде (задача линейного программирования). <...> Переход к задаче нелинейного программирования (нелинейной оптимизации) показывает, что линейная задача является частным случаем нелинейной. <...> Основные теоремы доказываются с помощью теоремы Куна-Таккера. <...> Решение одной из практических задач – поиска оптимального <...>
Оптимизация._Псевдообращение._Итерации_и_рекурсии.pdf
УДК 519.863
П433
Авторы: А.К. Погодаев, С.Л. Блюмин, С.П. Миловидов, А.С. Сысоев
Рецензенты: кафедра «Информационные системы и защита информации»
Тамбовского государственного технического университета
(зав. кафедрой д-р техн. наук, проф. Громов Ю.Ю.);
Рубан А.И., д-р техн. наук, проф., заслуженный деятель науки РФ,
зав. кафедрой информатики Института космических и информационных технологий
Сибирского федерального университета
Погодаев, А.К.
П433 Оптимизация. Псевдообращение. Итерации и рекурсии [Текст]: учебное пособие /
А.К. Погодаев, С.Л. Блюмин, С.П. Миловидов, А.С. Сысоев. – Липецк: Изд-во
Липецкого государственного технического университета, 2015. – 193 с.
ISBN 978-5-88247-741-6
В пособии систематически описаны элементы теории математического программирования,
определение, примеры, свойства и алгоритмы псевдообращения, а также постановка
и решение нелинейной задачи о наименьших квадратах, что приводит к рекуррентноитерационным
алгоритмам. Предназначено для студентов направлений, получающих углублённую
математическую подготовку, и связано с решением широкого круга задач. Включённый
в пособие материал будет полезен также инженерам, аспирантам, научным работникам,
применяющим в расчётах математические методы; для них пособие может служить
и в качестве справочника. В доступной для начинающих форме изложены важнейшие,
наиболее часто используемые определения, свойства и примеры задач оптимизации,
удобные в вычислительном отношении, пригодные для непосредственной реализации алгоритмы.
Рекомендовано
УМС ЛГТУ в качестве учебного пособия для бакалавров, обучающихся
по направлению подготовки ВПО 01.03.04 «Прикладная математика», магистров
по направлениям 01.04.04 «Прикладная математика», 09.04.01 «Информатика
и вычислительная техника».
УДК 519.863
П433
ISBN 978-5-88247-741-6
○ ФГБОУ ВПО «Липецкий государственный технический
университет», 2015
○ Погодаев А.К., Блюмин С.Л., Миловидов С.П.,
Сысоев А.С., 2015
c
c
Стр.3
Оглавление
Введение. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
Глава I. Основы оптимизации . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
§ 1. Задачи математического программирования . . . . . . . . . . . . . . . . . . . . . . 7
§ 2. Безусловная оптимизация. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
§ 3. Классическая задача математического программирования. . . . . . . . 19
§ 4. Нелинейное программирование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
§ 5. Пример численного решения задачи многомерной нелинейной
оптимизации. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
Глава II. Алгоритмы псевдообращения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
§ 6. Определение псевдообратной матрицы. . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
§ 7. Свойства псевдообратных матриц. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
§ 8. Рекуррентные алгоритмы псевдообращения . . . . . . . . . . . . . . . . . . . . . . 79
§ 9. Примеры нахождения псевдообратных матриц . . . . . . . . . . . . . . . . . . . 81
§ 10.Системы линейных уравнений и метод наименьших квадратов . . 89
Глава III. Итерации и рекурсии. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
§ 11.Общая классификация алгоритмов оптимизации . . . . . . . . . . . . . . . . . 113
§ 12.Нелинейная оптимизация: итерационные процедуры . . . . . . . . . . . . . 123
§ 13.Линейный метод наименьших квадратов:
рекуррентные процедуры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
§ 14.Нелинейный метод наименьших квадратов:
рекуррентно-итерационные процедуры . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
Задания и упражнения. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
Заключение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178
Библиографический список. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180
3
Стр.4
Введение
Многие практические задачи различных сфер человеческой деятельности
связаны с проблемами определения наилучшего, оптимального варианта
решения. Таковы, например, задачи выбора оптимальной производственной
программы предприятия, задача оптимального распределения ресурсов,
транспортные задачи и так далее. Для решения задач такого рода в математической
науке созданы и стремительно развиваются оптимизационные
процедуры. Существует огромное количество работ, посвящённых различным
сторонам математического программирования и теории оптимизации,
прикладным аспектам, методам численного решения. Изучение методов оптимизации
становится необходимым для практической работы специалиста
любой области – будь то экономика или техника.
Название пособия как бы разделяет его на три основные части: введение
в понятия оптимизации, понятие и алгоритмы псевдообращения матриц
и рекуррентно-итерационные процедуры решения задач о наименьших квадратах.
В
первой главе отражается стремление дать читателю развернутое, чёткое
и логически связанное представление об основных понятиях теории оптимизации.
Она начинается с постановки задачи оптимизации и подробно расcматривает
решение её в линейном виде (задача линейного программирования).
Излагаются известные классические методы отыскивания экстремумов
дифференцируемых функций. Переход к задаче нелинейного программирования
(нелинейной оптимизации) показывает, что линейная задача является
частным случаем нелинейной. Основные теоремы доказываются с помощью
теоремы Куна-Таккера. Усвоение материала облегчается последовательным
применением множителей Лагранжа и их содержательной интерпретацией.
4
Стр.5