Главная » Просмотр файлов » 1626435387-5d0ec7dd22f55dfcc65f3209f497fb0b

1626435387-5d0ec7dd22f55dfcc65f3209f497fb0b (844202), страница 7

Файл №844202 1626435387-5d0ec7dd22f55dfcc65f3209f497fb0b (Войтишек - Лекции по численным методам Монте-Карло) 7 страница1626435387-5d0ec7dd22f55dfcc65f3209f497fb0b (844202) страница 72021-07-16СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 7)

Поэтому имеется возможность использования «упрощенных» версий функции fξ (x).В частности, часто разумнымбывает предположить, что компоненты вектора ξ = ξ (1) , . . . , ξ (d) являются независимыми (см., например,[14]). Это означает, что плотность fξ x(1) , . . . , x(d) имеет видfξ x(1) , . . .

, x(d) = fξ(1) x(1) × fξ(2) x(2) × . . . × fξ(d) x(d) ,(2.24)т. е. условные плотности из соотношения (2.10) становятся «независимыми» и вся разница между представлениями(2.10) связана толькос порядком умножения плотностей fξ(i) x(i) .37(i)В этом случае каждое выборочное значение ξ0 случайной компоненты ξ (i) можно моделировать согласно своей разумно выбранной (сточки зрения решения проблемы 2.2) плотности fξ(i) x(i) , причем порядок моделирования – произвольный.Однако необходимо всегда помнить, что «удобство» моделирования случайного вектора ξ не всегда означает эффективность(экономичность) соответствующего метода Монте-Карло(алгоритмов 1.1 или 1.2) с оценивателем (монте-карловской оценкой) ζ = q(ξ).Для оптимизации этого метода необходимо минимизироватьзначение трудоемкости S = t × Dζ (см.

формулу (1.18)). Выборплотности fξ (x) в форме (2.24) отражает попытку уменьшить величинусреднего времени t, в то время как величина дисперсии Dζ при такомвыборе может быть достаточно большой (даже бесконечной).В ряде прикладных задач (в частности, при решении важной задачиоценки линейного функционала от решения интегрального уравненияФредгольма второго рода – см., например, [9, 13], а также разделы 6, 7данного пособия) требуется численно моделировать выборочное значе(m+1)(m+1)случайного вектора ξ̃= ξ˜(0) , ξ˜(1) , . . .

, ξ˜(m) , распредение ξ̃ 0ленного согласно плотности видаf(ξ̃(0) ,ξ̃(1) ,...,ξ̃(m) ) x(0) , x(1) , .., x(m) = π̃ x(0) × r1 x(0) , x(1) ××r2 x(1) , x(2) × . . . × rm x(m−1) , x(m) .(2.25)(m+1)Представление (2.25) означает, что вектор ξ̃обладает так называемым марковским свойством: для одного из представлений вида(2.10), а конкретнее, для тождественной подстановки(i0 , i1 , .

. . , im ) = (0, 1, . . . , m),распределение случайной компоненты ξ˜(j) полностью определяется фиксированным значением x(j−1) предыдущей по номеру компоненты ξ˜(j−1) :fξ̃(j) xx(0) , . . . , x(j−1) ≡ fξ̃(j) xξ˜(j−1) = x(j−1) = rj x(j−1) , x .(m+1)Таким образом, вектор ξ̃= ξ˜(0) , ξ˜(1) , . . . , ξ˜(m) представляетсобой отрезок длины (m + 1) цепи Маркова ξ˜(0) , ξ˜(1) , ξ˜(2) , . . . (см.,38например, [14]) с начальной плотностью π̃(x) = fξ̃(0) (x) и переходными плотностямиhirj (x0 , x) = rj ξ˜(j−1) = x0 → ξ˜(j) = x = rj xξ˜(j−1) = x0 ; (2.26)это условные плотности компонент ξ (j) при условии, что ξ˜(j−1) = x0 .Численное моделирование выборочных значений(0) (1)(m)ξ˜0 , ξ˜0 , .

. . , ξ˜0первых m + 1 состояний цепи Маркова реализуется с помощью следующего алгоритма.АЛГОРИТМ 2.5 (см., например, [9, 13]). Численно моделируем (ре(0)ализуем на компьютере) выборочное значение ξ˜0 начального состоя(0)˜ния ξцепи Маркова согласно плотности π̃(x). Затем для(j)j = 1, 2, . . . , m последовательно моделируем выборочные значения ξ˜0случайных величин (состояний цепи Маркова) ξ˜(j) согласно плотно(j−1)стям rj ξ˜0,x .Важным для приложений является случай, когда переходные плотности (2.26) одинаковы для всех j = 1, 2, . . .:rj (x0 , x) ≡ r(x0 , x),что означает, что марковская цепь ξ˜(0) , ξ˜(1) , ξ˜(2) , . . .

