Диссертация (1150625), страница 2
Текст из файла (страница 2)
Таким образом, эти сетки и последовательности оказываются тесносвязаны с понятием равномерной распределённости в смысле Вейля. В ряде случаев совокупность независимых реализаций случайной величины может быть заменена детерминированной(квазислучайной) структурой и привести к улучшенной сходимости. Так, в задаче численногоинтегрирования такая процедура может быть применена для любой интегрируемой по Римануподынтегральной функции, и при этом среднее по первым узлам будет стремиться к истинному значению интеграла при → ∞. Такой приём в сочетании со структурами, имеющимиопределённую асимптотику дискрепанса, получил название метода квази-Монте-Карло.В теории квази-Монте-Карло(︁последовательностьназывается low-discrepancy, если асимпто)︁ln тика её дискрепанса является .
В этом случае неравенство Коксмы-Хлавки, связывающее ошибку интегрирования с дискрепансом и вариацией подынтегральной функции (в смысле(︀ 1 )︀Харди-Краузе), обеспечивает скорость сходимости метода порядка 1−для сколь угодно малого > 0, что значительно лучше, чем порядок Монте-Карло. Первой известной low-discrepancyпоследовательностью является последовательность Холтона.
Уже упомянутая последовательность Соболя И.М. обладает ещё и тем преимуществом, что для неё известен эффективныйпоследовательный алгоритм Антонова И.А. и Салеева В.М. Более поздние конструкции, такиекак последовательности Форе Х. и Нидеррейтера Х., являются обобщением последовательности Соболя. Другой известной low-discrepancy конструкцией является класс решёточных правилинтегрирования (lattice rules).Самым известным недостатком метода квази-Монте-Карло является невозможность апостериорного контроля остатка, поскольку все известные оценки сверху, такие как неравенствоКоксмы-Хлавки и его обобщения, не являются конструктивными для практического применения.
В связи с этим разработаны способы рандомизации квазислучайных последовательностей(например, скрэмблинг Оуэна А.), и в практических задачах оценка погрешности также носитвероятностный характер. Это обстоятельство порождает необходимость проводить некоторое количество повторений процедуры с различными независимыми рандомизациями. Вопрос о доста-7точном количестве таких повторений не разрешён окончательно, что также порождает некоторыеограничения в практическом использовании квази-Монте-Карло.Вероятностные методы получили дальнейшее распространение в ряде других задач, для которых детерминированные алгоритмы оказывались слишком трудоёмкими.
Одной из таких задачявляется задача численного решения уравнений математической физики. Так, для внутренней⃒задачи Дирихле для оператора Лапласа, ∆ = 0 в области с краевым условием ⃒ = ,использование формул Грина и теоремы о среднем позволяет связать решение в точке с марковским процессом, обрывающимся на границе области. Этот результат позволяет свести задачу ксферическому процессу (процессу блуждания по сферам), траектории которого моделируютсянекоторое количество раз.
Применение расслоения в этом алгоритме сопряжено с алгоритмическими и вычислительными трудностями, а надёжной адаптации квази-Монте-Карло в настоящиймомент не существует. Это происходит в первую очередь потому, что последовательные точки вквазислучайных последовательностях формально не являются независимыми, что может приводить к катастрофическим последствиям даже в простейших схемах моделирования случайныхпроцессов. В настоящее время предпринимаются попытки расширить границы применимостиметода квази-Монте-Карло, но они ограничены лишь некоторыми частными случаями.Степень разработанности темыКоличество литературы, посвящённой теоретическим и практическим вопросам численныхметодов интегрирования, огромно. Среди этих работ можно назвать большое количество книги монографий (например, Крылов В.И.
[1], Бахвалов H.С. [2] и многие другие) и обзорныхжурнальных статей. Теория построения квадратурных формул, обладающих свойством точности для определённых классов функций, подробно описана в монографиях Соболева С.Л. [3],Мысовских И.П. [4].Обзор метода Монте-Карло и известных приёмов понижения дисперсии можно найти в книгах Ермакова С.М. и Михайлова Г.А. [5], Ермакова С.М. [6], Кохрана В.Г. [7]. Приём расслоенияхорошо известен и подробно изучен, однако дополнительный интерес вызывают свойства распределённости детерминированных последовательностей, имитирующих расслоение для разбиения на подмножества специального вида.Основы теории случайных интерполяционно-квадратурных формул изложены в книге Ермакова С.М.
[6]. Ключевыми в этой области являются работы Ермакова С.М. и Золотухина В.Г. [8],Ермакова С.М. [9, 10], Хэндскомба Д. [11]. Понятие допустимости случайной квадратуры введено и исследовано Ермаковым С.М. и Грановским Б.Л. [12], Ермаковым С.М. [13]. Случайныеквадратурные формулы представляют собой гибкий инструмент для решения сложных задач интегрирования методом Монте-Карло, в связи с чем обнаружение новых и обобщение имеющихсярезультатов представляет несомненную ценность.В теории метода квази-Монте-Карло в первую очередь необходимо выделить работы Соболя И.М.
[14, 15], Холтона Дж. [16], Нидеррейтера Х. [17]. Стандартная вычислительная схемарандомизированного квази-Монте-Карло достаточно хорошо известна, но асимптотика дисперсии метода получена только при наличии существенных ограничений.8Цель и задачи диссертационной работыЦелью диссертационной работы является исследование связи между классическими методами понижения дисперсии и свойствами квазислучайных последовательностей, а также изучениевопроса о возможности адаптации конструкций квази-Монте-Карло для алгоритмов, не сводимых к вычислению определённого интеграла по многомерному гиперкубу.
Для достижения означенной цели необходимо было решить следующие задачи.1) Использовать аппарат случайных квадратурных формул для получения класса формул, точных для кусочно-постоянных функций. Обобщить результаты Ермакова С.М. в многомерном случае с использованием обобщённых функций Хаара.2) Провести анализ дисперсии полученного класса формул и установить согласованность этого результата с оценкой сверху, сформулированной в общем виде Ермаковым С.М.
и Золотухиным В.Г.3) Проверить совместимость таких формул с квазислучайными последовательностями, в особенности с последовательностью Соболя. Представить новый метод оценки погрешностидля метода квази-Монте-Карло.4) Разработать численную схему, реализующую представленный подход. Исследовать свойства оценок, предложенных такой схемой.
Провести ряд численных экспериментов и проверить их соответствие теоретическим результатам.5) Выявить наличие связи между расслоением и (рандомизированным) квази-Монте-Карлов терминах асимптотики смещения и дисперсии в контексте задачи численного интегрирования и предложить адаптацию квази-Монте-Карло для задач, решаемых при помощимоделирования сферического процесса.Научная новизнаВсе результаты, полученные в диссертационной работе, являются новыми. А именно:1) Впервые установлена тесная связь между методами Монте-Карло и квази-Монте-Карлопосредством аппарата случайных квадратурных формул. Представлены новые результаты втеории случайных квадратурных формул, а имеющиеся результаты уточнены и дополнены.2) В отличие от существующих методов квази-Монте-Карло, которые не предоставляют конструктивной оценки погрешности либо оценивают неизвестную дисперсию, в работе впервые разработан новый метод оценивания схем рандомизированного квази-Монте-Карло,дисперсия которого известна теоретически.3) Предлагаемый метод рандомизации квазислучайных последовательностей и основанная нанём адаптация метода „блуждания по сферам“ предлагаются впервые.94) Все иллюстрирующие численные примеры, представленные в диссертационной работе,разработаны автором.Теоретическая и практическая значимость работыЗначимость диссертационной работы определяется тремя главными факторами.Во-первых, исследован класс формул, который можно рассматривать как предельный на стыке стохастического и детерминированного подходов в задачах численного интегрирования.
Такого рода формулы могут использоваться как в рамках традиционного метода Монте-Карло, являясь одним из методов понижения дисперсии, так и в сочетании с последовательностями методаквази-Монте-Карло, предоставляя конструктивный механизм оценки погрешности. Предлагаемая схема может быть применена к произвольной процедуре квази-Монте-Карло и не являетсяособенно трудной ни с точки зрения дополнительных вычислительных расходов, ни с точкизрения интерпретации конечного результата.
Такой подход может быть успешно применён взадачах, например, финансовой математики или вычислительной физики.Во-вторых, дополненный новыми результатами аппарат случайных квадратурных формул может послужить инструментом для отыскания новых классов квадратурных формул, обладающихопределёнными свойствами. Так, найдены достаточные условия для того, чтобы дисперсия таких формул была меньше, чем известная ранее верхняя граница.
Кроме того, показано, чтосистемы функций с попарно непересекающимися носителями не могут претендовать на пониженную таким способом дисперсию, что может послужить отправной точкой для дальнейшихисследований систем с более сложной структурой.В-третьих, новый метод рандомизации квазислучайных последовательностей может успешноконкурировать с существующими в задачах численного интегрирования.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
