Диссертация (Расслоение и метод квази-Монте-Карло)

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕНННЫЙ УНИВЕРСИТЕТНа правах рукописиАнтонов Антон АлександровичРасслоение и метод квази-Монте-Карло01.01.07 — вычислительная математикаДиссертация на соискание учёной степеникандидата физико-математических наукНаучный руководитель:доктор физико-математических наук, профессорЕрмаков С.М.Санкт-Петербург – 20152ОглавлениеВведение .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .41 Теоретические основы метода Qint . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121.11.2Обзор методов Монте-Карло и квази-Монте-Карло . . . . . . . . . . . . . . . . . . 121.1.1Две постановки задачи численного интегрирования . . . . . . . . .

. . . . . 121.1.2Традиционный метод Монте-Карло . . . . . . . . . . . . . . . . . . . . . . . 131.1.3Расслоенная выборка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141.1.4Случайные квадратурные формулы . . . . . . . . . . . . . . . . . . . . . . . 171.1.5Метод квази-Монте-Карло .

. . . . . . . . . . . . . . . . . . . . . . . . . . . 181.1.6Числовые сети и последовательности . . . . . . . . . . . . . . . . . . . . . . 211.1.7Последовательность Холтона . . . . . . . . . . . . . . . . . . . . . . . . . . . 221.1.8Последовательность Соболя . . . . . . . . . . . . . . . . . . . . . . .

. . . . 231.1.9Рандомизированный метод квази-Монте-Карло . . . . . . . . . . . . . . . . 25Квадратура Qint . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271.2.1Обобщённая система Хаара . . . . . . . . . . . . . . . . . . . . . . . . . . . 281.2.2Построение квадратуры Qint и анализ дисперсии . . . . . . . . . . . . . . . 301.2.3Некоторые результаты для теории случайных квадратурных формул . . . . 352 Практическое применение метода Qint . . .

. . . . . . . . . . . . . . . . . . . . . . . . 422.1Эквивалентные формулировки дисперсии Qint . . . . . . . . . . . . . . . . . . . . . 422.2Процедура Qint с повторами . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 452.3Оценивание дисперсии . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . 492.4Некоторые аспекты реализации алгоритма Qint . . . . . . . . . . . . . . . . . . . . 542.5Результаты численных экспериментов . . . . . . . . . . . . . . . . . . . . . . . . . . 602.5.1Произведение кубических полиномов .

. . . . . . . . . . . . . . . . . . . . . 612.5.2Плотность нормального распределения . . . . . . . . . . . . . . . . . . . . . 622.5.3Функция „Морокофф-Кафлиш №1“ . . . . . . . . . . . . . . . . . . . . . . . 642.5.4Кусочно-линейная функция . . . . . . . .

. . . . . . . . . . . . . . . . . . . . 662.5.5Выводы о практическом применении Qint . . . . . . . . . . . . . . . . . . . 6733 Расслоение и метод квази-Монте-Карло в различных задачах . . . . . . . . . . . . . 753.1О смещении рандомизированного квази-Монте-Карло . . .

. . . . . . . . . . . . . . 753.2Алгоритм гибридной битовой рандомизации . . . . . . . . . . . . . . . . . . . . . . 803.3Гибридная битовая рандомизация в задаче численного интегрирования . . . . . . . 853.4Гибридная битовая рандомизация для метода „блужданий по сфере“ . .

. . . . . . 88Заключение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98Список рисунков . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100Список таблиц . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101Список литературы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1024ВведениеАктуальность работыОдной из наиболее распространённых и ключевых задач в вычислительной математике является задача приближённого вычисления определённого интеграла. Такого рода задачи могутвозникать в различных академических исследованиях, но наиболее часто встречаются в прикладных областях. При этом они могут выступать как в качестве самостоятельных задач, так и являться важной промежуточной частью более сложных алгоритмов. В различных областях математики численное интегрирование активно используется для решения интегральных и интегродифференциальных уравнений.Наиболее полно разработана теория численного интегрирования по подмножествам одномерной вещественной оси R.

Для решения таких задач разработано множество различных классовоптимальных в том или ином строгом смысле квадратурных формул и сложных алгоритмов (среди них методы с автоматическим подбором шага, статистические и адаптивные методы). Этихинструментов достаточно, чтобы решить большинство практических задач с заданной наперёдточностью за разумное машинное время.Случай интегрирования по многомерным областям является гораздо более сложным и менееизученным.

