ВГУЭС Владивосток Моделирование случайных процессов Кийкова Елена Валерьевна Кафедра ИИКГ. - презентация

1 ВГУЭС Владивосток Моделирование случайных процессов Кийкова Елена Валерьевна Кафедра ИИКГ

2 К общим принципам имитации случайных воздействий на ЭВМ относятся: 1) Формирование базовой случайной величины (CB); 2) Преобразование базовой случайной величины в значения случайных величин распределенных по требуемому закону.

3 Способы формирования базовой случайной величины Непрерывная СВ имеет равномерное распределение в интервале [a,b], если ее функции плотности (рис. 1) и распределения (рис. 2) соответственно примут вид:

4 Рис.1 Функция плотности для равномерного распределения

5 Рис.2 Функция равномерного распределения

6 Определим числовые характеристики случайной величины принимающей значения x: математическое ожидание (уравнение 1), дисперсию (уравнение 2) и среднее квадратическое отклонение (уравнение 3): (1)

7 (2) (3)

8 При моделировании систем на ЭВМ приходится иметь дело со случайными числами интервала [0,1], когда границы интервала a=0, b=1.

9 Математическое ожидание такого распределения -, дисперсия - и среднеквадратическое отклонение -. ЭВМ оперирует с n-разрядными числами, поэтому на ЭВМ вместо непрерывной совокупности равномерных случайных чисел интервала [0,1] используют дискретную последовательность случайных чисел того же интервала. Закон распределения такой дискретной последовательности называют квазиравномерным распределением.

10 Получение квазиравномерных чисел Случайная величина, имеющая квазиравномерное распределение в интервале [0,1], принимает значения с вероятностями.

11 Математическое ожидание и дисперсия квазиравномерной СВ соответственно имеют вид:

12 В первом случае используем соотношение: Во втором случае имеем соотношение:

13 Таким образом, МО квазиравномерной случайной величины совпадает с МО равномерной случайной последовательности интервала [0,1], а дисперсия отличается множителем (2 n +1)/(2 n -1), который при достаточно больших n близок к единице. На ЭВМ невозможно получить идеальную последовательность случайных чисел т.к. можно оперировать только с конечным множеством чисел, и для получения значений х случайной величины используют формулы; поэтому такие последовательности называют псевдослучайными.

14 Моделирование случайных величин При моделировании дискретных случайных величин наиболее часто используются два метода: метод последовательных сравнений; метод интерпретации.

15 Метод последовательных сравнений Число r последовательно сравнивают со значением суммы Р1+Р2+..., где Р1 - вероятность наименьшего значения СВ Y, Р2 вероятность второго по величине значения. При первом выполнении условия r > проверка прекращается и дискретная СВ Y считается принявшей значение у i.

16 Процесс можно ускорить, применяя методы оптимизации перебора: дихотомии, ранжирования Р и т.д. Величины P i рассчитывают по функциям распределения вероятности, соответствующим моделируемому закону.

17 Метод интерпретации Метод основан на физической трактовке моделируемого закона распределения. Например, биномиальное распределение описывает число успехов в n независимых испытаниях с вероятностью успеха в каждом испытании Р и вероятностью неудачи g = 1 - Р. При моделировании этого распределения с помощью метода интерпретации выбирают n независимых СЧ, равномерно распределенных на интервале [0, 1], и подсчитывают количество тех из них, которые меньше Р. Это число и является моделируемой СВ.

18 Способы получения случайных чисел Существуют два способа формирования случайных чисел (CЧ): 1) с помощью специального физического датчика; 2) с помощью специальных программ.

19 Физический способ Для более быстрого генерирования случайных чисел были созданы механизированные устройства: в конце 1930-х годов Кендалл и Бабингтон-Смит использовали быстро вращающийся диск для подготовки таблицы, содержащей случайных однозначных чисел. Позднее разработаны электрические схемы, основанные на произвольно пульсирующих электронных лампах, которые выдавали до 50 случайных чисел в секунду.

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

