Дискретно-стохастические численные алгоритмы со сплайн-восполнениями тема диссертации и автореферата по ВАК РФ 01.01.07, кандидат физико-математических наук Милосердов, Владимир Владимирович

• Милосердов, Владимир Владимирович
• кандидат физико-математических наук
• 2006

Оглавление диссертации кандидат физико-математических наук Милосердов, Владимир Владимирович

Введение

1. Использование сеточных восполнений при решении задач методом Монте-Карло

1.1. Использование аппроксимаций в задачах статистического моделирования

1.2. Аппроксимации Стренга-Фикса.

1.3. Свойства аппроксимаций по методу узловых конечных элементов

1.4. Свойства аппроксимаций по абстрактному методу конечных элементов.

2. Дискретно-стохастические процедуры с использованием сплайн-аппроксимации Стренга — Фикса

2.1. Аппроксимации в стохастических методах численного интегрирования

2.2. ДСЧП глобальной аппроксимации функций. Оценка погрешности

2.3. Условная оптимизация дискретно-стохастических процедур

3. Численные эксперименты

3.1. Сравнение эффективности ДСЧП для различных сеточных восполнений

3.2. ДСЧП глобальной аппроксимации решения интегрального уравнения.

Введение диссертации (часть автореферата) на тему «Дискретно-стохастические численные алгоритмы со сплайн-восполнениями»

С развитием вычислительной техники возрастает интерес к численным методам решения прикладных задач, в том числе, к алгоритмам численного статистического моделирования (или методам Монте-Карло). Классические методы Монте-Карло применяются для вычисления отдельных скалярных величин, представимых в виде математических ожиданий от моделируемых на ЭВМ случайных элементов (см., например, [1-8]). В частности, при решении задач многомерного численного интегрирования используется представление интеграла в виде математического ожидания функции от случайного вектора. Аналогичным образом методы статистического моделирования используются при вычислении функционалов от решений интегральных уравнений; при этом используются представления таких функционалов в виде интегралов счетной размерности. Указанные алгоритмы позволяют получать отдельные значения интегралов, в том числе, значения решений интегральных уравнений в выбранных точках. В этой связи, одной из важных проблем, связанных с реализацией методов Монте-Карло на ЭВМ, является построение эффективных алгоритмов моделирования случайных элементов с заданными распределениями [1-6].

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

Наряду с классическими методами Монте-Карло, предназначенными в основном для вычисления отдельных скалярных величин, в последнее время развивается теория функциональных вероятностных алгоритмов, позволяющих оценить неизвестную функцию одновременно во многих точках (см. [7-15], а также библиографические списки в этих работах). Одним из первых функциональных алгоритмов явился метод зависимых испытаний для приближения интеграла, зависящего от параметра, предложенный А.С.Фроловым и Н.Н.Ченцовым [17]. Практическому применению функциональных алгоритмов при решении задач глобальной аппроксимации функций посвящены многие работы A.B. Войтишека [12-14]. В частности, в этих работах рассматривается концепция дискретно-стохастических численных процедур (ДСЧП), сутыо которых является построение глобальных приближений для функций с помощью детерминированных методов по приближённым значениям этих функций в узлах, вычисленным с помощью метода Монте-Карло.

Таким образом, и в задачах, где при моделировании случайных элементов точная плотность заменяется на приближённую, и при реализации ДСЧП возникает необходимость использовать детерминированные методы аппроксимации функций. Необходимо заметить, что кроме погрешности приближения детерминированного метода конструкция ДСЧП предъявляет повышенные требования к устойчивости метода относительно погрешности задания аппроксимируемой функции в узлах.

В данной диссертационной работе в качестве детерминированного метода аппроксимации функций рассматриваются аппроксимации Стренга — Фикса, построенные на прямоугольных сетках [18, 19]. Предполагается, что на области, на которой необходимо приблизить функцию, задана равномерная прямоугольная сетка и в каждом узле сетки заданы одна или несколько кусочно-полиномиальных финитных базисных функций. Аппроксимации Стренга — Фикса строятся как линейные комбинации базисных функций. Удобство аппроксимаций такого вида состоит в том, что они имеют локальный характер и их можно рассматривать на областях со сложной геометрией для произвольной размерности. Погрешность аппроксимации Стренга — Фикса напрямую зависит от степени кусочно-полиномиальных базисных функций. При использовании базисов более высокой степени удаётся получать более точные приближения при условии, что приближаемая функция является достаточно гладкой. В данной работе рассматриваются аппроксимации, полученные на основе кусочно-кубических базисных функций. Кроме того, в силу финитности базисных функций, аппроксимации Стренга — Фикса обладают свойствами устойчивости к погрешности задания функции в узлах. Наконец, рассматривая аппроксимации такого типа-с точки зрения статистического моделирования, заметим, что в случае применения аппроксимаций с базисными функциями на основе 2?-сплайнов при построении приближённых плотностей существует простой эффективный алгоритм моделирования.

Использование аппроксимаций Стренга — Фикса в ДСЧП впервые было предложено и исследоваио A.B. Войтишеком в [12-14] и получило развитие в работах Е.В. Шкарупа [14-16]. Идея ДСЧП глобальной аппроксимации функции заключается в следующем: на области, где необходимо построить глобальную аппроксимацию вводится сетка, далее в узлах данной сетки методом Монте-Карло строятся стохастические оценки значений приближаемой функции, и наконец, с помощью сеточного восполнения (аппроксимации Стренга — Фикса) функция аппроксимируется на всей области. В [12-15] разработаны подходы к исследованию ДСЧП при использовании аппроксимаций Стренга — Фикса в качестве сеточного восполнения на примере функций, заданных в интегральном виде, а именно: интеграла, зависящего от параметра,

Особенность исследуемых численных процедур заключается в том, что общая погрешность является случайной величиной. Однако, анализируя общую погрешность, можно выделить в ней две составляющие, одна из которых связана с погрешностью стохастических методов, а другая с погрешностью детерминированного метода приближения функций. Данные составляющие называют соответственно стохастической и дискретной компонентами погрешности ДСЧП. С точки зрения применения аппроксимации Стренга — Фикса дискретная компонента напрямую связана с погреши решения интегрального уравнения второго рода ностью аппроксимации, а стохастическая — со свойством устойчивости погрешности к ошибке задания функции в узлах сетки.

Поскольку погрешность ДСЧП является случайной величиной, то при её исследовании необходимо определить вид вероятностной сходимости этой величины к нулю при увеличении числа узлов сетки и числа испытаний при реализации алгоритмов метода Монте-Карло в узлах сетки. В [12] показано, что с точки зрения теории методов Монте-Карло естественным является так называемый ¿^""ОДХОД» когда в качестве меры погрешности рассматривается 1/2-норма разности между точной функцией и её глобальной аппроксимацией. В этом случае исследуется сходимость погрешности к нулю в среднем первого порядка. С точки зрения дискретных методов в качестве меры погрешности следует выбирать С-норму разности функций. Здесь целесообразно рассмотреть сходимость погрешности к нулю по вероятности. Аналогично для погрешности в пространстве С1 будем рассматривать сходимость по вероятности.

С помощью данных подходов в [12-15) исследована общая погрешность процедуры в случае использования аппроксимаций Стренга — Фикса, построенным по базисным функциям, являющимся тензорными произведениями Л-снлайнов. Кроме того, в данных работах подробно изучен случай мультилинейной аппроксимации, когда в качестве базисных функций для построения приближения берутся тензорные произведения 5-сплайнов первого порядка (функции-"крышки"). На основе оценок для общей погрешности ДСЧП получены выражения для условно-оптимальных параметров процедур, для которых трудоёмкость реализации процедуры достигает минимума при ограниченной сверху общей погрешности.

При построении мультилинейной аппроксимации выбор коэффициентов при базисных функциях достаточно очевиден. В силу того, что базисные функции являются разложением единицы в каждой точке пространства, в качестве коэффициентов целесообразно брать значения приближаемой функции в узлах сетки. Выбор мультилинейной аппроксимации с такими коэффициентами является оптимальным в случае, когда приближаемая функция не более чем дважды непрерывно дифференцируема. Однако часто приходится иметь дело и с более гладкими функциями, для которых можно строить аппроксимации более высокого порядка точности. В частности, в [16] исследуется применение эрмитовых кубических сплайнов специального вида для глобальной аппроксимации решения задачи Дирихле для уравнения Гельмгольца.

