ГЛАВА V. ПРИМЕНЕНИЕ МЕТОДА МОНТЕ-КАРЛО К РЕШЕНИЮ НЕКОТОРЫХ КРАЕВЫХ ЗАДАЧ ДЛЯ ДИФФЕРЕНЦИАЛЬНЫХ УРАВНЕНИЙ

§ 20. Применение метода Монте-Карло для решения краевых задач

Большое число прикладных вопросов приводит к необходимости решения краевых задач для уравнений математической физики. Наиболее типичным примером является решение задачи Дирихле (первая краевая задача) для двумерного и трехмерного уравнения Лапласа

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

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

Существен при этом тот факт, что увеличение размерности (числа независимых переменных) влечет за собой экспоненциальное увеличение количества узлов решетки.

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

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

Надо сказать, что связь между решением краевых задач и вероятностными процессами была уже давно отмечена в работе И. Г. Петровского [34]. Однако реальное использование этой связи для практического решения краевых задач (а не для исследования свойств случайных процессов) стало возможным лишь в связи с развитием современной вычислительной техники.

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

Для пояснения основной идеи достаточно рассмотреть задачу Дирихле для уравнения Лапласа. Пусть имеется некоторая область, и на ее границе Г задана некоторая функция Требуется найти такую функцию которая внутри данной области удовлетворяет уравнению Лапласа

и на границе Г области принимает заданные значения

где

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

внутренними; узлы, для которых число соседних внутренних узлов меньше четырех, называются граничными (рис. 7).

Значения функции и, заданные на контуре области Г, переносятся с этого контура в граничные узлы по специальным правилам.

Рис. 7.

В граничных узлах, следовательно, функция и принимает заданные значения:

Во внутренних узлах мы ищем значения функции исходя из соотношения

Здесь означают четыре узла, соседние к внутреннему узлу . Система уравнений (5.1)-это обычная система в конечных разностях. Рассмотрим связанную с системой (5.1) теоретико - вероятностную схему.

Эту схему принято рассказывать в виде так называемой «задачи о пьяных». Будем рассматривать стороны решетки как городские кварталы, а узлы — как

перекрестки городских улиц. Предположим, что из узла Р выходит «пьяный», который с равной вероятностью (а именно, равной ) может попасть в любой из соседних узлов. Аналогично, попав в очередной узел (войдя на очередной перекресток), «пьяный» с равной вероятностью идет по одному из примыкающих к этому перекрестку кварталов, пока не выйдет на следующий перекресток. Будем считать, что город обнесен глубоким рвом; сказывается в том, что, выйдя на границу города (т. е. граничный узел решетки), «пьяный» остается в этом узле, так сказать, свалившись в ров. Возникает вопрос об отыскании вероятности того, что «пьяный», выйдя из узла , окончит блуждание в граничном узле

Можно утверждать, что с вероятностью, равной единице, «пьяный» в конце концов окажется на границе города.

Найти искомую вероятность в явном виде сложно, однако нетрудно вывести соотношение для вероятности. Заметим, что событие, заключающееся в том, что «пьяный» попадет из точки в точку равносильно тому, что он либо попадет из точки в точку а оттуда в либо попадет из в а оттуда в либо попадет из точки в а оттуда в либо попадет из точки в через Здесь опять-таки через обозначены четыре соседних к узла. Так как вероятности попадания из равны 74, то по теореме сложения вероятностей

Таким образом, мы пришли к конечноразностному уравнению (5.1), связывающему вероятности. Кроме того, вероятность удовлетворяет следующим краевым условиям:

где и — граничные узлы.

Известно, что существует единственная функция, удовлетворяющая уравнениям (5.1) при данных краевых условиях.

Если промоделировать блуждание «пьяного» раз, заставляя его каждый раз выходить из точки , и сосчитать количество М испытаний, при которых путь «пьяного» оканчивается в точке то будем иметь

Таким образом получим приближенное решение уравнения (5.2) с краевыми условиями (5.3).

Чтобы решить задачу Дирихле с общими краевыми условиями, нужно немного обобщить нашу вероятностную схему. Именно, предложим дополнительно, что после того как «пьяный» сваливается в ров в граничном узле с него взимается штраф, равный Ясно, что величина штрафа, уплаченного «пьяным», вышедшим из точки , является случайной величиной. Обозначим ее

Величина штрафа может принимать значения

где — совокупность всех граничных узлов. Вероятность заплатить штраф равна

Значит, математическое ожидание штрафа определяется так:

Ясно, что величина зависит от точки выхода .

Эта функция удовлетворяет разностному уравнению

Действительно, подставив в и умножив обе части на мы получим после суммирования по всем граничным узлам равенство (5.5),

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

В самом деле, если подставить в (5.4), то в силу условий (5.3) в правой части (5.4) пропадут все слагаемые, кроме одного

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

Посмотрим, от чего зависит время решения рассматриваемой задачи.

Пусть узел имеет координаты Тогда соседние узлы имеют координаты (мы полагаем здесь )

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

В процессе решения надо всегда помнить величины — координаты начальной точки — текущие координаты «пьяного».

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