Рекуррентные алгоритмы Монте-Карло тема автореферата и диссертации по математике, 01.01.07 ВАК РФ

Санкт-Петербургский государственный университет

На правах рукописи

РГБ ОД

Гладкова Лидия Анатольевна г

1 * МАЙ 2и'0Э

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

01.01.07 - вычислительная математика

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

Санкт-Петербург 2000

Работа выполнена на кафедре статистического моделирования математико-механического факультета Санкт-Петербургского государственного университета.

Научный руководитель — доктор физико-математических наук, профессор С. М. Ермаков.

Официальные оппоненты: доктор физико-математических наук, профессор В. А. Егоров; кандидат физико-математических наук, доцент Н. К. Кривулин.

Ведущая организация — Санкт-Петербургский государственный технический университет.

Защита состоится " ШСИХ- 2000 г. в 1'Л час. на заседании диссертационного совета Д 063.57.30 по защите диссер .а-ций на соискание ученой степени доктора физико-математических наук в Санкт-Петербургском государственном университете по адресу: 198904, Санкт-Петербург, Ст. Петергоф, Библиотечная пл., д. 2.

С диссертацией можно познакомиться в Научной библиотеке им. М. Горького Санкт-Петербургского государственного университета по адресу: 199034, Санкт-Петербург, Университетская наб., д. 7/9.

Автореферат разослан СЛьЛСьШ- 2000 г.

Ученый секретарь диссертационного совета,

кандидат технических наук Ю. А. Сушков

Общая характеристика работы

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

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

Цель работы. Целью работы является

1. Определение и обоснование рекуррентного алгоритма Монте-Карло, исследование примеров его применения к различным вычислительным задачам.

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

3. Исследование асимптотики трудоемкости рекуррентного алгор-тима.

Научная новизна. В работе представлены следующие новые результаты:

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

2. Исследована стохастическая устойчивость рекуррентного алгоритма. Впервые получены необходимые и достаточные условия устойчивости.

3. Рассмотрены марковские процессы, связанные с рекуррентным алгоритмом Монте-Карло, и функционалы на их траекториях. Исследованы условия сходимости конечномерных распределений таких процессов к конечномерным распределениям решения некоторого стохастического дифференциального уравнения. Получен явный вид этого уравнения.

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

5. Получена асимптотика трудоемкости метода по числу частиц.

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

Практическая ценность. Полученные в диссертационной работе результаты могут быть использованы при построении алгоритмов метода Монте-Карло моделирования решений уравнений математической физики и исследовании свойств таких алгоритмов. Разработанный аппарат исследования трудоемкости позволяет судить о целесообразности применения того или иного метода в практических задачах.

Апробация работы. Основные результаты диссертации были представлены и докладывались на третьей международной конференции по моделированию " Mathematical methods in stochastic simulation and experimental design", St.Petersburg, 1998 и на семинарах кафедры статистического моделирования математико-механического факультета Санкт-Петербургского государственного университета.

Публикации. Основные результаты диссертации опубликованы в работах [1]-[2].

Структура и объем работы. Диссертация состоит из введения, четырех глав и списка литературы из 26 наименований. Общий объем работы составляет 115 стр.

Содержание работы

Во введении дается обзор литературы, обосновывается постановка задачи и кратко излагаются результаты диссертации.

Глава 1. В главе 1 описан рекуррентный алгоритм построения несмещенных оценок £п,п > О величин ип,тг > О, удовлетворяющих рекуррентному соотношению

ип +1 _ ¿(1)ип + 1 + ¿(2)ип + vn + l ф

с заданными значениями u°,vn,n > 0 и известными операторами И*) г (2)

Jjfi , '-'п ■

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

При этом параметры марковской цепи связаны с операторами г(1) г (2)

L„,L„' условиями согласования.

По аналогии с классической схемой Неймана-Улама выделены четыре основные оценки: "сверху вниз", "снизу вверх", по поглощению и по столкновениям. Доказана их несмещенность, вычислены вторые моменты.

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

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

