Метод Монте-Карло

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

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

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

Одной из интереснейших областей применения метода Монте-Карло являются краевые задачи и задачи с начальными условиями (задачи Коши). Связь между решением этих задач для некоторых классов дифференциальных уравнений и случайными процессами типа «блужданий» была известна достаточно давно, однако возможность применения этой связи для фактического отыскания численных решений уравнений появилась лишь с развитием компьютерной техники. Особенно важным преимуществом метода Монте-Карло при решении краевых задач является его приспособленность к многомерным задачам. Для пояснения основной идеи метода обратимся к задаче Дирихле на плоскости для уравнения Лапласа. Пусть имеется некоторая односвязная плоская область, на границе которой задана функция. Требуется найти такую функцию, которая внутри данной области удовлетворяет уравнению Лапласа:

и на границе области — кривой — принимает заданные значения

Обыкновенно при решении эту задачу сводят к некоторой конечно-разностной схеме. Нанесём на плоскость квадратную сетку с некоторым постоянным шагом. В дальнейшем будут рассматриваться только те узлы сетки, которые попали внутрь области. Эти рассматриваемые узлы сетки делятся на два сорта. Узлы, имеющие четыре соседних узла (лежащих в области), будут называться внутренними узлами; узлы, у которых число соседних меньше четырёх, будут называться граничными. В граничных узлах функция принимает заданные значения:, при этом значения функции переносятся с контура на граничные узлы по специальным правилам, на которых мы сейчас останавливаться не будем. В данный момент рассуждений нам важно лишь то, что функция задана в любой точке .Во внутренних узлах сетки мы будем искать значения функции, исходя из системы уравненийгде — четыре узла, соседних с данным внутренним узлом. Приведённая система уравнений — стандартная для подобных задач конечно-разностная схема. Получается она следующим образом. В уравнении Лапласазаменим производные и отношениями конечных разностей по следующим формулам:

где — выбранный нами шаг равномерной сетки. Тогда уравнение Лапласа запишется в следующем виде:

откудаичто совпадает с уравнением (2), поскольку если — некоторый узел сетки с шагом, то и — четыре соседних с ним узла: два имеют такую же ординату и абсциссы, отличающиеся на, у двух такие же абсциссы и отличающиеся на шаг ординаты. Теперь рассмотрим некоторую теоретико-вероятностную модель, иногда называемую «задачей о пьяных». Представим себе, что линии решётки — это улицы некоторого города с правильной квадратной планировкой кварталов, а узлы решётки — соответственно перекрёстки улиц. Теперь предположим, что в узле находится «пьяный», который с равной вероятностью в следующий контрольный момент времени может оказаться в любом из четырёх соседних узлов. И точно также, попав в следующий узел, наш «пьяный» опять же с равной вероятностью в следующий момент времени может шагнуть в любой из соседних узлов (причём в этот выбор включено и возвращение «пьяного» снова в узел). Основным свойством «пьяного» является то, что его выбор в каждом очередном узле никак не искажается предыдущей историей его «блужданий» и всё время остаётся равновероятным, — кроме тех случаев, когда он попадает в один из граничных узлов. Здесь мы предполагаем, что вокруг города, скажем, вырыт глубокий ров, и пьяный, попав в него в некоторой точке (граничном узле решётки), остаётся в этом месте до конца «игры».

Собственно, на этом «игра» (то есть очередная её «партия») и заканчивается. Можно доказать, что с вероятностью, равной единице, «пьяный» в конце концов окажется на границе города, во «рве», город окружающем. Найти искомую вероятность для каждой точки начала «блужданий», впрочем, довольно сложно, однако некоторое соотношение для вероятности вывести можно. Сделаем это. Заметим, что событие, состоящее в том, что наш «пьяный» попадёт из некоторой внутренней точки (узла) в некоторую граничную точку, равносильно тому, что: либо он попадает из узла в узел, а из него в узел (совершенно неважно, по какому конкретному маршруту); либо он попадает в узел, а оттуда — в узел, либо он попадёт в через узел, либо, наконец, через узел. Здесь, как и прежде, обозначают четыре узла, соседних с внутренним узлом. Поскольку вероятность попадания в узлы из узла равны между собой и равны каждая, то согласно теореме сложения вероятностей имеем:

Поскольку в функции на месте первого аргумента («узел старта») может, вообще говоря, быть и какая-либо граничная точка, получаем следующие краевые условия нашей задачи:

