Автореферат (Расслоение и метод квази-Монте-Карло)

На правах рукописи Антонов Антон Александрович Расслоение и метод квази-Монте-Карло 01.01.07 — вычислительная математика Автореферат диссертации иа соискание ученой степени кандидата физико-математических наук Санкт-Петербург — 201б Работа выполнена в Санкт-Петербургском государственном университете. Научный руководитель: Ермаков Сергей Михайлович доктор физико-математических наук, профессор Официальные оппоненты: Войтизпек Антон Вацлавович„ доктор физико-математических наук, профессор, Институт вычислительной математики и математической геофизики Сибирского отделения Российской Академии наук, ведущий научный сотрудник лаборатории стохастических задач Кузнецов Андрей Николаевич, кандидат физико-математических наук, Вологодский государственный университет, доцент кафедры прикладной математики Ведущая организация: Санкт-Петербургский государственный политехнический университет Петра Великою Защита состоится "30" марта 2016 и в 15 час.

00 мин. на заседании диссертационною совета Д 212.232.49 на базе Санкт-Петербургскою юсударственного университета по адресу: 199004, Санкт-Г!етербург, 1О-я линия В.О., д. 33, ауд. 74. С диссертацией можно ознакомиться в Научной библиотеке имени М. Горького Санкт-Петербургского государственного университета по адресу; 199034, Санкт-Петербург, Университетская наб., д. 7!9 и на сайте ййрздлрЬи.тА7меег2lйлегlапгоиог Йгаегрф. 2016 г.. Автореферат разослан " Ученый секретарь диссертационною совета Д 212.232.49, доктор физико-математических наук Ю. В. Чурин Общая характеристика работы Актуальность темы исследования Одной из наиболее распространенных и ключевых задач в вычислительной математике является задача приближенного вычисления определенного интеграла.

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

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

В теории многомерного численного интегрирования ключевым является следующий результат, полученный Бахваловым Н.С. Им установлено, что в размерности я на классе функций С,'"(А), имеющих ограниченные посгоянной А частные производные до порядка т включительно, сходимость любого детерминированного метода не может быть лучше, чем О(АЛ' ''ц') (где Х вЂ” количество вычислений подынтегральной функции).

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

