6Simulation systems Лекция 21 Реш ур-я (Материалы к лекциям), страница 2

Заметим, что событие, заключающееся в том, что пьяный попадет из точки Р в точку Q, равносильно тому, что он либо попадет из точки Р в точку Р₁, оттуда в Q, либо попадет из Р в Р₂, а оттуда в Q, либо из Р в Р_3, затем в Q, либо из Р в Р₄ и затем в Q. Здесь опять-таки через Р₁, Р₂, Р₃, Р₄ обозначаем четыре соседних к Р узла. Так как вероятности попадания из Р в каждый из Р₁, Р₂, Р₃, Р₄ равны 1/4, то по теореме сложения вероятностей

U(Р,Q)= (6)

Таким образом, мы пришли к конечно-разностному уравнению (1), связывающему не значения функции в точках, а вероятности. Кроме того, вероятность U(P,Q) удовлетворяет следующим краевым условиям:

где Q’’ и Q - граничные узлы. (7)

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

Если промоделировать блуждания пьяного N раз, заставляя его каждый раз выходить из точки Р₁ и сосчитать количество М испытаний, при которых путь пьяного оканчивается в точке Q, то будем иметь:

(8)

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

Чтобы решить задачу Дирихле с более общими краевыми условиями, необходимо немного обобщить приведенную вероятностную схему, а именно: предположим дополнительно, что после того, как пьяный сваливается в ров в граничном узле Q, с него взимается штраф, равный f(Q).

Ясно, что величина штрафа, уплаченного пьяным, вышедшим из точки Р, является случайной величиной.

Обозначим ее (P). Величина штрафа может принимать значение:

f(Q₁), f(Q₂)_{, .... ,}f(Q_S),

где - совокупность всех граничных узлов.

Вероятность заплатить штраф f(Q_i) равна U(P,Q_i). Значит математическое ожидание штрафа определится так:

Ясно, что величина (Р) зависит от точки выхода Р. Эта функция, как и ранее, удовлетворяет разностному уравнению:

Действительно, подставив Q=Q_i в полученное ранее

U(Р,Q_i)=

и умножив обе части на f(Q_i), мы получим после суммирования по всем граничным узлам Q_i приведенное равенство для (Р).

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

U(Q,Q) =1

U(Q’’,Q)=0 (Q’’Q)

в правой части выражения для (Р) пропадут все слагаемые, кроме одного

(Q) = U(Q,Q) f(Q) = f(Q);

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

Пример. Пусть U(X,Y)- решение уравнения Лапласа: ( т.е. F(X,Y)=0) в единичном квадрате 0X1, 0Y1, удовлетворяющее граничным условиям U(X,0)=0, U(0.Y)=0, U(1,Y)=Y, U(X,1)=X.

Вычислим значение функции в центре квадрата U(1/2, 1/2).

Выберем в квадрате сетку с шагом h=1/4 и перенумеруем узлы.

Для уравнения Лапласа =g_Ki, так, что  равно значению g в том узле, в котором случайная цепь перехода «пьяного» попадает на границу. Возле каждого граничного узла в прямоугольной рамке проставлено значение g для нашего примера.

Для построения случайных цепей воспользуемся таблицей случайных цифр. Если случайная цифра  окажется 0 или 4, то будем перемещаться в соседний узел справа; если  равно 1 или 5, то будем перемешаться влево; если  равно 2 или 6, то будем перемещаться вверх; если =3 или 7, то перемещаемся вниз; значения =8 или 9 опускаем. Предположим, мы получили следующий ряд случайных чисел:

8,6,5,1,5,9,0,7,9,5,6,6,1,5,5,6,6,4,3,4,5,6,5,5,8,1,2,3,3,2,9,4,3,7,7,5,7,8,0,2,5,2

Соответствующие этим цепям значения  равны 0, 0, 0, 1/2, 1/4, 0, 0, 0, 0, 1/4

Среднее арифметическое этих величин дает нам приближенное значения решения в точке (1/2, 1/2).

U(1/2, 1/2) 

Точное решение рассмотренной задачи U(1/2, 1/2)=0,25.

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

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

Пусть узел Р имеет координаты (Хо,Yo). . Тогда соседние узлы имеют координаты (при h=1): P₁=(Хо+1,Yo); P₂=(Хо,Yo+1); P₃=(Хо-1,Yo); P₄=(Хо,Yo-1).