Сравнив полученное соотношение с уравнением (2), мы увидим, что они идентичны, то есть вероятность в задаче о «блужданиях пьяного» удовлетворяет конечно-разностному уравнению (2), — а значит, найдя некоторый способ вычислить, мы вычислим и численное решение задачи Дирихле в точке .Если смоделировать блуждание нашего «пьяного» раз, заставляя его каждый раз снова выходить из точки, и сосчитать число испытаний, при которых его путь закончится в точке, то будем иметь

Это и будет приближённым численным решением задачи (3) с краевыми условиями (4) в точке. Заметим только, что это будет решением «модифицированной» задачи Дирихле, в которой. Способ перейти от этого условия к произвольной, в общем-то очевиден, поскольку. Однако поскольку мы имеем дело с вероятностной моделью, это простое домножение функции на необходимый нам множитель стоит рассмотреть более подробно. Один из множителей в получаемом произведении является по смыслу задачи вероятностью (а именно вероятностью попадания в точку при блужданиях по заданной решётке, начинающихся в точке). Второй — одним из возможных значений некоторой — в нашем случае дискретной — функции.

Следовательно, есть основания рассматривать это произведение как слагаемое некоторого математического ожидания. Несколько обобщим описанную вероятностную схему таким образом. Предположим, что вдобавок к сваливанию в «ров», окружающий город, с «пьяного» будет взиматься штраф, равный в каждой конкретной точке «сваливания» значению. Значение штрафа зависит от точки, в которой «пьяный» закончит свои блуждания по городу. Ясно, что величина штрафа, который в конечном итоге заплатит наш «пьяный», выходя из точки, является случайной величиной. может принимать значениягде совокупность всех внешних узлов нашей решётки. Вероятность заплатить штраф, равный, равна. Тогда математическое ожидание штрафа при выходе из точки будет определяться формулой

По смыслу задачи величина зависит от точки начала блужданий. Далее, функция удовлетворяет разностному уравнениюгде — по-прежнему суть узлы, соседние с внутренним узлом. Действительно, подставив в уравнение (2) вместо величину, затем домножив обе части на и, наконец, просуммировав полученное равенство по всем внешним узлам решётки (), мы получим верное равенство (5). Заметим также, что в любом внешнем узле функция удовлетворяет краевым условиям. Действительно, поскольку если подставить в правую часть равенства (4) вместо некоторую граничную точку, в сумме все слагаемые, кроме содержащего множитель, обратятся в нуль в силу условия (3). В итоге мы получим

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

где — задаваемая погрешность решения, а — дисперсия величины штрафа, получаемого при выходе из точки. Последняя оценивается (сверху) следующим простым способом:

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

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

Бусленко Н.П., Голенко Д. И., Соболь И. М., Срагович В. Г., Шрейдер Ю. А. Метод статистических испытаний (Метод Монте-Карло)/ Ю. А. Шрейдер, ред. — М.: Физматгиз, 1962. —

334 с. (Справочная математическая библиотека) Войтишек А. В. Основы метода Монте-Карло: Учеб. пособие / Новосиб.

гос. ун-т. Новосибирск, 2010. — 108 с. Гнеденко Б. В. Курс теории вероятностей: учебник. Изд. 8-е, испр и доп. / Б. В. Гнеденко.

— М.: Едиториал УРСС, 2005. — 448 с. (Классический университетский учебник.)Д.Л. Данилов, С. М. Ермаков. О сравнительной трудоёмкости метода Монте-Карло для решения систем линейных алгебраических уравнений./Д.Л. Данилов, С. М. Ермаков. -

Журнал вычислительной математики и математической физики, Том 35, 1995, № 5, стр. 661−676.Демидович Б. П., Марон И. А. Основы вычислительной математики: учеб. пособие / Б. П. Демидович, И. А. Марон. —

Москва: «Наука», 1966. — 665 с. Демидович Б. П., Марон И. А., Шувалова Э. З. Численные методы анализа. Приближение функций, дифференциальные и интегральные уравнения: учеб. пособие / Б. П. Демидович, ред.

— Москва: «Наука», 1967. — 368 с. Заварыкин В. М. и др. Численные методы: Учеб. Пособие для студентов физ.-мат.

Спец. пед. ин-тов / В. М. Заварыкин, В. Г. Житомирский, М. П. Лапчик. — М.: Просвещение, 1990. —

126 с. Лазакович Н. В., Сташулёнок С. П., Яблонский О. Л. Курс теории вероятностей: учеб. пособие / Н. В. Лазакович, С. П. Сташулёнок, О. Л. Яблонский. — Минск: «Электронная книга БГУ», 2003. — 322 с.