Диссертация (1150625), страница 3
Текст из файла (страница 3)
Кроме того, предлагаемая гибридная адаптация метода „блуждания по сферам“ сочетает в себе преимущества какМонте-Карло (смещение оценки имеет место, но оно не превосходит смещения базовой схемы),так и квази-Монте-Карло (значительное уменьшение дисперсии). Предлагаемая схема, по сути,даёт возможность использовать квазислучайные конструкции в таких задачах, где это традиционно считается невозможным или нецелесообразным.Методология и методы исследованияВ диссертационной работе использовались теория вероятностей, элементы математическогои функционального анализа и вычислительных методов, теория методов Монте-Карло и квазиМонте-Карло и теория случайных квадратурных формул.
В численных экспериментах широкоиспользовались последовательности Соболя, рандомизированные при помощи процедуры скрэмблинга. Программирование велось на языках C++ и R с использованием модифицированнойбиблиотеки HIntLib с открытым исходным кодом, а также ряда пакетов дополнений для R.Положения, выносимые на защиту1) Получен класс квадратурных формул, обладающих свойством точности для системы обобщённых функций Хаара. Проведён анализ дисперсии таких формул и показано, что такойподход является одним из методов гарантированного уменьшения дисперсии.102) Представлен ряд утверждений, обобщающих и дополняющих известные результаты в рамках теории случайных квадратурных формул.3) Проведена параллель между использованием полученного класса формул в рамках подходов Монте-Карло и квази-Монте-Карло.
Предложена новая схема оценки погрешности взадачах численного интегрирования методом квази-Монте-Карло.4) Разработан алгоритм, реализующий описанную схему. Исследованы свойства оценок, построенных этим алгоритмом. Приведены результаты работы алгоритма в широком спектревычислительных задач и показана его эффективность.5) Разработан альтернативный метод рандомизации квазислучайных последовательностей.Показано, что его использование, с одной стороны, значительно эффективнее, чем традиционное расслоение. С другой стороны, естественная параметризация предлагаемогометода позволяет сохранить асимптотику квази-Монте-Карло и превосходить существующие методы рандомизации в численных экспериментах.6) На основе предлагаемого алгоритма рандомизации предложена адаптация метода „блуждания по сферам“ для решения внутренней задачи Дирихле для оператора Лапласа.Степень достоверности и апробация результатовДостоверность и обоснованность теоретических результатов диссертационной работы подтверждается их согласованностью с известными утверждениями в теории методов Монте-Карлои квази-Монте-Карло, в частности с фактами теории случайных квадратурных формул.
Данные, полученные в ходе обширных вычислительных экспериментов, соответствуют полученнымтеоретическим результатам. Они приведены и подробно описаны в тексте диссертации.Основные результаты диссертационной работы докладывались на следующих конференциях:– Ninth International Conference on Monte Carlo and Quasi-Monte Carlo Methods in ScientificComputing (MCQMC-2010, Варшава, Польша);– Seventh International Workshop on Simulation (IWS-2013, Римини, Италия);– Ninth IMACS Seminar on Monte Carlo Methods (IMACS-2013, Аннеси-ле-Вьё, Франция);– Eleventh International Conference on Monte Carlo and Quasi-Monte Carlo Methods in ScientificComputing (MCQMC-2014, Лювен, Бельгия).Исследование по теме диссертационной работы выполнено при частичной поддержке грантов РФФИ №11-01-00769-а и №14-01-00271.Публикации по теме диссертацииОсновные результаты по теме диссертации изложены в 5 печатных изданиях, 3 [18–20] изкоторых изданы в журналах, рекомендованных ВАК.
В [18] соискателем сформулированы идоказаны теоремы 1 и 2 о виде и дисперсии формулы, точной для обобщённой системы Хаара,11а также результаты численных экспериментов. В [20] соискателю принадлежит лемма 2.5, атакже теоремы 2.6, 3.1 и 3.2. В обеих совместных работах соавтору – научному руководителю –принадлежит общая постановка задачи и план исследований.Структура работыДиссертация состоит из введения, трёх глав и заключения. Она изложена на 106 странцахтекста с 32 рисунками и 3 таблицами. Список литературы содержит 75 наименований.12Глава 1Теоретические основы метода Qint1.11.1.1Обзор методов Монте-Карло и квази-Монте-КарлоДве постановки задачи численного интегрированияРассмотрим произвольное пространство (X,F,), где X – непустое множество, а F – -алгебрадля подмножеств X с мерой на ней.
Здесь и далее мера предполагается -конечной, и дляудобства мы будем полагать (X) = 1. Это ограничение несущественно1 , и все последующиерезультаты могут быть сформулированы для произвольной -конечной меры тривиальным образом.Классической считается задача определения значения -мерного интеграла∫︁= ()(),(1.1)Xгде функция : X → R интегрируема по мере . Далее все утверждения о функциях, определённых на пространстве X, подразумевают традиционную оговорку о множествах нулевой -меры,которая опущена для краткости.Наиболее распространённым частным случаем такой задачи является такой случай, когдаX есть единичный -мерный гиперкуб = [0,1) , F – борелевская -алгебра B на нём, а – мера Лебега, обозначаемая далее .
Очевидно, что для любого выполнено ( ) = 1.Чтобы различать эти два случая, (X,F,) и ( ,B , ), мы будем называть их общей и частнойпостановкой, соответственно.Здесь и далее мы будем обозначать вектора жирным шрифтом (, 1 , . . . , ), а их скалярныекомпоненты – обычным ( = (1 , . . . , ), с добавлением запятой в случае уже имеющегосянижнего индекса: = (,1 , . . . , , )).Рассматриваемая задача численного интегрирования будет интересовать нас с точки зренияметодов Монте-Карло и квази-Монте-Карло. Сравнению этих методов с классическими и совре1Любая сигма-конечная мера сводится к мере с искомым свойством при помощи нормировки на константу; см.Колмогоров А.Н.
и Фомин С.В., [21], Ширяев А.Н. [22].13менными детерминированными методами посвящено достаточное количество литературы (средикоторых особенно выделяется работа Шюрера Р. [23]). Этот вопрос достаточно сложен и требуетдополнительного изучения, но он остаётся за рамками данного исследования.1.1.2Традиционный метод Монте-КарлоМетод Монте-Карло (также именуемый далее традиционным или наивным Монте-Карло, взарубежной литературе Monte Carlo, MC) широко используется в задачах, где размерность области интегрирования достаточно высока. Такие задачи возникают в различных разделах физики(например, физика элементарных частиц, термодинамика, оптика, статистическая физика), равнокак и во многих других областях (биология, химия, медицина, эконометрика). Более подробноеизложение метода можно найти в книгах Ермакова С.М. [6] и Соболя И.М.
[24].В рамках частной постановки задачи численного интегрирования простейшей оценкой интеграла служит сумма 1 ∑︁= ( ), =1(1.2)где 1 , . . . , – независимые случайные вектора, равномерно распределённые в . Это несмещённая оценка интеграла, т.е. E( ) = . Кроме того, в соответствии с сильным законом больших чисел, оценка сходится к истинному значению интеграла почти наверное:п.н. −−→ .(1.3)→∞Обычно предполагается, что функция интегрируема с квадратом, т.е. ∈ ℒ2 ( ).
В этомслучае дисперсия функции () конечна:2∫︁2∫︁( () − ) == 2 () − 2 .(1.4)Дисперсия оценки (1.2) будет равна⎛Var( ) =∫︁∫︁···⎝1∑︁⎞2 ( ) − ⎠ 1 . . . ==12.(1.5)Выражение (1.5) может быть интерпретировано следующим образом: средняя ошибка интегри√рования методом Монте-Карло равна / . Более подробно, в силу центральной предельнойтеоремы имеет место следующий доверительный интервал:(︃)︃(︂)︂∫︁12lim P √ 6 − 6 √=√exp −.→∞22(1.6)14На практике дисперсия подынтегральной функции 2 неизвестна, поэтому вместо неё для построения доверительного интервала (1.6) используется оценкаˆ2)︁21 ∑︁ (︁= ( ) − , − 1 =1(1.7)обладающая свойством несмещённости: E(ˆ 2 ( )) = 2 ( ). Таким образом, дисперсия оценкиМонте-Карло (1.2) на практике оценивается при помощи̂︂ ) =Var()︁2∑︁ (︁1 ( ) − .( − 1) =1Когда говорят о том, что сходимость метода Монте-Карло равна (1.8)(︁√1)︁, имеют в виду ве-роятностный характер этой сходимости, устанавливаемый шириной доверительного интервала (1.6).
В случае с классическими квадратурами вычислительной математики, напротив, сходимость подразумевается строго детерминированная.(︁ Так,)︁ например, для метода Симпсона в1многомерном случае порядок ошибки составляет 2/.Принципиальное отличие метода Монте-Карло от классических состоит ещё и в том, чтопорядок убывания ошибки не зависит от размерности интеграла . Это ведёт к тому, что с точкизрения асимптотики формула вида (1.2) превосходит классические квадратуры для достаточнонебольших , и этот разрыв только увеличивается с ростом размерности. Так, в сравнении свышеупомянутой формулой Симпсона метод Монте-Карло предпочтителен в этом плане ужедля > 5.1.1.3Расслоенная выборкаНесмотря на то, что асимптотика убыванияостатка для метода Монте-Карло не зависит от(︁ )︁1размерности интеграла, её порядок √ даёт достаточно медленную сходимость.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
