URSS.ru - Издательская группа URSS. Научная и учебная литература
Об издательстве Интернет-магазин Контакты Оптовикам и библиотекам Вакансии Пишите нам
КНИГИ НА РУССКОМ ЯЗЫКЕ


 
Вернуться в: Каталог  
Обложка Сухарев А.Г. Минимаксные алгоритмы в задачах численного анализа
Id: 76798
 
342 руб.

Минимаксные алгоритмы в задачах численного анализа. Изд.2

URSS. 2009. 304 с. Мягкая обложка. ISBN 978-5-397-00230-1.

 Аннотация

В настоящей монографии исследуются вопросы эффективности и оптимальности алгоритмов решения задач численного анализа. Рассмотрение ведется в рамках общей модели, в основу которой положена минимаксная концепция оптимальности вычислительных алгоритмов. При построении оптимальных алгоритмов широко используются теоретико-игровые и другие методы исследования операций и системного анализа.

Для студентов, аспирантов и специалистов в области прикладной математики.


 Оглавление

Предисловие
Список обозначений
Глава 1. Общая модель вычислений
 § 1.Основные понятия
 § 2.О рассматриваемых функциональных классах
 § 3.Классы детерминированных алгоритмов
 § 4.Минимаксная концепция оптимальности вычислительных алгоритмов и конкретные понятия оптимальности
 § 5.Сравнение наилучших гарантированных результатов в классах пассивных и последовательных алгоритмов
 § 6.Последовательно-оптимальные алгоритмы
 § 7.Стохастические алгоритмы
Глава 2. Вычисление интегралов
 § 1.Оптимальные квадратуры для функциональных классов, заданных квазиметриками
 § 2.Построение и исследование оптимальных квадратур для функциональных классов, заданных модулями непрерывности
 § 3.Последовательно-оптимальные и оптимальные на один шаг алгоритмы численного интегрирования
 § 4.Численный эксперимент
 § 5.Оптимальное вычисление повторных интегралов
 § 6.Вычисление кратных интегралов с помощью разверток типа кривой Пеано
Глава 3. Восстановление функций по их значениям
 § 1.Оптимальные пассивные алгоритмы
 § 2.Последовательно-оптимальные и оптимальные на один шаг алгоритмы восстановления функций
 § 3.Решение многошаговой антагонистической игры, связанной с задачей оптимального восстановления
Глава 4. Поиск глобального экстремума
 § 1.О выборе начальных точек для методов локальной оптимизации
 § 2.Оптимальный пассивный поиск для функционального класса, заданного квазиметрикой
 § 3.Сведение задачи построения последовательно-оптимального алгоритма для функционального класса, заданного квазиметрикой, к серии задач оптимального покрытия
 § 4.Конкретные вычислительные алгоритмы
 § 5.Учет погрешности вычислений
 § 6.Оптимальный на один шаг стохастический алгоритм
Глава 5. Некоторые специальные классы экстремальных задач
 § 1.Решение уравнений и систем уравнений
 § 2.Отыскание максимума функции минимума при связанных переменных
 § 3.Многокритериальные задачи оптимизации
Список литературы
Предметный указатель

 Предисловие

Посвящается
памяти моей матери
Александры Ильиничны Сухаревой
и моего отца
Григория Михайловича Сухарева

Вопросы эффективности численных методов, выбора наиболее эффективных методов для решения данной задачи или данного класса задач всегда занимали важное место в численном анализе. И в настоящее время оптимизация вычислительного процесса решения задач на ЭВМ является актуальной проблемой вычислительной математики, проблемой, которая стимулирует поиск новых численных методов и способов их реализации.

В предлагаемой книге для различных задач численного анализа изучаются способы оценки эффективности вычислительных алгоритмов и вопросы их оптимальности в рамках общей модели вычислений. Основными элементами общей модели, определяющими конкретные модели вычислений, являются: приближаемый функционал или оператор, соответствующий решаемой задаче; класс функций, с помощью которого описывается информация вычислителя о задаче; класс алгоритмов решения задачи, находящихся в распоряжении вычислителя; критерий оценки эффективности алгоритмов; концепция оптимальности; и, наконец, конкретное понятие оптимальности алгоритма в рамках принятой концепции. Использование общей модели вычислений позволяет дать единую трактовку различных задач численного анализа, ответить на ряд принципиальных методологических вопросов и установить общие свойства оптимальных алгоритмов.

В основу всех рассматриваемых в книге конкретных реализаций общей модели вычислений положена минимаксная концепция оптимальности, которую использовал в задачах вычислительной математики еще П.Л.Чебышев. Эта концепция отражает стремление вычислителя к получению наилучшего гарантированного результата (например, точности решения) относительно находящейся в распоряжении вычислителя информации о задаче.

