1626435387-5d0ec7dd22f55dfcc65f3209f497fb0b (844202), страница 30
Текст из файла (страница 30)
алгоритмы 10.2–10.8), выбираем номер η0 = m.2. Моделируем выборочное значение ξ 0 согласно плотности fm (u).В связи с решением проблемы 11.1 с помощью алгоритма 11.8 можно сформулировать следующие требования к функциональному базисуΞ(M ) :а) базисные функции χ(i) (u) и коэффициенты {w(i) } должны бытьнеотрицательными (см. соотношение (11.28));(i)б) моделирование выборочных значений ξ 0 , распределенных согласно соответствующим плотностям {fi (u)} является эффективным(экономичным);в) функция fξ (u) близка к функции Cg(u) в некоторой функциональной норме;г) аппроксимация (11.27) устойчива.Требования в и г являются «традиционными» для теории аппроксимации функций (см., например, [16]), а требования а, б специфичны181именно для перечисленных выше приложений.
Будем называть «моделируемыми» функциональные базисы Ξ(M ) , удовлетворяющие требованиям а и б.Сразу отметим, что далеко не все классические аппроксимационные базисы являютсяQM«моделируемыми». Например, функции базисаЛагранжа χ(i) (u) = j=1,j6=i (u−vj )/(vi −vj ), u ∈ R (см., например, [16])являются знакопеременными (т. е. требования а и б не выполняются).Обладая весьма хорошими аппроксимационными свойствами, аппроксимация Лагранжа имеет весьма неважные свойства устойчивости (особенно для равномерной сетки). Аналогичные недостатки имеют тригонометрические базисы.Наиболее удачной для использования в дискретно-стохастическихчисленных процедурах (к которым относится, в частности, алгоритм 11.8) оказалась конечно-элементная аппроксимация Стренга –Фикса [9, 17, 24, 26]. В одномерном случае хорошие свойства «моделируемости» имеет базис Бернштейна [24].11.5.
Общая схема метода исключения. Мажорантныйметод исключения и его обоснование. Если внимательно проанализировать представленные выше соображения о численном моделировании выборочных значений ξ 0 случайных векторов (случайных величин)ξ (см. прежде всего рассуждения из подраздела 2.8), то может сформироваться вполне справедливое мнение о том, что для весьма большогокласса распределений нет экономичных версий как стандартных алгоритмов 2.3, 2.4, так и альтернативных и специальных методов (типаалгоритмов 2.1, 11.1 и др.) моделирования значения ξ 0 .После рассмотрения представленной в этом подразделе вычислительной технологии (алгоритма мажоратного метода исключения) эта«брешь» будет закрыта и сформируется вывод о том, что в принципена компьютере можно получить выборочное значение ξ 0 для любого распределения (как минимум, мажорантным методом исключения –см.
также замечание 2.4), правда, соответствующий алгоритм можетоказаться не слишком экономичным (эффективным).Итак, в этом подразделе речь пойдет о так называемых методахисключения (иногда применяются термины методы отбора и методы отказов, которые также соответствуют, хотя и в меньшей степени,английскому термину rejection technique), широко применяемых в алгоритмах численного статистического моделирования (и не только длямоделирования случайных величин и векторов).Суть этих методов состоит в следующем.
Пусть случайный вектор182(случайная точка) θ распределен в некотором множестве G̃ и дано подмножество G ⊆ G̃.АЛГОРИТМ 11.9 (см., например, [9, 13]). Проводится некотороестатистическое испытание T и считается, что T состоялось, есличисленная реализация θ 0 вектора θ принадлежит G, и T не состоялось, если θ 0 ∈/ G.Назовем трудоемкостью s̃ алгоритма 11.9 средние затраты на построение выборочных значений θ j вектора θ до реализации T .Очевидно, что величина s̃ пропорциональна математическому ожиданию целочисленной случайной величины η, имеющей геометрическоераспределение с параметром (вероятностью «успеха») p = P{θ ∈ G} (см.формулу (10.22) из подраздела 10.8).Согласно формуле (10.23) имеемs̃ ∼ s = Eη =11=.pP{θ ∈ G}(11.30)Очевидно, что s ≥ 1.
Оптимизация алгоритма 11.9 связана с приближением величины s к единице.В подавляющем числе случаев алгоритм 11.9 применяется в следующей ситуации.Пусть требуется построить алгоритм численного моделирования выборочного значения ξ 0 случайного вектора (случайной величины) ξ,распределенного в области X ∈ Rd согласно плотности fξ (u), котораяпропорциональна заданной неотрицательной функции g(u), т. е.Zg(u)fξ (u) =, u ∈ X, Ḡ =g(u) du.(11.31)ḠXПредполагается, что ни один из рассмотренных ранее методов недает эффективного алгоритма моделирования значения ξ 0 .
Надеждуна построение требуемого моделирующего алгоритма дает следующееутверждение.УТВЕРЖДЕНИЕ 11.4 (см., например, [9, 13]). Пусть точка (ξ, η)равномерно распределена в областиG = {u ∈ X, 0 < v < g(u)},(11.32)т. е. в «подграфике» функции g(u) (обозначение (ξ, η) ∈ U (G)); приэтом ξ ∈ X и η ∈ (0, g(ξ)). Тогда случайный вектор ξ распределенсогласно плотности (11.31) (рис. 11.1).183ДОКАЗАТЕЛЬСТВО. То, что (d + 1)-мерная точка (ξ, η) равномерно распределена в области (11.32), означает, что совместная плотностьf(ξ ,η) (u, v) тождественно равна 1/Ḡ при (u, v) ∈ G и нулю иначе.Согласно формуле (2.5) для ξ (1) = ξ и ξ (2) = η имеемZfξ (u) =Zf(ξ ,η) (u, v) dv =0g(u)dvg(u)=.ḠḠУтверждение 11.4 доказано.Рис.
11.1. Иллюстрация к утверждению 11.4Таким образом, если получить выборочное значение (ξ 0 , η0 ) точки(ξ, η), равномерно распределенной в G, то значение ξ 0 будет искомым– распределенным согласно плотности (11.31).Возникает вопрос: каким образом можно реализовать точку, равномерно распределенную в «подграфике» заданной функции? Ответ наэтот вопрос дает следующее утверждение, которое является по сути обратным утверждению 11.4.184УТВЕРЖДЕНИЕ 11.5 (см., например, [9, 13]). Пусть случайныйвектор ξ (1) распределен согласно плотностиZg (1) (u)(1)fξ (1) (u) =, Ḡ =g (1) (u) du,(11.33)Ḡ(1)X(1)а условное распределение при фиксированном значении ξ (1) = ξ 0 слу(1) чайной величины η является равномерным в интервале 0, g (1) ξ 0.Тогда случайная точка ξ (1) , η равномерно распределена в «подграфике»G(1) = u ∈ X, 0 < v < g (1) (u)(11.34)функции g (1) (u), т. e.
ξ (1) , η ∈ U G(1) (рис. 11.2).ДОКАЗАТЕЛЬСТВО. То, что случайная величина η условно равно(1) мерно распределена в интервале 0, g (1) ξ 0означает, что ее условная(1)(1) плотность fη v u = ξ 0тождественно равна 1 g (1) ξ 0при(1) (1)v ∈ 0, gξ0и нулю иначе.Согласно формуле (2.4) для ξ (1) = ξ (1) и ξ (2) = η имеем, что плотность распределения случайной точки ξ (1) , η равнаfξ (1) ,η11g (1) (u)ξ (1) (u)fη (v|u) = Ḡ(1) × g (1) (u) ≡ Ḡ(1)и нулю иначе, т.
e. ξ (1) , η ∈ U G(1) . Утвержде- (u, v) = fпри (u, v) ∈ G(1)ние 11.5 доказано.Если в утверждении 11.5 выбрать ξ (1) = ξ (тогда g (1) (u) = g(u)и «подграфики» (11.32) и (11.34) тоже совпадают), то в совокупностис утверждением 11.4 получаем логический круг: нам нужно получитьвыборочное значение (ξ 0 , η0 ) случайной точки (ξ, η), равномерно распределенной в «подграфике» G (и тогда компонента ξ 0 является искомым выборочным значением, так как имеет требуемое распределениес плотностью (11.31)), но для этого нужно смоделировать выборочноезначение ξ 0 вектора ξ согласно плотности (11.31).Имеется еще, однако, утверждение 2.3, из которого следует, что еслипогрузить «подграфик» G в область G(1) в системе координат(u, v) ∈ Rl ; l = d + 1 (т. е. G ⊆ G(1) ) и реализовать выборочное зна(1)чение ξ 0 , η0 случайного вектора ξ (1) , η , равномерно распределен(1)(1)ного в G(1) , то при условии ξ 0 , η0 ∈ G пара ξ 0 , η0 равномерно185Рис.
11.2. Иллюстрация к утверждению 11.5(1)распределена в G. Тогда, согласно утверждению 11.4, вектор ξ 0 имееттребуемое распределение с плотностью (11.31).Конструирование области G(1) связано с расширением «подграфика» G в направлении оси v (рис. 11.3). Другими словами, рассматривается мажоранта g (1) (u) функции g(u), такая, что g(u) ≤ g (1) (u) приu ∈ X.Главное требование к мажоранте g (1) (u) таково, что для плотности(1)(11.33) имеется эффективный алгоритм (формула) вида ξ 0 = ψ (1) ᾱ1для моделирования выборочного значения случайного вектора ξ (1) согласно одному из вариантов алгоритма 2.3 (здесь ᾱ1 – соответствующийнабор стандартных случайных чисел). Это дает мажорантный метод исключения (рис. 11.3).АЛГОРИТМ 11.10 (см., например, [9, 13]). 1. Моделируем выбороч(1)ное значение ξ 0 случайного вектора (случайной величины) ξ (1) соглас(1)но плотности (11.33): ξ 0= ψ (1) ᾱ1 , а также значение(1)η0 = α2 g (1) ξ 0 (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
