Техника моделирования случайных процессов

 

Моделирование случайных процессов – мощнейшее направление в современном математическом моделировании. Событие называется случайным, если оно достоверно непредсказуемо. Случай­ность окружает наш мир и чаще всего играет отрицательную роль в нашей жизни. Однако есть обстоятельства, в которых случайность может оказаться полезной. В сложных вычислениях, когда искомый результат зависит от результатов мно­гих факторов, моделей и измерений, можно сократить объем вычислений за счет случайных значений значащих цифр.

При вероятностном моделировании используют различные методы, которые позволяют решать задачи из различных областей. Ниже перечислены сферы приме­нения вероятностных методов.

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

Метод имитационного моделирования: моделирование систем массового обслу­живания, задачи АСУ, АСУП и АСУТП, задачи защиты информации, моделирова­ние сложных игровых ситуаций и динамических систем.

Метод стохастической аппроксимации: рекуррентные алгоритмы решения задач статистического оценивания.

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

Другие методы: вероятностные методы распознавания образов, модели адапта­ции, обучения и самообучения.

При компьютерном математическом моделировании случайных процессов нель­зя обойтись без наборов так называемых случайных чисел, удовлетворяющих заданному закону распределения. На самом деле эти числа генерирует компьютер по определенному алгоритму, т.е. они не являются вполне случайными хотя бы потому, что при повторном запуске программы с теми же параметрами последова­тельность повторится; такие числа называют “псевдослучайными”.

Большинство программ – генераторов случайных чисел – выдают последовательность, в которой предыдущее число используется для нахождения последующего. Первое из них – начальное значение. Все генераторы случайных чисел дают последовательности псевдослучайных чисел, повторяющиеся после некоторого количества членов, называемого периодом, что связано с конечной длиной машинного слова. Самый простой и наиболее распространенный метод – метод вычетов, или линейный конгруэнтный метод, в котором очередное случайное число х nопреде­ляется “отображением”:

 

xn= (axn-1+ с) mod m,

 

где а, с, m – натуральные числа, mod – так называемая функция деления по модулю (остаток от деления одного числа на другое по модулю). Наибольший возможный период датчика равен m, но он зависит от a и с. Ясно, что чем больше период, тем лучше; однако реально наибольшее m ограничено разрядной сеткой ЭВМ. В любом случае используемая в конкретной задаче выборка случайных чисел должна быть короче периода, иначе задача будет решена неверно.

Для не слишком требовательного пользователя обычно достаточны возможности датчика (генератора) случайных чисел, встроенного в большинство языков программирова­ния. Так, в языке Паскаль есть функция random, значения которой – случайные числа из диапазона [0,1]. Ее использованию обычно предшествует использование процедуры randomize, служащей для начальной “настройки” датчика, т.е. получения при каждом из обращений к датчику разных последовательностей случайных чисел. Для задач, решение которых требует очень длинных некоррелированных последова­тельностей, вопрос осложняется и требует нестандартных решений. Равномерно распределенные случайные числа – простейший случай.

 

Пример моделирования случайного процесса

 

Метод статистического моделирования имеет множество приложений. Чаще всего он заключается в том, что для решения математической задачи строится некоторая случайная величина , такая, что математическое ожидание этой случай­ной величины Е() является значением искомого решения. Проводя достаточное количество раз эксперимент со случайной величиной , можно найти приближенное решение как среднее значение результатов эксперимента.

Рассмотрим задачу Бюффона. На поле, разграфленное параллельными прямыми, расстоя­ние между которыми L, бросается наугад игла длиной l (рис. 3.3). Какова вероят­ность того, что игла, упав, пересечет хотя бы одну прямую?

 

Рис. 3.3. К задаче Бюффона

 

Ж.Бюффон (XVIII в.) подсчитал: р = 2 l /L. Таким образом, если L = 2 l, то р = 1/. Кроме того, р = N1/N, где N – число бросаний, N1– число пересечений иглы с линиями.

Относительная доля случаев, когда игла пересечет хотя бы одну из параллельных прямых, равно р = 1/. Это был один из старинных способов определения числа .

Имитационное моделирование проведем следующим образом. Примем L = 1 и l =1/2. “Иглу” будем “бросать” в квадрат размером, скажем, 20х20, левый нижний угол которого имеет координаты (0, 0). Положение концов иглы будем задавать с помощью датчика равномерно распределенных случайных чисел в диапазоне от 0 до 20. Точнее говоря, эти числа определят направление отрезка, вдоль которого находится очередная игла; для того, чтобы ее длина была равна 1/2, вторую из случайных точек – концов отрезка – подвинем вдоль него до достижения указанной длины иглы. В математическом отношении это сводится к следующей несложной процедуре:

 генерация координат точек А(х1,у1), B(x2,y2);

 определение координат точки В1(х1+ (х2– х1), у1+ (у2– у1)), где

 

.

 

Поскольку расстояние между горизонтальными линиями взято равным единице, а сами линии имеют целочисленные координаты по у, то определить, пересекает ли игла прямую, очень просто – да, если целые части ординат точек А и В1различны.

 

Программа 3.1. Решение задачи Бюффона.

 

Program Buffon;

uses Crt;

Var I, J, K, M, N: Integer; X1, X2, Y1, Y2, A1: Real;

Begin

Randomize; M:= 30000; N:= 1;

For I:= 1 To M Do

Begin

X1:= Random * 20; Y1:= Random * 20; X2:= Random * 20;

Y2:= Random * 20;

A1:= 0.5 / Sqrt(Sqr(X2 – X1) + Sqr(Y2 – Y1));

J:= Round (Y1); К:= Round (Y1 + A1 * (Y2 – Y1));

If J <> К Then N:== N + 1

End;

WriteLn(‘pi=’, (N/M): 8: 5);

End.