Оптимальным алгоритмам решения задач численного анализа посвящена достаточно обширная журнальная литература. Имеются также несколько монографий, где наряду с рассмотрением конкретных задач закладываются основы общей теории оптимальных алгоритмов.

Тематика данной книги существенно отличается от традиционной тематики оптимальных численных методов, что выражается прежде всего в углубленном внимании к последовательным (адаптивным) вычислительным алгоритмам. При этом процесс вычислений рассматривается как управляемый процесс, а сам алгоритм -- как стратегия управления. Такой подход позволяет при построении оптимальных алгоритмов широко использовать теоретико-игровые и другие методы исследования операций и системного анализа. Использование этих методов оказывается плодотворным и позволяет получить целый ряд результатов, относящихся как к традиционным, так и к новым понятиям оптимальности.

Конечной целью исследования различных изучаемых в книге моделей вычислений является построение конкретного вычислительного алгоритма, допускающего программную реализацию. Центральное место занимает понятие последовательно-оптимального алгоритма, отражающее во многих случаях особенности организации реальных вычислительных процессов полнее, чем традиционные понятия оптимальности. Разработана общая схема построения последовательно-оптимальных алгоритмов. Сформулированы требования к модели вычислений, обеспечивающие возможность применения этой схемы для ряда задач численного анализа.

Книга состоит из пяти глав. Первая глава стоит особняком от остальных четырех. В ней вводится необходимая терминология, строится общая модель вычислений, подробно обсуждаются возникающие при этом методологические вопросы. Следует подчеркнуть, что относящуюся к оптимальным алгоритмам терминологию нельзя считать полностью установившейся. Так, вводимый в  гл.1 термин "итоговая операция алгоритма" соответствует термину "алгоритм" монографии Дж.Трауба, X. Вожьняковского (см. список литературы). Полученные в первой главе результаты неоднократно используются в дальнейшем. Она, таким образом, носит в известной степени вводный характер.

Последующие главы посвящены построению оптимальных методов решения конкретных задач численного анализа. В книге рассматриваются задачи вычисления интегралов, восстановления функций по их значениям, поиска глобального экстремума, решения уравнений и систем уравнений, отыскания максимина и многокритериальные задачи оптимизации. Разумеется, каждая задача исследуется в рамках конкретных, порою довольно ограничительных, предположений о функциональных классах и классах алгоритмов, о критериях оценки эффективности алгоритмов и используемых понятиях оптимальности, т.е. в рамках конкретной модели вычислений. Выбор в книге конкретных моделей определяется желанием наиболее полно продемонстрировать возможности, заложенные в общей модели, а также стремлением полнее учесть особенности реальных задач. Некоторые результаты, тесно связанные с тематикой книги (например, результаты по оптимальному поиску экстремума унимодальных функций), не вошли в нее лишь потому, что они уже неоднократно излагались и в монографиях, и в учебной литературе.

Список литературы достаточно обширен и включает многие работы, на которые нет непосредственных ссылок в тексте книги. В них либо изучаются те или иные вопросы оптимальности или оценки эффективности численных методов, либо эти работы тесно связаны с рассматриваемыми в книге конкретными задачами численного анализа. В то же время в список литературы в целях экономии места не вошел ряд имеющих непосредственное отношение к тематике книги работ из аннотированной библиографии к монографии Дж.Трауба, X. Вожьняковского.

Несколько слов о нумерации теорем, лемм и формул. В пределах каждой главы принята двойная нумерация: первое число указывает номер параграфа, второе -- номер соответствующей теоремы, леммы или формулы. При ссылках в пределах данной главы указываются только эти два номера. В противном случае к ним добавляется номер главы, например: теорема 5.3 гл.1, формула (3.4) гл.2.

Автор глубоко признателен всему коллективу кафедры исследования операций факультета вычислительной математики и кибернетики МГУ, творческая атмосфера которого имела огромное значение для создания этой книги.


 Об авторе

Алексей Григорьевич СУХАРЕВ

Доктор физико-математических наук, профессор. В 1971--1994 гг. работал в МГУ им. М. В. Ломоносова, преподавал на факультете вычислительной математики и кибернетики, заведовал лабораторией НИВЦ МГУ.

В начале 1990-х гг. основал компанию "Auriga" и руководит ею по сегодняшний день. "Auriga" входит в общемировые списки "Global Services 100" и "Global Outsourcing 100" ведущих провайдеров услуг в области информационных технологий, десятку ведущих компаний Центральной и Восточной Европы, и является старейшей в России компанией в этой области.

Опыт ученого, преподавателя, предпринимателя, накопленный А. Г. Сухаревым, нашел отражение в более чем 100 научных работах, в том числе 10 монографиях, учебниках и учебных пособиях, многие из которых опубликованы за рубежом, а также в ряде статей, посвященных индустрии информационных технологий, в ведущих деловых изданиях России, США и Индии.

 
© URSS 2016.

Информация о Продавце