Обозначим текущие координаты пьяного через (X,Y). В начальный момент имеем X=Xo, Y=Yo. Переход пьяного из узла Р в соседний узел соответствует прибавлению (или вычитанию) единицы к одной из координат X или Y. После того, как пьяный перейдет из узла Р в узел Рi, процесс повторяется. Только каждый раз необходимо проверять, не попал ли уже пьяный на границу города.

В процессе решения надо всегда помнить величины (Хо,Yo) - координаты начальной точки Р и (Х,Y) - текущие координаты пьяного.

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

Пусть число узлов при j-м блуждании равно _j. Тогда время решения Т определится:

Т=t(₁+₂+....+_N)

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

,

где  - погрешность решения, D(P)- дисперсия величины (P), а max f(Q)берется по всем граничным узлам решетки.

Число узлов, проходимых пьяным за одно блуждание, есть тоже случайная величина. Поэтому сумма этих величин приближенно равна математическому ожиданию величины, умноженной на N. Таким образом, время решения равно:

T  t N(E)

Среднее число шагов при блуждании E зависит от формы решетки и от шага h. Можно показать, что число блужданий зависит только от линейных размеров решетки, если принять h=1. Если r - радиус области G, то E_  r². Вообще говоря, время решения задачи имеет порядок

T 

Точность решения зависит еще от того, насколько мелкой выбрана решетка. Например, если мы хотим получить решение с точностью =0,001 от максимального значения f(Q), то тогда r~100, N~10000 и Т~ t 10⁸. Если считать, что вычисления ведутся на компьютере, где один шаг можно выполнять за 100 мксек, то полное время решения оказывается равным:

Т~ 10⁴ сек ~ 3 часа.

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

Более общие задачи

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

где ac-b²>0.

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

Можно также рассматривать и более общие краевые условия.

Так условие вида

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

В качестве примера нестационарной задачи рассмотрим уравнение теплопроводности

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

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

и начальному условию

Выбираем последовательность моментов времени: t=0, 1, 2, ... , K, ... .

Если выбрать разумное соотношение между масштабом времени и шагом решетки, то придем к уравнению:

U_K(P)=

где Р₁, Р₂, Р₃ и Р₄ - четыре соседних к Р узла.

Рассмотрим теперь следующий случайный процесс для того, чтобы найти значение U в точке Р в момент времени К. Решетку мы можем считать как и в предыдущей задаче, но теперь пьяный должен проходить за единицу времени ровно один квартал.

Предположим, что пьяный выходит из перекрестка Р и с равной вероятностью попадает в один из соседних перекрестков; оттуда он аналогично передвигается дальше, причем, если пьяный попадает на границу, то там остается. Весь процесс продолжается не более К шагов.

Если за К шагов пьяный не успел свалиться в ров, а оказался во внутреннем узле Р, то он платит штраф:

Если же он свалился в ров до истечения срока, то он платит штраф , где Q - точка границы, куда свалился пьяный.

Всего таких блужданий проделаем N. Суммарный штраф, поделенный на N есть приближенное значение решения конечно-разностного уравнения теплопроводности и приведенными граничными условиями.....

Чтобы показать это, вычислим математическое ожидание штрафа. Обозначим через V_K(P,Q) вероятность того, что через К шагов пьяный, выйдя из точки Р, окажется в точке Q. Условие которому удовлетворяет эта вероятность найти достаточно просто:

V_K(P,Q)= (A)

Величина V_K(P,Q) удовлетворяет следующим граничным условиям:

(при Q’’=Q,где Q’’ и Q - граничные узлы) (Б)

Заметим, что Vо(P,Р)=1, V_о(P,Q)=0, где P, Q - любые узлы (внешние и внутренние).

Наконец, V_K(P,Q)=0, так как из внешнего узла Q нельзя пройти во внутренний узел Р. Найдем математическое ожидание штрафа, заплаченного пьяным при выходе из точки Р. Величина штрафа принимает значение

q(P₁), q(P₂), ... , q(P_r), f(Q₁), f(Q₂), ... , f(Q_S) c вероятностями соответственно V_K(P,P₁), V_K(P,P₂), ... , V_K(P,P_r), V_K(P,Q₁), V_K(P,Q₂), ... , V_K(P,Q_S).

Следовательно, математическое ожидание штрафа равно

(С)

Подставим Q=Q_j в (А) и помножим обе части на f(Q_j).

Затем подставим Q=P_i и помножим на g(P_i). Сложим все произведения и получим: