Дискретно-стохастические численные алгоритмы со сплайн-восполнениями

• Автор: Милосердов, Владимир Владимирович
• Шифр специальности: 01.01.07
• Научная степень: Кандидатская
• Год защиты: 2006
• Место защиты: Новосибирск
• Количество страниц: 83 с.

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

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

J Df(u)du < rnesC/i ■ CD ^ Д ^1 + .
2) при использовании локальных аппроксимационных сплайнов с коэффициента-ми вида (1.29):
J Б/(u) du < mcsî/i • CD >
3) при использовании локальных аппроксимационных сплайнов с коэффициентами вида (1.30):
/ D/(u)du < mesU ■ 9CD.

В случае, когда случайные величины ]независимы, неравенства выглядят следующим образом
1') при использовании мулътикубических эрмитовых сплайнов вида (1.18):

Б/(и)«£и < тс511 • Со,

2/) при использовании локальных аппроксимационных сплайнов с коэффициентами вида (1.29):
I В/(и)<&1 < тся)!/! • Со = тея^ • 0.7191358пСд,
И) при использовании локальных аппроксимационных сплайнов с коэффициентами вида (1.30):
В/( и)йи < теэ^! • АС о-

Доказательство. В условиях теоремы значение /(и) аппроксимации Стренга — Фикса в точке и является линейной комбинацией случайных величин Поэтому сначала оценим величину дисперсии сверху в каждой точке области [/), а затем воспользуемся очевидной оценкой сверху для значения интеграла.
В общем случае для оценки дисперсии Б/(и) воспользуемся неравенством для дисперсии линейной комбинации случайных величин с некоторыми коэффициентами {ак}:
О акСк ^ тахБСк. (2.10)
Это неравенство несложно получить, используя формулу для дисперсии суммы случайных величин и неравенство |соу (£;, ^)| < ^/Б^ • Б(ф которое следует из неравенства Шварца [25]. При оценивании Б/(и) в качестве коэффициентов выступают значения базисных функций, используемых при построении аппроксимации, в точке и, а в качестве случайных величин — случайные значения у, функции в узлах.
В случаях 1) и 2) оценки для Б/(и) очевидным образом получаются аналогично доказательствам теорем 1.10, 1.14. Для случая 3) имеем