1626435387-5d0ec7dd22f55dfcc65f3209f497fb0b (844202), страница 3
Текст из файла (страница 3)
1.3) определяется соотношением n−2 (на четыре порядка лучше, чем у алгоритма 1.2; см., например, [16]).Рис. 1.3. Иллюстрация к формуле центральных прямоугольниковПогрешность чуть более «хитрой» формулы Симпсонаn x + x h Xii+1+ g(xi+1 )I≈ ×g(xi ) + 4g6 i=12(1.15)имеет порядок n−3 (см., например, [16]), и т. д.Методы (1.14), (1.15) отражают частные случаи квадратурных формул Ньютона – Котеса, которые строятся с помощью соответствующих полиномиальных сеточных приближений подынтегральной функции g(x). Хорошо известно (см., например, [16]), что при переходе кмногомерному случаю и при рассмотрении негладких подынтегральныхфункций g(x) построение «хороших» (в смысле скорости сходимости)сеточных кубатурных формул существенно затрудняется.15В свою очередь, порядок сходимости n−1/2 метода МонтеКарло (алгоритма 1.2) не зависит от размерности d (этот порядок сохраняется даже при приближении бесконечных сумм интеграловвида (1.9), (1.10)).
Свойства подынтегральной функции g(x) (в том числе гладкость) влияют только на величину дисперсии Dζ из соотношения(1.13).Поэтому «нишей» алгоритмов численного статистического моделирования считаются многомерные задачи со сложными (например,негладкими) входными данными (а таких задач на практике довольномного, если не большинство).В частности, при численном приближенииRинтеграла I = X g(x) dx, X ⊆ Rd , считается, что– для размерностей 1 .
d . 3 целесообразно использовать детерминированные кубатурные формулы (типа приближений (1.14), (1.15));– для размерностей d & 10 (включая задачи бесконечной размерности типа (1.9), (1.10)) практически не имеет конкурентов методМонте-Карло (алгоритм 1.2);– для размерностей 3 .
d . 10 можно использовать дискретностохастические методы численного интегрирования [17].1.9. Затраты и трудоемкость метода Монте-Карло. Важнымпреимуществом метода Монте-Карло является относительная простота подсчета затрат (а это, в свою очередь, следствие простоты схемы(1.1)), что существенно упрощает применение «корректного» оптимизационного критерия 1.1.Вычислительные затраты метода Монте-Карло (см. алгоритмы 1.1, 1.2) близки к времени вычисления суммы Sn и приблизительно равны величинеs = t × n,(1.16)где t – это среднее время подсчета одного выборочного значения ζi случайной величины ζ = q(ξ) (слово «среднее» здесь является принципиальным!).Из многочисленных практических расчетов известно, что формула√Dζ(1.17)δn ∼ H × √nопределяет поведение погрешности δn , при этом константа H невелика.
Проведенные нами аккуратные тестовые вычисления дали значениеH ≈ 0, 80... – точно устанавливаются только две первые десятичныецифры мантиссы.16Отсюда получается, что при заданном уровне погрешности ∆ дисперсия Dζ пропорциональна числу выборочных значений n. Действительно, из равенства√ 2DζH√= ∆ следует соотношение n =× Dζ.H×∆nЭто обосновывает возможность использования вместо затрат s из(1.16) пропорциональной ей, более практичной и информативной величиныS = t × Dζ.(1.18)Величина (1.18) называется трудоемкостью метода МонтеКарло и используется для формулировки следующего аналога сформулированного выше критерия 1.1.КРИТЕРИЙ 1.2 (см., например, [9, 13]). В алгоритмах методаМонте-Карло лучшим (оптимальным) является тот выбор случайной величины ζ = q(ξ) (для алгоритма 1.1) или плотности распределения fξ (x) вектора ξ (для алгоритма 1.2), который дает меньшеезначение трудоемкости S из (1.18).Критерий 1.2 дает ответ на вопрос из сформулированной выше проблемы 1.2.Как правило, уменьшение величины t из (1.18) связано с оптимизацией моделирования случайного вектора ξ (см., например, [9, 13], атакже раздел 2).Методы уменьшения дисперсии Dζ случайной величиныζ = g(ξ)/fξ (ξ) из соотношения (1.8) кратко представлены в разделах 3–5 данного пособия (см.
также книги [5, 9, 17]).1.10.Оцениваниетрудоемкостиспомощьюпредварительных расчетов. Иногда использование критерия 1.2 подвергается критике по той причине, что величины t и Dζ из соотношения(1.18) неизвестны. Тем не менее, эти величины могут быть достаточно просто оценены с помощью предварительных компьютерных расчетов (до использования алгоритмов 1.1 и 1.2 с большим количеством n 1 выборочных значений {ζi }).В частности, можно смоделировать относительно малое количествоn̂ n выборочных значений {ζi ; i = 1, ..., n̂} и построить следующееприближение для среднего времени t:17n̂t≈1Xt̂i ,n̂ i=1(1.19)где t̂i – время вычисления выборочного значения ζi .Эти же выборочные значения ζ1 , . . .
, ζn̂ можно использовать и дляоценивания неизвестной величины Dζ из соотношения (1.18). Простейшее приближение дисперсии Dζ может быть получено с помощьюформул (1.1), (1.3) для x = x и q(x) = x2 :n̂Dζ = Eζ 2 − (Eζ)2 ≈(1)Dn̂1X 2=ζ −n̂ i=1 in̂1Xζin̂ i=1!2;(1.20)см., например, [15].Если трактовать ζ1 , . . . , ζn̂ из соотношения (1.20) как независимыеодинаково распределенные (как ζ) случайные величины, то справедливоравенство1(1)Dζ.(1.21)EDn̂ = 1 −n̂(1)Действительно, имеем EDn̂ = Eζ 2 −E(Sn̂ /n̂)2 = Dζ −D(Sn̂ /n̂), так какE(Sn̂ /n̂) = Eζ.
Учитывая, что D(Sn̂ /n̂) = Dζ/n̂, получаем равенство(1.21).Соотношение (1.21) означает, что полученная статистическая оценка дисперсии Dζ является смещенной и состоятельной (см., например,(1)(1)[15]): EDn̂ 6= Dζ, но EDn̂ → Dζ при n̂ → ∞.(1)Разделим Dn̂ на (1 − 1/n̂) и рассмотрим величинуn̂(2)Dn̂1 X 21=ζi −n̂ − 1 i=1n̂(n̂ − 1)n̂X!2ζi,(1.22)i=1которая является несмещенной статистической оценкой дисперсии Dζ(см., например, [15]).На практике при приближении дисперсии Dζ из соотношения (1.18)по выборочным значениям {ζi ; i = 1, ..., n̂} используют обе статистические оценки (1.21) и (1.22) (они, как правило, дают близкие значениядисперсии).181.11. Простейшая параллелизация вычислений по методуМонте-Карло.
Отметим, что использование K независимых (и,вообще говоря, не одинаковых по производительности) процессоровна современных компьютерных системах для вычислений пометоду Монте-Карло дает эффект, близкий к идеальному,так как для фиксированного времени счета T может быть использованследующий аналог формулы (1.1):I≈S̃n1 (T ) (T ) + . .
. + S̃nK (T ) (T ).n1 (T ) + . . . + nK (T )(1.23)Здесь S̃nk (T ) (T ) – это сумма nk (T ) выборочных значений {ζi }, которая может быть независимо вычислена на k-ом процессоре современногомногопроцессорного компьютера за время T .Вообще у автора пособия сформировалось устойчивое убеждение втом, что вычислительный алгоритм тем эффективнее распараллеливается для вычислений на современной многопроцессорной технике, чемближе он к процедуре суммирования независимых слагаемых.
Остаетсязаметить, что именно такое суммирование и является основным элементом алгоритмов 1.1 и 1.2.1.12. Преимущества и недостатки метода Монте-Карло.Суммируя приведенные в этом разделе соображения (а также учитывая материалы последующих разделов), можно сформулировать следующие преимущества и недостатки методов Монте-Карло.К преимуществам алгоритмов численного статистического моделирования относятся:– возможность решения многомерных (в том числе бесконечномерных) задач численного интегрирования со сложными (в том числе негладкими) начальными данными;– возможность решения задач со случайными параметрами на основе принципа рандомизации (см.
раздел 3), в том числе возможностьмоделирования траекторий прикладных случайных процессов и полей(см. раздел 13);– возможность учета специальных свойств начальных данных (вчастности, с помощью принципа выборки по важности – см. раздел 4);√– универсальная (хотя и невысокая) скорость сходимости (порядка1/ n по числу выборочных значений {ζi ; i = 1, ..., n});– корректная теория оптимизации метода (см. критерии 1.1, 1.2);– естественная и практически идеальная параллелизация основнойсхемы метода.19Главным недостатком методов Монте-Карло следует назватьнекоторую «тяжеловесность» (неэкономичность) вычислений, которая,в свою очередь связана с:√– относительно медленной сходимостью метода (порядка 1/ n);– трудоемким получением каждого выборочного значения ζi (во всяком случае для «серьезных» прикладных задач, для которых среднеевремя t из (1.18) может быть значительным; см., в частности, разделы 2 и 6).2. Численное моделирование случайныхвекторов, метод обратной функциираспределения: обоснование алгоритмов,основные приложения2.1.
Теорема о разложении совместной плотностираспределения двумерного случайного вектора. Для многих разделов теории методов Монте-Карло (таких как моделирование случайных векторов – см. подраздел 2.3 – и прикладных цепей Маркова – см.подраздел 2.7; обоснование метода суперпозиции и мажорантного метода исключения – см. разделы 3, 11; построение метода математических ожиданий и метода расщепления – см.
раздел 3) важны соображения о построении и численноммоделировании двумерного случайноговектора ξ = ξ (1) , ξ (2) с зависимыми компонентами.ОПРЕДЕЛЕНИЕ 2.1 (см., например, [14]) Пусть ξ (1) и ξ (2) – этослучайные величины со значениями в R, и Â является сигма-алгебройборелевских множеств в R (по сути это различные комбинации объ=единений и пересечений интервалов). Функция P ξ (2) ∈ B u (1) (2)P ξ ∈ B ξ = u двух аргументов u ∈ R и B ∈ Â называетсяусловным распределением случайной величины ξ (2) при условии ξ (1) = u, если1) для любого A ∈ Â выполнено соотношение def Z (1) (2)P ξ (2) ∈ B u P ξ (1) ∈ du =E P ξ ∈ B u ;ξ ∈ A =A=Pnoξ (1) ∈ A ∩ ξ (2) ∈ B ;2) для каждого фиксированного u = u0 функция P ξ (2)является вероятностным распределением на множестве B.20(2.1) ∈ B u0ОПРЕДЕЛЕНИЕ2.2 (см., например,[14]). Предположим, что условное распределение P ξ (2) ∈ B u является абсолютно непрерывнымпо борелевской мере в R (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
