БАЗОВЫЕ ПСЕВДОСЛУЧАЙНЫЕ ЧИСЛА

БАЗОВЫЕ ПСЕВДОСЛУЧАЙНЫЕ ЧИСЛА

 КОНСТРУИРОВАНИЕ СЛУЧАЙНЫХ ЯВЛЕНИЙ В ИМ

Модели случайных явлений являются важной частью имитационных моделей.

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

Основным способом конструирования моделей случайных явлений является разработка их программных датчиков.

Достоинства:

Обеспечивается возможность управления процессом имитации (в частности, повторять реализации одних и тех же последовательностей, моделировать параллельно несколько независимых базовых псевдослучайных потоков).

Недостатки:

— программные датчики реализуются с помощью детерминированных алгоритмов, и поэтому формируемые с помощью них явления фактически не являются случайными: случайность лишь имитируется (отсюда название таких явлений – псевдослучайные).

Возникает проблема обеспечения высокого качества такой имитации (это приводит к необходимости контролировать качество имитации с помощью целого ряда статистических тестов);

— конструирование достаточно сложных случайных явлений (например, многомерных процессов) требует реализации весьма сложных в вычислительном отношении алгоритмов, что приводит к существенному увеличению вычислительной сложности ИМ.

Последовательность базовых чисел и производные случайные явления

Формирование реализаций случайных явлений любой сложности осуществляется в ИМ на основе следующей двухуровневой схемы:

— первый уровень — формирование базовой псевдослучайной последовательности : последовательности независимых равномерно распределенных чисел на отрезке [0,1]. В этих числах случайность, независимость и равномерность распределения лишь имитируются;

— второй уровень – функционально‑алгоритмическое преобразование базовых чисел в реализации случайных явлений с заданными статистическими характеристиками.

При таком подходе качество моделируемых случайных явлений практически полностью определяется качеством генераторов базовых псевдослучайных чисел (БПЧ).

Программные датчики базовых псевдослучайных чисел

Основные требования к программным датчикам БПЧ:

— хорошее качество (статистическая равномерность и независимость чисел);

— датчик должен давать достаточно большое число неповторяющихся чисел;

— высокое быстродействие;

— возможность исследования функционального влияния параметров датчика на его характеристики.

Существуют разные варианты алгоритмов генерации БПЧ. Одним из наиболее эффективных и распространенных является вариант реализации так называемого конгруэнтного метода.

 

О выборе величин М и Xо

 

Показано, что максимальная длина этого отрезка для мультипликативного датчика L= М – 1.

Для этого Xо и М должны быть взаимно простыми, а А – первообразным корнем уравнения =1(mod M) [КорнГ., КонТ. Справочник по математике для научных работников и инженеров. М.: Наука, 1973г.].

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

Кроме того, величина М влияет на быстродействие датчика. Составными частями операции у=х (mod M) являются деление и умножение на М. Если величину М брать равной М=2^b или M=10^d (b и d – длины машинного слова в двоичном и, соответственно, десятичном компьютере), то операции умножения и деления на М в таких ЭВМ будут сводиться к сдвигу точки мантиссы числа.

Такое определение М, с одной стороны, обеспечит максимальное быстродействие датчика, а с другой стороны – максимальную длину отрезка апериодичности.

Но есть и отрицательный эффект такого выбора: младшие разряды БПЧ при этом оказываются достаточно сильно коррелированными [10]. Чтобы снизить коррелированность значение М для соответствующего компьютера выбирают равным 2^b–1 или 10^d–1. Очевидно это приводит к снижению быстродействия датчика.

 О выборе значения параметра А.

Оно определяет качество имитации статистической равномерности датчика. Если рассмотреть заполнение единичного квадрата точками, соответствующими парам чисел xi и xi–1 идеального датчика базовых чисел, то оно должно быть статистически равномерным (рис.3.6 а)

а)                             б)

              Рис.3.6

Для рассматриваемого датчика БПЧ это принципиально невозможно, так как указанные пары чисел могу находиться в этом квадрате только на наклонных пилообразных участках линий зависимости xi от xi–1(рис.3.6 б) При этом существует бесконечное число точек этого квадрата, которые вообще не могут реализоваться. Однако дело не так «трагично», как кажется на первый взгляд. При выборе значения параметра А достаточно большим расположение пар БПЧ не будет отличаться от соответствующей выборки теоретически равномерно распределенного в единичном квадрате вектора в смысле любых критериев, связанных с усреднением по области с линейными размерами, существенно превышающими 1/А. Таким образом, чтобы имитировать статистическую равномерность, величина А должна быть достаточно большой.

Так для 40‑разрядной ЭВМ хорошим является датчик

 Хi = Хi–1(mod ),                                    (3.9)

 а для 36‑разрядной ЭВМ –

Хi = Хi–1(mod ).                                     (3.10)

БАЗОВЫЕ ПСЕВДОСЛУЧАЙНЫЕ ЧИСЛА

 КОНСТРУИРОВАНИЕ СЛУЧАЙНЫХ ЯВЛЕНИЙ В ИМ

Модели случайных явлений являются важной частью имитационных моделей.

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

Основным способом конструирования моделей случайных явлений является разработка их программных датчиков.

Достоинства:

Обеспечивается возможность управления процессом имитации (в частности, повторять реализации одних и тех же последовательностей, моделировать параллельно несколько независимых базовых псевдослучайных потоков).

Недостатки:

— программные датчики реализуются с помощью детерминированных алгоритмов, и поэтому формируемые с помощью них явления фактически не являются случайными: случайность лишь имитируется (отсюда название таких явлений – псевдослучайные).

Возникает проблема обеспечения высокого качества такой имитации (это приводит к необходимости контролировать качество имитации с помощью целого ряда статистических тестов);

— конструирование достаточно сложных случайных явлений (например, многомерных процессов) требует реализации весьма сложных в вычислительном отношении алгоритмов, что приводит к существенному увеличению вычислительной сложности ИМ.

1234Следующая ⇒

Поделиться: