При исследовании различных динамических систем часто используются имитационные модели. Согласно одному из определений, имитационная модель это определенный алгоритм, описывающий функционирование системы во времени, реализация которого осуществляется с помощью соответствующей машинной программы.
При невозможности описать весь спектр воздействующих на систему факторов в модель вводится элемент случайности. Таким образом, для работы моделирующей программы необходима генерация случайных чисел.
Компьютерная программа, работающая по определенному алгоритму, может генерировать только псевдослучайные числа. Результаты работы различных алгоритмов проверяются статистическими тестами. Для генерации случайных чисел в программу подставляются случайным образом начальные условия. Для моделирования могут быть необходимы случайные величины с самыми разными характеристиками, но обычно, сначала генерируется базовая последовательность случайных чисел. Совокупность независимых, равномерно распределенных на отрезке [0,1] случайных величин Ri , (i=0,1…) называется последовательностью базовых случайных чисел. Гистограмма, показывающее равномерное распределение величин представлена на рисунке 1.
Рисунок 1 – Гистограмма равномерного распределения величин
Алгоритм середины квадратов Неймана
Первый алгоритм для получения псевдослучайных чисел был предложен Дж. Фон Нейманом в 1951 г. Он называется методом середины квадратов.
Пусть задано случайно выбранное 4-значное число R0 = 0.9876.
Возведя его в квадрат, получим 8-значное число R02 = 0.97535376.
Выбрав четыре средних цифры этого числа, получим следующее псевдослучайное число: R1 = 0.5353.
Повторив операцию возведения в квадрат R12 = 0,28654609 и процедуру выбора средних цифр числа R12, получим очередное псевдослучайное число: R2 = 0.6546.
Таким образом, получен очень простой рекуррентный алгоритм генерирования псевдослучайных точек, который называется методом Неймана или методом серединных квадратов. Для запуска алгоритма достаточно задать некоторое произвольное начальное число R0. Разным стартовым числам, вообще говоря, будут соответствовать разные последовательности чисел.
Блок-схема данного алгоритма представлена на рисунке 2.
Рисунок 2 – Блок-схема реализации метода середины квадратов Неймана
Программная реализация данного метода на языке программирования java script представлена на рисунке 3.
Рисунок 3 – Реализация метода на языке программирования java script
Этот алгоритм не оправдал себя: получалось больше чем нужно для равномерного распределения малых значений Ri. Кроме того, весьма часто последовательность случайных чисел оказывается слишком короткой, т.е. после некоторого Ri числа начинают повторяться. Также в последовательности может вообще отсутствовать случайность, как если в качестве начального числа выбрано R0=0.4500.
Модифицированный метод Неймана
Значительно лучшие результаты дает определенная модификация алгоритма Неймана, состоящая в том, что вначале произвольно выбирается пара чисел R0 и R1. Составляется их произведение R0*R1, и его средние цифры используются в качестве числа R2. Процесс повторяется для R1, R2 с получением R3 и т.д.
Блок-схема данного алгоритма представлена на рисунке 4.
Рисунок 4 – Блок-схема реализации модифицированного метода Неймана
Программная реализация данного метода на языке программирования java script представлена на рисунке 5.
Рисунок 5 – Реализация модифицированного метода Неймана на языке программирования java script
Такой рекуррентный метод дает меньшее отклонение образуемых псевдослучайных чисел от равномерного распределения, нежели метод Неймана.