является однородной (см., например, [14]).соотношением (2.25) совместная плотность состояний По аналогии с (0) ˜(1)(m)˜˜ξ ,ξ ,...,ξдля однородной цепи Маркова имеет видf(ξ̃(0) ,ξ̃(1) ,...,ξ̃(m) ) x(0) , x(1) , .., x(m) = π̃ x(0) × r x(0) , x(1) ××r x(1) , x(2) × . . . × r x(m−1) , x(m) .(2.27)Численное моделирование выборочных значений первых m + 1 состояний однородной цепи Маркова реализуется следующим образом.АЛГОРИТМ 2.6 (см., например, [9, 13]). Численно моделируем выбо(0)рочное значение ξ˜0 согласно плотности π̃(x). Затем для j = 1, 2, .

. . , m(j)последовательно моделируем выборочные значения ξ˜0 согласно плот(j−1)ностям r ξ˜0,x .39Наконец, для практически важных расчетов, связанных с решением интегральных уравнений Фредгольма второго рода, нам потребуется введение и численное моделирование прикладной цепи Марковаили однородной цепи Маркова, обрывающейся с вероятностьюединицаξ (0) , ξ (1) , ..., ξ (N )(2.28)(см., например, [9, 13], а также разделы 6, 7 данного пособия).(m+1)Здесь номер m = N последней компоненты вектора ξ̃являетсяслучайным, а вместо переходной плотности рассматривается переходная функцияp(x0 , x) = 1 − p(a) (x0 ) × r(x0 , x),(2.29)где значение 0 ≤ p(a) (x0 ) ≤ 1 трактуется как вероятность обрыватраекторииприкладнойцепиМаркова(соответственноp(s) (x0 ) = 1 − p(a) (x0 ) – вероятность «выживания»), аr(x0 , x) = rξ(j) xξ (j−1) = x0 – условная вероятностная плотность типа (2.26) (одинаковая для всех j = 1, ..., N ).При моделировании траекторий прикладной цепи Маркова (2.28) используется аналог алгоритмов 2.5, 2.6, в котором перед моделированием(j−1)(j)очередного перехода ξ0→ ξ0 проверяется, не является ли состоя(j−1)ние ξ0точкой обрыва траектории.Этот розыгрыш обрыва траектории происходит согласно стандартному алгоритму моделирования выборочных значений дискретной случайной величины, принимающей только два значения (см., например,[9, 13], а также подраздел 10.3 данного пособия – алгоритм 10.3).(j−1) АЛГОРИТМ 2.7.

Если α0 < p(a) ξ0, то происходит обрыв траектории; иначе моделирование траектории продолжается; здесьα0 ∈ U (0, 1) – стандартное случайное число.В итоге алгоритм моделирования траекторий прикладной цепи Маркова (2.28) выглядит следующим образом.АЛГОРИТМ 2.8 (см., например, [9, 13]). 1. Полагаем j := 1.

Чис(j−1)(0)ленно моделируем выборочное значение ξ0= ξ0 согласно начальнойплотности π(x).(j−1) 2. Согласно вероятности p(a) ξ0и алгоритму 2.7 определяемфакт обрыва траектории.3. Если обрыв траектории произошел, то полагаем N = j − 1 ипрекращаем моделирование траектории.404. Если обрыва не произошло, то численно моделируем выбороч(j)(j−1)ное значение ξ0 согласно плотности r ξ0, x , а затем полагаемj := j + 1 и переходим на пункт 2 данного алгоритма.В алгоритме 2.8 и далее знак «:=» означает переприсваивание,т. е. при A := B числа или результаты вычислений в правой части Bпомещаются в ячейку памяти ЭВМ с именем A.3.

Метод интегральной суперпозиции.Рандомизация. Метод условногоматематического ожидания. Методрасщепления3.1. Метод интегральной суперпозиции. В этом разделе мы используем рассуждения подразделов 2.1 и 2.2 в многомерном случае (т. е.с учетом замечания 2.2) для изучения методов рандомизации, означающих специальное введение случайных величин для построения и модификации численных алгоритмов.Сразу отметим, что сама общая схема метода Монте-Карло (алгоритм 1.1) и ее применение для вычисления интеграла (алгоритм 1.2)являются примерами рандомизации задачи приближенного вычислениявеличины I, связанными со специальным введением случайных величин(оценивателей) ζ.Сначала представим следующий пример применения метода рандомизации при численном моделировании случайных векторов.Предположим, что требуется построить алгоритм численного моделирования (реализации на компьютере) выборочного значения ξ̃ 0k-мерного вектора ξ̃, плотность которого представляет собой интеграл,зависящий от параметра u ∈ U ⊆ Rk :Zf ˜ (u) =p(u, v) dv; u ∈ U ; V ⊆ Rm ,(3.1)ξVи, кроме того,1) функция p(u, v) является совместной плотностью распределенияd-мерного случайного вектора ξ = ξ̃, η̃ в X = U × V ⊆ Rk (здесьd = k + m), для которой, в частности, можно выписать многомерныйаналог представления (2.6), (2.7) (с заменой ξ (1) на ξ̃ и ξ (2) на η̃):p(u, v) = fη̃ (v)f ˜ (u|v);ξ41(3.2)Zfη̃ (v) =p(u, v)p(u, v) du; f ˜ (u|v) =;ξfη̃ (v)U(3.3)2) в соответствующем аналоге формулы (2.5) (это комбинация формул (3.1) и (3.2))Zf ˜ (u) =fη̃ (v)f ˜ (u|v) dv,(3.4)ξξVкоторый можно назвать формулой для «безусловной» плотности случайного вектора (случайной величины) ξ̃, плотности (3.3) являются«моделируемыми»: для реализации выборочного значения η̃ 0 случайного вектора (случайной величины) η̃, распределенного согласно плотности fη̃ (v), и выборочного значения ξ̃ 0 случайного вектора ξ̃, распределенного согласно плотности f ˜ (u|v) (для каждого фиксированногоξv), имеютсяэффективные (экономичные)алгоритмы (формулы) видаη̃ 0 = ψη̃ ᾱ1 , ξ̃ 0 = ψ ˜ ᾱ2 ; v , где ᾱi – соответствующие наборы станξдартных случайных чисел.При сделанных предположениях можно рассмотреть следующий многомерный аналог алгоритма 2.2 (с заменой ξ (1) на ξ̃ и ξ (2) на η̃) – методинтегральной суперпозиции (рандомизации).АЛГОРИТМ 3.1 (см., например, [9, 13]).