Одним из наиболее известных и универсальных приемов понижения дисперсии является введение зависимости в распределение узлов интегрирования. На этой идее основана теория иитсрпо~пщионно-квадратурных формул со случайными узлами, разработанная Ермаковым С.М. и Золотухиным В.Г.; Ермаковым С.М. и Грановским БГЕ введено понятие допустимости таких процедур на классах функций и исследованы критерии такой допустимости. Частным случаем использования квадратур со случайными узлами является широко известный прием расслоенной выборки (зпабйеб зашр11прк Он заключается в разбиении области интегрирования на несколько подобластей, интегрирование по которым в простейшем случае ведется раздельно.

Бахваловым Н.С. получен еще один важный результат относительно сходимости недетсрминированных методов на классе г,с'(А1, А именно, любой такой метод имеет вероятностный порядок сходимостн не быстрее, чем О(АХ "'"~' Чз) . Для класса Ез оптимальный порядок сходимости вероятностного метода равен О ! =.), то есть даже простейший метод Монте-Карло в этом Ь'.!' случае неулучшасм по порядку. Несмотря на окончательный результат Бахвалова Н.С. относительно широкого класса С,"'(Л),многими исследователями предпринимались попытки получить оценки сходимостн методов интегрирования на других, более узких классах функций. Так, в работах Коробова Н.М. рассматриваются классы Н," и Е',.' и строятся параллелепипедальные сетки, для которых скорость сходимости весьма близка к оптимальной.

Похожих результатов достиг Соболь И.М. на классах Яя функций с быстро убывающими коэффициентами Фурье по системе Хаара. Им построена ЛП,-последовательностзь обеспечивающая на этих классах почти наилучший порядок сходимости. В ряде случаев при использовании Монте-Карло совокупность независимых реализаций случайной величины может быть заменена детерминированной (квазислучайной) структурой и привести к улучшенной сходимости.

Так, в задаче численного интегрирования такая процедура может быть применена для любой интегрируемой по Риману подынтегральной функции, и при этом среднее по первым Ж узлам будет стремиться к истинному значению интеграла при А' — г ж. Такой прием в сочетании со структурами, имеющими определенную асимптотику дискрепапса, получил название метода квази-Монте-Карло. В рамках теории квази-Монте-Карпо последовательность называется 1ов-б1асгерапсу, если аснмптотика ее дискрепанса есть О(ы.,Р ). В этом случае известное неравенство Коксмы-Хлавки обеспечивает скорость сходимости метода порядка О(х,,) для сколь угодно малого положительного е.

ЛП,-последовательность Соболя И.М., являясь !озч-г11асгерапсу последовательностью, обладает еще и тем преимуществом, что для нее известен эффективный последовательный алгоритм Антонова И.А. и Салеева В.М. Одним из принципиальных недостатков метода квази-Монте-Карло является невозможность апостериорного контроля остатка. Это обстоятельство порождает необходимость проводить некоторое количество повторений процедуры с различными независимыми рандомизациями.

Вопрос о достаточном количестве таких повторений не разрешен окончательно. Вероятностные методы получили дальнейшее распространение в ряде других задач, для которых детерминированные алгоритмы оказывались слишком трудоемкими. Так, для внутренней задачи Дирихле для оператора Лапласа, гзи = О в области г' с краевым условием и~ = Л, использование формул Грина 1дп и теоремы о среднем позволяет связать решение в точке с марковским процессом, обрывающимся на гравице области. Этот результат позволяет свести задачу к сферическому процессу (процессу блуждания по сферам), траектории которого моделируются некоторое количсство раз.

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

и многие другие) и обзорных журнальных статей. Теория построения квадратурных формул, обладающих свойством точности для определенных классов функций, подробно описана в монографиях Соболева С.Л., Мысовских И.П. Обзор метода Монте-Карло и известных приемов понижения дисперсии можно найти в книгах Ермакова С.М. и Михайлова ЕА., Ермакова С.М., Кохрана В.Г.

Прием расслоения хорошо известен и подробно изучен, однако дополнительный интерес вызывают свойства распредоленности детерминированных последовательностей, имитирующих расслоение для разбиения на подмножества специального вида. Основы теории интерполяционно-квадратурных формул со случайными узлами изложены в книге Ермакова С.М. Ключевыми в этой области являются работы Ермакова С.М. и Золотухина В.Г,, Хэндскомба Д, Понятие допустимости таких квадратур введено и исследовано Ермаковым С.М. и Грановским Б.Л. Квадратурныс формулы со случайными узлами представляют собой гибкий инструмент для решения сложных задач интегрирования методом Монте-Карло, в связи с чем обнаружение новых и обобщение имеющихся результатов представляет несомненную ценность. В теории метода квази-Монте-Карло в первую очередь необходимо выделить работы Соболя И.М., Холтона Дж., Нидеррейтера Х. Стацдартная вычислительная схема рандомизированного квази-Монте-Карло достаточно хорошо известна, но асимптотика дисперсии метода получена только при наличии существенных ограничений.

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

Для достижения означенной цели необходимо было решить следующие задачи. 1) Использовать аппарат квадратурных формул со случайными узлами для получения класса формул, точных для кусочно-постоянных функций. Обобщить результаты Ермакова С.М. в многомерном случае с использованием обобщенных функций Хаара. 2) Провести анализ дисперсии полученного класса формул и установить согласованность этого результата с оценкой сверху, сформулированной в общем виде Ермаковым С.М, и Золотухиным ВЗЕ 3) Проверить совместимость таких формул с квазислучайными последовательностями, в особенности с последовательностью Соболя. Представить новый метод оценки по~регпности для метода квази-Монте-Карло.