--PAGE_BREAK--
2.3 Понятие о решение задачи Дирихле для уравнения Лапласа методом Монте-Карло
Пусть на плоскости дана область с кусочно-гладкой границей . В области построим квадратную сетку с шагом :
, (1)
Мы предполагаем, что сетка состоит из внутренних узлов и граничных узлов первого рода. Граничные узлы сетки образуют ее границу. Грубо говоря, граница представляет собой линейный ряд точек , аппроксимирующий криво-криволинейную границу области с точностью до .
Представим себе частицу , которая совершает равномерное случайное блуждание по узлам сетки (1). А именно, находясь во внутреннем узле сетки , эта частица за один переход с одной и той же вероятностью, равной 1/4, может переместиться в один из четырех соседних узлов: или в (шаг влево), или в (шаг вправо), или в (шаг вниз), или в (шаг вверх), причем каждый такой единичный переход совершенно случаен и не зависит от положения частицы и ее прошлой истории. Будем считать, что блуждание частицы заканчивается, как только эта частица попадет на границу ; в этом смысле граница представляет собой «поглощающий экран». Можно доказать, что с вероятностью, равной 1, блуждание точки через конечное число шагов заканчивается на границе.
Если частица начала свое блуждание с фиксированной внутренней точки сетки , то конечная совокупность последовательных положений этой частицы: где и , называется траекторией частицы (с шагами) или историей блуждания.
Равномерное случайное блуждание частицы на плоскости можно организовать с помощью равномерно распределенной последовательности одноразрядных случайных чисел, принимающих значения. Для этого, например, достаточно производить розыгрыш, т. е. случайную выборку из чисел , придерживаясь инструкции, указанной в таблице 1 (Приложение B); причем числа 8 и 9 переигрываются.
Случайные числа берутся из готовых таблиц или вырабатываются электронной машиной. Последний способ при работе на счетной машине предпочтительнее, так как он позволяет не загружать сильно память машины.
Пусть в точках границы Г области G определена некоторая функция . Перенесем эти значения на границу сетки . Например, для каждого граничного узла определим ближайшую по горизонтали (или вертикали) точку и положим
.
Для краткости введем обозначение
.
Пусть – вероятность того, что траектория частицы, вышедшей из узла сетки , закончится в граничном узле . Так как блуждание точки неизбежно заканчивается на границе в первой же точке выхода ее на границу, то
, (2)
где суммирование распространяется на все точки границы , причем
(3)
где – граничный узел.
Составим сумму
, (4)
где точка пробегает всю границу . Если функцию рассматривать как случайную величину, принимающую значения на границе , то сумма (4) представляет собой математическое ожидание (среднее значение) функции на границе для траекторий, начинающихся в точке («премия за выход на границу» из начальной точки ). Частица, начавшая свое случайное блуждание из внутреннего узла , после первого шага с вероятностью, равной 1/4, попадает в один из четырех соседних узлов. Поэтому случайные блуждания, начинающиеся в узле , в зависимости от вида траекторий распадаются на четыре категории новых случайных блужданий:
По формуле полной вероятности имеем
(5)
Отсюда, умножая обе части равенства (5) на граничные значения и суммируя по всем возможным значениям и , на основании формулы (4) получим
. (6)
Кроме того, в силу формулы (3) имеем
, (7)
если точка .
Рассмотрим теперь задачу Дирихле об отыскании функции , гармонической области и принимающей на ее границе заданные непрерывные значения . Согласно методу сеток эта задача сводится к нахождению значений искомой функции во внутренних узлах некоторой сетки при условии, что значения в граничных узлах известны и равны . Неизвестные определяются из системы линейных уравнений
(8)
Сравнивая формулы (8) с формулами (6), (7), мы усматриваем, что они совпадают с точностью до обозначений. Следовательно, искомые неизвестные можно рассматривать как математические ожидания . Величины допускают экспериментальное определение. Рассмотрим достаточно большое число равномерных случайных блужданий частицы по узлам сетки , исходящих из фиксированного узла и заканчивающихся на границе . Пусть соответствующие точки выхода частицы на границу . Заменяя математическое ожидание эмпирическим математическим ожиданием, будем иметь
. (9)
Формула (9) дает статистическую оценку величины и может быть применена для приближенного решения задачи Дирихле. Метод решения задач, основанный на использовании случайных величин, получил общее название метода Монте-Карло.
Заметим, что с помощью формулы (9) можно непосредственно найти приближенное значение решения задачи Дирихле в единственной фиксированной точке сетки , не зная решения задачи для остальных точек сетки. Этим обстоятельством метод Монте-Карло для задачи Дирихле резко отличается от обычных стандартных способов решения этой задачи.
Интересно отметить, что вероятность , в силу формулы (4), представляет собой аналог функции Грина для задачи Дирихле в области. Эта величина может быть найдена экспериментально на основании формулы (9), если задать следующие граничные условия:
.
Построив такую функцию Грина, мы получаем возможность, применяя формулу (9), просто
находить приближенное решение задачи Дирихле для области данной границей при любых граничных значениях .
Недостатком рассмотренного варианта метода Монте-Карло для задачи Дирихле является слабая сходимость по вероятности при эмпирического математического ожидания
к математическому ожиданию . Чтобы устранить это неблагоприятное обстоятельство, используют различные модификации случайных блужданий. Кроме того, при решении задачи полезно учитывать также, что блуждание частицы , начинающееся в точке
автоматически является случайным блужданием частицы, начинающимся в любой промежуточной точке траектории этой частицы.
2.4 Метод «блуждания» по сферам
Укажем другой метод Монте-Карло для решения задачи Дирихле для уравнения Лапласа, не связанный с разностными уравнениями. Пусть задана ограниченная связная область и точка . Определим случайную траекторию следующим образом: положим ; далее, если точка известна, то построим окружность произвольного радиуса , расположенную внутри , и на этой окружности выберем случайную точку (рис. 2, Приложение C).
Таким образом, , где , и угол равномерно распределен в интервале .
Приведем теорему: если функция удовлетворяет в области уравнению Лапласа
, (1)
то при каждом и при любых математическое ожидание равно значению в начале траектории.
Доказательство. Придадим более точный смысл утверждению о произвольности радиуса . Будем считать, что задана некоторая плоскость , которая тождественно равна нулю при всех , превосходящих минимальное расстояние от до границы , а также при ; случай также допускается; и выбор осуществляется в соответствии с плотностью . Пусть – плотность распределения точки в . Тогда математическое ожидание величины равно
.
По теореме о среднем значении гармонической функции
.
Поэтому
.
При точка и . Применяя индукцию, получим утверждение теоремы.
Построение траекторий рассмотренного типа в трехмерном случае иногда называют блужданием по сферам.
Приведенную выше траекторию можно использовать для приближенного решения задачи Дирихле. Пусть на границе области задана ограниченная функция . Обозначим через искомое решение, удовлетворяющее внутри уравнению (1) и обращающееся в при .
Фиксируем достаточно малую окрестность границы (рис. 3, Приложение D). Чтобы вычислить , будем строить траектории вида до тех пор, пока случайная точка не попадет в . Пусть – ближайшая к точка границы . Можем считать, что значение случайной величины приближенно равно . Построив траекторий такого типа, получим значения , по которым оценивается искомое решение
. (2)
Замети, что сходимость по вероятности
, (3)
когда не вытекает из теоремы Хинчина, говорящей о том, что последовательность одинаково распределенных независимых величин, у которых существуют математические ожидания, подчиняется закону больших чисел, так как в сумме (3) фигурируют различных случайных величин, различающихся правилами выбора Можно, однако воспользоваться другой формой закона больших чисел – теоремой Чебышева:
Если величины независимы и существует и , то при
(Доказательство этой теоремы легко получить, применяя к величине неравенство Чебышева – ).
В нашем случае все , а дисперсии , где . В самом деле, как известно, максимум и минимум гармонической функции достигаются на границе области, так что при всех .
Такой метод расчета считается более быстрым, чем метод использования разностных уравнений, так как вдали от границы позволяет делать большие шаги . Обычно рекомендуют выбирать максимально возможные радиусы .
Данный метод был предложен Дж. Брауном и обоснован М. Мюллером, который доказал, в частности, что вероятность того, что траектория никогда не попадет в , равна нулю. Дальнейшее развитие метода – организация зависимых испытаний, решение уравнений более общего вида, использование вместо кругов других фигур (для которых известны функции Грина).
Задача Дирихле для уравнения Пуассона и ее решение методом Монте-Карло с использованием метода сеток
В ограниченной связной области плоскости с простой границей рассмотрим дифференциальной уравнение с частными производными
(1)
где – искомая функция. Уравнение (1) при называется уравнением Лапласа, а при – уравнением Пуассона.
Применяя метод сеток для решения краевых задач, прежде всего появляется задача замены дифференциальных уравнений разностными уравнениями. Аппроксимации дифференциального уравнения разностным заключается в том, что производные, входящие в дифференциальное уравнение, заменяются линейными комбинациями значений функции в узлах сетки по тем или иным формулам численного дифференцирования. В зависимости от того, какими формулами численного дифференцирования будем пользоваться, получим различную точность аппроксимации дифференциального уравнения разностным.
Предположим, что на границе задана некоторая функция (часто пишут g(
S), где — длина дуги границы, отсчитываемая от какой-нибудь фиксированной точки). Требуется найти такое решение уравнения (1), которое на границе совпадает с :
. (2)
Задачу об отыскании решения уравнения
(3)
удовлетворяющего граничному условию, называют задачей Дирихле для уравнения Пуассона.
Для приближенного решения этой задачи выбирают на плоскости достаточно мелкую квадратную сетку с шагом (рис.1, Приложение А). Координаты узлов этой сетки пусть будут, а значения для краткости обозначим и . Узел называютвнутренним, если и он, и все четыре соседних с ним узла принадлежат , в противном случае узел , принадлежащей называют граничным.
Во внутреннем узле уравнение заменим разностным
(4)
которое перепишем в виде
(5)
В граничных узлах
. (6)
Решение алгебраической системы при приближается к решению задачи Дирихле для уравнения (1).
Перенумеруем все узлы, принадлежащие (в произвольном порядке), и перепишем в том же порядке уравнения (3), (4). Тогда получим систему вида
(7)
Матрица этой системы имеет следующую структуру: внутреннему узлу с номером отвечает строка , в котором четыре элемента равны ¼, а остальные – нули; граничному узлу с номером отвечает строка; все диагональные элементы=0. (Все собственные значения такой матрицы по абсолютной величине меньше единицы.) Свободные члены этой системы, если узел внутренний, и , если узел граничный.
Один из методов решения системы (5) является метод Монте-Карло. Построим данный метод для расчета — значения решения в одном заранее заданном узле. Выберем матрицу переходов
Здесь – символ Кронекера:.
Далее строим следующую цепь:
1)
2) если узел внутренний, то с одинаковой вероятностью ¼ выбираем в качестве номер одного из соседних с ним узлов;
3) если узел граничный, то цепь останавливается:. Рассчитываем вес вдоль цепи по правилу: пока цепь не попала на границу, далее . Вычисляем случайную величину по формуле
, (8)
где – номер первого выхода цепи на границу.
В формуле (6) все вычисляются по формуле и лишь последнее равно значению .
Замечание. Если вместо граничных условий (2) заданы более сложные условия, например:
,
то уравнения (6) наряду с будут содержать также значения в некоторых узлах. И случайная цепь, попав на границу, останавливаться не будет.
Если количество цепей достаточно велико, то решение задачи Дирихле в узле определяется по формуле
. (9) продолжение
--PAGE_BREAK--