Численно моделируем выборочное значение ξ̃ 0 случайного вектора (случайной величины) ξ̃, распределенного согласно плотности (3.4), используя алгоритм (формулу) ξ̃ 0 = ψ ˜ ᾱ2 ; η̃ 0 , где выборочное значение η̃ 0 случайного вектораξ(случайной величины) η̃ реализованона компьютере с помощью алгоритма (формулы) η̃ 0 = ψη̃ ᾱ1 .ЗАМЕЧАНИЕ 3.1. Отличие алгоритма 3.1 от многомерного аналогаалгоритма 2.2 (с заменой ξ (1) на ξ̃ и ξ (2) на η̃) состоит в том, что в алгоритме 2.2 компоненты ξ (1) и ξ (2) являются равнозначными (одинакововажными), в то время как в алгоритме 3.1, учитывая постановку задачидля метода интегральной суперпозиции, компонента ξ̃ вектора ξ = ξ̃, η̃является основной (для моделирования), а компонента η̃ – вспомогательной.ЗАМЕЧАНИЕ 3.2. Метод интегральной суперпозиции (алгоритм 3.1)является некоторой альтернативой алгоритму 2.3 (когда последний алгоритм неприменим и одновременно справедливо представление (3.4) с соответствующими предположениями).Следует отметить, что применение алгоритма 3.1 является довольноредким.42При этом весьма частым является применение дискретного аналогаалгоритма 3.1 для случая, когда вспомогательный случайный вектор η̃является одномерной целочисленной случайной величиной η.Здесь интеграл (3.4) превращается в соответствующую взвешеннуюсумму моделируемых плотностей, а при моделировании целочисленногозначения η0 вспомогательной случайной величины η используется тот илииной алгоритм моделирования дискретной случайной величины (см.,например, [9, 13], а также раздел 10 данного пособия).Соответствующий алгоритм называется методом дискретной суперпозиции или просто методом суперпозиции (см., например, [9, 13], атакже подраздел 11.1 данного пособия).ЗАМЕЧАНИЕ 3.3.

Ситуацию, возникающую при постановке задачидля метода интегральной суперпозиции можно трактовать следующим образом.Пусть нам требуется численно смоделировать выборочное значениеk-мерной компоненты ξ̃ d-мерного случайного вектора ξ = ξ̃, η̃ (здесьd = k + m).«Подходящим» для моделирования оказывается многомерный аналогалгоритма 2.2 (с заменой ξ (1) на ξ̃ и ξ (2) на η̃) для разложения (3.2), (3.3)(это аналог формул (2.6), (2.7)), в то время как для разложения типа (2.4),(2.5) многомерный аналог алгоритма 2.1 (все с той же заменой ξ (1) на ξ̃и ξ (2) на η̃) построить не удается по той причине, что интеграл (3.4) (или(3.1)) не берется аналитически.К слову, такую ситуацию, когда одно из разложений (2.4), (2.5) или(2.6), (2.7) является «моделируемым», а второе – нет, дает технологияраспределенного (взвешенного) параметра для конструирования моделируемых распределений двумерных случайных векторов с зависимыми компонентами (технология Б), представленная далее в подразделе 14.3 данного пособия (см.

Характеристики

Тип файла
PDF-файл
Размер
2,55 Mb
Тип материала
Высшее учебное заведение

Список файлов книги

Свежие статьи
Популярно сейчас
Зачем заказывать выполнение своего задания, если оно уже было выполнено много много раз? Его можно просто купить или даже скачать бесплатно на СтудИзбе. Найдите нужный учебный материал у нас!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6710
Авторов
на СтудИзбе
287
Средний доход
с одного платного файла
Обучение Подробнее