Сходимость и оптимизация численных дискретно-стохастических процедур

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

Содержание
Введение
1 Общие подходы к оптимизации дискретно-стохастических численных методов
1.1 Дискретно-стохастические численные методы (ДСЧМ) аппроксимации
функций
1.2 Погрешности ДСЧМ аппроксимации функции
1.3 Условно-оптимальные параметры ДСЧМ аппроксимации функции
2 Дискретно-стохастические численные методы с несмещенными оценками в узлах сетки
2.1 ДСЧМ аппроксимации интегралов, зависящих от параметра
2.2 Погрешности ДСЧМ аппроксимации интеграла, зависящего от параметра
2.3 Условно-оптимальные параметры ДСЧМ аппроксимации интеграла, зависящего от параметра
2.4 ДСЧМ аппроксимации решения интегрального уравнения второго рода
2.5 Погрешности ДСЧМ аппроксимации решения интегрального уравнения
второго рода
2.6 Условно-оптимальные параметры ДСЧМ аппроксимации решения интегрального уравнения второго рода
2.7 Вычисление констант
2.8 Численные примеры
2.8.1 Численные примеры для интеграла, зависящего от параметра
2.8.2 Численные примеры для интегрального уравнения
3 Многомерный аналог метода полигона частот
3.1 Верхние границы для дискретной компоненты погрешности и смещения
многомерного аналога метода полигона частот (МАМПЧ)
3.2 Верхние границы для стохастической компоненты погрешности МАМПЧ
3.3 Погрешность и условно-оптимальные параметры МАМПЧ
3.4 Использование МАМПЧ при решении одной стохастической задачи теории переноса излучения
3.5 Погрешность и условная оптимизация МАМПЧ при решении нелинейных
интегральных уравнений методом простой итерации
Заключение
Библиография

Введение
С развитием вычислительной техники возрастает интерес к численным методам решения прикладных задач, в частности, к статистическому моделированию (или методу Монте-Карло) [1 - 17].
Классические методы Монте-Карло строятся для вычисления многократных интегралов. Кроме того, методы статистического моделирования используются при вычислении функционалов от решений интегральных уравнений; при этом используются представления таких функционалов в виде интегралов счетной размерности. Указанные алгоритмы позволяют получать отдельные значения интегралов, в том числе, значения решений интегральных уравнений в выбранных точках.
Если же речь идет о параметрическом интегрировании или об оценке решений интегральных уравнений в целом, то здесь требуются специальные подходы. Одним из первых таких подходов явился так называемый метод зависимых испытаний, обоснованный и исследованный в [18-20].
В последние годы активно разрабатываются новые функциональные алгоритмы метода Монте-Карло [13, 14,16, 17, 19 - 42] (см. также обзоры литературы в [13, 14, 17]).
Исследованию таких алгоритмов посвящены, в частности, работы автора [21, 26, 28, 29, 31, 33 - 37, 42], обзор которых и представляет содержание данной диссертации. Исследуемые алгоритмы статистического моделирования мы будем называть дискретностохастическими (или функциональными) численными методами глобальной аппроксимации функций. Эти методы связаны с предварительной дискретизацией задачи (введением сетки), оценкой решения в узлах сетки методом Монте-Карло с последующим восполнением решения по полученным приближенным значениям в узлах сетки. Особенностью исследуемых численных процедур является наличие дискретной и стохастической составляющих погрешности алгоритма, что приводит к некоторым сложностям при исследовании сходимости и при оптимизации упомянутых процедур. В частности, возможны различные подходы к выбору вероятностной меры оценки погрешности и критерия оптимальности алгоритма. Поэтому разработка теории сходимости и оптимизации дискретно-стохастических алгоритмов является актуальной задачей.
Погрешность дискретно-стохастической численной процедуры является случайной величиной, поэтому требуется выбрать вид вероятностной сходимости этой величины к нулю при увеличении числа узлов сетки и числа испытаний при реализации алгоритмов метода Монте-Карло в узлах сетки. С точки зрения теории методов Монте-Карло наиболее естественным является так называемый Ь2-подход. Здесь в качестве меры погрешности выбирается Ь2-мера со сходимостью в среднем. Тогда стохастическая компонента погрешности представляет собой интеграл от функции дисперсии глобальной аппроксимации решения, которая определяет эффективность алгоритмов статистического моделирования.
С точки зрения дискретных методов в качестве меры погрешности следует выбирать С-меру (супремум модуля разности двух непрерывных функций). В работах [13, 14, 17]

