Столярчук В.А. “Системы моделирования”. Материалы к лекциям. Лекция №21

Лекция № 21

9.5. Моделирование методом Монте-Карло задач математической физики и задач смешанного типа.

Оглавление

Лекция № 21 1

9.5.1. Связь между решением краевых задач и вероятностными процессами 1

9.5.2. Задача Дерихле для уравнения Лапласа 3

9.5.3. Оценка времени решения краевой задачи 10

9.5.4. Более общие задачи и особенности метода 11

9.5.5. Применение метода Монте-Карло для решения задач смешанного типа. 16

9.5.1. Связь между решением краевых задач и вероятностными процессами

Связь между решением краевых задач и вероятностными процессами была уже давно (в 1934г.), отмечена в работе И.Г. Петровского, но реализации этой связи стала возможной лишь в связи с появлением ЭВМ.

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

Уравнения	Математическая форма	Примеры задач
Лапласа	 f = 0	Установившееся течение жидкости. Стационарные тепловые поля. Безмоментная теория оболочек.
Пуассона	 f = -k	Теплопередача с внутренними источниками тепла.
Дифузии	 f =	Нестационарная теплопроводность
Волновое	 f =	Распростанение звуковых волн
Бигармоническое	 2f = F(x,y)	Деформация пластин

Здесь: ;  ²f = ;

Через оператор Лапласа задача Дирихле записывается внутри и на границе области так:

U=0; U _Г =0;

При этом на границе Г области неизвестная функция принимает заданные значения: U_Г = f(Q), где QГ

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

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

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

Итак, рассмотрим задачу Дирихле для уравнения Лапласа.

9.5.2. Задача Дирихле для уравнения Лапласа

В ограниченной связной области G плоскости X,Y с простой границей G^O рассмотрим дифференциальное уравнение с частными производными.

, (1)

где U=U(X,Y) искомая функция.

Повторяем, что уравнение (1) при F(X,Y)=0 называется уравнением Лапласа, которым описываются многие физические процессы или состояния (см. таблицу). При F(X,Y)0 - уравнением (1) называют уравнением Пуассона.

Предположим, что на границе G^O задана некоторая функция g(X,Y) (часто пишут g(S), где S - длина дуги границы, отсчитываемая от какой-нибудь фиксированной точки). Требуется найти такое решение U(X,Y) уравнения (1), которое на границе совпадает с g(X,Y):

U(X,Y) _G^o = g (X,Y) (2)

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

Обычно эту задачу сводят к некоторой конечно-разностной, для чего поступают следующим образом.

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

Для приближенного решения этой задачи обычно выбирают на плоскости достаточно мелкую квадратную сетку с шагом h. Координаты узлов этой сетки пусть будут X_j=jh, Y_l=ih, а значения U(X_j,Y_l) и F( X_j,Y_l) для краткости обозначим U_jl и F_jl. Узлы сетки делятся на два сорта. Узлы, для которых четыре соседних узла лежат в области или на ее границе, называют внутренними; узлы, для которых число соседних внутренних узлов меньше четырех, называют граничными.

j,i+11 j+1,i j,i

Узел (j,i) называют внутренним, если и он и все четыре соседних с ним узла (j-1,l), (j+1,l), (j,l-1), (j,l+1) принадлежат G+GO, в противном случае узел (j,l), принадлежащий G+GO, называют граничным.

Во внутреннем узле (j,i) уравнение (1) заменяется разностным уравнением:

(3)

которое можно переписать в виде:

(4)

В граничных узлах полагаем: U_j,i=g_j,i (Значения g_j,i сносят с ближайших точек границы G^O).

Именно соотношения типа (4) натолкнули исследователей на мысль использовать метод Монте-Карло для решения задач, описываемых дифференциальными уравнениями в частных производных.

Для этого запишем нашу задачу в несколько других обозначениях и для более простого уравнения – уравнения Лапласа.

Итак, пусть имеется некоторая область и на ее границе Г задана некоторая функция f(Q). Требуется найти такую функцию U(P), которая внутри данной области удовлетворяет уравнению Лапласа

U = 0 (здесь , как и ранее, оператор Лапласа: )

и на границе Г области принимает заданные значения U_Г =f(Q), где QГ.

Задавшись некоторым числом h (шагом) проводят в плоскости сетку, образуя множество узлов. В дальнейшем рассматривают только те узлы сетки, которые попали внутрь области. Как уже говорилось, узлы сетки делятся на два вида. Узлы, для которых четыре соседних узла лежат в области или на ее границе, называют внутренними и обозначаем символом Р; узлы, для которых число соседних внутренних узлов меньше четырех, называют граничными. Их обозначаем символом Q.

Qi+1 Qi Qi-1 QS-2 Q4 QS-1 QS Q1 Q2 Q3 P3 P2 P В граничных узлах функция U принимает заданные значения U(Q ) = f(Q) Во внутренних узлах мы ищем значения функции U(P), исходя из соотношения:

U(P)= (5)

Здесь Р_1, Р_2, Р_3, Р₄ - означают четыре узла, соседние к внутреннему Р. Как мы уже видели, система таких (4) уравнений - это обычная система в конечных разностях. Рассмотрим связанную с системой (4) теоретико-вероятностную схему. Эту схему принять рассказывать в виде так называемой задачи о пьяных.

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

Будем считать, что город обнесен глубоким рвом: это сказывается в том, что выйдя на границу города (т.е. граничный узел решетки), пьяный остается в этом узле, так сказать, свалившись в ров.

Возникает вопрос об отыскании вероятности U(P,Q) того, что пьяный, выйдя из узла Р, окончит блуждание в граничном узле Q.

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

Найти искомую вероятность в явном виде сложно, однако можно вывести соотношение для этой вероятности.