Глава 2. Глава 2 посвящена вопросам устойчивости рекуррентного алгоритма. При этом мы ограничиваемся исследованием спектральной устойчивости.

Определение 1 Стохастический алгоритм слабо устойчив, если

||соу£п||<Сп при всех п > О для некоторого С £ Ж.

Определение 2 Стохастический алгоритм сильно устойчив, если

||соу^п||1<С при всех п > О для некоторого С € М-

Здесь соу£п - матрица ковариаций оценок, || • || - некоторая матричная норма.

Таким образом, задача сводится к отысканию линейного рекуррентного соотношения, связывающего элементы матриц ковариаций оценок п > 0:

со^п+1 = Ппсоу£п + рп. (2)

Для этого используется следующий прием: матрица ковариаций "растягивается" в вектор, составленный из ее элементов.

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

В случае интегральных уравнений все соотношения понимаются в слабом смысле.

Операторы, входящие в соотношения (2), получены в явном виде для общего случал и для некоторых частных, более удобных в практических задачах.

Завершает главу серия примеров исследования устойчивости рекуррентных алгоритмов при помощи доказанных теорем.

Глава 3. В Главе 3 рекуррентный алгоритм рассматривается в применении к системам линейных дифференциальых уравнений. После дискретизации по времени с шагом Д< они сводятся к (явно-неявной) рекуррентной процедуре.

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

В Главе 3 изучаются условия сходимости конечномерных распре--делений процессов и распределений функционалов от к соответствующим распределениям марковского процесса являющегося решением некоторого стохастического дифференциального уравнения.

При некоторых условиях на параметры алгоритма получены достаточные условия сходимости и явный вид предельного стохастического дифференциального уравнения.

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

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

ственного приема поддержания постоянного числа частиц.

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

Показано, что оценка метода частиц является асимптотически несмещенной при N-* оо, где N - число частиц. Получена оценка порядка трудоемкости метода. Это позволяет сравнивать алгоритм метода частиц с другими стохастическими алгоритмами.

Публикации автора по теме диссертации

[1] JI. А. Гладкова, С. М. Ермаков, Рекуррентные алгоритмы Монте-Карло для решения кинетических уравнений. Статистические модели с приложениями в эконометрике и смежных областях. Сб. работ кафедры статистического моделирования СПбГУ, С,-Петербург, НИИХХ СПбГУ, 1999, с. 50-75.

[2] S. М. Ermakov, L. Gladkova, On the Complexity of Particle Method for Partial Differential Equations. 3rd Workshop on Simulation, St. Petersburg, 1998, p. 16-19.

История вопроса

Развитие методов Монте-Карло связано с применением стохастических алгоритмов в области теории переноса излучения ([8], [13]). В частности, схема Неймана-Улама ([10]) возникла в связи с проблемой точности моделирования решения задачи переноса излучения. При этом схема Неймай^-УлаЖ' "состоит в моделировании цепей Маркова и, с другой стороны, тесно связана с итерационным процессом

Хп+1 = АХп +

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

Это обстоятельство потребовало развития новых методов, применимых к более широкому классу уравнений. Существенный шаг в этом направлении был сделан в работах [5], [3]. Во второй из них исследование было проведено в применении к разностному аналогу волнового уравнения, сформулированы условия стохастической устойчивости, приведен пример неустойчивой схемы.

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

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

Однако, задачи этого типа достаточно сложны. Их анализ осуществляется сравнительно просто после введения дискретного времени. Заметим, что при решении практических задач дискретизация по времени является стандартным приемом и служит достаточно общим инструментом исследования. В особенности она важна, когда применяются метод расщепления или метод дробных шагов ([21]), позволяющие заменить исходную задачу последовательностью более простых задач.

Если исходное уравнение имеет вид

Ltu + v(t), (0.1) где ^ - линейный оператор, а и - искомая (вектор-) функция, то после дискретизации с шагом Д£ по времени получаем приближенные соотношения: ип+1 ип

Д£

Ьпип + Vй (явная схема) или (0-2) ип+1 ип ип+1 ип

--- = Ьп-\-1ип+1 + Vй (неявная схема). (0-3)

-А V

Если же представить в виде суммы = + ь[2\ то можно построить явно-неявную схему:

0.4)

Полученное рекуррентное соотношение определяет рекуррентный характер связанных с ним стохастических алгоритмов.

Язык рекуррентного алгоритма дает возможность связать разные по своей природе стохастические алгоритмы и является инструментом для исследования асимптотического поведения их трудоемкости.

Возникает также вопрос о предельном поведении серий последовательностей оценок рекуррентного алгоритма и связанных с ними марковских процессов при Д£ —>• 0. В предлагаемой работе получены условия сходимости конечномерных распределений таких процессов к конечномерным распределениям некоторого диффузионного процесса. Полученные результаты позволяют проследить нюансы взаимосвязи предельных переходов по пространственным и временной переменным с основными классами оценок Монте-Карло.

В диссертационной работе получены некоторые обобщения результатов, опубликованных ранее в работах [3], [4]. Эти обобщения потребовали, в частности, введения некоторого нового класса цепей Маркова, с помощью которого строится и обосновывается рекуррентный алгоритм.

Структура диссертации

В главе 1 описан рекуррентный алгоритм построения несмещенных оценок £п,п > 0 величин ип,п > 0, удовлетворяющих рекуррентному соотношению ип+1 = 41)«п+1 + Ь&ип + vn+1 (0.5) с заданными значениями и°,уп,п > 0 и известными операторами т( 1) г (2) ■ип ? -ип •

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

При этом параметры марковской цепи связаны с операторами г(1) г(2)

Ьп' ,Ьп условиями согласования.

По аналогии с классической схемой Неймана-Улама выделены четыре основные оценки: "сверху вниз", "снизу вверх", по поглощению и по столкновениям. Доказана их несмещенность, вычислены вторые моменты.

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

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

Глава 2 посвящена вопросам устойчивости рекуррентного алгоритма. При этом мы ограничиваемся исследованием спектральной устойчивости. Так, слабая стохастическая устойчивость определяется как свойство алгоритма, заключающееся в линейном росте нормы матрицы ковариации при росте п. Сильная стохастическая устойчивость определяется как ограниченность последовательности норм матриц ковариации оценок при всех п.

Таким образом, задача сводится к отысканию линейного рекуррентного соотношения, связывающего элементы матриц ковариа-ций оценок £п,п > 0: со^п+1 = 7гпсоу£п + рп. (0.6)

Для этого используется следующий прием: матрица ковариаций "растягивается" в вектор, составленный из ее элементов.

Устойчивость рекуррентного алгоритма, для оценок которого выполняется соотношение типа (0.6), определяется значением нормы операторов 71п и ограниченностью последовательности рп. Получены достаточные, а также в некоторых случаях необходимые и достаточные условия слабой и сильной стохастической устойчивости.

В случае интегральных уравнений все соотношения понимаются в слабом смысле.

Операторы, входящие в соотношения (0.6), получены в явном виде для общего случая и для некоторых частных, более удобных в практических задачах.

Завершает главу серия примеров исследования устойчивости рекуррентных алгоритмов при помощи доказанных теорем.

В главе 3 рекуррентный алгоритм рассматривается в применении к системам линейных дифференциальых уравнений. После дискретизации по времени с шагом At они сводятся к (явно-неявной) рекуррентной процедуре.

Рассмотрим последовательность серий случайных величин, где каждая серия есть последовательность оценок £п величин, удовлетворяющих этой рекуррентной процедуре, полученная с помощью рекуррентного алгоритма при фиксированном Д£. Рассмотрим кусочно-линейный процесс с вершинами в точках п,пДг),п > 0.