Таким образом, актуальной является проблема применения более гладких, чем мультилинейные, конечно-элементных восполнений при реализации ДСЧП и при приближении вероятностных плотностей. В данной диссертационной работе эта проблема решена с помощью мультикубических аппроксимаций Стренга — Фикса, которые строятся на основе кусочно-кубических одномерных базисных функций. Предлагается рассматривать более общий по сравнению с [12-15] подход к понятию аппроксимации Стренга — Фикса, который изложен в [18]. В частности, предлагается рассматривать использование аппроксимаций двух видов: по методу узловых конечных элементов и по абстрактному методу конечных элементов. Выбор мультикубических аппроксимаций в качестве решения проблемы использования гладких восполнений обусловлен тем, что, с одной стороны, для них значительно увеличивается точность аппроксимации по сравнению с линейным случаем, а с другой стороны, с дальнейшим ростом степени базисных функций существенно усложняется задача определения и вычисления коэффициентов. Кроме того, использование аппроксимаций с базисами высоких степеней имеет смысл только для очень гладких функций.

Рассматриваемые в данной диссертационной работе мультикубические аппроксимации Стренга — Фикса по методу узловых конечных элементов и абстрактному методу известны в теории сплайн-функций [21, 22\ как эрмитовы локальные сплайны и локальные кубические сплайны. Для таких сплайнов в [21, 22] выписан явный вид коэффициентов и получены утверждения о погрешности приближения для одномерного и двумерного случаев. В данной работе для эрмитовых кубических сплайнов и для локальных кубических сплайнов выписан явный вид коэффициентов для случая произвольной размерности и доказаны утверждения о погрешности аппроксимации функций и их первых производных. Кроме того, для всех видов аппроксимации получены утверждения об устойчивости данных сплайнов и их первых производных к ошибке задания данных в узлах сетки.

Основной целью данной диссертационной работы является исследование возможностей применения мультикубических конечно-элементных аппроксимаций в задачах статистического моделирования. Во-первых, рассматривается использование в стохастических методах численного интегрирования мультикубических аппроксимаций Стренга — Фикса с базисными функциями, являющимися тензорными произведениями кубических В-сплайнов. Во-вторых, исследуются ДСЧП глобальной аппроксимации функций, заданных в интегральном виде, в случае применения в качестве сеточного восполнения аппроксимаций Стренга — Фикса по методу узловых конечных элементов и по абстрактному методу конечных элементов.

Применение аппроксимаций в задаче численного интегрирования рассматривается на примере алгоритма выборки по важности, который основан на выборе моделируемой плотности, пропорциональной аппроксимации Стренга—Фикса модуля подынтегральной функции. Для алгоритма выборки по важности на основе утверждений о погрешности аппроксимации Стренга — Фикса исследуется связь между параметрами аппроксимации и общей погрешностью вычисления интеграла. Для случая знакопеременных подынтегральных функций предложен метод, позволяющий повышать скорость сходимости в алгоритме. Наконец, для случая использования аппроксимаций Стренга — Фикса рассматривается задача условной оптимизации параметров стохастических алгоритмов численного интегрирования. Задача состоит в определении значений параметров алгоритма, для которых трудоёмкость вычислений минимальна при условии, что погрешность вычисления интеграла ограничена сверху заданной величиной. В качестве параметра оптимизации рассматривается общее количество узлов сетки, необходимое для построения аппроксимации Стренга — Фикса. Получен явный вид оптимального количества узлов в случае использования мультикубических аппроксимаций Стренга — Фикса при построении приближённых плотностей,

В данной диссертационной работе основным объектом применения гладких кусочно-элементных восполнений являются дискретно-стохастические численные процедуры глобальной аппроксимации функций, заданных в интегральном виде. ДСЧП для случая применения мультикубических аппроксимаций Стренга — Фикса исследуется на примере интеграла, зависящего от параметра. В узлах сетки для интеграла, зависящего от параметра, рассмотрены несмещенные зависимые и независимые стохастические оценки, полученные с помощью метода Монте-Карло. Аналогично известным (см. [12-15]) подходам в пространствах Ь?, С получены верхние границы для погрешностей исследуемых функциональных алгоритмов с помощью утверждений о погрешности и устойчивости аппроксимации Стренга — Фикса. Кроме того, получены верхние границы для общей погрешности в пространстве С1. На основе этих оценок доказаны утверждения о сходимости глобальных аппроксимаций к приближаемым функциям в соответствующих пространствах. Для ДСЧП глобальной аппроксимации рассмотрена задача о минимизации трудоёмкости реализации процедуры при условии, что общая погрешность не превосходит заданной величины. Для случая использования кубических аппроксимаций Стренга — Фикса получены явные выражения для вычисления оптимальных параметров или утверждения о разрешимости задачи минимизации, которые гарантируют сходимость численных методов. Проведено тестирование исследуемых численных схем на примере интегралов, которые являются многомерными как по переменной интегрирования, так и по параметру. Проведён сравнительный анализ параметров ДСЧП для случаев использования мультилинейной и мультикубической интерполяции. Кроме того, показаны возможности применения ДСЧП с гладкими восполнениями для решения задач переноса излучения и краевых задач математической физики.

Диссертация состоит из Введения, трех глав, Заключения и списка литературы, содержащего 33 наименования.

Заключение диссертации по теме «Вычислительная математика», Милосердов, Владимир Владимирович

Заключение

Сформулируем основные результаты работы, которые выносятся на защиту и характеризуют новизну исследования.

1. Для мультикубических аппроксимаций Стренга — Фикса, которые являются многомерными обобщениями эрмитовых и локальных кубических сплайнов, выписан явный вид коэффициентов. Для данных видов аппроксимации получены оценки сверху для погрешности приближения функций и их первых производных. Выписан явный вид констант в оценках погрешностей.

2. Исследованы свойства устойчивости мультикубических аппроксимаций Стренга — Фикса к погрешности задания значений приближаемой функции в узлах сетки. Получены оценки сверху для величины возмущения аппроксимации, обусловленного погрешностью в узлах.

3. Исследованы возможности применения мультикубических аппроксимаций Стренга — Фикса в алгоритме выборки по важности для решения задачи численного интегрирования. Получена оценка сверху для дисперсии стохастической оценки значения интеграла. На основе данной оценки исследована трудоёмкость алгоритма выборки но важности и решена задача условной минимизации трудоёмкости при фиксированном значении погрешности вычислений. Предложена модификация технологии «отделения подынтегральной функции от нуля».

4. Разработан новый С ^подход к исследованию дискретно- стохастических численных процедур (ДСЧП). Для пространства С1, а также для пространств С, на примере приближения интеграла, зависящего от параметра, получены оценки сверху для общей погрешности глобальной аппроксимации. Доказаны утверждения о сходимости ДСЧП в рассматриваемых функциональных пространствах.

5. Получены формулы для вычисления условно-оптимальных значений параметров дискретно-стохастических численных процедур (ДСЧП) с мультикубическими восполнениями. Для данных значений достигается минимум трудоёмкости процедуры при условии, что оценка сверху для общей погрешности глобальной аппроксимации на превосходит заданного значения.

6. Проведено тестирование ДСЧП с мультикубическими восполнениями на примере аппроксимации интеграла, зависящего от параметра. Результаты расчётов полностью согласуются с теоретическими выкладками и подтверждают, что использование мультикубических восполнений существенно снижает трудоёмкость ДСЧП по сравнению с мультилинейными восполнениями.

7. Показаны возможности применения ДСЧП с мультикубическими восполнениями для глобального приближения решения интегрального уравнения второго рода на примере задачи, имеющей важное значение в теории переноса излучения.

Список литературы диссертационного исследования кандидат физико-математических наук Милосердов, Владимир Владимирович, 2006 год

1. Соболь И.М. Численные методы Монте-Карло. - М.: Наука, 1973.

2. Ермаков С.М., Михайлов Г.А. Статистическое моделирование. М.: Наука, 1982.

3. Войтишек А.В. Основы метода Монте-Карло в алгоритмах и задачах. Новосибирск: НГУ, 1997. Часть I: Обзор методов Монте-Карло. Генераторы случайных и псевдослучайных чисел.

4. Войтишек А.В. Основы метода Монте-Карло в алгоритмах и задачах. Новосибирск: НГУ, 1997. Часть И: Моделирование дискретных случайных величин. Моделирование непрерывных случайных величин методом обратной функции распределения.

5. Войтишек А.В. Основы метода Монте-Карло в алгоритмах и задачах. Новосибирск: НГУ, 1997. Часть IV: Моделирование случайных величин с распределениями, связанными с гамма-распределением. Моделирование случайных процессов и полей.

6. Войтишек А.В. Основы метода Монте-Карло в алгоритмах и задачах. Новосибирск: НГУ, 1999. Часть V: Вычисление многократных интегралов. Аппроксимация интегралов, зависящих от параметра.

7. Mikhailov G.A. Minimization of Computational Costs of Non-Analogue Monte Carlo Methods // Series of Soviet and East European jnathematics. Vol. 5. Singapore: World Scientific, 1991.

8. Mikhailov G.A. New Monte Carlo Methods with Estimating Derivatives. Utrecht: VSP, 1995.

9. Михайлов Г.А. Весовые методы Монте-Карло. Новосибирск, Изд-во СО РАН, 2000.

10. Войтишек А.В. Дискретно-стохастические численные методы (Диссертация на соискание уч. степени доктора физ.-матем. наук). Новосибирск, 2001.

11. Voytishek A.V. On the errors of discretely stochastic procedures in estimating globally the solution of an integral equation of the second kind // Russian Journal of Numerical Analysis and Mathematical Modelling. 1996. - V. 11, N 1. - P. 71 - 92.

12. Шкарупа Е.В. Сходимость и оптимизация дискретно-стохастических процедур // (Диссертация на соискание уч. степени кандидата, физ.-матем. наук). Новосибирск, 2000.

13. Makarov R., Shkarupa Е. Functional algorithms of Monte Carlo method for solving nonlinear boundary problems // Proceedings of the International conference on computational mathematics. Novosibirsk, 2004. - P. 341 - 346.

14. Фролов А.С., Ченцов H.H. О вычислении методом Монте-Карло определенных интегралов, зависящих от параметра // Журнал вычислительной математики и математической физики. 1962. - Т. 2, N 4. - С. 714 - 717.

15. Стренг Г., Фикс Дж. Теория метода конечных элементов. М.: Мир, 1977.

16. Марчук Г.И., Агошков В.И. Введение в проекционно-сеточные методы. М.: Наука, 1981.

17. Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. Численные методы. М.: Наука, 1987.

18. Завьялов Ю.С., Квасов Б.И., Мирошниченко В.Л. Методы сплайн-функций. М.: Наука, 1980.

19. Стечкин С.Б., Субботин Ю.Н. Сплайны в вычислительной математике. М.: Наука, 1976.

20. Владимиров B.C. Уравнения математической физики. М.: Наука, 1981.

21. Елепов Б.С. и др. Решение краевых задач методом методом Монте-Карло. Новосибирск: Наука, 1980.

22. Боровков А.А. Теория вероятностей.- М.: Наука, 1986.

23. Милосердое В.В. Условная оптимизация дискретно-стохастических численных процедур в случае применения кубических сплайнов // Сибирский журнал вычислительной математики. 2006. - Т. 9, N 2. - С. 147-163.

24. Voytishek A.V., Miloserdov V.V., Shvets V.V. Some problems of conditional optimization of discrete-stochastic numerical methods // Proceedings of the Fifth Workshop on Simulation (St.Petersburg, Russia; June 26 July 2, 2005). - P. 735-740.

25. Милосердое В.В. Использование кубических сплайнов в дискретно-стохастических численных алгоритмах // Материалы VII Международного семинара-совещания «Кубатур-ные формулы и их приложения» (Красноярск, 18-23 августа 2003 года). С. 90-96.

26. Милосердое В.В. Использование кубических сплайнов в дискретно-стохастических численных алгоритмах // Труды конференции молодых ученых. Новосибирск, изд-во ИВМиМГ СО РАН, 2003. - С. 80-90.