Диссертация (1150625), страница 13
Текст из файла (страница 13)
В некоторых случаях наблюдаются скачки в константе сходимости, ко-69Оценка стандартного отклонения2-7МетодMCQint_0Qint_1Qint_2Qint_3Qint_4Qint_5Qint_6Qint_7Qint_8Qint_9Qint_10Qint_11Qint_12Qint_13Qint_14Best Qint2-82-92-102-112829210211212213214Количество вычислений подынтегральной функции215216Рисунок 2.9: Плотность нормального распределения, = 20, без внешних повторовгда кратно , то есть в такие моменты, когда бинарное рассечение проводится равномернопо всем имеющимся размерностям.Мы можем очертить круг вопросов, которые могли бы служить ориентиром для дальнейшихисследований предлагаемой схемы.
Во-первых, представляет интерес возможность построенияиного алгоритма разбиения гиперкуба, при котором подмножества X1 , . . . , X имели бы болеесложную форму. Это позволило бы снять существующее ограничение = 2 , которое можетиграть существенную роль в прикладных задачах.
С этим вопросом тесно связана другая перспективная возможность: адаптивная схема Qint, которая строила бы оптимальное (в некоторомстрогом смысле) разбиение с учётом уже имеющейся информации о подынтегральной функции.Во-вторых, схема Qint совместима с любой (,)-последовательностью, а не только с точкамиСоболя. В этом свете предложенный метод может иметь очень широкое применение, например,в сочетании с последовательностями Нидеррейтера или Форе.Наконец, принципиальное значение играет дальнейшее улучшение процедуры оцениваниядисперсии.
Известные квазислучайные последовательности (в их число входит и последовательность Соболя) обладают ещё и тем свойством, что проекции точек на координатные плоскоститакже обладают свойствами равномерной (в смысле дискрепанса) распределённости. Это свойство в настоящий момент не учитывается оценкой дисперсии Qint, но оно может иметь важноевлияние на скорость сходимости квази-Монте-Карло.
Возможно, выигрыш от перехода к квазислучайным последовательностям лишь частично улавливается процедурой Qint. Вполне веро-702-62-72-8Оценка стандартного отклонения2-9МетодMCQint_0Qint_1Qint_2Qint_3Qint_4Qint_5Qint_6Qint_7Qint_8Qint_9Qint_10Best QintRQMC2-102-112-122-132-142-152-162-172-182829210211212213214Количество вычислений подынтегральной функции215216Рисунок 2.10: Плотность нормального распределения, = 20, 16 внешних повторовятно, что рандомизированный квази-Монте-Карло обладает свойством точности для ещё какойто системы функций. Отыскание такой системы (не являющейся линейно зависимой с системойХаара) могло бы уточнить имеющуюся оценку.Основные результаты второй главы диссертационной работы посвящены вопросам практического применения полученного ранее класса квадратурных формул, точных для семейства кусочно-постоянных функций Хаара.
При помощи вспомогательной системы индикаторных функций удаётся получить несколько эквивалентных формулировок дисперсии схемы Qint(теорема 8), которые более удобны для построения апостериорных оценок. По аналогии с рандомизированным квази-Монте-Карло вводится обобщённая схема Qint, предполагающая повторений схемы по точек в каждой с условием независимости рандомизации между схемами.Вид обобщённой схемы и её дисперсия установлены теоремой 9.
Проводится анализ сходимостипо параметрам и .На основе теоретических результатов об обобщённой схеме предлагается несколько способовоценивания дисперсии в практических задачах. Теорема 10 даёт представление о монотонностидисперсии обобщённой схемы и её оценки для частного случая = 2 , = 2 с точки зрениябаланса между и . Предлагается правило бинарного рассечения: последовательный алгоритмпостроения согласованных ( , )-разбиений для произвольной размерности . Предложеннаясхема применяется к нескольким тестовым задачам, проводится анализ эффективности Qint вразных размерностях.712-52-62-7Оценка стандартного отклонения2-8МетодMCQint_0Qint_1Qint_2Qint_3Qint_4Qint_5Qint_6Qint_7Qint_8Qint_9Qint_10Best QintRQMC2-92-102-112-122-132-142-152-162-172-182-192829210211212213214Количество вычислений подынтегральной функции215216Рисунок 2.11: Функция „Морокофф-Кафлиш №1“, = 1, 16 внешних повторов2-52-6Оценка стандартного отклонения2-7МетодMCQint_0Qint_1Qint_2Qint_3Qint_4Qint_5Qint_6Qint_7Qint_8Qint_9Qint_10Best QintRQMC2-82-92-102-112-122-132-142-152829210211212213214Количество вычислений подынтегральной функции215216Рисунок 2.12: Функция „Морокофф-Кафлиш №1“, = 2, 16 внешних повторов72Оценка стандартного отклонения2-7МетодMCQint_0Qint_1Qint_2Qint_3Qint_4Qint_5Qint_6Qint_7Qint_8Qint_9Qint_10Qint_11Qint_12Qint_13Qint_14Best Qint2-82-92-102-112829210211212213214Количество вычислений подынтегральной функции215216Рисунок 2.13: Функция „Морокофф-Кафлиш №1“, = 30, без внешних повторов2-7Оценка стандартного отклонения2-8МетодMCQint_0Qint_1Qint_2Qint_3Qint_4Qint_5Qint_6Qint_7Qint_8Qint_9Qint_10Best QintRQMC2-92-102-112-122-132-142829210211212213214Количество вычислений подынтегральной функции215216Рисунок 2.14: Функция „Морокофф-Кафлиш №1“, = 30, 16 внешних повторов732-32-4Оценка стандартного отклонения2-5МетодMCQint_0Qint_1Qint_2Qint_3Qint_4Qint_5Qint_6Qint_7Qint_8Qint_9Qint_10Best QintRQMC2-62-72-82-92-102-112-122-132-142829210211212213214Количество вычислений подынтегральной функции215216Рисунок 2.15: Кусочно-линейная функция, = 3, 16 внешних повторов2-32-4Оценка стандартного отклонения2-52МетодMCQint_0Qint_1Qint_2Qint_3Qint_4Qint_5Qint_6Qint_7Qint_8Qint_9Qint_10Best QintRQMC-62-72-82-92-102-112-122-132-142829210211212213214Количество вычислений подынтегральной функции215216Рисунок 2.16: Кусочно-линейная функция, = 5, 16 внешних повторов74Оценка стандартного отклонения2-3МетодMCQint_0Qint_1Qint_2Qint_3Qint_4Qint_5Qint_6Qint_7Qint_8Qint_9Qint_10Qint_11Qint_12Qint_13Qint_14Best Qint2-42-52-62-72-82829210211212213214Количество вычислений подынтегральной функции215216Рисунок 2.17: Кусочно-линейная функция, = 10, без внешних повторов2-22-3Оценка стандартного отклонения2-4МетодMCQint_0Qint_1Qint_2Qint_3Qint_4Qint_5Qint_6Qint_7Qint_8Qint_9Qint_10Best QintRQMC2-52-62-72-82-92-102-112-122-132829210211212213214Количество вычислений подынтегральной функции215216Рисунок 2.18: Кусочно-линейная функция, = 10, 16 внешних повторов75Глава 3Расслоение и метод квази-Монте-Карло вразличных задачахКак нам удалось показать в предыдущих главах, расслоение в методе Монте-Карло и концепция равномерной распределённости для квазислучайных последовательностей имеют многообщего.
Более того, детерминированные low-discrepancy сети и последовательности можно вопределённом смысле рассматривать как некий „предельный“ случай расслоения, притом настолько удачный, что в момент перехода к этому „пределу“ происходит качественный скачокв асимптотике дискрепанса, и, соответственно, дисперсии рандомизированного квази-МонтеКарло. Это рассуждение свидетельствует в пользу той идеи, что любое практическое расслоение в различных задачах, решаемых методом Монте-Карло, можно заменить на адаптированныйквази-Монте-Карло, то есть последний приобретает смысл нового метода понижения дисперсии.Всё вышесказанное рассматривалось нами только в рамках задачи численного интегрирования, которая является привычной средой для квази-Монте-Карло.
Однако метод Монте-Карлоимеет гораздо более широкую область применения, в которую, среди прочих, входят задачи моделирования распределений и траекторий процессов. Важным для дальнейшего развития методаквази-Монте-Карло является вопрос о его применимости в таких, более алгоритмически сложных задачах.
В этой главе мы покажем, каким образом традиционные для Монте-Карло схемымогут быть изменены, чтобы использовать расслоение, и, далее, чтобы задействовать квазислучайные последовательности и их преимущества.3.1О смещении рандомизированного квази-Монте-КарлоКак уже отмечалось ранее, алгоритм Qint представляет собой новый подход к процедуреоценивания дисперсии рандомизированного квази-Монте-Карло.
Легко наблюдать, что предлагаемый алгоритм может иметь несколько достаточно простых модификаций, расширяющих область его применения. Одной из таких модификаций является обобщение на случай основания > 2: для произвольной (,)-последовательности по основанию можно построить такую схему разбиения гиперкуба, чтобы обеспечивалось свойство равномерности распределения узлов.76Другой вопрос, который представляет интерес, может быть сформулирован следующим образом.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