В главе 3 изучаются условия сходимости конечномерных распределений процессов и распределений функционалов от £л к соответствующим распределениям марковского процесса являющегося решением некоторого стохастического дифференциального уравнения.

При некоторых условиях на параметры алгоритма получены достаточные условия сходимости и явный вид предельного стохастического дифференциального уравнения.

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

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

В этом смысле результаты главы 3 являются обобщением результатов, полученных в работах [11], [16], [12].

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

Показано, что оценка метода частиц является асимптотически несмещенной при N оо, где N - число частиц. Получена оценка порядка трудоемкости метода. Это позволяет сравнивать алгоритм метода частиц с другими стохастическими алгоритмами.

Об обозначениях

Перечислим обозначения, принятые в диссертационной работе.

1) Под точкой жЕ®^ подразумеваем вектор-столбец. Для всякого вектора ж = (жх5., ж^) =

1. хт - транспонированный вектор (строка);

2. |ж| - модуль вектора:

М = ух1 + --- + х1

3. Обозначим символом Кк к-й базисный вектор: < при % = 1,. с?, А; = 1,., с?. г [ 0 иначе

2) Для всякой матрицы А порядка с1х.с1:

1. Ат - транспонированная матрица;

2. (Над А - диагональ матрицы А, (Над А Е

3. А (А) - максимальное по модулю собственное число матрицы А.

Единичную матрицу будем обозначать буквой I.

3) Обозначения, связанные с интегральными уравнениями.

1. Для всякой ограниченной функции /(ж) и заряда /х(с?ж) = ! /(х)р((1х).

2. Дельта-меру, сосредоточенную в точке Х: будем обозначать

3. Символом \[х\ будем обозначать полную вариацию заряда ц.

4. Для двух зарядов (мер) V символом /IX V будем обозначать их прямое произведение. Будем также использовать обозначение ц2 = /IX/I.

5. Символом X будем обозначать тождественный оператор.

6. Для всякого интегрального оператора А символом Х(Л) будем обозначать наибольшее по модулю собственное число оператора Л.

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

Для любых двух векторов х, у G

1. [х,у]е - вектор, составленный из произведений соответствующих компонент векторов х и у: х,у]е = (xiyi,.,xdyd)]

Для векторов, составленных из квадратов компонент вектора, будем применять обозначение

Х^ ^ = [ж, х\е — (XI, . . . , X.

И вообще, для любой степени п будем обозначать х^- ^ = (Xi,., xd ) .

2. | - вектор, составленный из частных соответствующих компонент векторов ж и у:

X /Хх хЛ у V2/i г/d/ '

3. а(х,у) - матрица dxd, составленная из попарных произведений компонент векторов х и у: а(х,у) = •

Вместо а(х,х) будем для краткости писать а(х).

5) Введем обозначения для операций поэлементного умножения и деления матриц. Для любых dxd-матриц А = = H&zjll

1. [А,В]е - матрица, составленная из произведений соответствующих элементов матриц А ж В:

А,В]е = \\а^Ь{ й

2. - матрица, составленная из частных соответствующих элементов матриц А и В\

А В агЗ

Ьц г,3=1

Для матриц, составленных из квадратов элементов матрицы, будем применять обозначение

А™ = [А,А]е = а гэ 1 г,3=1

И вообще, для любой степени п будем обозначать

АЫ = а^ к*

3. Для всяких матрицы А и вектора х будем обозначать сI А х агз х3

6) Пусть А = Ца^-Ц - матрица с1хс1. Тогда будем обозначать 1. Вектор длины с12

А = (а>ц) Е

2. Матрица в(А) = \\в(А)гЛз,,Г1 1 Ог.чйт

При этом порядок, в котором элементы матрицы выписываются У в строку, не имеет значения, важно только, чтобы А и в (А) были согласованы с точки зрения этого порядка. Для исследования устойчивости (глава 2) нам понадобятся специфические обозначения.

7) Пусть А,В- матрицы с1х<1, х €

