Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Столярчук В.А. “Системы моделирования”. Материалы к лекциям. Лекция №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 = ;

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

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) уравнение (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.

U(P)= (5)

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

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

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

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

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

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

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.

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

Список файлов лекций