1626435387-5d0ec7dd22f55dfcc65f3209f497fb0b (844202), страница 12
Текст из файла (страница 12)
Описание примера 5.2 закончено.5.3. Выборка по группам. Рассмотрим следующее представлениеприближаемого интеграла (4.1):ZI=Zg(x) dx =XXq(x)fξ (x) dx =M ZXm=1Xmq(x)fξ (x) dx; q(x) =g(x),fξ (x)где Xm – это подмножества области интегрирования X, имеющие взаимные пересечения меры нуль, и такие, что X = X1 ∪ . . . ∪ XM .Введем обозначенияZZfξ (x)pm =fξ (x) dx, Im =q(x)fξ (x) dx, fξ (m) (x) =pmXmXmдля x ∈ Xm .Предположим, что fξ (x) = 0 для x 6∈ X.
Тогда p1 + . . . + pM = 1.Кроме того,hiI1 + . . . + IM = I и Im = E pm q ξ (m) ,где случайный вектор ξ (m) распределен в подобласти Xm согласно плотности fξ (m) (x).АЛГОРИТМ 5.2 (см., например, [9, 13]). Для каждого m = 1, ..., Mприближенно вычисляем значения Im согласно стандартному алго (m) ритму 1.2 с числом nm выборочных значений ξ im случайного вектора ξ (m) , распределенного согласно плотности fξ (m) (x):Im ≈nmpm X(m) q ξ im ,nm i =1m73и используем приближениеI≈Zn(M )nmMXpm X(m) q ξ im ;=nm=1 m i =1(5.9)mгдеn = n1 + .
. . + nM .(5.10)Алгоритм 5.2 определяет метод выборки по группам или метод расслоенной выборки.Для M = 2 алгоритм 5.2 отличается от метода интегрированияпо части области, так как для последнего считается, что интеграл I2известен, а для алгоритма 5.2 величина I2 считается приближенно методом Монте-Карло с помощью численного моделирования значений (2)ξ i2 ; i2 = 1, . . . , n2 .Сравним выборочную дисперсиюDZn =Dζnоценивателя ζ = q(ξ) стандартного весового алгоритма 1.2 приближения интеграла I (здесь моделируется n случайных точек ξ i во всейобласти интегрирования X согласно плотности fξ (x)) и выборочную(M )дисперсию DZnDZn(M ) =метода расслоенной выборки:2 XnmMM XXp2m Dq ξ (m)pm(m) Dq ξ im =,nmnmm=1m=1i =1(5.11)mгде1Dq ξ (m) =pmZXmq 2 (x)fξ (x) dx −Impm2.(5.12)При выводе соотношений (5.11), (5.12) использованы независимость (m) величин ξ im и свойства дисперсии (см., например, [14]).Для корректности этого сравнения принципиальным является соблюдение условия (5.10).УТВЕРЖДЕНИЕ 5.2 (см., например, [5, 9, 13]).
Минимум величины(M )DZn равен" M#2qX1d2n =.(5.13)pm Dq ξ (m)n m=174Эта величина не превышает значение выборочной дисперсии DZnдля стандартного алгоритма 1.2 и реализуется дляqnpm Dq ξ (m)qnm = P.(5.14)0 M0Dq ξ (m )m0 =1 pmДОКАЗАТЕЛЬСТВО. Несложно убедиться в том, что при подстановке значений (5.14) в соотношение (5.11) получается число d2n из формулы (5.13).Чтобы показать минимальность этого числа среди различных значений (5.11), заметим, что величину d2n можно представить в виде2s rM(m)XDqξnm .×pmd2n = nnmm=1Используя неравенство Коши – Буняковского!2KKKXXX2ak bk≤ak ×b2k ,k=1k=1(5.15)k=1получаемd2nMMMXXXp2m Dq ξ (m)p2m Dq ξ (m)nm×== DZn(M ) ,≤nnnmmm=1m=1m=1что и требовалось показать.Осталось доказать, что d2n ≤ DZn .Умножая значения (5.12) на pm и суммируя эти произведения по m,получаемMXm=1pm Dq ξ (m) =ZXq 2 (x)fξ (x) dx −M2XIm.pm=1 mИспользуя в очередной раз неравенство Коши – Буняковского (5.15),получаем!2 " M #2MXXI√mI2 =Im=× pm≤√pmm=1m=175≤MMM22XXXImIm×pm =.ppm=1 mm=1m=1 mОтсюда следует, что1DZn =n1≥n"ZZ2Xq (x)fξ (x) dx − IM2XImq (x)fξ (x) dx −pXm=1 m2#1=n"2MX≥#pm Dq ξ(m).m=1(M )Последнее выражение равно значению DZnпри условии, чтоnm = n pm .(5.16)d2n ≤ DZn(M ) |nm =n pm ≤ DZn .(5.17)ПоэтомуУтверждение 5.2 доказано.Утверждение 5.2 показывает, что оптимальная версия выборки погруппам в определенной степени похожа на выборку по важности: берется больше случайных узлов в тех «важных» подмножествах Xm области интегрирования, где большими являются значения pm и Dq ξ (m) .Однако здесь распределение узлов задается не с помощью специального выбора плотности распределения, а с помощью определения чиселвыборочных значений в Xm при ограничении (5.10).Как это часто бывает, использование теоретически оптимальных значений (5.14) затруднено.
Причин здесь как минимум две.Первая из них связана с тем, что величины {nm } должны бытьцелыми. Решением этой проблемы является выбор целых чисел {nm },наиболее близких к значениям (5.14) и удовлетворяющих ограничению(5.10).Вторая (более серьезная, принципиальная) трудность приn использоoвании формул (5.14) связана с тем, что величины дисперсий Dq ξ (m)неизвестны и не могут быть получены с помощью предварительныхрасчетов.Однако можно заметить, что при доказательстве утверждения 5.2мы показали, что метод расслоенной выборки дает уменьшение дисперсии по сравнению со стандартным алгоритмом 1.2 уже при условии76nm = npm – см.
соотношения (5.16), (5.17). Соотношение (5.16) определяет типическую выборку – см., например, [15].Получить типическую выборку на практике, как правило, несложно.Например, если интегрирование идет по одномерному единичному кубуX = ∆(d) (как в примере 5.1), то можно взять в качестве fξ (x) плотность равномерного распределения и разбить куб ∆(d) на одинаковыеподкубики Xm ; m = 1, ..., M объема pm = 1/M . В этом все величины{nm } одинаковы и равны n/M , и надо лишь позаботиться о том, чтобыэто число было целым.На описанной технологии разбиения единичного куба для некоторых «крайних» случаев (в частности, при n1 = ...
= nM = 1) удается получить оптимальные (по порядку верхней оценки погрешности)кубатурные формулы Н. С. Бахвалова для подынтегральных функций«ограниченной» гладкости (см., в частности, [9, 17]). Эти конструкции в свое время послужили основой для создания теории дискретностохастических методов численного интегрирования [17].В следующем тестовом примере показаны ситуации удачного и неудачного выбора чисел {nm } в методе выборки по группам.ПРИМЕР 5.3 [5, 9, 17].
Рассмотрим тестовую задачу вычисленияинтегралаZ1ex dx = e − 1.I=0Сначала оценим величину I с использованием n = 10 точек, равномерно распределенных в интервале (0, 1):I ≈ Z10 =eα1 + . . . + eα10; αi ∈ U (0, 1); i = 1, ..., 10.10Выборочная дисперсия этой оценки равна"ZZ 12 #e21−12xx= 2DZ10 =e dx −e dx10 0012− (e − 1)2≈ 0, 02421.10Теперь разобьем (0, 1) на два интервала (0, 1/2) и [1/2; 1) (т. е.
здесьM = 2) и будем выбирать в них равномерно распределенные точки по(1)(2)формулам ξi1 = 0, 5αi1 и ξi2 = 0, 5 (1 + αi2 ). Тогда p1 = p2 = 1/2 и(2)Zn1 +n2 =n1n21 X1 X(1)(2)exp ξi1 +exp ξi2 ,2n1 i =12n2 i =11277причем n1 + n2 = 10.Согласно формуле (5.11), дисперсия этой оценки равнаD exp ξ (1)D exp ξ (2)+,4n14n2(2)DZn1 +n2 =гдеD exp ξ(1)1/2Ze=22xD exp ξZxdx− 2e dx0(2)!21/2Z√= e−1−4( e−1)2 ≈ 0, 03492,01=2e2x1/2Z!21dx− 2xe dx√= e2 −e−4(e− e)2 ≈ 0, 09493.1/2Согласно соотношению (5.14), оптимальное число n1 следует выбирать близким к. 1 pp1p(1)(1)(2)D exp ξ +D exp ξ≈ 3, 775.5 D exp ξ22Возьмем n1 = 4 и n2 = 6.
Тогда(2)DZ4+6 =11D exp ξ (1) +D exp ξ (2) ≈ 0, 006138,1624что заметно (в четыре раза) меньше, чем DZ10 .Если же взять типическую выборку n1 = n2 = 5 (см. формулу(5.16)), то(2)DZ5+5 =1 D exp ξ (1) + D exp ξ (2) ≈ 0, 006493,20что также меньше, чем DZ10 .В качестве примера неудачного выбора n1 и n2 можно рассмотретьn1 = 9 и n2 = 1. Здесь(2)DZ9+1 =11D exp ξ (1) + D exp ξ (2) ≈ 0, 02470,364что уже больше, чем DZ10 . Описание примера 5.3 закончено.785.4. Краткий обзор методов уменьшения трудоемкостистандартного весового алгоритма метода Монте-Карло длявычисления интеграла. Подведем некоторые итоги.В данном пособии (а также в учебниках [5, 9, 13, 17] и др.) представлен целый ряд технологий уменьшения трудоемкости S = t × Dζстандартного весового алгоритма 1.2 метода Монте-Карло для «методической» задачи численного приближения интеграла I.В частности, к проблеме уменьшения среднего времени t моделирования выборочных значений ζi = q (ξ i ) относятся все вопросы, связанные с моделированием случайных векторов и величин (см., в частности,разделы 2, 3, 9–14 данного пособия).
Как отмечено выше, к существенному изменению величины t (по сравнению со стандартным алгоритмом 1.2) может привести использование метода расщепления (см. подраздел 3.4), метода выделения главной части (см. подраздел 5.1) и др.К методам уменьшения величины t относятся также геометрическийметод, метод равномерной выборки [5] и их эффективные дискретностохастические модификации [17].В свою очередь, к методам уменьшения дисперсии Dζ можно отнести метод условных математических ожиданий (см.
подраздел 3.3),метод выборки по важности (см. раздел 4), метод выделения главнойчасти (см. подраздел 5.1), метод интегрирования по части области(см. подраздел 5.2), выборку по группам (см. подраздел 5.3). Сюда жеможно добавить метод многомерной симметризации [5, 17], метод споправочным множителем [5], а также их эффективные дискретностохастические модификации [17].К сожалению, далеко не все методы из приведенного обширногосписка могут быть эффективно использованы для проблемы построения рандомизированных алгоритмов численного решения прикладных(практически значимых) интегральных уравнений Фредгольма второгорода, к рассмотрению которой мы обратимся в следующих трех разделах данного пособия.796. Применение прикладных цепей Маркова.Исторически важный пример: модельпереноса частиц (особенности численнойреализации)6.1.«Естественность»использованиятраекторийобрывающихся цепей Маркова в качестве рандомизированныхитерационных численных моделей. В подразделе 2.8 упомянуто отом, что при построении алгоритмов численного статистического моделирования используется компьютерная реализация траекторийцепей Маркова, для которых выполнен простейший вариант марковского свойства: распределение следующего состояния полностью определяется фиксированным значением предыдущего (см., например, [14],а также соотношения (2.25), (2.26)).Следует особо выделить то обстоятельство, что в связи с ограниченностью компьютерной оперативной памяти на ЭВМ можно реализовывать только итерационные рандомизированные алгоритмы «с малойпамятью», то есть свойство марковости является фундаментальным для численных рандомизированных итерационныхмоделей и алгоритмов.В классической теории вероятностей цепь Марковаξ˜(0) , ξ˜(1) , .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