1. Обозначим за 6(х) диагональную матрицу <1х(1, для которой сИад5(х) = х.

2. Обозначим за (3(х,А) матрицу с?хс?, для которой

3(х, А)ц — + ХуАц при всех г,] = 1,., с?.

8) Для матриц А, В порядка обозначим:

1. к(А) - матрица (12хс12 такая, что 4 \ | ? ^ - 5 ^ | о иначе;

2. ш(А,В) - матрица с?2Хб£2 такая, что

АхдВуъ ~Ь AjsBij , 5 — cv{A,B)ij.s>t =

О иначе.

9) Введем еще два обозначения.

1. Для любой симметричной матрицы А введем вектор длины 1)/2 string (А) =

А22, • • •, \Addi

-^-31? ^42, • • • ,Ad,d-2, • • • , Д*,] в строку последовательно выписаны элементы главной диагонали, умноженные на 1/2, затем нижней поддиагонали и т. д.) Вектор string (А) взаимно-однозначно задает симметричную МАТРИЦ,у А.

2. Для любого вектора х = (xi,., ж^) обозначим 1опд(х) = (а?!,., Xd, 0,., 0) - вектор длины d(d+l)

Т. е. вектор 1опд{х) получается из х дополнением нулей до d(d+1) ДЛИНЫ —•

Последние два обозначения будут использоваться только графе 2.4.

1. S. M. Ermakov, L. Gladkova, On the Complexity of Particle Method for Solving Partial Differential Equations. 3rd Workshop on Simulation, St. Petersburg, 1998, p. 16-19.

2. S. M. Ermakov, W. Wagner. Monte Carlo difference schemes for the wave equations, WIAS, Berlin, 1999.

3. W. Wagner. Monte Carlo evaluation of functionals of solutions of stochastic differential equations. Akademie der Wissenschaften der DDR, Karl-Weierstrass-Institut fur Mathematik, Berlin, 1988.

4. С. M. Ермаков, А. В. Иванова, О стохастической устойчивости разностных схем, Вестник ЛГУ, серия: мат., мех., астр., 1991, Выпуск 1, 1, с. 30-34.

5. Д. Л. Данилов, С. М. Ермаков. О сложности схемы Неймана-Улама для решения системы сеточных уравнений многомерной задачи Дирихле. Вестник Санкт-Петербургского университета. Сер. 1: мат., мех., астр., 1991, Выпуск 1, с. 11-14.

6. А. А. Беляева, С. М. Ермаков. О методе Монте-Карло с запоминанием промежуточных результатов. Вестник Санкт-Петербургского университета. Сер. 1: мат., мех., астр., 1996, Выпуск 3, 15, с. 8-14.

7. Ермаков С. М., Метод Монте-Карло и смежные вопросы. Изд. 2-е. М., Наука, 1975.

8. Halton J. Н., A retrospective and prospective survey of the Monte Carlo method, SIAM Rev. (1970) 12, 1, 1-63.

9. G. E. Forsithe, R. Z. Leibler. Matrix inversion by the Monte Carlo methods. Math, tables and other aids to comp, 4 (1950), p. 127129.

10. Г. А. Михайлов. Расчеты критических систем методом Монте-Карло. Журнал вычислительной математики и математической физики. Том 6, 1, 1966.

11. P. A. Raviart. An analysis of particle methods, Numerical Methods in Fluid Dynamics, Lecture Notes in Math., vol. 1127, 1985, p. 243-324.

12. С. M. Ермаков, В. В. Некруткин, А. С. Сипин. Случайные процессы для решения классических уравнений математической физики. М., Наука, 1984.

13. И. И. Гихман, А. В. Скороход. Введение в теорию случайных процессов. М., Наука" 1977.

14. А. Д. Вентцель. Курс теории случайных процессов. Изд. 2-е. М., "Наука", 1996.

