Введение к работе
Актуальность темы. Метод Монте-Карло является основным инструментом решения многомерных задач математической физики. При этом, как правило, исходная задача сводится к интегральному уравнению второго рода, после чего применяется схема Неймана -Улама, связанная с методом простых итераций решения этого уравнения. Таким образом, исходному уравнению сопоставляется некоторый марковский процесс. Для решения эволюционных уравнений с помощью вычислительных методов во многих случаях уместно применить дискретизацию по времени (например, в методе дробных шагов, методе расщепления и др.) Далее на каждом шаге можно применить схему Неймана - Улама. Это придает алгоритму рекуррентный характер. В связи с этим возникает серия задач, относящихся к исследованию свойств алгоритмов рекуррентного типа. Актуальность таких задач объясняется, в первую очередь, широким кругом приложений рекуррентных алгоритмов. Разработанные методы позволяют исследовать скорость сходимости алгоритмов в прикладных задачах и оценивать их сложность по сравнению с другими стохастическими методами.
Диссертационная работа посвящена исследованию итерационных методов общего характера. Аппарат, развитый в диссертации, позволяет строить и исследовать новые методы Монте-Карло, а также служит теоретической базой для изучения ряда известных алгоритмов.
Цель работы. Целью работы является
-
Определение и обоснование рекуррентного алгоритма Монте-Карло, исследование примеров его применения к различным вычислительным задачам.
-
Получение результатов об условиях стохастической устойчивости рекуррентного алгоритма, о слабой сходимости связанных с ним марковских процессов, а также выявление связи рекуррентного алгоритма с другими стохастическими методами.
3. Исследование асимптотики трудоемкости рекуррентного алгор-
тима.
Научная новизна. В работе представлены следующие новые результаты:
-
Впервые рассмотрен специальный класс цепей Маркова и на его основе построен рекуррентный алгоритм Монте-Карло. Доказана несмещенность оценок, вычислены их моменты. Показана возможность применения рекуррентного алгоритма к решению уравнений в частных производных, интегральных уравнений, а также систем линейных алгебраических уравнений.
-
Исследована стохастическая устойчивость рекуррентного алгоритма. Впервые получены необходимые и достаточные условия устойчивости.
3. Рассмотрены марковские процессы, связанные с рекуррент
ным алгоритмом Монте-Карло, и функционалы на их траекториях.
Исследованы условия сходимости конечномерных распределений та
ких процессов к конечномерным распределениям решения некоторого
стохастического дифференциального уравнения. Получен явный вид
этого уравнения.
-
Впервые предложен метод частиц решения эволюционных уравнений с граничными условиями. Показано, что метод частиц может быть определен на языке рекуррентного алгоритма.
-
Получена асимптотика трудоемкости метода по числу частиц.
Общая методика исследования. В работе использовалась теория мар ковких процессов, стохастических дифференциальных уравнений, теория метода Монте-Карло, теория разностных схем для уравнений в частных производных, теория слабой сходимости распределений, а также теория линейных операторов.
Практическая ценность. Полученные в диссертационной работе результаты могут быть использованы при построении алгоритмов метода Монте-Карло моделирования решений уравнений математической физики и исследовании свойств таких алгоритмов. Разработанный аппарат исследования трудоемкости позволяет судить о целесообразности применения того или иного метода в практических задачах.
Апробация работы. Основные результаты диссертации были представлены и докладывались на третьей международной конференции но моделированию " Mathematical methods in stochastic simulation and experimental design", St.Petersburg, 1998 и на семинарах кафедры статистического моделирования математико-механического факультета Санкт-Петербургского государственного университета.
Публикации. Основные результаты диссертации опубликованы в работах [1]-[2].
Структура и объем работы. Диссертация состоит из введения, четырех глав и списка литературы из 26 наименований. Общий объем работы составляет 115 стр.
