Использование метода ветвей и границ при адаптации рабочей нагрузки к параметрам вычислительного процесса (стр. 4 из 7)

Из формулы (8) следует, что при

среднеквадратичное отклонение σ квазиравномерной совокупности стремится к

. Ниже приведены значения отношения среднеквадратичных значений двух величин ξ и η в зависимости от числа разрядов, причём величина η имеет равномерное распределение в интервале [0,1] (табл. 1).

Таблица 1

k	2	3	5	10	15
σ_ξ/σ_η	1,29	1,14	1,030	1,001	1,00

Из табл. 1 видно, что при k>10 различие в дисперсиях несущественно.

На основании вышеизложенного задача получения совокупности квазиравномерных чисел сводится к получению последовательности независимых случайных величин z_i (i=1,2,…, k), каждая из которых принимает значение 0 или 1 с вероятностью 1/2. Различают два способа получения совокупности этих величин: физический способ генерирования и алгоритмическое получение так называемых псевдослучайных чисел. В первом случае требуется специальная электронная приставка к цифровой вычислительной машине, во втором случае загружаются блоки машины.

При физическом генерировании чаще всего используются радиоактивные источники или шумящие электронные устройства. В первом случае радиоактивные частицы, излучаемые источником, поступают на счётчик частиц. Если показание счётчика чётное, то z_i=1, если нечётное, то z_i=0. Определим вероятность того, что z_i=1. Число частиц k, которое испускается за время Δt, подчиняются закону Пуассона:

Вероятность чётного числа частиц

Таким образом, при больших λΔt вероятность P{Z_i=1} близка к 1/2.

Второй способ получения случайных чисел z_i более удобен и связан с собственными шумами электронных ламп. При усилении этих шумов получается напряжение u(t), которое является случайным процессом. Если брать его значения, достаточно отстоящие друг от друга, так чтобы они были некоррелированы, то величины u(t_i) образуют последовательность независимых случайных величин. Обычно выбирают уровень отсечки a и полагают

причём уровень a следует выбрать так, чтобы

Также применяется более сложная логика образования чисел z_i. В первом варианте используют два соседних значения u(t_i) и u(t_i₊₁), и величина Z_i строится по такому правилу:

Если пара u(t_i) – a и u(t_i₊₁) – a одного знака, то берётся следующая пара. Требуется определить вероятность при заданной логике. Будем считать, что P {u(t_i)>a}=W и постоянная для всех t_i. Тогда вероятность события

равна по формуле событий A₁H_v. Здесь H_v – это вероятность того, что v раз появилась пара одинакового знака

u(t_i) – a; u(t_i₊₁) – a. (9)

Поэтому вероятность события A₁H_v

P{A₁H_v}=W (1-W) [W²+(1-W)²]^v.

Это – вероятность того, что после v пар вида (9) появилось событие A₁. Оно может появиться сразу с вероятностью W (1-W), оно может появиться и после одной пары вида (9) с вероятностью

W (1-W) [W²+(1+W)²]

и т.д. В результате

или

Отсюда следует, что если W=const, то логика обеспечивает хорошую последовательность случайных чисел. Второй способ формирования чисел z_iсостоит в следующем:

Пусть

W=P {u(t_i)>a}=1/2+ξ.

Тогда

P{Z_i=1}=2W (1-W)=1/2–2ξ².

Чем меньше ξ, тем ближе вероятность P{Z_i=1} к величине 1/2.

Для получения случайных чисел алгоритмическим путём с помощью специальных программ на вычислительной машине разработано большое количество методов. Так как на ЦВМ невозможно получить идеальную последовательность случайных чисел хотя бы потому, что на ней можно набрать конечное множество чисел, такие последовательности называются псевдослучайными. На самом деле повторяемость или периодичность в последовательности псевдослучайных чисел наступает значительно раньше и обусловливается спецификой алгоритма получения случайных чисел. Точные аналитические методы определения периодичности, как правило, отсутствуют, и величина периода последовательности псевдослучайных чисел определяется экспериментально на ЦВМ. Большинство алгоритмов получается эвристически и уточняется в процессе экспериментальной проверки. Рассмотрение начнём с так называемого метода усечений. Пусть задана произвольная случайная величина u, изменяющаяся в интервале [0,1], т.е.

. Образуем из неё другую случайную величину

u_n=u [mod 2^-n], (10)

где u [mod2^-ⁿ] используется для определения операции получения остатка от деления числа u на 2^-ⁿ. Можно доказать, что величины u_n в пределе при

имеют равномерное распределение в интервале [0,1].

По существу с помощью формулы (10) осуществляется усечение исходного числа со стороны старших разрядов. При оставлении далёких младших разрядов естественно исключается закономерность в числах и они более приближаются к случайным. Рассмотрим это на примере.

Пример 1. Пусть u= 0,10011101… = 1·1/2 + 0·1/2² + 0·1/2³ + 1·1/2⁴ + 1·1/2⁵ + 1·1/2⁶ + 0·1/2⁷ + 1·1/2⁸ + …

Выберем для простоты n=4. Тогда {umod 2^-4} = 0,1101…

Из рассмотренного свойства ясно, что существует большое количество алгоритмов получения псевдослучайных чисел. При этом после операции усечения со стороны младших разрядов применяется стандартная процедура нормализации числа в цифровой вычислительной машине. Так, если усечённое слева число не умещается по длине в машине, то производится усечение числа справа.

При проверке качества псевдослучайных чисел прежде всего интересуются длиной отрезка апериодичности и длиной периода (рис. 3). Под длиной отрезка апериодичности L понимается совокупность последовательно полученных случайных чисел α₁, …, α_L таких, что α_i

α_jпри

, но α_L₊₁ равно одному из α_k (

Под длиной периода последовательности псевдослучайных чисел понимается T=L-i+1. Начиная с некоторого номера i числа будут периодически повторяться с этим периодом (рис. 3).

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

2.2 Точность метода Монте-Карло

Метод Монте-Карло применяется там, где не требуется высокой точности. Например, если определяют вероятность поражения мишени при стрельбе, то разница между p₁=0,8 и p₂=0,805 несущественна. Обычно считается, что метод Монте-Карло позволяет получить точность примерно 0,01–0,05 максимального значения определяемой величины.

Получим некоторые рабочие формулы. Определим по методу Монте-Карло вероятность пребывания системы в некотором состоянии. Эта вероятность оценивается отношением

где M – число пребываний системы в этом состоянии в результате N моделирований. Учитывая выражение для дисперсии величины M/N

и неравенство Чебышёва

, (11)

напишем

. (12)

Величина

есть ни что иное, как ошибка моделирования по методу Монте-Карло. С помощью формулы (11) можно написать следующую формулу для величины (12):

или

где p₀ – вероятность невыполнения этой оценки. С помощью частоты M/N может быть получена оценка математического ожидания m_x некоторой случайной величины X. Ошибка этой оценки

находится с помощью соотношения

Отсюда видно, что ошибка моделирования находится в квадратичной зависимости от числа реализаций, т.е.

. (13)