Рекуррентные алгоритмы Монте-Карло

• Автор: Гладкова, Лидия Анатольевна
• Шифр специальности: 01.01.07
• Научная степень: Кандидатская
• Год защиты: 2000
• Место защиты: Санкт-Петербург
• Количество страниц: 115 с.

Введение
История вопроса
Развитие методов Монте-Карло связано с применением стохастических алгоритмов в области теории переноса излучения ([8], [13]). В частности, схема Неймана-Улама ([10]) возникла в связи с проблемой точности моделирования решения задачи переноса излучения. При этом схема НеймайД-'Улам&'состоит в моделировании цепей Маркова и, с другой стороны, тесно связана с итерационным процессом
Хп+1 = АХп + К
Развитые в связи с этим алгоритмы расходовали небольшой объем машинной памяти, однако для их применения требовалось выполнение условия сходимости мажорантного процесса, что резко ограничивало область применимости схемы Неймана-Улама.
Это обстоятельство потребовало развития новых методов, применимых к более широкому классу уравнений. Существенный шаг в этом направлении был сделан в работах [5], [3]. Во второй из них исследование было проведено в применении к разностному аналогу волнового уравнения, сформулированы условия стохастической устойчивости, приведен пример неустойчивой схемы.
Понятие устойчивости играет большую роль в исследовании свойств стохастических алгоримов. Во многих случаях неустойчивость, проявляющаяся в экспоненциальном росте дисперсии оценок, делает применение схемы Неймана-Улама невозможным.
Альтернативой схеме Неймана-Улама могут служить, в частности, методы, использующие аппарат стохастических дифференциальных уравнений. Для решения эллиптических уравнений по-

строены эффективные алгоритмы такого рода ([18]). Строго говоря, такие алгоритмы не укладываются в схему Неймана-Улама. Безусловно, представляет интерес разработка общего языка, позволяющего с единой точки зрения взглянуть на эти два типа стохастических алгоритмов. Определенный прогресс в установлении такой общности был достигнут в работе [4].
Однако, задачи этого типа достаточно сложны. Их анализ осуществляется сравнительно просто после введения дискретного времени. Заметим, что при решении практических задач дискретизация по времени является стандартным приемом и служит достаточно общим инструментом исследования. В особенности она важна, когда применяются метод расщепления или метод дробных шагов ([21]), позволяющие заменить исходную задачу последовательностью более простых задач.
Если исходное уравнение имеет вид
= £;« + *;(£}, (0.1)
где - линейный оператор, а и - искомая (вектор-) функция, то
после дискретизации с шагом Д£ по времени получаем приближен-
ные соотношения:
ип+1

(0.3)
ТО МОЖНО
д.П+1 _ п,П
- А— = 41)«п+4+1 “"+1+г’п- (°-4)
Полученное рекуррентное соотношение определяет рекуррентный характер связанных с ним стохастических алгоритмов.
Язык рекуррентного алгоритма дает возможность связать разные по своей природе стохастические алгоритмы и является инструментом для исследования асимптотического поведения их трудоемкости.

+ Vті (неявная схема).
Если же £* представить в виде суммы Ь% = построить явно-неявную схему:

Возникает также вопрос о предельном поведении серий последовательностей оценок рекуррентного алгоритма и связанных с ними марковских процессов при At —> 0. В предлагаемой работе получены условия сходимости конечномерных распределений таких процессов к конечномерным распределениям некоторого диффузионного процесса. Полученные результаты позволяют проследить нюансы взаимосвязи предельных переходов по пространственным и временной переменным с основными классами оценок Монте-Карло.
В диссертационной работе получены некоторые обобщения результатов, опубликованных ранее в работах [3], [4]. Эти обобщения потребовали, в частности, введения некоторого нового класса цепей Маркова, с помощью которого строится и обосновывается рекуррентный алгоритм.
Структура диссертации
В главе 1 описан рекуррентный алгоритм построения несмещенных оценок £п,п > 0 величин ип,п > 0, удовлетворяющих рекуррентному соотношению
ип+1 = + Ь(2 )ип + уП+1
с заданными значениями гг°,цп,п > 0 и известными операторами
Для этого сначала вводится специальный класс цепей Маркова, множество состояний которых - целочисленная решетка, ограниченная слева, справа и снизу. Траектории цепей устроены так: сначала движение по горизонтали, затем переход на верхний слой, после чего цепь обрывается. Движение вниз запрещено.
При этом параметры марковской цепи связаны с операторами
г(1) т( 2)
Ь)г', Ьп' условиями согласования.
По аналогии с классической схемой Неймана-Улама выделены четыре основные оценки: ’’сверху вниз”, ’’снизу вверх”, по поглощению и по столкновениям. Доказана их несмещенность, вычислены вторые моменты.
Рекуррентный характер алгоритма позволяет понизить дисперсию, вводя дополнительное усреднение на каждом шаге итераций.
а для второй схемы (1.49)
( ~т т 0 .. 0
т —т т 0
А = 0 т —т .. 0 >
V о 0 0 .. -т /
/ 1 — г т 0 0
Ьт 1 — г !г 0
В = 0 т 1 — т 0
V 0 0 0 .. 1 - г )
Ясно, что применение рекуррентного алгоритма предпочтительнее в случае схемы (1.52) - (1.53).
1.4.2 Применение к интегральным уравнениям
Рассмотрим следующее интегро-дифференциальное уравнение:
г~:- = !К{(у,<1х)11г(<1у) + I Л, йу). (1.54)
Здесь > 0 - семейство а-конечных зарядов, операторы К%Ь% удовлетворяют всем условиям пункта 1.3.1 при всех Ь> 0, //*,£> О - искомое семейство зарядов.
Определение 1.4.1 Мы будем говорить, что семейство распределений
ри1 > О
удовлетворяет рекуррентному соотношению (1.54), если для всякой непрерывной ограниченной функции / выполняется
(/ > (Н) = Н КС)
= (/, I Кг(у, йх)у)) + (/, / Ьг{у, <1х)г(ёу))
Как и в случае уравнения в частных производных, выберем At и заменим производные в левых частях (1.54) и (1.55) их разностными аналогами с шагом At. Представим оператор Ку,<1х) в виде