Р. Г. Стронгина. Ниж- ний Новгород: Изд-во Нижегородского университета, 2002, 217 с
Уменьшение дисперсии. Расслоенная выборка
жүктеу/скачать 1,64 Mb. Pdf көрінісі
|
Seminar 1
| Уменьшение дисперсии. Расслоенная выборка
Скорость сходимости метода Монте-Карло порядка ( ) 2 1/ − n O , без- условно, является неудовлетворительной, и очень часто применяются специальные приемы, позволяющие улучшить сходимость. Один из них основан на разбиении области интегрирования на ряд подобластей (на расслаивании выборки) и организации независимых расчетов в каждой из подобластей. Представим область интегрирования в виде суммы непересекаю- щихся подобластей U m i i A A 1 = = , ∅ = j i A A I ( j i ≠ ). В этом случае исходный интеграл представляется: i i A i m i A i i A S x p x p dx x p S dx x p x g S dx x p x g i i ) ( ) ( ; ) ( ; ) ( ) ( ) ( ) ( ≡ = = = θ ∫ ∑ ∫ ∫ =1 . (3) Здесь p i (x) является плотностью распределения в области A i . Тогда оценка исходного интеграла складывается из оценок интегралов по подобластям A i : ∑ = θ = θ m i i i S 1 ˆ ˆ где ∑ = = θ i n k i k i i x g n 1 1 ) ( ˆ . (4) (n i – объем выборки в области A i , } { i k x – независимые реализации слу- чайной величины с плотностью распределения p i (x)). Дисперсия оцен- ки равна ∑ = θ = θ m i i i D S D 1 2 ˆ ˆ . При заданном разбиении области интегриро- вания осуществим оптимальный выбор объема выборки в каждой из 106 подобластей min ˆ ,... , → ∑ θ = N n n n n i m D 2 1 . Нетрудно показать, что оптималь- ный объем выборки в подобласти должен быть пропорционален стан- дартному отклонению оценки интеграла в данной подобласти: ∑ = σ σ = m i i i i i i S S N n 1 (5) Используя данный результат, рассмотрим метод распараллелива- ния вычислений с декомпозицией по области интегрирования. Исход- ная область интегрирования разбивается на достаточно большое число подобластей, существенно большее количества вычислительных узлов (процессоров). Каждый из узлов будет осуществлять оценку интеграла в одной из подобластей, причем расчет разделяется на два этапа: 1. оценка стандартного отклонения в подобласти и регулировка объ- ема выборки в подобласти; 2. непосредственный расчет. Каждому из процессоров назначается область, в которой еще не производились расчеты. Поскольку объем выборки различен в каждой из подобластей, какой-либо процессор закончит расчеты в подобласти раньше остальных. Освободившийся процессор передает результаты расчетов на главную машину, которая осуществляет оценку интеграла по всей области интегрирования, после чего освободившемуся процес- сору назначается очередная подобласть, в которой не осуществлялось интегрирование. В силу того, что количество подобластей интегриро- вания существенно больше числа вычислительных узлов, простой процессоров минимален и возможен лишь в самом конце расчетов. жүктеу/скачать 1,64 Mb. Достарыңызбен бөлісу:
|