Автореферат (Бессеточные методы Монте-Карло решения краевых задач для уравнений в частных производных)

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТНа правах рукописиСИПИН Александр СтепановичБЕССЕТОЧНЫЕ МЕТОДЫ МОНТЕ-КАРЛО РЕШЕНИЯКРАЕВЫХ ЗАДАЧ ДЛЯ УРАВНЕНИЙ В ЧАСТНЫХПРОИЗВОДНЫХ01.01.07 — вычислительная математикаАВТОРЕФЕРАТдиссертации на соискание учёной степенидоктора физико-математических наукСанкт-Петербург — 2016Работа выполнена в Вологодском государственном университетеНаучный консультант:доктор физико-математических наук,профессор ЕРМАКОВ Сергей МихайловичОфициальные оппоненты: доктор физико-математических наук, профессор БЕЛОПОЛЬСКАЯ Яна Исаевна(Санкт-Петербургскийгосударственныйархитектурно-строительныйуниверситет,профессор кафедры математики)доктор физико-математических наук, профессор САБЕЛЬФЕЛЬД Карл Карлович (Институт вычислительной математики и математической геофизики СО РАН, главный научныйсотрудник лаборатории стохастических задач)доктор физико-математических наук, доцентХАЗАНОВ Владимир Борисович (СанктПетербургскийгосударственныйморскойтехнический университет, профессор кафедрыприкладной математики и математическогомоделирования)Ведущая организация:Московский государственный университет имени М.

В. Ломоносова (факультет вычислительной математики и кибернетики)Защита состоится « »2016 г. вчасов на заседаниидиссертационного совета Д212.232.49 на базе Санкт-Петербургского государственного университета по адресу: 199004, Санкт-Петербург, 10-я линия, д.33, ауд. 74.С диссертацией можно ознакомиться в Научной библиотеке им. М. Горького Санкт-Петербургского государственного университета по адресу: 199034,Санкт-Петербург, Университетская наб., 7/9 и на сайте:http://spbu.ru/disser2/disser/sipin_alexandr_diss.pdfАвтореферат разослан « »Учёный секретарьдиссертационного советадоктор физико-математических наук2016 г.Чурин Ю.

В.Общая характеристика работыАктуальность темыКраевые задачи для уравнений в частных производных являются математическими моделями многих реальных процессов, изучаемых в естественныхи технических науках. Численные методы решения краевых задач разнообразны и интенсивно развиваются. Наряду с методом конечных разностей, вариационными и проекционными методами для решения краевых задач успешно применяются и методы Монте-Карло (методы статистического моделирования).

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

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

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

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

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

Статистические оценки строятся на траекториях блуждания по сетке иявляются несмещенными для сеточной функции. По отношению к решениюдифференциального уравнения статистические оценки имеют смещение равное погрешности разностной схемы.Ко второй группе относятся методы, основанные на представлении решений краевых задач в виде математического ожидания функционала от траектории диффузионного случайного процесса [3], производящим операторомкоторого является дифференциальный оператор краевой задачи. Для получения статистических оценок используются приближения случайного процесса, найденные путем решения стохастического дифференциального уравнения разностными методами.

Наиболее развитый метод такого типа носит название многосеточный метод Монте-Карло (Multilevel Monte CarloMethod, [4, 5]). Получаемые при этом оценки являются смещенными. Величина смещения или ее порядок по шагу разностной схемы оцениваются. Внастоящее время такие методы интенсивно развиваются, так как позволяют решать краевые задачи для уравнений с переменными коэффициентами,встречающиеся в финансовой математике.К третьей группе относятся бессеточные методы, которые связаны с построением статистических оценок на траекториях цепей Маркова с дискретным временем и непрерывным фазовым пространством.

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

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

Схема Неймана-Улама также тесно связана с вероятностной теорией потенциала , что позволяет эффективно использовать теорию мартингалов для исследования случайных блужданий и несмещенных оценок решенийкраевых задач на траекториях этих блужданий.Если интегральное уравнение получено из теоремы о среднем значении, тосоответствующее блуждание происходит внутри области. Первым и наиболееизвестным алгоритмом такого типа является алгоритм блуждания по сферам [6], решающий задачу Дирихле для уравнения Пуассона в ограниченнойобласти.

Алгоритм прост в реализации и достаточно эффективен. Он основанна интегральном представлении решения уравнения Пуассона в центре шарас помощью функции Грина. Во второй половине XX века алгоритмы блужданий внутри области были построены для уравнений второго порядка, главнойчастью которых является оператор Лапласа. Исследования в этом направлении интенсивно велись в Ленинградском государственном университете (подруководством С.М.Ермакова), в Новосибирском государственном университете (под руководством Г.А.Михайлова), в Болгарии (I.Dimov), в Германии(K.K.Sabelfeld, W.Wagner), в США (M.Mascagni).

Результаты исследованийотражены в монографиях [8, 11, A2, A3].Если интегральное уравнение получается на основе уравнений теории потенциала, то говорят об алгоритмах случайного блуждания по границе. Повидимому, впервые такой алгоритм был применен для решения задачи Неймана [A16] в выпуклой области. Несмещенные статистические оценки длярешения задачи были построены на траекториях блуждания по границе области, каждая следующая точка которого видна из предыдущей в случайном направлении, определяемом изотропным вектором в полупространстве.Плотность (по отношению к мере Лебега на поверхности) вероятности перехода за один шаг в таком блуждании является ядром Гаусса (для телесногоугла), что естественным образом связывает процесс блуждания с уравнениями теории потенциала.

Алгоритмы решения уравнений теории потенциа5ла для оператора Лапласа и оператора теплопроводности были разработаныО.Курбанмурадовым, К.К.Сабельфельдом и Н.А.Симоновым [10].Бессеточные алгоритмы построены для многих практически важных краевых задач.Цели работыВ данной работе рассматриваются методы построения несмещенных и малосмещенных оценок решений краевых задач для эллиптических и параболических уравнений в частных производных как с постоянными, так и с переменными коэффициентами. Задачи рассматриваются в классической постановке.