15. Talay D., Probabilistic Numerical Methods for Partial Differential Equations: Elements of Analysis, in Probabilistic Models for Nonlinear Partial Equations, D. Talay, L. Tubaro (ed.), Lecture Notes on Math., vol. 1627,p. 148-194, Springer-Verlag, 1996.

16. Yu. N. Kashtanov. The Generations Method for Higher Eigenvalue Estimation. 2nd Workshop on Simulation, St. Petersburrg, 1996, p. 32-36.

17. Г. Дж. Кушнер. Вероятностные методы аппроксимации в стохастических задачах управления и теории эллиптических уравнений. М., Наука, 1985.

18. Ю. JI. Далецкий, С. В. Фомин. Меры и дифференциальные уравнения в бесконечномерных пространствах. М., Наука, 1983.

19. С. Г. Михлин, X. Л. Смолицкий. Приближенные методы решения дифференциальных и интегральных уравнений. М., Наука, 1966.

20. Яненко Н. Н., Метод дробных шагов решения многомерных задач математической физики. Новосибирск, "Наука", Сиб. отд-ние, 1967.

21. А. А. Самарский. Теория разностных схем. М., Наука, 1977.

22. А. Н. Колмогоров, С. В. Фомин. Элементы теории функций и функционального анализа. Изд. 2-е М., Наука, 1968.

23. Д. Ф. Кузнецов. Численное моделирование стохастических дифференциальных уравнений и стохастических интегралов. С.-Петербург, Наука, 1999.

24. М. А. Алексидзе. Фундаментальные функции в приближенных решениях граничных задач. М., Наука, 1991.

25. Р. П. Федоренко. Введение в вычислительную физику. М., Изд-во Московского физико-технического института, 1994.Рекуррентный алгоритм Монте-Карло

26. Описание рекуррентного алгоритма .11.1 Специальный класс цепей Маркова.11.2 Построение прямых оценок.11.3 Построение сопряженных оценок.11.4 Метод понижения дисперсии.

27. Условные средние и условные ковариации оценок . . .12.1 Теорема о несмещенности оценок.12.2 Вычисление условных ковариаций .

28. Рекуррентный алгоритм для интегрального уравнения13.1 Предположения и основные оценки.13.2 Повышение точности оценки.13.3 Вычисление средних и вторых моментов .

29. Рекуррентный алгоритм в примерах.14.1 Применение к уравнениям в частных производных .14.2 Применение к интегральным уравнениям . . .14.3 Системы алгебраических уравнений.Устойчивость рекуррентного алгоритма

30. Понятие устойчивости стохастического алгоритма . .

31. Общий случай и теорема об устойчивости.22.1 Дискретный случай.22.2 Случай интегрального оператора с ядром . . .22.3 Теорема об устойчивости .

32. Условия устойчивости для некоторых классов оценок 2.3.1 Дискретный случай.23.2 Случай интегрального оператора.49

33. Условия устойчивости для некоторых классов оценок. Продолжение.50

34. Примеры исследования стохастической устойчивости 5425.1 Условия устойчивости основных оценок . 5425.2 Пример Холтона.57Слабая сходимость оценок рекуррентного алгоритма 6031 Вводные замечания.60

35. Теоремы о сходимости для оценок "сверху вниз" . 6232.1 Уравнения в частных производных и марковские процессы.6232.2 Предельные теоремы для прямых оценок . 66

36. Случай интегрального оператора с ядром. Оценка "снизу вверх" .76

37. Пример и алгоритм моделирования.81Метод частиц и его связь с рекуррентным алгоритмом 8741 Вводные замечания. 87

38. Решения эволюционных уравнений в слабом смысле . 88

39. Метод частиц для решения эволюционных уравнений 90

40. Метод частиц для решения эволюционных уравнений на языке рекуррентного алгоритма .96

41. Методы перехода на один шаг.10045.1 Применение фундаментальных решений . 10145.2 Схема Эйлера.10145.3 Схема Мильштейна.10245.4 Применение инфинитеземальных операторов . 10346 Вопросы трудоемкости.106