Навигация
3. Применение ГСЧ
Одна из задач, в которых применяются ГСЧ, – это грубая оценка объемов сложных областей в евклидовом пространстве более чем четырех или пяти измерений. Разумеется, сюда входит и приближенное вычисление интегралов. Обозначим область через R; обычно она определяется рядом неравенств. Предположим, что R – подмножество n‑мерного единичного куба K. Вычисление объема множества R методом Монте-Карло сводится к тому, чтобы случайным образом выбрать в K большое число N точек, которые с одинаковой вероятностью могут оказаться в любой части K. Затем подсчитывают число M точек, попавших в R, т.е. удовлетворяющих неравенствам, определяющим R. Тогда M/N есть оценка объема R. Можно показать, что точность такой оценки будет довольно низкой. Тем не менее, выборка из 10 000 точек обеспечит точность около 1%, если только объем не слишком близок к 0 или 1. Такой точности часто бывает достаточно, и добиться лучшего другими методами может оказаться очень трудно.
В качестве примера можно рассмотреть вычисление площади фигуры, заданной некоторой системой неравенств. Пусть фигура будет определена следующим образом:
.
Сначала необходимо определить прямоугольную область, из которой будут выбираться случайные точки. Это может быть любая область, полностью содержащая фигуру, площадь которой требуется найти. Возьмем в качестве исходной области прямоугольник с координатами углов (0; –1) – (1; 1). Будем последовательно генерировать точки, равномерно распределенные внутри этого прямоугольника, и для каждой точки проверять неравенства, описывающие фигуру. Если точка удовлетворяет всем неравенствам, значит, она принадлежит фигуре. При достаточно большом числе таких экспериментов отношение числа точек NF, удовлетворяющих неравенствам, к общему числу сгенерированных точек NR показывает долю площади прямоугольника, которую занимает фигура. Площадь прямоугольника SR известна (в нашем случае она равна 2), площадь фигуры SF вычисляется тривиально:
.
Очевидно, что для такой простой области можно легко посчитать область через определенный интеграл. Тем не менее, описанный метод применим и в случае гораздо более сложных фигур, когда рассчитать площадь другим способом становится слишком сложно.
Другим примером приближенного взятия определенного интеграла с помощью ГСЧ является вычисление объема шара в n‑мерном пространстве. Объем n‑мерного шара выражается формулой:
,
где Γ(z) – некоторая гамма-функция, определяемая следующим соотношением:
Γ (z+1)=z·Γ(z),
Γ(1)=1.
Таким образом, для натуральных z гамма-функция равна факториалу z. Для вычисления знаменателя можно воспользоваться известным значением
:
.
Можно показать, что для шара единичного радиуса при увеличении размерности n объем стремится к нулю. Наиболее просто это можно объяснить тем, что числитель растет со скоростью степенной функции, а знаменатель – с факториальной. Таким образом, для больших n метод вычисления через случайные числа будет давать значительные погрешности.
4. Генерирование равномерно распределенных случайных чисел
Почти повсеместно используемый метод генерирования псевдослучайных целых чисел состоит в выборе некоторой функции f, отображающей множество целых чисел в себя. Выбирается какое-нибудь начальное число х0, а каждое следующее число порождается с помощью рекуррентного соотношения:
xk+1 = f(xk)
Число xk часто называется зерном (англ. seed) ГСЧ и полностью определяет текущее состояние ГСЧ и следующее генерируемое значение.
Поначалу функции f выбирались как можно более сложные и трудно понимаемые. Например, f(x) определялась как целое число, двоичное представление которого составляет средний 31 разряд 62‑разрядного квадрата числа x (модификация метода средин квадратов). Но отсутствие теории относительно f приводило к катастрофическим последствиям. Для метода средин квадратов это уже упоминавшееся зацикливание при обращении очередного числа в нуль. Поэтому уже довольно давно перешли к использованию функций, свойства которых вполне известны. Всякая последовательность целых чисел из интервала (0, 231–1) должна содержать повторения самое большое после 231≈109 элементов. Используя теорию чисел, можно выбрать такую функцию f, для которой наперед будет известно, что ее период максимально возможный или близкий к максимальному. Этим избегается преждевременное окончание или зацикливание последовательности. Дальнейшее использование теории чисел может более или менее предсказать характер последовательности, давая пользователю некоторую степень уверенности в том, что она будет достаточно хорошо моделировать случайную последовательность чисел.
Представим генерирование чисел в диапазоне [0; 1] рекуррентым методом графически (см. рис. 1). Очевидно, функция f(x) должна быть определена на всем отрезке [0; 1] и иметь на этом отрезке непрерывную область значений [0; 1], в противном случае генерируемые числа будут составлять лишь несобственное подмножество указанного отрезка.
а) б)
Рис. 1. Графическое представление рекуррентного ГСЧ:
а) с «плохой» функцией f(x); б) с «хорошей» функцией f(x).
Считается, что функция f(x) тем лучше подходит для генерирования случайных чисел, чем более плотно и равномерно ее график заполняет область xÎ[0; 1], yÎ[0; 1]. Например, функция, приведенная на рис. 1, а, будет давать последовательность чисел с сильной корреляционной зависимостью соседних элементов. В случае функции, приведенная на рис. 1, б, эта зависимость будет значительно слабее.
В настоящее время широкое распространение получили линейные конгруэнтные ГСЧ. В таком ГСЧ каждое следующее число получается на основе единственного предыдущего, при этом используется функция f вида:
f(х) = (ах+с) mod m,
где для n‑разрядных двоичных целых чисел m обычно равно 2n.
Конгруэнтный ГСЧ выдает псевдослучайные целые числа в интервале (0, m). Параметры x0, a и c – целые числа из той же области, выбираемые исходя из следующих соображений:
1. x0 может быть произвольно. Для проверки программы возможно x0=1. В дальнейшем в качестве x0 можно брать текущее время, преобразованное в число из интервала (0, m). Такой подход обеспечивает различные последовательности для различных запусков программы.
2. Выбор a должен удовлетворять трем требованиям (для двоичных машин):
a) a mod 8 = 5;
b) 
;
c) двоичные знаки а не должны иметь очевидного шаблона.
Похожие работы
... на выходах генератора формируются два числа (на выходе счётчика 2 и выходе сумматора 10). Первое из них соответствует нечёткому значению интервала времени, необходимого для достижения поставленной цели, а второе - нечёткому значению результата настройки. В отличие от известных предложенный метод (алгоритм) позволил создать простой по своей структуре генератор случайных чисел, у которого наработка
... η с функцией распределения F(y) из случайной величины ζ, равномерно-распределенной в интервале [0,1], используются различные методы. К основным методам моделирования случайных чисел с заданным законом распределения относятся: - метод обратной функции - метод отбора или исключения - метод композиции. 2. Метод обратной функции Если ζ- равномерно-распределенная на интервале ...
... величины, распределенной по показательному закону, может служить время между появлениями двух последовательных событий простейшего потока.2.2. Начало алгоритмизации. Для получения двух последовательностей из 50 случайных чисел с показательным и нормальным законами распределения необходимо организовать цикл, который будет выполнятся 50 раз. Внутри цикла будем пользоваться функцией из Турбо Паскаля ...
... нельзя в полной мере назвать случайными, поскольку между ними имеется зависимость, а также наличие периодов в последовательности псевдослучайных чисел. К алгоритмическим методам получения ГСЧ относиться метод серединных квадратов, предложенный в 1946 г. Дж. фон Нейманом. Метод серединных квадратов Имеется некоторое четырехзначное число R0. Это число возводится в квадрат и заносится в R1. Далее ...
0 комментариев