Несмотря на ряд имеющихся ключевых результатов, теория многомерного интегрирования содержит большое количество открытых вопросов. Это связано в первую очередь с тем,что при увеличении размерности вычислительная трудоёмкость классических методов быстровозрастает. Кроме того, область интегрирования может иметь гораздо более сложную конфигурацию, поэтому значительная часть исследований посвящена только тем задачам, область интегрирования которых имеет достаточно простую форму (гиперкуб, шар или симплекс). Задачасведения произвольной области к стандартной также весьма сложна и сопряжена, как правило,с наличием существенных накладных расходов в процессе вычислений.Большинство имеющихся методов численного интегрирования можно отнести к трём основным группам: традиционные квадратурные (кубатурные при > 1) формулы, методы МонтеКарло и теоретико-числовые методы (методы квази-Монте-Карло).

Здесь и далее мы будем использовать термин „квадратурная формула“ независимо от того, какова размерность областиинтегрирования.В теории многомерного численного интегрирования ключевым является следующий результат, полученный Бахваловым H.С. Им установлено, что в размерности на классе функций (), имеющих ограниченные постоянной частные производные до порядка включитель-5)︁(︁но, сходимость любого детерминированного метода не может быть лучше, чем −/ (где – количество вычислений подынтегральной функции). Легко увидеть, что с ростом размерности этот порядок становится слишком медленным (нестрого говоря, при / <12оптимальныйметод начинает проигрывать в скорости сходимости методу Монте-Карло). Это обстоятельстводало толчок изучению недетерминированных методов интегрирования, то есть таких методов,где приближённое значение интеграла зависит от некоторого количества случайных величин.Необходимо понимать, что в таком случае детерминированная оценка погрешности квадратурной формулы заменяется на вероятностную, то есть имеющую место с некоторым наперёд заданным уровнем доверия.

Такие методы получили значительное распространение и выделилисьв отдельную группу методов численного интегрирования под общим названием метод МонтеКарло.Даже в простейшем случае метод Монте-Карло обладает рядом несомненных преимуществ.Это и крайняя простота реализации, и последовательный характер исполнения, обеспечивающийпрактически неограниченный параллелизм, и удобная схема апостериорного контроля погрешности. Важночто даже базовый метод Монте-Карло имеет в классе ℒ2 сходимость(︁ подчеркнуть,)︁порядка √1, которая не зависит от размерности интеграла.

Кроме того, существует обшир-ный спектр приёмов уменьшения дисперсии, позволяющих эффективно ускорять сходимостьметода.Одним из наиболее известных и универсальных приёмов понижения дисперсии являетсявведение зависимости в распределение узлов интегрирования. На этой идее основана теорияслучайных интерполяционно-квадратурных формул, разработанная Ермаковым С.М.

и Золотухиным В.Г. В рамках этой теории узлы интегрирования рассматриваются как случайные величиныс определённым совокупным распределением, а веса квадратурной формулы являются функцией узлов. Ермаковым С.М. и Грановским Б.Л. введено понятие допустимости таких процедур наклассах функций и исследованы критерии такой допустимости.Другим универсальным способом ускорения сходимости метода Монте-Карло является методрасслоенной выборки (stratified sampling). Он заключается в разбиении области интегрированияна несколько подобластей, интегрирование по которым в простейшем случае ведётся раздельно.При этом количество узлов в каждой конкретной подобласти зависит от её объёма, или, в болеесложных случаях, от конфигурации разбиения в целом.Бахваловым H.С. получен ещё один важный результат относительно сходимости недетерминированных методов на классе ().(︁ А именно, любойтакой метод имеет вероятностный)︁−/−1/2порядок сходимости не быстрее, чем .

Более того, такой метод построен имконструктивным образом и доказано, что представленная оценка неулучшаема в плане(︁ )︁порядка.Для класса ℒ2 оптимальный порядок сходимости вероятностного метода равен √1 , то естьдаже простейший метод Монте-Карло в этом случае неулучшаем по порядку.Несмотря на окончательный результат Бахвалова H.С. относительно широкого класса (),многими исследователями предпринимались попытки получить оценки сходимости методов интегрирования на других, более узких и более часто встречающихся на практике классах функций.6Так, в работах Коробова Н.М. рассматриваются классы и , для которых строятся параллелепипедальные сетки, для которых скорость сходимости весьма близка к оптимальной и отличается от неё лишь на множитель вида ln , где не зависит от . Построение такого рода сетокпорождает ряд вспомогательных теоретико-числовых задач о выборе оптимальных коэффициентов.

Похожих результатов достиг Соболь И.М. на классах функций с быстро убывающимикоэффициентами Фурье по системе Хаара.Им)︁ построена ЛП -последовательность, обеспечи(︁вающая порядок сходимости, равный −1/ , где не зависит от . При построении такойпоследовательности также возникает задача о подборе оптимальных параметров (направляющихчисел), решаемая методами теории чисел.Теоретико-числовые конструкции, предложенные Коробовым Н.М. и Соболем И.М., выделяются, помимо прочего, специфическим поведением величины дискрепанса (discrepancy, отклонение) – функции, являющейся количественной характеристикой расположения набора точекв единичном гиперкубе.