21 Преимуществом физических датчиков является высокая скорость формирования случайных чисел. К недостаткам физических датчиков случайных чисел относятся: 1) изготовление отдельного прибора; 2) не позволяют гарантировать качество последовательности непосредственно во время моделирования системы на ЭВМ, а также повторно получать при моделировании одинаковые последовательности чисел.

22 Программный способ Наибольшее применение в практике моделирования на ЭВМ для генерации последовательностей псевдослучайных чисел получили алгоритмы вида: представляющие собой рекуррентные соотношения первого порядка, для которых начальное число x 0 и постоянные параметры заданы.

23 1. Получаемые числа должны быть равномерно распределены в интервале [0,1] и не должны иметь корреляции друг с другом, в противном случае результаты моделирования могут оказаться полностью недействительными. 2. Чтобы генератор можно было использовать на практике, он должен обладать быстродействием и не требовать больших затрат памяти. Хороший арифметический генератор случайных чисел должен обладать следующими свойствами.

24 3. Генератор должен обеспечивать возможность точно воспроизводить заданный поток случайных чисел. 4. В генераторе должен быть предусмотрен простой способ получения отдельных потоков случайных чисел. Поток это просто часть последовательности случайных чисел, производимых генератором, очередной поток начинается в том месте, где заканчивается предыдущий.

25 Метод серединных квадратов Одной из исторически первых процедур получения псевдослучайных чисел была процедура, получившая название серединных квадратов, был предложен фон Нейманом и Метрополисом в 1940-х годах.

26 Пусть имеется 2n - разрядное число, меньше 1: возведем его в квадрат:, а затем возьмем средние 2n разрядов:, которые и будут очередным числом. Алгоритм получения последовательности случайных чисел методом серединных квадратов сводится к следующему:

27 Например: и т.д.

28 Недостатком этого метода является наличие корреляции между числами последовательности, а в ряде случаев случайность вообще может отсутствовать. Например:

29 Метод срединных квадратов вовсе не является случайным, то есть непредсказуемым (это наиболее существенный его недостаток). На самом деле, если мы знаем одно число, следующее число является полностью предопределенным, по­скольку правило его получения неизменно. Фактически, когда задается x 0, предопределяется вся последовательность чисел x i. Это замечание касается всех арифметических генераторов.

30 Линейные конгруэнтные генераторы Широкое применение при моделировании на ЭВМ получили линейные конгруэнтные процедуры генерации псевдослучайных последовательностей. В них последовательность целых чисел x 1,x 2,… определяется по рекурсивной формуле

31 где m (модуль), (множитель), c (приращение) и x 0 (начальное число или значение) являются неотрицательными целыми числами. Т. о., согласно формуле, для получения x i - нужно разделить на x i-1 +c, т. е. x i будет остатком этого деления.

32 Конгруэнтная процедура получения последовательностей случайных квазиравномерно распределенных чисел может быть реализована мультипликативным (с параметром c = 0) либо смешанным методом (с параметром c > 0).

33 Мультипликативный метод Задает последовательность неотрицательных целых чисел, не превосходящих m по формуле: Для машинной реализации, где p = 2, а q - число бит в машинном слове.

34 Алгоритм построения последовательности сводится к следующим шагам: 1)выбрать в качестве x 0 произвольное нечетное число; 2) вычислить коэффициент, где t любое целое положительное число; 3) найти произведение, содержащие не более 2q значащих разрядов;

35 4) взять q младших разрядов в качестве первого члена последовательности X 1 ; 5) определить дробь x 1 =X 1 /2 q - это и есть искомое число; 6) присвоить X 0 =X 1 ; 7) вернуться к 3 пункту.

36 Cмешанный метод Сначала выбирается значение m. Чтобы получить длинный период и высокую плотность величин x i в интервале [0, 1], величина m должна иметь большое значение. Самым удачным выбором является m=2 b, где b- число битов в слове задействованного компьютера.

37 БЛАГОДАРЮ ЗА ВНИМАНИЕ