Введение к работе
Актуальность темы. С развитием вычислительной техники возрастает интерес к численным методам решения прикладных задач, в том числе, к алгоритмам численного статистического моделирования (или методам Монте-Карло). Классические методы Монте-Карло применяются для вычисления отдельных величин, предста-вимых в виде математических ожиданий от моделируемых на ЭВМ случайных элементов. В последнее время развивается теория функциональных вероятностных алгоритмов, позволяющих оценить неизвестную функцию одновременно во многих точках. Одним из первых функциональных алгоритмов явился метод зависимых испытаний для приближения интеграла, зависящего от параметра, предложенный А.С.Фроловым и Н.Н.Ченцовым. В работах Г.А.Михайлова, А.В.Войтишека и Е.В.Шкарупа рассмотрена концепция дискретно-стохастических численных процедур (ДСЧП), включающая введение дискретной сетки, оценку исследуемой функции в узлах сетки методом Монте-Карло и последующее построение глобальной аппроксимации в некоторой области, основанное на разложении функции по соответствующему функциональному базису. Основными примерами функций, при приближении которых эффективно используются ДСЧП, являются интеграл, зависящий от параметра, и решение интегрального уравнения Фредгольма второго рода.
При построении ДСЧП очень важным является выбор используемого метода аппроксимации функции, при котором необходимо руководствоваться соображениями минимизации трудоемкости процедуры. Поэтому методы аппроксимации следует выбирать так, чтобы уменьшить количество узлов сетки, необходимых для построения приближения с заданной погрешностью. Помимо этого, конструкция ДСЧП предъявляет повышенные требования к устойчивости метода относительно погрешности задания данных в узлах сетки. Кроме того, известны также возможности эффективного применения аппроксимационных методов для приближения сложных вероятностных плотностей распределения (включая задачи численного стохастического интегрирования). Таким образом, и в задачах, где при моделировании случайных элементов точная плотность заменяется на приближенную, и при реализации ДСЧП возникает необходимость использовать детерминированные методы аппроксимации функций. По многим показателям целесообразным является
использование для данных задач аппроксимаций на основе финитных кусочно-полиномиальных базисных функций — аппроксимаций Стренга — Фикса.
Достаточно хорошо изучен случай использования аппроксимаций, построенных на основе финитных мультилинейных базисов с порождающей функцией, представляющей собой В-сплайн первого порядка. Выбор мультилинейной аппроксимации является оптимальным в случае, когда приближаемая функция не более чем дважды непрерывно дифференцируема. Однако часто приходится иметь дело и с более гладкими функциями, для которых можно строить аппроксимации более высокого порядка точности. Таким образом, актуальной является проблема применения более гладких, чем мульти-линейные, конечно-элементных восполнений при реализации ДСЧП и при приближении вероятностных плотностей.
В данной диссертационной работе эта проблема решена с помощью мультикубических аппроксимаций Стренга — Фикса, которые строятся на основе кусочно-кубических одномерных базисных функций. Рассмотрен общий подход к приближению функций, изложенный в монографии Г. Стренга и Дж. Фикса. Предлагается исследовать возможности использования аппроксимаций двух видов: по методу узловых конечных элементов и по абстрактному методу конечных элементов. Выбор мультикубических аппроксимаций в качестве решения проблемы использования гладких восполнений обусловлен тем, что, с одной стороны, для них значительно увеличивается точность аппроксимации по сравнению с линейным случаем, а с другой стороны, с дальнейшим ростом степени базисных функций существенно усложняется задача определения и вычисления коэффициентов. Кроме того, использование аппроксимаций с базисами высоких степеней имеет смысл только для очень гладких функций.
Рассматриваемые в данной диссертационной работе мультикуби-ческие аппроксимации Стренга — Фикса по методу узловых конечных элементов и абстрактному методу известны в теории сплайн-функций в одномерном случае как эрмитовы локальные сплайны и локальные кубические сплайны. Для таких сплайнов ранее был получен явный вид коэффициентов и доказаны утверждения о погрешности приближения для одномерного и двумерного случаев. В данной работе для эрмитовых и локальных мультикубических сплайнов выписан явный вид коэффициентов для случая произвольной размерности и доказаны утверждения о погрешности аппроксимации
функций и их первых производных. Кроме того, для всех рассматриваемых видов аппроксимации получены утверждения об устойчивости данных сплайнов и их первых производных к ошибке задания данных в узлах сетки.
Важной проблемой в теории ДСЧП является выбор вероятностного подхода к оценке погрешности, поскольку погрешность является случайной величиной. Наиболее глубоко исследованы Li- и С-подходы, позволяющие разложить погрешность на компоненты - детерминированную и стохастическую. В данной работе, помимо упомянутых, разрабатывается новый (71-подход к оценке погрешностей ДСЧП с гладкими восполнениями. Одним из основных в теории ДСЧП является вопрос об оптимальном с точки зрения минимизации трудоемкости выборе параметров процедуры — числа узлов сетки и числа статистических испытаний в каждом узле. В данной работе решается проблема выбора условно-оптимальных параметров ДСЧП с гладкими восполнениями для L2-, С- и (71-подходов.
Основные цели работы.
Получить явный вид коэффициентов приближения эрмитовыми и локальными мультикубическими сплайнами в многомерном случае. Доказать утверждения о скорости сходимости и устойчивости полученных приближений функций и их производных.
Изучить возможности использования мультикубических приближений функций в алгоритме выборки по важности.
Разработать С1-подход для построения верхних границ погрешности и выбора условно-оптимальных параметров для дискретно-стохастических численных процедур (ДСЧП) с мультикубическими восполнениями.
Получить верхние границы погрешности и условно-оптимальные параметры ДСЧП с мультикубическими восполнениями для 1і2~, С- и (71-подходов (на примере задачи приближения интеграла, зависящего от параметра).
Продемонстрировать особенности использования ДСЧП с мультикубическими восполнениями на тестовых и прикладных задачах (включая случаи приближения решений интегральных уравнений).
Методика исследований базируется на теории численных алгоритмов, в первую очередь, методов Монте-Карло и проекционно-сеточных методов. Используются также результаты из теории дискретно-стохастических численных методов.
Научная новизна работы. В диссертации получены следующие новые результаты, выносимые на защиту:
Для мультикубических аппроксимаций Стренга — Фикса, которые являются обобщениями эрмитовых и локальных кубических сплайнов, выписан явный вид коэффициентов и доказаны утверждения о погрешности приближения функций и их первых производных, а также исследованы свойства устойчивости.
Исследованы возможности применения мультикубических аппроксимаций Стренга — Фикса в алгоритме выборки по важности. Предложена модификация технологии «отделения подынтегральной функции от нуля».
Разработан новый С '-подход к оценке погрешности и условной оптимизации дискретно-стохастических численных процедур (ДСЧП) с мультикубическими восполнениями.
Для случая приближения интеграла, зависящего от параметра, получены верхние границы погрешностей и выражения для условно-оптимальных параметров ДСЧП с мультикубическими восполнениями (в смысле 1і2~, С- и (71-подходов).
Проведено тестирование ДСЧП с мультикубическими восполнениями на примере аппроксимации интеграла, зависящего от параметра. Показаны возможности применения ДСЧП с мультикубическими восполнениями для глобального приближения решения интегрального уравнения второго рода на примере прикладной задачи из теории переноса излучения.
Практическая ценность работы. Разработанные в диссертации подходы к построению верхних границ погрешности и получению выражений для условно-оптимальных параметров ДСЧП с мультикубическими восполнениями могут применяться при глобальном приближении гладких решений задач математической физики. Использование мультикубических восполнений позволяет существенно снизить трудоемкость процедур решения таких задач по сравнению с изученным ранее мультилинейным случаем.
Публикации. Основные результаты опубликованы в 8 работах, список которых помещен в конце автореферата.
Апробация работы. Результаты, изложенные в диссертации, были представлены на V Международной конференции по моделированию (Санкт-Петербург, 2005 г.) [2], на VII Международном совещании «Кубатурные формулы и их приложения» (Красноярск, 2003) [3], на VIII Международном совещании «Кубатурные формулы и их приложения» (Улан-Удэ, 2005) [4], на конференциях молодых ученых Института вычислительной математики и математической геофизики 2003 и 2005 годов [5, 6], на XLI и XLIII Международных конференциях «Студент и научно-технический прогресс» (Новосибирск, НГУ, 2003, 2005) [7, 8]; на семинарах отдела статистического моделирования в физике и объединенном семинаре кафедры вычислительной математики НГУ и ИВМиМГ СО РАН.
Структура и объем работы. Диссертация состоит из введения, трех глав, содержащих 9 параграфов, заключения, списка литературы из 33 наименований. Объем работы - 83 машинописных страницы.
