1626435387-5d0ec7dd22f55dfcc65f3209f497fb0b (844202), страница 24
Текст из файла (страница 24)
Здесь проверяют частоту появления различных цифр в числах, реализуемых генератором(тест «проверка частот»); частоту различных двузначных чисел среди пар цифр, реализуемых подряд генератором (тест «проверка пар»);частоту различных интервалов между двумя последовательными нулями (тест «проверка интервалов»); частоту различных четырехзначных чисел среди четверок цифр, реализуемых подряд (тест «проверкакомбинаций»); частоту появления q одинаковых цифр подряд («тестсерий» длины q) и др.
В упомянутых тестах также активно используется критерий хи-квадрат.Для проверки качества стандартных случайных и псевдослучайныхчисел используют также критерий ω 2 Н. В. Смирнова, корреляционныекритерии и др.Сформулируем ряд замечаний относительно использования генераторов стандартных случайных чисел в параллельных вычислениях пометоду Монте-Карло (см. также [9, 31]).Напомним (см.
подраздел 1.11 данного пособия), что использованиеK одинаковых независимых процессоров путем распределения междуними независимых испытаний уменьшает трудоемкость статистического моделирования по сути в K раз (возможно эффективное использование и не одинаковых процессоров – см. формулу (1.23)).Если число процессоров K (а значит, и число испытанийn = n1 + ... + nK ) велико, то необходимый объем выборки стандартных случайных чисел тоже велик, поэтому целесообразно использованиедлиннопериодных псевдослучайных последовательностей, для которыхсуществует простой способ их разбиения на K частей необходимой длины. Метод вычетов (9.13) дает элементарный способ такого разбиения.148Пусть µ 1 – количество стандартных случайных чисел, требующихся для вычислений на одном процессоре. Для k-го процессора начальное число в методе вычетов с множителем Q выберем по формуле(k,µ)α0= uk,µ /2m ; uk,µ = uk−1,µ Qµ (mod 2m ).(9.19)Такой способ распределения случайных чисел по процессорам называют bf–генератором (сокращение от «big–frog»–генератор; см.
[9, 31]).В отделе статистического моделирования в физике Института вычислительной математики и математической геофизики СО РАН реализован bf-генератор с µ = 1026 (в качестве исходного используетсядатчик (9.13) с параметрами m = 128 и p = 50054) [31].
Такой генератор позволяет распределять исходную последовательность примернона 1012 процессоров, и соответствующих количеств псевдослучайныхчисел для каждого процессора с избытком хватает для вычислительныхпотребностей. Подробное описание генератора, программы вычисленияначальных значений (9.19), множителей Qµ = Qµ (mod 2m ), а также результаты тестирования датчика приведены в книге [31].Отметим, что в случае, когда µ невелико и равно количеству псевдослучайных чисел, требующихся для построения одной траектории,использование чисел (9.19) в качестве начальных для каждой траектории определяет lf–генератор (сокращение от «little–frog»–генератор; см.[9, 31]). В отличие от обычного способа распределения случайных чисел«подряд» (т.
е. в порядке обращения к генератору (9.13)) lf-генераторобеспечивает малое изменение результатов моделирования при маломизменении параметров задачи. В связи с этим lf-генератор более корректно проверяется решением типовых задач по сравнению с обычнымгенератором (9.13).9.7.
Использование квазислучайных чисел. Введем ряд определений и сформулируем ряд утверждений из работ [5, 32].Рассмотрим d-мерный единичный куб ∆(d) .ОПРЕДЕЛЕНИЕ 9.2. Последовательность точек x1 , . . . , xi , . . . называется равномерно распределенной в ∆(d) , если соотношениеnZ1Xg(xi )g(x) dx = limn→∞ n∆(d)i=1выполнено для любой функции g, интегрируемой в ∆(d) по Риману.149УТВЕРЖДЕНИЕ 9.8. Для того чтобы последовательность точекx1 , . . . , xi , . . . была равномерно распределенной в ∆(d) , необходимо и достаточно, чтобыдля любойподобласти A ⊆ ∆(d) выполнялось равенство limn→∞ Sn (A)/n = Ā; здесь Ā – объем области A, а Sn (A) –количество точек с номерами 1 ≤ i ≤ n, принадлежащих A.ОПРЕДЕЛЕНИЕ 9.3.
Отклонениемгруппы точек x1 , . . . , xn называется величина Dn = supx∈∆(d) Sn (Px ) − nP̄x , где Px – параллелепипед с диагональю Ox (здесь O – начало координат), объемом P̄x и сребрами, параллельными координатным осям.УТВЕРЖДЕНИЕ 9.9. Для того чтобы последовательность точекx1 , . . . , xi , . . . была равномерно распределенной в ∆(d) , необходимо и достаточно, чтобы выполнялось равенство limn→∞ (Dn /n) = 0.Чем быстрее убывает соотношение Dn /n, тем более равномерно распределена последовательность. Известно, что 1/2 ≤ Dn ≤ n [32], нонеясно, каков наилучший порядок роста Dn при n → ∞.Достаточно подробно исследованы определяемые ниже последовательности Холтона и Соболя, для которых выполнено равенствоDn = O(lnd n) (эти последовательности являются наиболее популярными примерами так называемых квазислучайных чисел).ОПРЕДЕЛЕНИЕ 9.4.
Пусть r1 , . . . , rd – попарно взаимно простыечисла (на практике обычно берут первые d простых чисел: r1 = 1,r2 = 3, r3 = 5, . . .). Последовательностью Холтона называетсямножество точек в ∆(d) с координатамиyi = pr1 (i), . . . , prd (i) .Здесь pr (i) = 0, a1 a2 . . . am−1 am (это запись в r-ичной системе счисления) при i = am am−1 . . . a2 a1 (это также запись в r-ичной системесчисления).ОПРЕДЕЛЕНИЕ 9.5.
Пусть в двоичной системе счисленияi = em em−1 . . . e2 e1 . Для всех j = 1, . . . , d определим(1)qi,j = e1 Vj(2)∗ e2 V j(m)∗ · · · ∗ em Vj.Здесь знаком ∗ обозначена операция поразрядного сложения по мо(s)дулю два в двоичной системе. Числа Vj берутся из специальныхтаблиц (подробности см. в [5, глава 7]). ЛПτ -последовательностьИ. М. Соболя образуют точкиzi = qi,1 , . . . , qi,d .150В книге [5] отмечена возможность совместного использования квазислучайных и псевдослучайных чисел для повышения эффективностиалгоритмов метода Монте-Карло, применяемых для решения задач высокой размерности.
Замечено также, что можно ожидать большего эффекта от применения квазислучайных чисел тогда, когда используютсяэкономичные (имеющие относительно небольшую величину трудоемкости) алгоритмы метода Монте-Карло.Имеется достаточно много публикаций, в которых приводятся результаты тестовых вычислений интегралов с использованием квазислучайных чисел в алгоритме 1.2 для X = ∆(d) . В случаях, когда размерность интегралов (1.8) была относительно невелика (d ≤ 10) и подынтегральные функции g(x) были гладкими, получались значительныевыигрыши по скорости сходимости к точному значению интеграла посравнению с алгоритмом 1.2, в котором использовались псевдослучайные числа.Как уже отмечалось в разделах 1, 4, 5 данного пособия, именно длятаких же размерностей d и функций g(x) оказываются эффективными дискретно-стохастические методы, описанные в книге [17].
Приросте размерности задачи (вплоть до бесконечности – как в соотношениях (7.14), (7.15)) и «сложности» исходных данных (подынтегральной функции, области интегрирования) эффективность использованиядискретно-стохастических модификаций и квазислучайных чисел заметно падает; в этих случаях используются «обычные» методы МонтеКарло с псевдослучайными числами.9.8.
Два важных замечания. В заключение этого раздела сформулируем два важных замечания.ЗАМЕЧАНИЕ 9.1. Как правило, генераторы псевдослучайных чисел,представленные в современных версиях языков программирования(F ORT RAN, СИ++ и др.), достаточно хорошо протестированы и дают статистически удовлетворительные результаты вычислений по методу Монте-Карло (во всяком случае, для задач, в которых используетсяумеренно большое количество выборочных значений случайных величин).Поэтому, несмотря на сформулированные выше замечания о возможныхнедостатках датчиков (конечность используемой мантиссы, периодичностьи т. п.), в дальнейшем будем полагать, что используемый в расчетах генератор стандартных случайных чисел дает «настоящие» (теоретические)выборочные значения αi случайной величины α ∈ U (0, 1).ЗАМЕЧАНИЕ 9.2.
Мультипликативный метод вычетов (9.13), дажереализованный оптимально для используемого языка программирования,151является относительно трудоемким (по сравнению, например, с простымумножением чисел). Поэтому при оптимизации алгоритмов метода МонтеКарло целесообразно по-возможности уменьшать число обращений к подпрограмме типа RAN DOM .10. Моделирование дискретных случайныхвеличин10.1.Основныеклассыалгоритмовмоделированияслучайных величин и векторов. Способы представленияраспределения дискретной случайной величины. Как указано вподразделе 2.4 и в разделе 9 данного пособия, наличие экономичного генератора стандартных чисел позволяет получать на ЭВМ выборочныезначения случайных величин и векторов с произвольными законамираспределения.ЗАМЕЧАНИЕ 10.1. Среди алгоритмов моделирования выборочныхзначений случайных величин и векторов будем выделять:– стандартные методы и их модификации; для непрерывных случайных величин это метод обратной функции распределения (алгоритм 2.4) и поэтапный алгоритм моделирования случайного вектора(алгоритм 2.3); для дискретных случайных величин это представленныедалее алгоритмы 10.1 и 10.4 и квантильный метод (алгоритм 10.6);– альтернативные алгоритмы широкого применения; длянепрерывных случайных величин это методы интегральной и дискретной суперпозиции (алгоритмы 3.1 и 11.1), мажорантный метод исключения (алгоритм 11.10), а также алгоритмы, основанные на переходе кновым системам координат (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