для перехода к этой мере предлагается использовать теоремы вложения [43].
При этом нужно изучать сходимость в среднем к нулю производных от погрешности. Кроме того, следует отметить, что оценки погрешности, получаемые из теорем вложения, являются достаточно грубыми и реализуемыми лишь для небольших размерностей задач.
Более точные верхние границы погрешности в метрике С можно получить, если взять более слабую, чем в среднем, сходимость погрешности к нулю по вероятности. Такой метод исследования погрешности дискретно-стохастических численных алгоритмов мы будем называть прямым или С-подходом [21 - 23].
Некоторое отличие от монографий [13, 14, 17] (см. также обзоры литературы в этих изданиях] в данной работе состоит в выборе восполнения решения по полученным приближенным значениям в узлах. В [13, 14,17] используется специальное линейное восполнение. Здесь мы будем использовать аппроксимацию Стренга-Фикса [44, 45] с кусочнолинейной производящей функцией (или функцией-крышкой [45]); такое восполнение мы будем называть мультилинейной аппроксимацией [21 - 23].
В работах [38 - 41] показано, что класс восполнений, которые можно использовать в дискретно-стохастических процедурах, достаточно широк и, более того, методика построения верхних границ для дискретных компонент погрешности функциональных алгоритмов практически идентична для различных восполнений. Поэтому основные результаты данной работы технически несложно перенести на дискретно-стохастические процедуры с более гладкими, чем мультилинейное, восполнениями подобно тому, как это сделано в [38 - 41].
Наибольший интерес (и часто - трудность) составляет построение верхних границ для стохастических компонент погрешностей функциональных численных методов для того или иного подхода. Здесь играют роль как свойства соответствующего восполнения (в частности, свойство ”сноса погрешности в узлы” [21 - 23]), так и особенности используемых стохастических оценок значений решения в узлах. Здесь важно смещенные они или несмещенные, зависимые или независимые, векторные или скалярные. Изучению этих особенностей посвящена значительная часть данной работы.
Естественно, важно и то, для приближения какой функции используется та или иная дискретно-стохастическая численная процедура. В качестве основных примеров таких функций рассматриваются интеграл, зависящий от параметра
<Р1(х) = 1к1{у,х)(1у, (1)

и решение интегрального уравнения второго рода
¥2{х) = 1к2{у,х)у>2(у)с1у + ф(х), т.е. 2 = К(/>2 + . (2)

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

Лемма 2.14 [24, 25] Если выполнены условия Леммы 2.13 и соотношения (2.53), (2.55) то существует константа Ну, для которой
sup V £2 (®) < Ну ,
то есть, в частности, выполнено Предположение 1.3 для (Y и Ну = const.
Замечание 2.6 При выборе оптимальных плотностей TTopt и popt можно использовать, как и для процедуры Б, подход из [51] (см. Замечание 2.2), и по аналогии с (2.13) минимизировать величину

,§<»).= 1Е Х>2(-)-Ш) (2-59)
I-1 в
для £(ж) = £2 (т), где В - функциональное пространство, которому принадлежат функции <р2 и f2, t — 1(2) - среднее время реализации одной траектории {;?o,j , ... , zjПо аналогии с (2.14), наиболее простой вид оптимальных плотностей получается для В = W2P+1'(X) [51]:
_ ,.л Ф(у)т(у) _ k2(y,x)r(x)
я opt {у) - J т(г) dz, Popt(y, X)- х) г(г) dz (2.60)

для т = 72 при выполнении условий Леммы 2.9 и условия
Т2{у) = J2 / ВГ*№у> х) (2 Ч>2,х{у') - Ыу, х)) <** > 0;
|т|<р+1 у
здесь <р2 х{у) является решением уравнения (2.58), а неотрицательная функция Т2 может быть найдена как единственное решение уравнения
(2.61)
для т = т2 и Т = Т2.
Приведем окончательные утверждения для оценок по методу сопряженных блужданий и локальных оценок для Ь2- и С-подходов.
Лемма 2.15 [24, 25] (Погрешность ДСЧМ аппроксимации функции <р2 в Ь2-метрике, в узлах сетки используется метод сопряженных блужданий).
Если выполнены Предположения 1.2 и 2.1 и, кроме того,
а) справедливы соотношения
Y [ [ Щ)к?(У’х)( dxdv < х>
i:|m|<2y у
£Л | ж)|2 dxdy < 1 и ф <Е WiY),
(2.62)
т:т<2у у
б) р{гу,х) ф 0 при к2(у, х) = к2(х,у) ф 0, то для фиксированного М & N существуют положительные константы Н= Н«1) и Я» = Н2М] 1) такие, что выполнено соотношение
I 1 1/22 (н{,))2 (н{1))2
(е8у = I:Е у ((*) - 1{М)2())2 1 < (2.63)
для 5 = <>(1) и / = 1,2,3.