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

• Войтишек, Антон Вацлавович
• доктор физико-математических наук
• 2001

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

Введение.

Глава 1. Функциональная сходимость численных моделей случайных полей.

1.1. Специальные условия функциональной сходимости последовательностей случайных функций в пространствах С(!Г) и D^).

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

1.3. Слабая сходимость вычислительных моделей случайных полей, связанных с точечными потоками Пальма.

Глава 2. Дискретно—стохастические методы вычисления многократных интегралов.

2.1. Геометрический метод Монте-Карло и его модификации.

2.2. Построение выборки по важности с использованием аппроксимации

Стренга-Фикса.

2.3. Дискретно-стохастические методы уменьшения дисперсии.

2.4. Использование существенной выборки.

Глава 3. Дискретно—стохастические методы аппроксимации интегралов, зависящих от параметра.

3.1. Стохастические оценки в узлах сетки. Достаточные условия сходимости метода зависимых испытаний.

3.2. Построение верхних границ погрешностей функциональных алгоритмов.

3.3. Условная оптимизация функциональных алгоритмов.

3.4. Многоуровневый метод зависимых испытаний.

Глава 4. Дискретно-стохастические методы аппроксимации решения интегрального уравнения второго рода.

4.1. Несмещенные стохастические оценки в узлах сетки. Верхние границы компонент погрешности.

4.2. Общие утверждения о сходимости и условно-оптимальные параметры функциональных алгоритмов с несмещенными оценками в узлах сетки.

4.3. Многомерный аналог метода полигона частот.

Глава 5. Применение дискретно-стохастических численных методов

5.1. Об одной стохастической задаче теории переноса излучения.

5.2. Исследование смешанных алгоритмов решения интегро-дифференциальных систем.

5.2.1. Модельная каталитическая задача.

5.2.2. Одномерная задача радиационно-кондуктивного теплопереноса.

5.3. Об одном итерационном методе решения нелинейных интегральных уравнений.

5.4. Тестирование дискретно-стохастических численных методов.

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

5.4.2. Тестирование алгоритмов численного интегрирования из Разделов

2.2 и 2.3.

5.4.3. Вычисление констант в выражениях для условно-оптимальных параметров из Разделов 3.3, 4.2 и 4.3.

5.4.4. Тестирование алгоритмов аппроксимации интеграла, зависящего от параметра, из Раздела 3.1.

5.4.5. Тестирование многоуровневого метода зависимых испытаний из Раздела 3.4.

5.4.6. Тестирование алгоритмов аппроксимации решения интегрального уравнения второго рода из Разделов 4.1 и 4.

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

С развитием вычислительной техники возрастает интерес к численным методам решения прикладных задач, в частности, к статистическому моделированию (или методу Монте-Карло) [1 - 15, 16 - 20, 21 - 23] (см. также обзоры литературы в этих книгах); здесь и далее ссылки на работы автора диссертации выделены жирным шрифтом. В теории методов Монте-Карло можно выделить пять основных разделов [4 - 6, 10]: а) численное моделирование случайных величин, векторов и функций; б) вычисление многократных интегралов; в) приближение интегралов, зависящих от параметра; г) решение интегральных уравнений второго рода; д) приложения методов Монте-Карло к задачам вычислительной математики и математической физики.

Традиционно методы Монте-Карло рассматриваются в качестве альтернативных "детерминированным" численным методам (в частности, конечно-разностным и конечно-элементным схемам) (см., например, [24 - 27]). Однако во многих случаях эффективными оказываются алгоритмы, содержащие в себе элементы детерминированных и стохастических численных схем. Такие комбинированные алгоритмы будем называть дискретно-стохастическими численными методами. Исследованию этих методов посвящена данная работа, которая состоит из Введения, пяти глав, двух приложений, Заключения и списка литературы из 267 наименований.

Следует сразу отметить, что спектр дискретно-стохастических численных методов достаточно широк. Комбинированные алгоритмы возникают во всех перечисленных выше разделах теории методов Монте-Карло. Для каждого из разделов мы приведем важнейшие примеры таких алгоритмов и изучим вопросы сходимости и оптимизации соответствующих численных схем.

Начнем с моделирования случайных величин. Как хорошо известно [1 - б, 10, 16], численная реализация случайных величин состоит из двух этапов:

1) реализуются значения а\,. , а^ стандартного случайного числа а, равномерно распределенного на полуинтервале [0,1), с помощью специального устройства или программы, которое называется генератором случайных (псевдослучайных) чисел;

2) с помощью некоторых преобразований полученных чисел {оу} вычисляются значения случайных величин с более сложными законами распределения.

Большинство расчетов по методу Монте-Карло произведено и производится с помощью генераторов псевдослучайных чисел, представляющих собой некоторые вычислительные программы, которые, в свою очередь, реализуют рекуррентные последовательности вида an+i = S(an), (0.1) или их модификации; здесь S - неслучайная функция, определенная на отрезке [0; 1]. То есть по существу речь идет о детерминированной последовательности, обладающей свойствами последовательности независимых случайных величин. Наиболее часто используется функция S вида ^(а:) = {М х} для достаточно большого натурального множителя М, здесь {Л} обозначает дробную часть числа А. В этом случае алгоритм (0.1) называется мультипликативным методом вычетов [4, 5, 10, 16, 23]. Таким образом, в самой основе алгоритмов численного статистического моделирования, на уровне генераторов псевдослучайных чисел, используются по сути комбинированные методы вида (0.1).

При моделировании дискретной случайной величины £ с конечным числом значений xi,., хп и распределением вероятностей Р(£ = Xj) = р,-, г = 1,., п используется следующая стандартная процедура.

АЛГОРИТМ 0.1 [1 - б, 10, 17]. Реализуем значение Q := а и полагаем т := 1. Производим переприсваивание

Q:=Q-Pm (0.2) то есть заносим новое значение (a—pi) в ячейку Q). Если новое Q не положительно, то в качестве т выбираем текущее его значение и считаем, что для данного испытания £ = хт. Если Q>0um = n — 1, то ( = хп. Если же Q > 0 и т < п — 1, то в производим переприсваивания т := т + 1 и (0.2) и вновь производим проверку Q на положительность и т.д.

Алгоритм 0.1 реализуем также в случае моделирования дискретной случайной величины со счетным числом значений; при этом должны иметься формулы вычисления Pi — Ш или рекуррентного пересчета p,+i = /г(ьР:') вероятностей, и перед очередным переприсваиванием (0.2) должно производиться вычисление вероятности рт. Реализация случайной величины £ с конечным числом значений заметно упрощается, когда все значения .,хп равновероятны, то есть все р,- равны 1/п (такое распределение вероятностей называется дискретным равномерным [28]): т — [a n] + 1, £ = хт, (0.3) где [Л] - целая часть числа А [1 - 6, 10, 17].

Следующий прием, который мы назовем квантильным методом [17, 29, 30], позволяет существенно снизить трудоемкость стандартного Алгоритма 0.1 для случая большого или даже счетного числа значений {х,} дискретной случайной величины и здесь существенно используется формула (0.3).

Зададим целое число К и введем на полуинтервале [0,1) равномерную сетку {Wk — к/К] к = 0,1,., К} (число К, как правило, в два-три раза меньше п). Далее построим массив целых чисел Хк = min{j : Rj = р\ + . + pj > ly^-i}, к = 1,., К, который называется массивом нижних квантилей. Этот массив задает номер j элемента массива {i?,-; i = 1,., гг}, с которого следует начинать поиск "вверх" (то есть, как и в Алгоритме 0.1, вычитать величины Rq, q = j, j + 1,. из а до получения первого отрицательного значения) при Wk-i < а < Wk. Окончательно моделирование дискретной случайной величины выглядит следующим образом.

АЛГОРИТМ 0.2 [17, 29, 30]. 1. Генерируем значение а равномерно распределенной на полуинтервале [0,1) случайной величины.

2. Вычисляем номер к полуинтервала [to^-i, ю^), в который попадает а по формуле (0.3): к = [Ка\ + 1.

3. Реализуем последовательный поиск "снизу вверх" начиная с Rxk

В связи с введением сетки {и;*;} Алгоритм 0.2 можно назвать дискретно-стохастическим. Заметим также, что хотя квантильный метод существенно сокращает вычислительные затраты, он требует дополнительной оперативной памяти ЭВМ.

Во многих ситуациях в данной работе рассматривается следующая конструкция. Пусть в R' определена неотрицательная функция 9?(й) и задано компактное множество

U с R'. Для простоты полагаем, что U - выпуклая ограниченная область с границей в R'. Рассмотрим интерполяцию функции (р, основанную на ее разложении по неотрицательным базисным функциям {Хт}, построенным на дискретной сетке {im}: ~ Ц^тХш(й), (0.4) т коэффициенты {u;m} выражаются через значения функции ip и ее производных в узлах сетки. Сделаем следующее

ПРЕДПОЛОЖЕНИЕ 0.1. Число узлов хт) в которых wmxm(u) 0 для всех й = (гг^1),., и^) € U, конечно и равно М.

Переобозначим через ., хм} и {toi,., wm} те узлы и коэффициенты из (0.4), которые удовлетворяют Предположению 0.1. Тогда в правой части (0.4) получим конечную сумму м

4>(й) » L[M)ip{u) = ^2wiXi(u). (0.5) i=l

В данной работе в основном будет рассматриваться случай, когда Wi = <p(xi), при этом м ip(u) к L{M)ip(u) = (°-6) t=i

В качестве основного примера базиса {Хш}5 удовлетворяющего Предположению 0.1, рассмотрим далее аппроксимацию Стренга-Фикса [26, 27], которая строится следующим образом.

Будем предполагать, что {хт} является равномерной прямоугольной сеткой, то есть каждому узлу хт можно сопоставить мультииндекс (f-m) = ., так, что хт — (q[m^h,., q\m^hy, здесь шаг сетки h по всем переменным один и тот же (несложно построить аппроксимацию Стренга-Фикса и для неравномерных сеток, однако при этом нужно использовать более громоздкие обозначения). В этом случае

М ~ h~l и h ~ M~1/l, (0.7) где знак заменяет слово "пропорционально". Рассмотрим базис т(й) = Х(?М,.„9Г,)(-(1), ■ ■ • , «(0) = " Х * '* ' Х *(jT ~ (0"8) где х ~ финитная производящая функция [27]. В силу ограниченности множества U и финитности функций (0.8) базис {Хт} удовлетворяет Предположению 0.1 и условию (0.6). Как и в [27], в качестве производящей функции х возьмем В-сплайн порядка г: X /?(г). (0.9)

Как известно (см., например, [27]), В-сплайн можно определить как (г + 1)-й член рекуррентной последовательности = /3^ * где

0(О)Ы) f 1 для - 1/2 < и < 1/2; ^ ' [0 иначе, а знак " *" обозначает свертку. Выбор аппроксимации Стренга-Фикса (0.5), (0.6), (0.8), (0.9) объясняется тем, что эта интерполяция обладает рядом свойств, позволяющих эффективно использовать ее как при моделировании случайных величин и случайных векторов (см. далее Задачу 0.1), так и при построении дискретно-стохастических алгоритмов численного интегрирования (см. Главу 2) и глобальной аппроксимации функций, представленных в интегральной форме (см. Главы 3 и 4). Важными частными случаями аппроксимации (0.5), (0.8), (0.9) являются г = 0 - это кусочно-постоянная интерполяции функции ср, а также 1 — 1, г = 1 - это кусочно-линейная интерполяция функции tp одного переменного. Кроме того, при I > 1 и г = 1 будем называть (0.5), (0.8), (0.9) мулътилинейной интерполяцией функции <р (здесь линейность функции 1цм)<Р получается только вдоль координатных осей, а в целом линии уровня этой функции получаются "гиперболического" типа, так как значения координат в (0.8) перемножаются). Для всех этих случаев приближение функции <р имеет вид (0.6) (то есть можно положить Wi = tp(x;)) [27]. Рассмотрим следующую

ЗАДАЧА 0.1. Построить алгоритм численного моделирования случайного вектора (для 1 = 1- случайной величины) "Е, имеющего совместную плотность распределения

Р~(й) = С L(M)tp(u), С = 1/с, с— Ь(м)<р(й) du. (0.10) ж'

В Приложении 1 предсталено решение этой задачи (здесь использованы работы автора [17, 18, 31 - 34]).

Отметим три ситуации, в которых возникает необходимость моделирования случайных векторов по плотности (0.10).

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

Здесь можно использовать следующий прием. С помощью физических экспериментов получаем значения ., в^ случайной величины в и построим гистограмму случайной величины в [35]. Для этого разделим весь диапазон наблюденных значений а,Ь], а = тт(б<У\.-,<!)> Ь = тах(бР,.,^) на разряды w,i, £,■); г = 1,., М; а = й0 < щ < • • • < йм = Ъ и подсчитаем частоты и* = rrii/Nv (здесь т,- - число значений {в^}, приходящихся на -й разряд). Гистограмму г рв{й) = . V\ = m* .--, щ.1<й<щ- i = l,.,M (0.11) щ - Nv[ui-ui-i) можно переписать в виде (0.10) для I = 1, г = 0, U = [а,Ь], полагая

771' щ - 1 = (Ь- а)/М - h; х{ = (щ + i)/2; = ,,—-г;

J\v {Ui — 1)

X,W \ 0 иначе, i = 1,.,M.

Функцию (0.11) можно теперь использовать в качестве моделирующей плотности для получения новых значений e[W\ ■ • ■ ^Nw ПРИ численной реализации математической модели Wy; при этом нужно решать Задачу 0.1.

Интересен вопрос об оптимальном соотношении параметров Ny и М, определяющих функцию (0.11). Учитывая то, что базисные функции (0.12) являются ортогональными на [а, 6], то есть

Хп,Х,2) = [хп{й)хФ)<1й = | J' ие^еЬ = при г > 0 базисные функции (0.8), (0.9) не являются ортогональными), то здесь применим следующий подход, предложенный в [36] (см. также [5, 6, 10]).

Пусть в - случайная величина, распределенная на конечном промежутке [а, Ь] и имеющая на этом промежутке достаточно гладкую плотность распределения рд, и 0t,., - ее независимые реализации. Если ф\,., фм ~ ортогональные и нормированные на [a, b] функции:

Фь,Фь) = fj4mi2{u)du = | J' З^1 = г2' то (рд,ф{) являются коэффициентами Фурье функции рд. Кроме того, (рд,ф{) = Ет/>,(0), и тогда функция

М Л Nv

0ЛЗ)

NV j=1 служит несмещенной оценкой ряда Фурье то есть при достаточно большом М сумма (0.13) будет служить хорошим приближением в среднем для рд. Если хМ/уЯ = ( fЛ при й € Iй1-1' ty

Y K ' А К " [0 иначе, г = 1,., М, см. (0.12)), то приближение (0.13) вновь представляет собой гистограмму (0.11).

ЛЕММА 0.1 [10, 36]. Если производная <Ppg/du2 ограничена на [а,6], то уклонение

1 /з гистограммы (0.11) от графика плотности при числе ступеней М ~ Лу в лучшем случае имеет по вероятности порядок Ny1^3.

Имеется также теория разложения плотности по системе ортонормированных с весом функций и использования приближений типа (0.13). Из этой теории следует, что для гладких плотностей рд целесообразно использовать не гистограммы, а более сложные ортогональные разложения (см., например, [10]). Для этого же случая можно использовать неортогональные представления вида (0.10). Например, при для / = 1, г = 1, U = [а, 6], щ - й;1 = (Ь - а)/М = /г; х,- = (щ + «,•i)/2; х0 = а — hj1\ xM+i = Ь + /г/2;

4>{xi) = ЛГ /.m' .—г5 = <р(*м+0 = 0; Nv (Ui - щ-1)

Х.'(м) = й — Xi-i)/h при й 6 £,), it+i - u)/h при u£[xi,xi+1), (0-14)

0 иначе суммирование в (0.6) производится от г = 0 до г = М + 1) получаем кусочно-линейное представление плотности, которое носит название полигон частот.

Вторая ситуация, в которой требуется решать Задачу 0.1, возникает в случае, когда совместная плотность случайного вектора в, распределенного в области U С R!, имеет сложный вид (то есть не удается построить простых моделирующих формул или алгоритмов для компонент в), и строится приближение (0.10) для ip = р§ и моделирование осуществляется по построенному приближению р§{й) = Н Ь{м)рд(й); нормировочная константа Н введена здесь для того, чтобы функция рд осталась плотностью: /я 1 рв{й) du = 1. В связи с тем, что метод Монте-Карло используется в основном для оценки линейных функционалов вида (h,pg) = JR! h(u) Рд(й) du, для оценки близости плотностей pg и рд можно использовать, как и в классических работах по теории интерполяции плотностей (см., например, [39]), норму пространства Li((7) и исследовать погрешность

S(Ll)= [ \pe(u)-Pg(u)\du.

J it

В частности, для 1 = 1, U = [а, Ь] справедлива следующяя

ЛЕММА 0.2 [37]. Пусть А - множество всех борелевских множеств интервала (а,Ь). Тогда

5(bi)2SUp / щ(у)йй— / pg(u)du\.

0 JA J А 1

ASA

В качестве следствия Леммы 0.2 можно получить оценку погрешности вычисления функционалов: h,p§) - (h,pg)\ < vrai sup |/i(s)| (2 sup / pg(u)dii- / p§(u)dv,), h € LTO([/).

6[a,b] V JA

Однако, например, для исследования вопроса об изменении дисперсии соответствующего метода Монте-Карло, получаемого при замене плотности pg на р§, требуются более сильные метрики, чем (например, метрики пространств и даже С([/))

- см. Раздел 2.2. В связи с этим приведем утверждения об аппроксимирующих свойствах приближения Стренга-Фикса (0.5), (0.6), (0.8) в соответствующих функциональных пространствах. Обозначим W) = ( £ Ш - W(")))2<^)1/2, m:|m|<r здесь

S[°lr)) = Pcl')[<PiLW)lP)= £ sup|Dm(<^(u) - L(M)<p(u))\] m-.}m\<r^U a\m\

•""•^.„^/w. « = (»<",.,-«I, где т = (mi,., mi), mi - целые неотрицательные числа, |m| = mi + . + т;. Заметим, что = <Г2<0)) и *<с> = (0)).

ЛЕММА 0.3 [26, 27]. Для х е C^-^R) и

Ч> G C^(U) (0.15) найдется набор коэффициентов {го,-} из (0.5), для которого справедливо неравенство tfcW) < Hs М-^'1 |M|ccr)(f/) = Hi hr-s |M|c(r)(f/), 0 < * < r - 1, (0.16) см. (0.7)), причем константы Hs и H's не зависят от <р и h.

ЛЕММА 0.4 [26, 27]. Если {ii,. ,хм} являются точками непрерывности функции ср и ее производных, входящих в выражения для {го,-}, то для х € W^(R) и ip G W{;+1)(U) (0.17) найдется набор коэффициентов {го,-} из (0.5), для которого справедливо неравенство < Hs M-^-'W = H's |M|<+1)(f/), о < , < r. (0.18)

Заметим, что

X = /?<г) € W<r)(R) и x = P[r) e C(r1)(R), (0.19) и что для г = 0 и г = 1 указанный в Леммах 0.3 и 0.4 набор коэффициентов {и;,-} представляет собой значения функции ip в узлах сетки, то есть выполнено соотношение (0.6) (см. [27], Глава 2, §5).

Чтобы обеспечить условие непрерывности функции tp и ее производных в точках {Si,., хм} (см- Лемму 0.4), используем следующий результат.

ЛЕММА 0.5 (теорема вложения) [38]. Если U - ограниченная область, звездная относительно некоторого шара, f 6 и

I < 2(r + 1), (0.20) то существует функция f € С(/7), совпадающая почти всюду на U с функцией /, такая, что f\\c{u)<H\\f\\w^1){uy где Н - константа, не зависящая от выбора функции /.

Из Леммы 0.5 следует, что при выполнении условия (0.20) функцию / € W<r+1)(f/) можно отождествлять с эквивалентной ей непрерывной функцией /. Поэтому для выполнения упомянутого выше условия Леммы 0.4 разумно сделать

ПРЕДПОЛОЖЕНИЕ 0.2. Для всех рассматриваемых далее функций f из ~W2+1\U) справедливы соотношения (0.20) и f = f Е C(U).

Потребность решения Задачи 0.1 может также возникнуть при реализациии мажорантного метода исключения [4 - 6, 10, 18, 29].

Пусть в области W С R/ задана положительная функция /f > 0 при w € W и ft(w) — 0 при w £ W), причем Gi = Jw f^(w)dw < оо (при этом сама константа Gi может быть неизвестной) и требуется построить алгоритм моделирования случайного вектора £ с совместной плотностью

Pi(w) = f№)fGi. (0.21)

Если стандартные приемы моделирования случайного вектора £ (например, представление совместной плотности рg в виде произведения условных плотностей и последовательное моделирование компонент вектора £ методом обратной функции распределения или методом суперпозиции [4 - 6, 10, 18, 29]) не реализуемы, то можно использовать следующий прием.

Построим функцию /ир, заданную на той же области W 6 R' и такую, что fuP{w) > f(r{w) > 0 для всех w £ W, при этом Gup — fw fup(w) dw < оо, и имеются эффективные моделирующие формулы (в дальнейшем - ФОРМУЛЫ (0.22)) реализации случайного вектора fj по совместной плотности р^(ги) = fuP{w)/Gup.

АЛГОРИТМ 0.3 [5, 10, 18]. 1. Моделируем вектор fj0 по формулам (0.22). Реализуем также случайную величину 7 = а }Up{fjo) (здесь а по-прежнему стандартное случайное число).

2. Если 7 > f^{fjo), то испытание считаем несостоявшимся и повторяем п. 1 алгоритма, если же 7 < f^(fjo), то принимаем £ = fj0.

Алгоритм 0.3 является частным случаем общей схемы метода исключения.

АЛГОРИТМ 0.4. Пусть случайный вектор ф распределен в некотором множестве X и дано подмножество А С. X. Проводим статистическое испытание Т, при этом считаем, что Т состоялось, если ф £ А, иТ не состоялось, если ф А.

ЛЕММА 0.6 [4, 18]. Трудоемкость реализации испытания Т (среднее число попыток до получения Т) в Алгоритме 0.4 пропорциональна величине s — 1 /р, где р = ~Р(ф € А).

Из Леммы 0.6 следует, что трудоемкость Алгоритма 0.3 пропорциональна величине

1 Gup

Таким образом, мажоранту fup функции /^ следует подбирать так, чтобы площади G и Gup были близки; при этом, очевидно, близкими должны быть и сами функции fup и /В качестве fup целесообразно взять кусочно-постоянные "окаймления" функции /^ (особенно в многомерном случае при I > 1) и для реализации значений fj (см. пункт 1 Алгоритма 0.3) требуется решать Задачу 0.1.

Рассмотрим также модификацию Алгоритма 0.3, которая может оказаться эффективной для случая, когда вычисление значения функции f^(fjo) является трудоемким, а потому велики затраты на проверку неравенства 7 > f[{fjo) в пункте 2 Алгоритма 0.3.

Построим функцию fiow, заданную на той же области W € R' и такую, что /f(^) > fiow{w) > 0 для всех w € W, при этом вычисление значения построенной функции fiow является значительно менее трудоемким, чем вычисление значения функции fg. Тогда можно рассмотреть следующую модификацию Алгоритма 0.3.

АЛГОРИТМ 0.5 (двусторонний метод исключения) [29, 39, 40, 41]. 1. Как и в Алгоритме 0.3, моделируем вектор fj0 по формулам (0.22). Реализуем также случайную величину 7 = afUp(f]о).

2. Производим сначала проверку неравенства 7 < fiow(fj0). Если оно верно, то принимаем £ = щ. В противном случае проверяем далее неравенство 7 < 0); если оно верно, то £ = fjo, иначе испытание считаем несостоявшимся и повторяем пункт 1 алгоритма.

Если функции /ир, и fiow близки, то, с одной стороны, вероятность р = G/Gup близка к единице и среднее число испытаний до получения "состоявшегося" испытания близко к единице, а с другой стороны, трудоемкая проверка 7 < f^(fjo) будет происходить достаточно редко. В качестве миноранты fiow также целесообразно использовать кусочно-постоянные приближения "снизу" функции [40].

Отметим также, что метод исключения имеет аналогию с геометрическим методом Монте-Карло для вычисления интегралов, и здесь также возможно использование двусторонних технологий (см. далее описание Раздела 2.1).

Таким образом, дискретно-стохастические методы (в частности, связанные с решением Задачи 0.1) возникают уже на стадии моделирования случайных величин и случайных векторов.

В Главе 1 исследуются комбинированные алгоритмы, возникающие при реализации траекторий случайных функций.

В Разделе 1.1 представлены результаты по теории слабой (функциональной) сходимости последовательностей случайных функций в пространствах С(Т) (непрерывных на Т С R' функций с метрикой "супремум модуля разности") и D(T) (функций без разрывов второго рода с обобщенной метрикой Скорохода) [15, 21, 42 - 60], которые использованы далее в Разделах 1.2, 1.3, 3.1 для обоснованного применения численных моделей случайных функций и метода зависимых испытаний. Показано, как можно преобразовать общие необходимые и достаточные условия слабой сходимости (условие сходимости на алгебре, образующей ст-алгебру выборочного пространства, и условие слабой компактности мер) к более жестким достаточным, но легко проверяемым условиям. Так, для пространств С(Т) и D(T) условие сходимости на алгебре сводится к условию сходимости конечномерных распределений (и здесь уже можно использовать предельные теоремы теории случайных функций, в частности, центральную предельную теорему - см., например, [50, 51]). В свою очередь, теорема Арцела [61] и ее аналоги позволяют свести условие слабой компактности мер для пространств С(Т) и D(T) к условиям малости модуля непрерывности. Дальнейшие упрощения утверждений о слабой сходимости последовательностей случайных полей связаны с переходом к условиям слабой компактности в терминах приращений, а затем - к дифференциальным и мо-ментным условиям. В Разделе 1.1 также рассмотрен вопрос о том, какие функционалы непрерывны в метриках пространств С(Т) и D(T) (в частности, доказана непрерывность функционала F(y) — supt-eT y(t), у 6 С(Т) V D(Т)). Результаты этого раздела опубликованы в работах автора [19, 62 — 70].

В Разделе 1.2 рассмотрены различные виды сходимости численных рандомизированных спектральных моделей гауссовских случайных полей: в среднеквадратическом, слабая, равномерная по вероятности [10 - 12, 15, 21, 71 - 76]. Численные методы построения таких моделей можно трактовать как дискретно-стохастические, так как они основаны на разбиении спектрального пространства на непересекающиеся множества и на построении допредельных интегральных сумм для спектральных представлений моделируемых случайных функций. При этом можно достичь совпадения корреляционных характеристик модели и моделируемого поля за счет рандомизации используемых точек спектра [71]. Такие конструкции применяются в основном для моделирования гауссов-ских случайных полей, так как на практике удается моделировать только независимые слагаемые интегральной суммы спектрального представления, а в этом случае, в силу центральной предельной теоремы для случайных функций [50], предел интегральной суммы представляет собой гауссовскую случайную функцию. В свою очередь, для реализации негауссовских полей следует моделировать зависимые слагаемые интегральной суммы, что, вообще говоря, непросто. Кроме того, для получения информации о конечномерных распределениях предельного поля требуется доказывать более тонкие (по сравнению с центральной) предельные теоремы, которые будут к тому же обладать малой степенью общности. Для получения негауссовских траекторий более перспективным является рассмотрение различных преобразований спектральных моделей гауссовских случайных полей. В Разделе 1.2, в частности, исследованы преобразования, основанные на рассмотрении функций на гауссовских траекториях, а также на комбинировании гауссовских спектральных моделей со случайными величинами [21, 78 - 83]; исследован вопрос о функциональной сходимости моделей, полученных с помощью этих преобразований. Результаты данного раздела опубликованы в работах автора [19, 63 - 70, 84 - 87].

В Разделе 1.3 исследованы вопросы слабой сходимости моделей случайных процессов и полей на точечных потоках Пальма [10, 11, 21, 72, 88]. Эти модели представляют собой кусочно-постоянные аппроксимации некоторых предельных случайных функций на стохастических сетках. Особо отметим, что автором для специального класса корреляционных функций предложена новая численная модель такого типа, более экономичная (по сравнению с ранее предложенными) как в смысле численной реализации, так и простоты обоснования функциональной сходимости. Результаты этого раздела опубликованы в работах [89 — 91].

В Главе 2 исследованы способы решения следующей

ЗАДАЧА 0.2. Построить алгоритм вычисления интеграла

1= f f(u) du, и = {йе R* : f(u) ф 0}. (0.23)

J U

Рассмотрены различные модификации стандартного метода Монте-Карло. Этот алгоритм основан на представлении

1 = 1 Ф(о)рч-(о) du = Е£, (0.24)

А А где £ = Ф(^), Ф(й) = }{й)/рц{и). Для выполнения (0.24) достаточно потребовать Рщ(и) ф 0 при й € U. Функция pfj является плотностью в R', то есть р^(й) > 0 и fRi рщ(й) dii = 1, а /-мерный случайный вектор fj распределен по плотности р^.

АЛГОРИТМ 0.6 (Стандартный метод Монте-Карло вычисления многократного интеграла) [1 - б, 10, 16, 20]. 1. Реализуем п значений случайного вектора fj: щ,., fjn.

2. Вычисляем приближенное значение интеграла (0.23): i«b = -itti = -i:*m- (0-25)

П п

7 = 1 7 = 1

Если в (0.25) трактовать г/i,.,r/„ как набор независимых одинаково распределенных случайных векторов с совместной плотностью распределения рто случайные величины = Ф(щ),. , = Ф(fjn) будут также независимыми одинаково распределенными с математическим ожиданием I (см. соотношение (0.24)) и дисперсией а2 = = / Ф2(й) рп(й) du-I2= f du - I2. (0.26)

Ju Ju pn{u) v '

Если величина (0.26) конечна, то в силу закона больших чисел (см., например, [28, 92]) формула (0.25) верна для достаточно больших п. В силу центральной предельной теоремы (см., например, [28, 92]) для достаточно больших п имеет место соотношение

P{\I~U<c(e)^=)=l-e, (0.27) из которого следует, что стандартный Алгоритм 0.6 имеет по вероятности погрешность порядка 1 /у/п. Поэтому для приближенного вычисления интеграла с гладкой подынтегральной функцией и небольшой размерности I области U метод Монте-Карло заведомо проиграет детерминированным квадратурным и кубатурным формулам [24, 25, 93 - 95]. Однако метод Монте-Карло имеет и ряд несомненных преимуществ. Прежде всего, скорость сходимости метода не зависит от увеличения размерности и возрастания сложности задачи. Поэтому метод Монте-Карло применяется при решении Задачи 0.2 для многомерного случая и (или) "сложной" подынтегральной функции / (и иногда -для "сложной" области интегрирования U).

Важным достоинством метода Монте-Карло является также возможность оценки погрешности по результатам вычислений, которую дает соотношение (0.27). Здесь уместно заметить, что если даже величина а заранее неизвестна, то несложно получить ее приближенное значение, используя ту же выборку что используется при подсчете математического ожидания Е£ [4 - 6, 10, 16]: а п

1 у^РШ 1 (у/fah -1П Ш) п{п-\)У^р,{т]зу

Исторически некоторое время (в 50-е годы прошлого столетия) активно использовался так называемый геометрический метод Монте-Карло, основанный на построении мажоранты положительной подынтегральной функции / и розыгрыше равномерно распределенной точки в "подграфике" этой мажоранты. В монографии [4] этот метод рассмотрен в качестве альтернативы Алгоритму 0.6. Геометрический метод может быть эффективным (сравнительно с Алгоритмом 0.6) в достаточно экзотическом случае, когда функция Ф-1 существует и ее значения вычисляются значительно быстрее, чем значения Ф.

В Разделе 2.1 показано, что геометрический метод является частным случаем стандартного Алгоритма 0.6, а также установлена аналогия геометрического метода с методами исключения (Алгоритмы 0.3 и 0.5). В частности, использование двусторонних технологий позволяет существенно расширить сферу применимости геометрического метода. Результаты данного раздела опубликованы в [20, 39, 40, 96, 97].

Количество вычислительной работы при реализации Алгоритма 0.6 определяется величиной s = nt, где t - среднее время ЭВМ, затрачиваемое на вычисление одного значения Из соотношения (0.27) следует, что при фиксированном £ количество испытаний п пропорционально дисперсии V поэтому в качестве величины, характеризующей затраты метода Монте-Карло, можно выбрать

S — ta2. (0.28)

Величина S называется трудоемкостью метода Монте-Карло [4 - 6, 10, 16, 20].

Таким образом, плотность Pfj следует выбирать так, чтобы минимизировать трудоемкость (0.28).

ЛЕММА 0.7 [4 - 6, 10, 20]. Минимальная дисперсия реализуется в случае, когда плотность р^ пропорциональна модулю подынтегральной функции: fl)= l/WI

Ju l/HI<™ и равна a2min = (fa |/(й)| du)2 - I2.

Заметим, что если подынтегральная функция / не меняет знак на С/, то сг^п = 0. Выборка fji,.,fjn по плотности (0.29) называется существенной. Из Леммы 0.7 можно сделать вывод о том, что в ряде случаев можно добиться уменьшения трудоемкости S Алгоритма 0.6, выбирая плотность рщ близкой к функции (0.29). Алгоритм 0.6 в этом случае называется выборкой по важности [4 - 6, 10, 20], что соответствует английскому термину "important sampling". Такое название объясняется тем, что если р^ пропорциональна /, то в тех частях области U, в которых |/| больше и вклад которых в интеграл I более существенен, будет выбираться больше случайных точек.

В Разделе 2.2 исследован Алгоритм 0.6, в котором в качестве плотности р^ выбрана нормированнная аппроксимация Стренга-Фикса (0.5), (0.6), (0.8), (0.9) для <р = CF, где F = |/| и С - нормирующая константа:

С = 1 /J L{M)F(w)dw.

При таком выборе плотности р^ в первом пункте Алгоритма 0.6 требуется решать Задачу 0.1 для случая / > 1. Получено выражение для условно-оптимального числа узлов, используемых при построении аппроксимации. Предложен ряд модификаций исследуемого алгоритма (в частности, концепция "отделения плотности от нуля"). Результаты данного раздела опубликованы в [20, 32 — 34].

В Разделе 2.3 аппроксимация Стренга-Фикса подынтегральной функции использована уже в алгоритме выделения главной части [4 - 6, 10, 20]. Показано, что получаемый метод по скорости сходимости и простоте реализации не уступает алгоритму выборки по важности из Раздела 2.2. Предложена также смешанная численная схема, использующая идеи построения алгоритмов выборки по важности и выделения главной части. В этом же разделе дается обзор возможностей применения "детерминированных" технологий в других методах понижения дисперсии стандартного алгоритма метода Монте-Карло. Рассмотрены, в частности, интегрирование по части области, метод условных математических ожиданий, выборка по важности по части переменных, сложная симметризация переменных и метод расслоенной выборки [4 - 6, 10, 20]. Далее в Разделе 2.3 приведен обзор работ, посвященных построению оптимальных (в смысле теории сложности) алгоритмов численного интегрирования [1, 3 - 6, 10, 24, 25, 93 - 95, 98 - 106]. Обсуждается, в частности, соотношение между "детерминированными" кубатурными

0.29) формулами [24, 25, 93 - 95] и методами Монте-Карло [4, 6, 10, 24, 25]. Здесь важно отметить, что явной границы между детерминированными и стохастическими численными алгоритмами интегрирования не существует, и оптимальные алгоритмы этого типа являются по сути дискретно-стохастическими [24, 25, 99 - 106]. К сожалению, последние алгоритмы, как правило, трудно реализуемы на практике. В конце Раздела 2.3 приведены примеры комбинированных дискретно-стохастических алгоритмов вычисления континуальных (в частности, винеровских) интегралов. Результаты данного раздела опубликованы в [20, 34].

В Разделе 2.4 исследован вопрос о возможности использования заданной существенной выборки при решении Задачи 0.2. Предложен алгоритм, основанный на введении функции, интеграл от которой известен. Эта функция должна быть достаточно близкой к подынтегральной, и для ее построения вновь можно использовать конечно-элементные аппроксимации подынтегральной функции. Кроме того, отмечено, что существенную выборку можно получать мажорантным методом исключения. Показано, что в случае, когда существенная выборка не задана, при вычислении интеграла не следует стремиться ее воспроизводить, а лучше использовать стандартный метод Монте-Карло со случайными узлами, близкими (но в точности не совпадающими) по распределению к существенной выборке. Результаты данного раздела опубликованы в работе [39].

Переходя к обзору Глав 3 и 4, отметим, что помимо задач вычисления многократных интегралов "классические" методы статистического моделирования используются при вычислении функционалов от решений интегральных уравнений; при этом используются представления таких функционалов в виде интегралов счетной размерности. Указанные алгоритмы позволяют получать отдельные значения интегралов, в том числе, значения решений интегральных уравнений в выбранных точках. Если же речь идет о параметрическом интегрировании или об оценке решений интегральных уравнений в целом, то здесь требуются специальные подходы. Одним из первых таких подходов явился так называемый метод зависимых испытаний, предложенный в [107, 108]. В последние годы активно разрабатываются новые функциональные алгоритмы метода Монте-Карло (см. обзоры литературы в [13, 14, 22, 23]). В Главах 3 и 4 исследуются комбинированные алгоритмы, которые мы будем называть дискретно-стохастическими (или функциональными) численными методами глобальной аппроксимации функций if, представленных в интегральной форме. В качестве основных примеров таких функций рассматриваются интеграл, зависящий от параметра р1(й)=[ f(u,v)dv, ueUcR', veVcB™, (о.зо)

J V и решение (и) интегрального уравнения второго рода р2(й) = Jvk(u,v)ip2(v)dv + ip(u), ueU С VCR'. (0.31)

Предполагается, что существуют достаточно эффективные алгоритмы метода Монте-Карло для оценки функции <р(й) в одной или нескольких точках й £ U. Дискретно-стохастические методы имеют следующую общую структуру.

АЛГОРИТМ 0.7 По аналогии с (0.4) рассмотрим интерполяцию функции <р, основанную на разложении по базисным функциям {х'т\> построенным на дискретной сетке у^й) (0.32)

Полагаем, что для этого разложения выполнено Предположение 0.1. Переобозначим через {xi,.,xM} и через {xi,.,ХлЛ и Ц,.-.,1Им} те узлы из {хт} и соответствующие им базисные функции и коэффициенты, которые удовлетворяют этому предположению. Тогда, по аналогии с (0.5), в правой части (0.32) получим конечную сумму м р(й) и Lm<p(u) = (0-33) i=l

Более подробно будет изучаться случай м

4>(й) « L(M)ip{u) = J2(0.34) t'=i

В этом случае для оценки значений {^(х,)} реализуем алгоритмы метода Монте-Карло с числами реализаций {гс,}: п* j=1 где j-я реализация (У> - стохастической оценки метода Монте-Карло для значения <р(х{), i = 1,., М. Окончательно приближение вида (0.34) функции (р имеет вид м р(й) и Ь{м)ф(й) = *!•(")• (°-36) i=i

Для более общего случая (0.33) окончательное приближение имеет вид м ф) и ьтф(й) = £ Wi x|(«), (0.37) где Wi явлются соответствующими комбинациями оценок вида (0.35) для значений функции ip в узлах сетки (включающими конечно-разностные приближения производных).

В качестве основного примера системы функций {Хт} рассмотрим конечно-элементный базис (0.8) аппроксимации Стренга-Фикса с производящей функцией (0.9). При этом для г = 0 и г = 1 можно использовать приближение (0.36). Выбор аппроксимации Стренга-Фикса определяет некоторое отличие исследуемых здесь численных схем от алгоритмов из [13, 14, 22, 23] (см. также списки литературы в этих монографиях), в которых используется специальное линейное восполнение. Одной из основных проблем, изучаемых в Главах 3 и 4, будет вопрос о скорости сходимости Алгоритма 0.7 при согласованном увеличении параметров М и п = min(rci,. ,пм)

Особенностью исследуемых численных процедур является наличие детерминированной и стохастической составляющих погрешности Алгоритма 0.7, что приводит к некоторым сложностям при исследовании сходимости и при оптимизации упомянутых процедур. В частности, возможны различные подходы к выбору вероятностной меры оценки погрешности и критерия оптимальности алгоритма. С точки зрения теории методов Монте-Карло при исследовании погрешностей комбинированных дискретно-стохастических численных методов глобальной аппроксимации функций ip = ipi V </>2 наиболее естественным является так называемый L2~подход. Здесь в качестве меры погрешности выбирается Ь2-мера. Погрешность дискретно-стохастической численной процедуры являтся случайной величиной, и поэтому требуется выбрать вид вероятностной сходимости этой величины к нулю при увеличении числа узлов сетки и числа испытаний при реализации алгоритмов метода Монте-Карло в узлах сетки. Для L2-подхода выбирается сходимость в среднем. Тогда стохастическая компонента погрешности определяется дисперсиями оценок значений решения в узлах сетки, которые, в свою очередь являются монте-карловскими критериями эффективности этих оценок. В ряде задач требуется вычислять значения "жестких" функционалов от решения ip (в частности, супремум на компактном множестве). В этом случае в качестве меры погрешности следует выбирать С-меру (супремум модуля разности двух непрерывных функций). В монографиях [13, 14, 22, 23] (см. также обзоры литературы в этих изданиях) для перехода к этой мере предлагается использовать теоремы вложения [38]. При этом нужно изучать сходимость в среднем к нулю производных решения. Кроме того, следует отметить, что верхние границы погрешности, получаемые из теорем вложения, являются достаточно грубыми и реализуемыми лишь для небольших размерностей задач. Более точные верхние границы погрешности в метрике С можно получить, если взять более слабую, чем в среднем, сходимость погрешности к нулю по вероятности. Такой метод исследования погрешности дискретно-стохастических численных алгоритмов мы будем называть С-подходом. Сразу отметим, что С-подход позволяет применить предельные теоремы теории вероятностей при получении верхних границ для стохастической компоненты погрешности Алгоритма 0.7.

При построении верхних границ для детерминированных компонент погрешности используется теория соответствующего восполнения (для восполнения (0.5), (0.6), (0.8) применяются Леммы 0.3, 0.4). При этом важным является вопрос о том, какому функциональному пространству принадлежит исследуемая функция ip = <р\ V у>2 - см. соотношения (0.15), (0.17).

Наибольший интерес (и часто - трудность) составляет построение верхних границ для стохастических компонент погрешностей функциональных численных методов для того или иного подхода. Здесь играют роль как свойства соответствующего восполнения, так и особенности используемых стохастических оценок значений решения в узлах. Важно смещенные они или несмещенные, зависимые или независимые, векторные или скалярные. Естественно, имеет значение и то, для приближения какой функции - <pi или (р2 ~ используется та или иная комбинированная численная процедура. Для интеграла (pi, зависящего от параметра, в качестве стохастических оценок в узлах сетки в данной работе рассматриваются независимые оценки (в каждом узле подбирается своя вероятностная плотность), оценки по методу зависимых испытаний (здесь и плотность, и реализуемые по ней случайные векторы одни и те же для всех узлов), а также смешанные оценки. Предлагается также концепция зависимых оценок с оптимальными плотностями. Все эти оценки являются несмещенными. Для решения ip2 интегрального уравнения (0.31) в работе изучаются несмещенные оценки по методу сопряженных блужданий, локальные, векторные и локально-векторные оценки, а также смещенные оценки по многомерному аналогу метода полигона частот. Здесь уместно заметить, что оценки по методу сопряженных блужданий и векторные оценки для функции ip2 из (0.31) являются соответственно скалярным и векторным аналогами независимых оценок для функции (pi из (0.30). В свою очередь, локальные и локально-векторные оценки являются скалярным и векторным аналогами оценок по методу зависимых испытаний.

Сформулируем следующее

ПРЕДПОЛОЖЕНИЕ 0.3. Коэффициенты {го,} из (0.33) и их стохастические оценки {W,} из (0.37) таковы, что одновременно выполнены Леммы 0.3, 0.4 и соотношения sup |ЦМ)<р(й) - Ь{М)ф{й)| < Сг . max - фП((х{)|, (0.38) u£U «—1|.|М lvL(„t(u)Ju<C>mesUm^.(0.39)

Отметим, что в левых частях неравенств (0.38), (0.39) стоят стохастические компоненты погрешностей Алгоритма 0.7 для С- и Ь2-подходов соотвественно. Соотношения (0.38), (0.39) определяют свойство "сноса погрешности в узлы" аппроксимации Стренга-Фикса (0.5), (0.8), (0.9) (это аналог свойства устойчивости приближения функции). Отметим, что для г = 0, г = 1 и приближения (0.36) соотношения (0.38), (0.39) несложно доказать (см. Раздел 3.2). Соотношения (0.38), (0.39), очевидно, выполняются и в случае, когда коэффициенты го,- из (0.33) выбираются с помощью решения задачи интерполяции = у (ж,) (в силу линейности этой задачи), однако при этом могут не выполняться Леммы 0.3 и 0.4 (а значит, и Предположение 0.3). Класс функций, удовлетворяющих Предположению 0.3 при г > 1 требует отдельного изучения.

Для максимума дисперсий из (0.39) и для рассматриваемых функций и <^2 на основании Лемм 0.3, 0.4 удается построить верхние границы. При построении верхних границ для максимума из (0.38) для независимых оценок в узлах (скалярных и векторных) в данной работе используются результаты теории порядковых статистик из [109], а для методов с зависимыми оценками в узлах - теория метода зависимых испытаний.

Для многих используемых в приложениях интегральных уравнений второго рода (в том числе, нелинейных и стохастических) можно с успехом использовать аппроксимацию решения по многомерному аналогу метода полигона частот. Здесь предполагается, что узлы {ж,} являются центрами одинаковых малых кубов {С/,}, на которые разбивается область U. С помощью основной оценки метода Монте-Карло (см., например, [10]) вычисляются функционалы А,) = Ju (<^2(")/mes {/,) du (здесь для всех функционалов используются одни и те же траектории цепи Маркова), которые и принимаются за приближенные значения в узлах сетки {ж,}; затем реализуется восполнение

0.36) или (0.37) с базисными функциями (0.8), (0.9). Соответствующие стохастические оценки являются смещенными и "слабо" зависимыми, причем и смещение, и зависимость уменьшаются с ростом числа узлов. При построении верхних границ для стохастических компонент погрешности этого алгоритма в рамках С-подхода потребовалось доказывать специальные аналоги утверждений теории порядковых статистик для случая зависимых случайных величин, корреляции которых убывают с ростом числа величин.

Отметим, что все условия, обеспечивающие возможность построения верхних границ погрешностей дискретно-стохастических алгоритмов глобальной аппроксимации функций, выражены в терминах подынтегральной функции / (для функции (pi из (0.30)), ядра к и свободного члена ф интегрального уравнения (для функции <^2 из (0.31)).

Особое внимание в работе уделено проблеме выбора параметров функциональных численных методов. Выбору подлежат число узлов сетки М, вероятностные плотности р, определяющие стохастические оценки в узлах, а также минимум числа реализаций оценок в узлах сетки п. Используется подход из [13, 14]. Фиксируется допустимый уровень погрешности 7, которому приравнивается верхняя граница Т(М, щр) погрешности Алгоритма 0.7. При этом условии минимизируется функция трудоемкости, аргументами которой являются выбираемые параметры. Практически для всех рассматриваемых в данной работе функциональных алгоритмов такую задачу удалось решить при условии, что вероятностные плотности р выбраны и фиксированы, то есть минимизация трудоемкости производилась по М и п, соответствующие критические значения выбираемых параметров названы далее условно-оптимальными.

В Главе 3 рассмотрены общие подходы к оптимизации дискретно-стохастических численных методов и их реализация для функции (0.30).

В Разделе 3.1 описаны независимые и зависимые стохастические оценки в узлах сетки для интеграла, зависящего от параметра. Рассмотрен вопрос об ослаблении условий сходимости метода зависимых испытаний (по сравнению с работами [107, 108]). Здесь существенно использованы полученные в Разделе 1.1 достаточные условия функциональной сходимости последовательностей случайных функций в пространствах С(U) и D(U). Предложены концепции смешанных оценок и зависимых оценок с оптимальными плотностями. Результаты данного раздела опубликованы в [20, 63, 67 — 70, 110 - 117].

В разделе 3.2 определены L2- и С-подходы к исследованию сходимости функциональных алгоритмов. Показано, что для этих подходов погрешность распадается на детерминированную и стохастическую составляющие (для смещенных оценок появляется также компонента смещения). В связи с получением верхних границ для детерминированных компонент погрешностей (с использованием Лемм 0.3, 0.4) получены условия, обеспечивающие соотношения (0.15), (0.17) для функции (pi. Доказаны неравенства (0.38). (0.39) для аппроксимации Стренга-Фикса (0.6), (0.8), (0.9) при г = 0 и г = 1. Эти неравенства позволяют строить верхние границы для стохастических комнонент погрешностей и смещения функциональных алгоритмов. В Разделе 3.2, в частности, получены верхние границы стохастических компонент погрешностей функциональных алгоритмов аппроксимации интеграла y?i, зависящего от параметра. Для процедур с независимыми несмещенными оценками в узлах {ж,} для этого использована теория порядковых статистик, а для зависимых оценок - рассмотренная в Разделе 3.1 теория метода зависимых испытаний. Приведены общие утверждения о погрешностях дискретно-стохастических процедур аппроксимации функции ipi из (0.30) для L2- и С-подходов. Результаты данного раздела опубликованы в [20, 33, 111 — 125].

В Разделе 3.3 сформулирована задача условной оптимизации. Замечено, что в большинстве случаев верхняя граница Т имеет вид T(M,h]p) = Ci$i(M, щр) + С2$2(М, щр), при этом порядки возрастания условно-оптимальных параметров при 7 —> 0 можно получить из соотношений Ф^М, щр) ~ 7 и Ф2(М, щр) ~ 7. Минимизация трудоемкости позволяет уточнить константы в выражениях для условно-оптимальных параметров. На основе верхних границ погрешностей, полученных в Разделе 3.2, выписаны выражения для условно-оптимальных параметров функционального Алгоритма 0.7 с зависимыми и независимыми оценками в узлах сетки. Результаты данного раздела опубликованы в [20, 112, 117, 120, 123, 124, 126].

В Разделе 3.4 описан многоуровневый метод зависимых испытаний из [127, 128], оптимальный в смысле теории информационной сложности [101, 102]. Этот алгоритм основан на технологии выделения главной части. Отмечены обстоятельства, ограничивающие возможности применения этого алгоритма на практике. Сформулированы выводы из численных экспериментов подраздела П.3.4. В частности, отмечено, что параметры многоуровневого алгоритма, выбираемые на основании простой стоимостной модели, на деле не являются оптимальными. Поэтому требуются более тонкие исследования этого метода на основе весовых стоимостных моделей. Результаты данного раздела опубликованы в [129].

В Главе 4 рассматриваются те же вопросы, что и в Разделах 3.1 - 3.3, но на этот раз - для более сложной функции <р2 из (0.31).

В Разделе 4.1, в частности, описаны несмещенные стохастические оценки в узлах сетки для решения интегрального уравнения второго рода: независимые (полученные по методу сопряженных блужданий) и зависимые (или локальные) оценки, а также их векторные аналоги. Затем рассмотрены вопросы построения верхних границ для детерминированных и стохастических компонент погрешностей рассматриваемых функциональных алгоритмов. При использовании Лемм 0.3 и 0.4 для построения верхних границ детерминированных компонент погрешностей пришлось доказывать утверждения о принадлежности функции <р2 используемым функциональным пространствам В = C^(U) V W^r+1^(J7) (см. условия (0.15), (0.17)), причем условия этих утверждений удалось выразить в терминах ядра к и свободного члена ф интегрального уравнения (0.31). В свою очередь, при получении верхних границ для стохастических компонент погрешности потребовались аналогичные (то есть выраженные в терминах к и ф) утверждения об ограниченности дисперсий оценок функции в узлах сетки. Соответствующие формулировки и доказательства приведены в Разделе 4.1. Результаты этого раздела представлены в [20, 67 - 70, 110 - 113, 115, 117 - 120, 123 - 126, 130 -139].

В Разделе 4.2 получены общие теоремы о погрешностях комбинированных алгоритмов аппроксимации решения интегрального уравнения (0.31) (всего 6 утверждений; не удалось пока получить верхних границ для погрешностей локально-векторных оценок) и выписаны выражения для условно-оптимальных параметров рассматриваемых дискретно-стохастических процедур. Приведены соображения о выборе плотностей р, определяющих цепи Маркова, используемые для построения стохастических оценок в узлах. Результаты данного раздела опубликованы в [20, 112, 113, 115, 117 — 120, 123 - 126] (см. также работу [140], выполненную под научным руководством автора диссертации).

В Разделе 4.3 рассматриваются вопросы сходимости и условной оптимизации многомерного аналога метода полигона частот. Погрешность этого функционального алгоритма распадается (как для L2-, так и для С-подхода) на три части - помимо детерминированной и стохастической компонент возникает смещение. Предложены подходы к оценке смещения на основе разложения решения в ряд Тейлора. Приведены соображения о нецелесообразности использования гладких восполнений при реализации многомерного аналога метода полигона частот (то есть достаточно использовать базисные функции (0.8), (0.9) сг = 1 и приближение (0.36)). Получены также верхние границы для дисперсий оценок метода полигона частот, что дает возможность ограничить стохастическую компоненту погрешности для Ь2-подхода. С учетом того, что корреляции оценок в узлах убывают с ростом числа узлов, удалось, по аналогии с рассуждениями из теории экстремумов нормальных последовательностей, получить асимптотические верхние границы стохастической компоненты погрешности метода полигона частот для С-подхода. На этой основе сформулированы окончательные утверждения о погрешностях многомерного аналога метода полигона частот и получены выражения для условно-оптимальных параметров рассматриваемой процедуры. Результаты данного раздела опубликованы в 112, 113, 117, 120, 125] (см. также работы [141, 142], выполненные под научным руководством автора диссертации).

В Главе 5 рассмотрены различные приложения алгоритмов из Глав 1 - 4 и их аналогов. Приведены также результаты тестирования этих алгоритмов.

В Разделе 5.1 рассмотрен ряд вопросов решения стохастических задач математической физики. В частности, построенная в Разделе 1.3 экономичная вычислительная модель случайного поля использована при получении асимптотических (при росте оптической толщины слоя) формул для проходящего излучения через плоские стохастические слои вещества (реализуется методология работ [143, 144]). Здесь уместно заметить, что предположение о стохастической структуре облучаемого слоя является весьма естественным для ряда задач переноса излучения, в которых требуется оценить суммарный поток проходящего излучения [7, 11, 15, 21 - 23]. Аналитически и численно для используемой стохастической модели среды показано, что оптически толстый стохастический слой пропускает больше излучения, чем "детерминированный" (усредненный). Продемонстрирована возможность эффективного использования метода полигона частот для получения профилей (вдоль толщины слоя) плотностей столкновения и их производных, что позволило определить участки слоя, в которых происходит наиболее быстрое расхождение интенсивностей излучения для стохастической и усреденной сред. В Разделе 5.1 также отмечено, что введение стохастических элементов (случайных коэффициентов, случайных функций и т.п.) часто эффективно осуществляется за счет дополнительной рандомизации вероятностных представлений решений задач математической физики (рассматриваемая в разделе стохастическая задача теории переноса излучения может служить примером такой рандомизации). Это является одной из причин интенсивного развития теории таких вероятностных представлений (см. [9 - 14, 22, 23, 145 - 150], а также списки литературы в этих монографиях). Приведено вероятностное представление решения нелинейного разностного уравнения из [151]. Отмечено также, что в последнее время интенсивно развиваются численные методы, связанные с решением стохастических дифференциальных уравнений [152 - 154]. Результаты данного подраздела опубликованы в [16, 90, 91, 117, 121, 151].

В Разделе 5.2 исследуются смешанные дискретно-стохастические алгоритмы решения интегро-дифференциальных систем из двух уравнений. Первое из них, так называемое "полевое" уравнение, содержит неизвестную функцию 0 и интеграл по некоторой неизвестной функции распределения Ф. Для функции Ф, в свою очередь, справедливо соотношение типа уравнения переноса излучения; задаются также соответствующие начальные и граничные условия. Идея построения алгоритмов численного решения таких систем достаточно естественна и проста: "полевое" уравнение решать детерминированным методом (конечно-разностным, конечных элементов, коллокаций и т.д.), а источники, являющиеся линейными функционалами от решения уравнения переноса, оценивать с помощью метода Монте-Карло. В подразделе 5.2.1 приведены примеры практически важных задач из [155, 156 - 159], для численного решения которых применяются такие численные схемы. Приведены результаты тестирования смешанного алгоритма рассматриваемого класса на примере решения модельной каталитической задачи из [155]. Предложен подход к построению верхней границы погрешности этого алгоритма. В подразделе 5.2.2 рассмотрен алгоритм "конечных элементов - Монте-Карло" для решения одномерной нелинейной задачи радиационно-кондуктивного теплоперено-са (РКТ) [160 - 167]. Построены различные стохастические оценки конечно-элементных вкладов в источник уравнения теплопроводности (оценки по столкновениям, по поглощениям; локальные, векторные и локально-векторные оценки); проведен их сравнительный анализ и численное тестирование. Для оптически тонких слоев наилучшими оказались оценки по пробегу, а для оптически толстых слоев - локально-векторные оценки. Для случая "слабо линейной" задачи РКТ предложен подход к построению верхней границы погрешности для рассматриваемого комбинированного алгоритма. Результаты данного подраздела опубликованы в [31, 68, 130 - 133, 136, 137, 139, 168].

В Разделе 5.3 рассмотрено применение многомерного аналога метода полигона частот при решении нелинейных интегральных уравнений

Ч> = G(y>), (0.40) где tp принадлежит пространству С(2)(Х), а множество X и ее образ Y — <р{Х) совпадают и являются ограниченными выпуклыми областями с границей в R'. Предполагается, что решение сэтого уравнения может быть найдено методом простой итерации, начиная с некоторого приближения то есть ip[*] = Jimy4, где <^[т] = G(^[m~1]), (0.41) причем j]G(^H) pMjj < ду\ш\ рМц = ^sup ^[т]{х) yW^ 0<д<1 (0.42) xeY здесь и далее индекс в квадратных скобках обозначает номер итерации) и на каждой итерации решается линейное интегральное уравнение второго рода $т\х) = f + Ч) (0.43)

J У методом полигона частот и затем в качестве берется соответствующее приближение то есть Ь{М)(р[т\ч>[т-1])- (0-44)

Алгоритм такого типа впервые предложен в [169] (см. также [13, 170]); в этой же работе построены верхние границы погрешности и выражения для условно-оптимальных параметров в L/2-норме. Под научным руководством автора диссертации в [171, 172] Е.В.Шкарупа удалось решить эти же вопросы для более сложного С-подхода. Проведено тестирование алгоритма на примере модельных нелинейных уравнений из [173 - 175].

В Разделе 5.4 приведены результаты тестирования алгоритмов, рассмотренных в Главах 2 - 4. В подразделе 5.4.1 приведены соображения о целесообразности использования траекторий спектральных моделей случайных полей из Раздела 1.2 в качестве подынтегральных функций при тестировании алгоритмов численного (в том числе, параметрического) интегрирования. Такой выбор подынтегральных функций дает возможность соблюсти "независимость" тестирования, получить (хотя бы в простейших случаях) точные значения решения и порядки верхних границ оценки погрешности, контролировать гладкость и трудоемкость вычисления подынтегральной функции. Результаты данного подраздела опубликованы в [87]. В подразделе 5.4.2 исследуются адаптивные алгоритмы численного интегрирования из Разделов 2.2, 2.3 (соответствующие результаты опубликованы в [32, 176]). В подразделе 5.4.3 предложены алгоритмы вычисления констант, имеющихся в выражениях для верхних границ погрешностей и условно-оптимальных параметров исследуемых в Главах 3 и 4 численных процедур [117]. В подразделе 5.4.4 представлены результаты тестирования алгоритмов аппроксимации функций (0.30) из [111]. В подразделе 5.4.5 приведены результаты расчетов по многоуровневому алгоритму, позволившие сформулировать основные выводы Раздела 3.4 [129]. Наконец, в подразделе 5.4.6 рассмотрено специальное тестовое уравнение вида (0.31) с известным решением, на примере которого проведено сравнение дискретно-стохастических численных процедур, рассмотренных в Главе 4; в силу гладкости ядра к и свободного члена ф наилучшие результаты дала комбинированная процедура с локальными оценками в узлах сетки [117, 120]. Отметим также, что во всех тестах выбранные значения условно-оптимальных параметров обеспечили заданный уровень погрешности 7.

В Приложении 1 для решения Задачи 0.1 для случая, когда все коэффициенты {го,-} из (0.5) положительны, построен специальный алгоритм метода суперпозиции для получения выборочных значений случайных векторов с плотностью распределения, представляющей собой аппроксимацию Стренга-Фикса некоторой неотрицательной функции. Для произвольных {го,-} предложен алгоритм метода исключения (см. Алгоритм 0.3). Показано, что в одномерном случае метод обратной функции распределения и модифицированный метод суперпозиции для моделирования случайных величин с кусочно-постоянной и кусочно-линейной плотностями совпадают. Результаты данного раздела опубликованы в [17, 18, 31 — 34].

В Приложении 2 описан электронный учебник по методам Монте-Карло, в разработке которого автор принимал активное участие. Результаты данного раздела опубликованы в [16 - 20, 177 - 179].

В Заключении сформулированы основные результаты работы.

По материалам, представленным в диссертации, опубликовано: 8 статей в центральных российских журналах [34, 39, 70, 89, 116, 118, 121, 151], 9 статей в международных журналах [33, 87, 90, 97, 115, 120, 124, 125, 139], 13 статей в материалах Всесоюзных и международных конференций [40, 69, 96, 119, 122, 126, 129, 130, 135, 136, 176, 177, 178], 5 учебных пособий [16 - 20], 17 статей в сборниках ВЦ и ИВМ и МГ СО РАН [31, 62, 63, 65, 66, 84, 85, 110, 111, 114, 131, 134, 137, 138, 155, 168, 179], 8 препринтов ВЦ СО РАН [32, 91, 112, ИЗ, 117, 123, 132, 133], кандидатская диссертация [68]; имеются также тезисы Всесоюзных и международных совещаний, семинаров и конференций (в список литературы включены лишь важнейшие из них [64, 67, 86]). Результаты из диссертации были представлены на V Всесоюзной конференции Университета Дружбы Народов им. П.Лумумбы (Москва, март 1982), Всесоюзной научно-технической конференции "Вероятностные методы и средства" (Новгород, июнь 1983), конкурсе работ мододых ученых ВЦ СО РАН 1983 года (3 премия), I Всесоюзной конференции молодых исследователей "Актуальные вопросы теплофизики и физической гидрогазодинамики" (Новосибирск, март 1985), VII Всесоюзном совещании "Методы Монте-Карло в вычислительной математике и математической физике" (Новосибирск, октябрь 1985) [130], I Всемирном конгрессе общества математической статистики и теории вероятностей им. Бернулли (Узбекистан, Ташкент, сентябрь 1986) [64], Межреспубликанской научно-технической конференции "Вероятностные автоматы и их приложения" (Грузия, Батуми, октябрь 1986), II Всесоюзной конференции молодых исследователей "Актуальные вопросы теплофизики и физической гидрогазодинамики" (Новосибирск, март 1987), VI Всесоюзной научно-технической конференции "Радиационный теплообмен в технике и технологии" (Литва, Каунас, сентябрь 1987), Межреспубликанской школе-семинаре "Методы Монте-Карло и их приложения" (Казахстан, Алма-Ата, сентябрь 1987), Всесоюзной конференции "Актуальные проблемы вычислительной и прикладной математики" (Новосибирск, ноябрь 1987), Всесоюзной школе "Актуальные проблемы вычислительной математики и математической физики" (Черноголовка Московской области, март 1988), конкурсе работ молодых ученых ВЦ СО РАН 1988 года (1 премия), киевском городском семинаре по гауссовским случайным процессам (Украина, апрель 1989), V Международной Вильнюсской конференции по теории вероятностей и математической статистике (Литва, июнь 1989) [67], школе-семинаре "Актуальные проблемы теории статистического моделирования и ее приложения" (Узбекистан, Ташкент, сентябрь 1989), международном совещании "Monte Carlo Methods and Parallel Algorithms" (Болгария, Примор-ско, сентябрь 1989) [69], Всесоюзной конференции "Актуальные проблемы вычислительной и прикладной математики" (Новосибирск, ноябрь 1990) [86], конференциях модоло-дых ученых ВЦ СО РАН (март 1983, 1985 - 1991), VIII Всесоюзном совещании "Методы Монте-Карло в вычислительной математики и математической физике" (Новосибирск, 1991) [135, 136], международной конференции "Advanced Mathematics, Computations and Applications" (Новосибирск, июнь 1995), Международной научно-методической конференции "Новые информационные технологии в университетском образовании" (Новосибирск, март 1996) [177], международном совещании "Mathematical Methods in Stochastic Simulation and Experimental Design" (Санкт-Петербург, июнь 1996) [119, 126], международном семинаре "Algorithms and Complexity for Continuous Problems" (Германия, Даг-штуль, октябрь 1996), международной научно-практической конференции "Новые информационные технологии в университетском образовании" (Новосибирск, март 1997) [178], семинаре по вычислительной математике университета г.Кайзерслаутерн (Германия) - три лекции (январь - февраль 1998), семинаре по статистическому моделированию института Вейерштрасса г.Берлин (Германия, февраль 1998), международном семинаре "Algorithms and Complexity for Continuous Problems" (Германия, Дагштуль, май 1998), международном совещании "Third Petersburg Workshop on Simulation" (Санкт-Петербург, июнь 1998) [122], Третьем сибирском конгрессе по прикладной и индустриальной математике (Новосибирск, июнь 1998), международной конференции "Оптимизация численных методов" (Уфа, сентябрь 1998), международной конференции "Second IMACS Seminar on Monte Carlo Methods" (Болгария, Варна, июнь 1999), V международном семинаре-совещании "Кубатурные формулы и их приложения" (Красноярск, сентябрь 1999) [96], международной конференции "Комплексный анализ, дифференциальные уравнения и смежные вопросы" (Уфа, июнь 2000), IV сибирском конгрессе по прикладной и индустриальной математике (Новосибирск, июнь 2000), международном семинаре "Modern Problems in Applied Probability" (Новосибирск, август 2000), международном совещании "Fourth Petersburg Workshop on Simulation" (Санкт-Петербург, июнь 2001) [40, 129], VI международном семинаре-совещании "Кубатурные формулы и их приложения" (Уфа, июль 2001) [176] и неоднократно на семинаре ВЦ и ИВМ и МГ СО РАН "Статистическое моделирование в физике". Результаты из диссертации также представлены в спецкурсе "Методы Монте-Карло - II (функциональные оценки)", который ежегодно читается автором студентам старших курсов механико-математического факультета Новосибирского госуниверситета.

Несколько слов об оформлении работы. После названия раздела в тексте диссертации указывается ссылка на работы автора, содержащие результаты этого раздела, ссылки на работы других авторов делаются непосредственно в тексте. Чтобы разделить обзорные части диссертации и достижения автора, те материалы, которые автор считает новыми, набраны жирным шрифтом. Система обозначений в каждом разделе своя, то есть, например, вторая лемма в Разделе 2.1 (то есть в первом разделе второй Главы) будет обозначаться "ЛЕММА 2.1.2"; ссылки на формулы имеют такой же вид, но только номер формулы заключается в круглые скобки. Ссылки на литературу производятся по порядку упоминания в тексте и заключаются в квадратные скобки. Формулировки определений и утверждений выделены курсивом.

Автор выражает благодарность своему учителю чл.-корр. РАН Г.А.Михайлову за постоянное внимание к работе и ценные советы, своим коллегам профессорам С.М.Пригарину, М.М.Бежановой, доцентам О.А.Махоткину, С.А.Ухинову, Л.А.Москвиной, к.ф.-м.н. Г.А.Квашнину и ученикам к.ф.-м.н. Е.В.Шкарупа, Н.Г.Головко, Т.Е.Мезенцевой, Е.Г.Каблуковой, П.С.Рузанкину, Д.Р.Колюхину, А.В.Иванову за плодотворное сотрудничество; профессорам А.Д.Вентцелю, Н.Н.Ченцову, И.М.Соболю, В.В.Юринскому, С.Хайнриху, С.М.Ермакову, В.В.Пененко, Ю.Н.Григорьеву, Л.Я.Савельеву, М.С.Иванову, М.Д.Рамазанову, М.В.Носкову, В.И.Половинкину, К.К.Сабель-фельду, Б.А.Каргину, С.С.Артемьеву, П.Мате, С.Огава, С.Фоссу, доцентам С.В.Рога-зинскому, О.А.Курбанмурадову, Н.А.Симонову, А.А.Пашко, Е.Синдамбиве, А.Келлеру за полезные обсуждения результатов работы; сотрудникам отдела статистического моделирования в физике ИВМ и МГ СО РАН и всем тем, кто поддерживал автора при выполнении настоящей работы.

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

Заключение

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

В связи с тем, что многие оценки и модели имеют вид последовательностей случайных полей, рассмотрены вопросы слабой (или функциональной) сходимости таких последовательностей в пространствах С(Т) и D(T). Построены специальные удобные для использования в теории методов Монте-Карло дифференциальные и моментные условия, достаточные для выполнения условия слабой компактности, обеспечивающего (вместе с условием сходимости конечномерных распределений) слабую сходимость последовательностей случайных функций в С(Г) и D(T). На этой основе ослаблены достаточные условия сходимости метода зависимых испытаний.

Получены условия сходимости конечномерных распределений и ослаблены моментные условия слабой сходимости спектральных (рандомизированных и нерандомизированных) моделей однородного гауссовского случайного поля. Исследован класс моделей случайных полей, реализуемых с помомощью преобразований спектральных моделей, получены условия слабой сходимости таких преобразованных моделей. Спектральные (преобразованные и непреобразованные) модели использованы при тестировании алгоритмов численного (в том числе, параметрического) интегрирования.

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

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

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

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

На основании свойства "сноса погрешности в узлы сетки" аппроксимации Стренга-Фикса построены верхние границы стохастических компонент погрешности для зависимых и независимых оценок в узлах сетки. Для Ь2-подхода для этого получены верхие границы для дисперсий оценок в узлах. Для С-подхода проведены рассуждения с использованием теории порядковых статистик (для независимых оценок в узлах сетки) и теории метода зависимых испытаний (для зависимых оценок в узлах). При получении верхних границ стохастической компоненты погрешности метода полигона частот сформулированы и доказаны аналоги утверждений теории независимых порядковых статистик для случая "слабо зависимых" случайных величин. Сформулированы общие утверждения о погрешностях рассматриваемых процедур в терминах заданных функций и плотностей, используемых при построении стохастических оценок в узлах. Для всех исследуемых численных процедур решена задача нахождения условно-оптимальных значений параметров (числа узлов сетки и числа испытаний метода Монте-Карло), обеспечивающих минимальную трудоемкость дискретно-стохастических процедур при заданном уровне погрешности. Проведено тестирование исследуемых численных схем. Исследован многоуровневый метод зависимых испытаний, обеспечивающий оптимальный порядок сходимости (в смысле теории сложности) дискретно-стохастических процедур приближения интеграла, зависящего от параметра, с гладкой подынтегральной функцией. Численно показано, что выбор параметров многоуровневой процедуры по теории, основанной на простой стоимостной модели, на деле оказывается неоптимальным.

Исследован комбинированный алгоритм типа "конечно-разностный метод - метод Монте-Карло" для численного решения модельной системы уравнений, описывающей простейший каталитический процесс. Полученная методика использована при изучении алгоритма решения нелинейной системы уравнений вида "уравнение теплопроводности с источником энергии излучения - уравнение переноса для интенсивности излучения" , описывающей одномерный (то есть происходящий в бесконечном горизонтально однородном слое) нестационарный процесс радиационно-кондуктивного теплопереноса (РКТ). Алгоритм включал метод Эйлера по времени, метод конечных элементов по координате и метод Монте-Карло для вычисления вкладов источника в системе Галер-кина. Проведен сравнительный анализ различных стохастических оценок вкладов источника; рассматривались оценки по столкновениям, по поглощениям; локальные, векторные и новые локально-векторные оценки. Для оптически тонких слоев наилучшими оказались оценки по пробегу, а для оптически толстых слоев - локально-векторные оценки. Для случая "слабо линейной" задачи РКТ предложен подход к построению верхней границы погрешности для рассматриваемого комбинированного алгоритма.

Построены верхние границы погрешности и условно-оптимальные параметры С-подхода для многомерного аналога метода полигона частот, используемого при решении нелинейных интегральных уравнений методом простой итерации.

Разработаны методологические основы и реализованы основные модельные задачи электронного учебника по методам Монте-Карло. В это пособие, в частности, вошел ряд результатов из данной диссертационной работы.

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

1. Hammersley J.M., Handscomb D.C. Monte Carlo Methods. - New York: John Wiley and Sons, 1.c., 1964.

2. Freiberger W., Grenander U. A Short Course in Computational Probability and Statistics. Springer, 1971.

3. Спанье Дж., Гелбард 3. Метод Монте-Карло и задачи переноса нейтронов. М.: Атомиздат, 1972.

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

5. Михайлов Г.А. Некоторые вопросы теории методов Монте-Карло. Новосибирск, Наука, 1974.

6. Ермаков С.М. Метод Монте-Карло и смежные вопросы. М.: Наука, 1974.

7. Марчук Г.И. и др. Метод Монте-Карло в атмосферной оптике. Новосибирск: Наука, 1976.

8. Франк-Каменецкий А.Д. Моделирование траекторий нейтронов при расчете реакторов методом Монте-Карло. М.: Атомиздат, 1978.

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

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

11. Михайлов Г.А. Оптимизация весовых методов Монте-Карло. М.: Наука, 1987.

12. Сабельфельд К.К. Методы Монте-Карло в краевых задачах. М.: Наука, 1989.

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

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

15. Ogorodnikov V.A., Prigarin S.M. Numerical Modelling of Random Processes and Fields: Algorithms and Applications. Utrecht: VSP, 1996.

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

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

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

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

20. Пригарин С.М. Введение в численное моделирование случайных процессов и нолей. Части I, II. Новосибирск, изд-во НГУ, 1999.

21. Mikhailov G.A. Parametric Estimates by the Monte Carlo Method. Utrecht: VSP,1999.

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

23. Бахвалов Н.С. Численные методы. М.: Наука, 1975.

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

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

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

27. Ширяев А.Н. Вероятность. М.: Наука, 1980.

28. Devroy L. Non-Uniform Random Variate Generation. Springer-Verlag, 1986.

29. Махоткин О.А. Квантильный метод моделирования дискретных случайных величин // Теория и приложения статистического моделирования. Новосибирск, 1989. -С. 33 - 42.

30. Войтишек А.В., Махоткин О.А. Решение задач радиационно-кондуктивного тепло-переноса методом Монте-Карло. III одномерная спектральная задача // Теория и приложения статистического моделирования. - Новосибирск, 1984. - С. 122 - 136.

31. Войтишек А.В., Колюхин Д.Р. Использование аппроксимации Стренга-Фикса при вычислении многократных интегралов методом Монте-Карло. Новосибирск, 1996.- 23 с. (Препринт / РАН. Сибирское отделение. ВЦ; 1073).

32. Voytishek A.V. Using the Strang-Fix approximation in discrete-stochastic numerical procedures // Monte Carlo Methods and Applications. 1997. - Vol. 3, No. 2. - P. 89 -112.

33. Войтишек А.В. Применение аппроксимации Стренга-Фикса при вычислении многократных интегралов методом Монте-Карло // Сибирский журнал вычислительной математики / РАН. Сибирское отделение. Новосибирск, 1999. - Т. 2, N 2. - С. 111- 122.

34. Вентцель Е.С. Теория вероятностей. М., 1962.

35. Ченцов Н.Н. Оценки неизвестной плотности распределения по наблюдениям // Доклады Академии Наук СССР. 1962. - Т. 147, N 1. - С. 45 - 48.

36. Деврой JL, Дерфи JI. Непараметрическое оценивание плотности (Li). М.: Мир, 1988.

37. Соболев C.JI. Некоторые применения функционального анализа в математической физике. М.: Наука, 1988.

38. Войтишек А.В., Ухинов С.А. Использование существенной выборки в методе Монте-Карло // Сибирский журнал вычислительной математики / РАН. Сибирское отделение. Новосибирск, 2001. - Т. 4, N 2. - С. 111 - 122.

39. Makhotkin О.A., Voytishek A.V., Ivanov A.V. Usage of piece-constant interpolations in the double-sided Monte Carlo technique // Proceedings of the Fourth Petersburg Workshop on Simulation, St.Peterburg, June , 2001. P. 328 - 333.

40. Махоткин О.А. Эффективный алгоритм моделирования конечных одномерных плотностей вероятности методом двустороннего исключения // Сибирский журнал вычислительной математики / РАН. Сибирское отделение. Новосибирск, 2000. - Т. 4 (в печати).

41. Дуб Дж. Вероятностные процессы. М.: Издательство иностранной литературы, 1956.

42. Ченцов Н.Н. Слабая сходимость случайных процессов с траекториями без разрывов второго рода и так называемый "эвристический" подход к критериям согласия типа Колмогорова-Смирнова // Теория вероятностей и ее применения. 1956. ~ Т. 1, N 1. - С. 155 - 161.

43. Прохоров Ю.В. Сходимость случайных процессов и предельные теоремы теории вероятностей // Теория вероятностей и ее применения. 1956. - Т. 1, N 2. - С. 178 -238.

44. Колмогоров А.Н. О сходимости А.В.Скорохода // Теория вероятностей и ее применения. 1959. - Т. 1, N 2. - С. 239 - 247.

45. Скороход А.В. Предельные теоремы для случайных процессов // Теория вероятностей и ее применения. 1956. - Т. 1, N 3. - С. 289 - 319.

46. Ченцов Н.Н. Предельные теоремы для некоторых классов случайных функций // Труды Всесоюзного совещания по теории вероятностей и математической статистике. Ереван, 1960. - С. 280 - 285.

47. JTe Кам Л. Сходимость по распределению случайных процессов // Математика. -1960. Т. 4, N 3. - С. 107 - 142.

48. Varadarajan V.S. Convergence of stochastic prosseses // Bulletin of American Mathematical Society. 1961. - N 67. - P. 276 - 280.

49. Гихман И.И., Скороход А.В. Введение в теорию случайных процессов. М: Наука, 1965.

50. Гихман И.И., Скороход А.В. Теория случайных процессов. Т. 1. М.: Наука, 1971.

51. Боровков А.А. Сходимость распределений функционалов от случайных процессов // Успехи математических наук. 1972. - Т. 27, N 1 (163). - С. 3 - 41.

52. Jain N.C., Marcus М.В. Central limit theorems for C(5')-valued random variables // Journal of Functional Analysis. 1975. - V. 19, N 3. - P. 216 - 231.

53. Боровков А.А. Сходимость мер и случайных процессов // Успехи математических наук. 1976. - Т. 31, N 2 (188). - Т. 3 - 68.

54. Биллингсли П. Сходимость вероятностных мер. М.: Наука, 1977.

55. Мишура Ю.С. О сходимости случайных полей в J-топологии // Теория вероятностей и математическая статистика. Киев, 1977. - Т. 17. - С. 102 - 110.

56. Иванов А.В. О сходимости распределений функционалов от измеримых случайных полей // Украинский математический журнал. 1980. - Т. 32, N 1. - С. 27 - 34.

57. Wilson R.J. Weak convergence of probability measures in spaces of smooth functions // Stochastic Processes and Their Applications. 1986. - V. 23. - P. 333 - 337.

58. Пригарин C.M. Слабая сходимость вероятностных мер в пространствах непрерывно дифференцируемых функций // Сибирский математический журнал. 1993. - Т. 34, N 1. - С. 140 - 144.

59. Пригарин С.М. О сходимости и оптимизации функциональных оценок метода Монте-Карло в пространствах Соболева // Сибирский журнал вычислительной математики / Сиб. отд-ние. Новосибирск, 1999. - Т. 2, N 1. - С. 57 - 67.

60. Колмогоров А.Н., Фомин С.В. Элементы теории функций и функционального анализа. М.: Наука, 1972.

61. Войтишек А.В. Об одном условии слабой сходимости численных моделей случайных полей // Теория и приложения статистического моделирования. Новосибирск, 1985.- С. 48 55.

62. Войтишек А.В. Дифференциальные условия слабой сходимости стохастических оценок и моделей // Методы статистического моделирования. Новосибирск, 1986. -С. 35 - 52.

63. Войтишек А.В. Дифференциальные условия слабой сходимости последовательностей случайных функций // Тезисы докладов Первого Всемирного конгресса общества математической статистики и теории вероятностей им. Бернулли, Т. 1. М.: Наука, 1986. - С. 467.

64. Войтишек А.В. Слабая сходимость стохастических оценок и моделей в D для случая гладкой предельной функции // Численные методы статистического моделирования.- Новосибирск, 1987. С. 36 - 40.

65. Войтишек А.В., Пригарин С.М. Моментные условия функциональной сходимости численной рандомизированной численной спектральной модели гауссовских однородных полей // Теория и приложения статистического моделирования. Новосибирск, 1988. - С. 40 - 46.

66. Войтишек А.В. Функциональная сходимость стохастических оценок и моделей (Диссертация на соискание ученой степени кандидата физико-математических наук: 01.01.07). Новосибирск, 1990. - 174 с.

67. Войтишек А.В., Пригарин С.М. О функциональной сходимости оценок и моделей в методе Монте-Карло // Журнал вычислительной математики и математической физики. 1992. - Т. 32, N 10. - С. 1641 - 1651.

68. Михайлов Г.А. Численное построение случайного с заданной спектральной плотностью // Доклады Академии Наук СССР. 1978. - Т. 238, N 4. - С. 793 - 795.

69. Михайлов Г.А. Приближенные модели случайных процессов и полей // Журнал вычислительной математики и математической физики. 1983. - Т. 23, N 3. - С. 558- 566.

70. Шалыгин А.С., Палагин Ю.И. Прикладные методы статистического моделирования. JL: Машиностроение, 1986.

71. Пригарин С.М. О слабой сходимости приближенных моделей гауссовских случайных полей // Теория и приложения статистического моделирования. Новосибирск, 1988. - С. 31 - 39.

72. Prigarin S.M. Convergence of numerical models of random fields in Monte Carlo methods // Russian Journal of Numerical Analysis and Mathematical Modelling. 1992. - V. 7, N 5. - P. 441 - 456.

73. Kurbanmuradov 0. Convergence of numerical models for the Gaussian fields // Russian Journal of Numerical Analysis and Mathematical Modelling. 1995. - V. 10, N 4. - P. 311 - 324.

74. Булганова H.A. Сходимость приближенных моделей случайных полей (Диссертация на соискание ученой степени кандидата физико-математических наук: 01.01.07).- Алматы, 1995. 107 с.

75. Пиранишвили З.А. Некоторые вопросы статистико-вероятностного моделирования случайных процессов // Вопросы исследования операций. Тбилиси: Мицниереба, 1966. - С. 53 - 91.

76. Быков В.В. Цифровое моделирование в статистической радиофизике. М.: Советское радио, 1971.

77. Тихонов В.И. Статистическая радиотехника. М.: Радио и связь, 1982.

78. Товстик Т.М. Моделирование векторного марковского процесса с произвольным одномерным распределением // Вестник ЛГУ. 1985. - N 8. - С. 10 - 20.

79. Войтишек А.В. Исследование слабой сходимости моделей гауссовских случайных полей с заданным спектральным разложением корреляционной функции // Моделирование на вычислительных системах. Новосибирск, 1982. - С. 119 - 129.

80. Войтишек А.В. Рандомизированная численная спектральная модель стационарной случайной функции // Математические и имитационные модели систем. Новосибирск, 1983. - С. 17 - 25.

81. Voytishek A.V., Dyatlova E.G., Mezentseva Т.Е. Transformation of the spectral models of the Gaussian random fields // Russian Journal of Numerical Analysis and Mathematical Modelling. 2000. - V. 15, N 6. - P. 507 - 519.

82. Михайлов Г.А. Моделирование случайных процессов и полей на основе точечных потоков Пальма // Доклады Академии Наук СССР. 1982. - Т. 262, N 3. - С. 531 -535.

83. Михайлов Г.А., Войтишек А.В. Сходимость вычислительных моделей случайных полей, связанных с точечными потоками Пальма // Доклады Академии Наук. 1994.- Т. 335, N 3. С. 291 - 294.

84. Войтишек А.В., Михайлов Г.А. Численная реализация специальных моделей стохастически-неоднородных полей. Новосибирск, 1995. - 31 с. - (Препринт / РАН. Сибирское отделение. ВЦ; 1034).

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

86. Никольский С.М. Кубатурные формулы. М: Физматгиз, 1958.

87. Соболев С.Л. Введение в теорию кубатурных формул. М.: Наука, 1974.

88. Соболев С.JI., Васкевич В.Л. Кубатурные формулы. Новосибирск, изд-во ИМ СО РАН, 1996.

89. Voytishek A.V., Dyatlova E.G., Mezentseva Т.Е. Geometrical Monte Carlo method and it's modifications // Monte Carlo Methods and Applications. 2000. - Vol. 6, N 2. - P. 131 - 139.

90. Sard A. Best approximate integration formulas; best approximation formulas // American Journal of Mathematics 1949. - Vol. 71. - P. 80 - 91.

91. Haber S. Numerical evaluation of multiple integral // SIAM Review. 1970. - V. 12, N 4. - P. 481 - 526.

92. Traub J.F., Wasilkowski G.W. and Wozniakowski H. Information-based Complexity. -1988. Academic Press, New York.

93. Novak E. Deterministic and Stochastic Error Bounds in Numerical Analysis // Lecture Notes in Mathematics 1349. 1988. - Springer Verlag.

94. Heinrich S. Random approximation in numerical analysis // Functional Amalysis. -Marcel Dekker, 1994. P. 123 - 171.

95. Heinrich S. Complexity of Monte Carlo algorithms // The Mathematics in Numerical Analysis (Lectures in Applied Mathematics). Park City, Utah, 1996. - P. 1621 - 1633.

96. Иванов B.M., Кореневский М.Л., Кульчицкий О.Ю. Адаптивные схемы метода Монте-Карло повышенного порядка точности // Доклады РАН. 1999. - Т. 367, N 5. - С. 590 - 593.

97. Кореневский М.Л. Разработка адаптивно-статистических методов вычисления определенных интегралов (Диссертация на соискание ученой степени кандидата физико-математических наук: 05.13.18). Санкт-Петербург, 2000.

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

99. Фролов А.С., Ченцов Н.Н. Использование зависимых испытаний в методе Монте-Карло для получения гладких кривых // Труды Всесоюзного совещания по теории вероятностей и математической статистике. Вильнюс, 1962. - С. 425 - 437.

100. Литбеттер М., Ротсен X., Линдгрен Г. Экстремумы случайных последовательностей и процессов. М.: Мир, 1989.

101. Войтишек А.В., Пригарин С.М. Обоснование метода зависимых испытаний для многомерного параметра // Теория и приложения статистического моделирования. -Новосибирск, 1989. С. 73 - 80.

102. Shkarupa E.V., Voytishek A.V. Comparizon of two procedures for global stochastic estimation of functions // Bulletin Novosibirsk Computing Center. Series: Numerical Analysis. 1993. - V. 4. - P. 71 - 81.

103. Войтишек А.В. Дискретно-стохастические процедуры глобальной оценки решения интегрального уравнения второго рода. Общие вопросы. Новосибирск, 1994. - 23 с. - (Препринт / РАН. Сибирское отделение. ВЦ; 1018).

104. Войтишек А.В. Дискретно-стохастические процедуры глобальной оценки решения интегрального уравнения второго рода. Оценки погрешности. Новосибирск, 1995. - 53 с. - (Препринт / РАН. Сибирское отделение. ВЦ; 1049).

105. Войтишек А.В. Зависимые испытания с оптимальными плотностями в дискретно-стохастических численных процедурах // Труды ВЦ СО РАН. Серия: Вычислительная математика. Вып. 4. - Новосибирск, 1996. - С. 28 - 34.

106. 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.

107. Войтишек А.В. Дискретно-стохастические процедуры оценки интеграла, зависящего от параметра // Журнал вычислительной математики и математической физики. 1996. - Т. 36, N 8. - С. 23 - 38.

108. Войтишек А.В., Шкарупа Е.В. Дискретно-стохастические процедуры глобальной оценки решения интегрального уравнения второго рода. Оптимизация. Новосибирск, 1997. - 96 с. - (Препринт /РАН. Сибирское отделение. ВЦ; 1091).

109. Войтишек А.В. Асимптотика сходимости дискретно-стохастических численных методов глобальной оценки решения интегрального уравнения второго рода // Сибирский математический журнал. 1994. - Т. 35, N 4. - С. 728 - 736.

110. Войтишек А.В. О допустимом классе восполнений для дискретно-стохастических процедур глобальной оценки функций // Сибирский журнал вычислительной математики / РАН. Сиб. отд-ние. Новосибирск, 1998. - Т. 1, N 2. - С. 119 - 134.

111. Voytishek A.V. On the permissible class of interpolations for discrete-stochastic procedures of global estimaton of functions // Proceedings of the Third Petersburg Workshop on Simulation, St.Peterburg, June 28 July 3, 1998. - P. 137 - 140.

112. Войтишек А.В. Дискретно-стохастические процедуры глобальной оценки решения интегрального уравнения второго рода. Допустимый класс восполнений. Новосибирск, 1998. - 33 с. - (Препринт /РАН. Сибирское отделение. ИВМ и МГ; 1131).

113. Shkarupa E.V., Voytishek A.V. Convergence of discrete-stochastic numerical procedures with independent or weakly dependent estimators at grid nodes // Journal of Statistical Planning and Inference. 2000. - V. 85. - P. 199 - 211.

114. Heinrich S, Sindambiwe E. Monte Carlo complexity of parametric integration // Journal of Complexity. 1999. - V. 15. - P. 317 - 341.

115. Sindambiwe E. Optimal Algorithms for Parametric Integration (PhD). Aachen: Shaken Verlag, 1999.

116. Voytishek A.V., Mezentseva Т.Е. Practical use of multilevel algorithms // Proceedings of the Fourth Petersburg Workshop on Simulation, St.Peterburg, June , 2001. P. 500 -505.

117. Войтишек А.В., Махоткин О.А. Особенности построения векторных оценок функционалов при численном решении задачи радиационно-кондуктивного теплопереноса // Численные методы статистического моделирования. Новосибирск, 1987. - С. 110- 127.

118. Войтишек А.В. Оценка функционалов при решении задачи радиационно-кондуктивного теплопереноса. Новосибирск, 1988. - 23 с. - (Препринт/АН СССР. Сибирское отделение. ВЦ; 811).

119. Войтишек А.В. Применение локальных оценок для аппроксимации интенсивности излучения в плоском слое. Новосибирск, 1988. - 19 с. - (Препринт/АН СССР. Сибирское отделение. ВЦ; 815).

120. Войтишек А.В. Функциональная сходимость монте-карловской оценки решения интегрального уравнения второго рода с кусочно-гладким ядром // Вычислительная математика и моделирование в физике. Новосибирск, 1989. - С. 24 - 32.

121. Войтишек А.В. Использование процедур сглаживания функций в методе зависимых испытаний // Материалы 8-го Всесоюзного совещания "Методы Монте-Карло в вычислительной математики и математической физике". Т. 1. Новосибирск, 1991.- С. 71 74.

122. Войтишек А.В. Локально-векторная оценка радиационных потоков в плоском слое // Теория и приложения статистического моделирования. Новосибирск, 1990. - С. 83 - 91.

123. Войтишек А.В. Использование процедур сглаживания функций при построении локальной оценки метода Монте-Карло // Теория и приложения статистичекого моделирования. Новосибирск, 1991. - С. 33 - 38.

124. Voytishek A.V. Statistical estimation of radiative flows in numerical solution of radiative-conductive heat transfer problems // Russian Journal of Numerical Analysis and Mathematical Modelling. 1992. - V. 7, N 4. - P. 343 - 369.

125. Шкарупа E.B. С-подход к оценке погрешности и оптимизации векторных дискретно-стохастических процедур глобальной оценки решения интегрального уравнения второго рода // Труды ВЦ СО РАН. Серия: Вычислительная математика.- 1996. Вып. 4. - С. 146 - 167.

126. Шкарупа Е.В. Дискретно-стохастические процедуры глобальной оценки решения интегрального уравнения второго рода. Метод полигона частот. Новосибирск, 1996.- 34 с. (Препринт/РАН. Сиб. отд-ние. ВЦ; 1076).

127. Шкарупа Е.В. Оценка погрешности и оптимизация метода полигона частот для глобального решения интегрального уравнения второго рода // Журнал вычислительной математики и математической физики. 1998. - Т. 38, N 4. - С. 612 - 627.

128. Михайлов Г.А. Асимптотика средней интенсивности излучения для некоторых моделей стохастических сред // Известия Академии наук СССР. Серия: Физика атмосферы и океана. 1982. - Т. 18. - С. 1289 - 1295.

129. Михайлов Г.А., Середняков А.С. Численные и асимптотические оценки влияния размерности модели стохастической среды на оценки переноса излучения // Оптика атмосферы и океана. 1997. - Т. 10, N 3. - С. 201 - 210.

130. Вентцель АД. Курс теории случайных процессов. М.: Наука, 1975.

131. Вентцель А.Д., Фрейдлин М.И. Флуктуации в динамических системах под действием малых случайных возмущений. М.: Наука, 1979.

132. Ермаков С.М., Некруткин В.В., Сипин А.С. Случайные процессы для решения классических уравнений математической физики. М.: Наука, 1984.

133. Freidlin М. Functional Integration and Partial Differential Equations. Princeton, 1985.

134. Sabelfeld К.К., Simonov N.A. Random Walks on Boundary for Solving PDEs. -Utrecht: VSP, 1994.

135. Sabelfeld K.K., Shalimova I.A. Spherical Means for PDEs. Utrecht: VSP, 1997.

136. Войтишек А.В. Вероятностный подход к нахождению асимптотики решения нелинейных разностных уравнений // Вестник МГУ, серия: Математика, механика. -1982. N 4. - С. 22 - 28.

137. Милыптейн Г.Н. Численное интегрирование стохастических дифференциальных уравнений. Свердловск: УГУ, 1988.

138. Kloeden Р.Е., Platen Е., Schurz Н. Numerical Solution of SDE Through Computer Experiments. Berlin: Springer-Verlag, 1994.

139. Артемьев С.С. Численное решение стохастических дифференциальных уравнений. Новосибирск: НГУ, 1995.

140. Махоткин О.А., Войтишек А.В. Численное исследование погрешности решения модельной нелинейной интегро-дифференциальной системы методом Монте-Карло // Методы и алгоритмы статистического моделирования. Новосибирск, 1983. - С. 128 - 138.

141. Махоткин О.А., Кузнецов Ю.И., Слинько М.Г. Моделирование процессов в случае движения в реактивной среде // Управляемые системы. Новосибирск, 1970. -Выпуск 6. - С. 83 - 90.

142. Busoni G., Frosali G. A temperature-dependent nonlinear neutron transport problem // Journal Math. Anal. Appl. 1979. - V. 72, N 2. - P. 703 - 715.

143. Cambell P. Monte Carlo method for radiative transfer // International Journal of Heat and Mass Transfer. 1967. - V. 10, N 4. - P. 519 - 529.

144. Neunzert H., Wick J. Theoretiche und numerische ergebnisse zur nichlinearen Vlasov-Gleichung method // Lecture Notes in Mathematics. 1972. - V. 267. - P. 159 - 185.

145. Зигель P., Хауэлл Дж. Теплообмен излучением. М.: Мир, 1975.

146. Цой П.В. Методы расчета задач тепломассопереноса. М.: Энергоатомиздат, 1984.

147. Махоткин О.А. Решение задач радиационно-кондуктивного переноса методом Монте-Карло. I общий алгоритм // Численные методы и статистическое моделирование в теории переноса. - Новосибирск, 1980. - С. 119 - 130.

148. Махоткин О.А. Решение задач радиационно-кондуктивного переноса методом Монте-Карло. II серая среда // Методы и алгоритмы статистического моделирования - Новосибирск, 1983. - С. 116 - 127.

149. Махоткин О.А. Математические основы радиационного теплообмена. Новосибирск, изд-во ВЦ СО РАН, 1988.

150. Аль-Абед А., Сакадура Дж.-Ф. Комбинированный метод Монте-Карло конечных разностей для решения задачи совместного радиационно-кондуктивного тепло-переноса тепла в полупрозрачных средах // Теплопередача. - 1983. - Т. 105, N 4. -С. 247 - 249.

151. Мельниченко А.С., Огибин В.Н. Применение метода Монте-Карло к решению спектральных задач лучистого теплообмена / / Журнал вычислительной математики и математической физики. 1977. - Т. 17, N 4. - С. 1068 - 1074.

152. Kraus H.G. Hybrid finite element Monte Carlo method for coupled conduction and gas radiation enclousure heat transport // Numerical Methods in Engeneering. - 1988. -V. 26, N 2. - P. 361 - 378.

153. Войтишек А.В. О погрешности численного решения задачи радиационно-кондуктивного теплопереноса для плоского случая // Теория и приложения статистического моделирования. Новосибирск, 1988. - С. 165 - 180.

154. Михайлов Г.А. Трудоемкость методов Монте-Карло для глобальной оценки решений многомерных задач. Новосибирск, 1990. - 42 с. - (Препринт / АН СССР. Сибирское отделение; ВЦ; 922).

155. Mikhailov G.A. Cost of Monte Carlo methods for global estimation of solutions of multidimensional problems // Soviet Journal of Numerical Analysis and Mathematical Modelling. 1991. - V. 6, N 2. - P. 131 - 150.

156. Шкарупа E.B. Оценка погрешности и оптимизация в метрике пространства С метода Монте-Карло при итерационном решении нелинейных интегральных уравнений.// Труды конференции молодых ученых ИВМиМГ СО РАН. Новосибирск, 1997.- С. 197 211.

157. Plotnikov M.Yu., Shkarupa E.V. Error estimation and optimization in С space of Monte Carlo iterative solution of nonlinear integral equations.// Monte Carlo Methods and Application. - 1998. - Vol. 4, N 1. - P. 53-70.

158. Михайлов Г.А., Плотников М.Ю. Оценка "по пробегу" для решения линейного и нелинейного уравнения переноса излучения в целом // Доклады Академии Наук. -1994. Т. 337, N 2. - С. 162 - 164.

159. Plotnikov M.Yu. Using the weighted Monte Carlo method for solving nonlinear integral equations// Russian Journal of Numerical Analysis and Mathematical Modelling. 1994.- V. 9, N 2. P. 121 - 147.

160. Войтишек А.В., Каблукова Е.Г. Исследование адаптивных дискретно-стохастических алгоритмов численного интегрирования // Материалы VI Международного семинара-совещания "Кубатурные формулы и их приложения", Уфа, 2 -7 июля 2001 года. С. 46 - 52.

161. Bezanova М.М., Moskvina L.A., Voytishek A.V. Study of radiation transfer using the computational educational manual on Monte Carlo methods // Bulletin Novosibirsk Computing Center. Series: Numerical Analysis. 2000. - V. 9. - P. 19 - 24.

162. Винклер В. Условия непрерывности выборочных функций случайных полей // Теория вероятностей и ее применения. 1959. - Т. 4, N 4. - С. 480.

163. Юринский В.В. О выборочной непрерывности случайных полей // Теория вероятностей и ее применения. 1973. - Т. 18, N 3. - С. 633 - 639.

164. Фихтенгольц Г.М. Курс дифференциального и интегрального исчисления. М.: Изд-во техн.-теоретической литературы, 1948. - Т. 1-3.

165. Канторович JI.B., Акилов Г.П. Функциональный анализ. М.: Наука, 1984.

166. Никольский С.М. Приближение функций многих переменных и теоремы вложения.- М.: Наука, 1969.

167. Ядренко М.И. Спектральная теория случайных полей. Киев: Вища школа, 1980.

168. Kushner H.J. An application of the Sobolev imbedding theorems to criteria for the continuity of prosses with a vector parameter // Ann. Math. Statist. 1969. - V. 40, N 2. - P. 517 - 526.

169. Яглом A.M. Корреляционная теория стационарных случайных функций. Ленинград: Гидрометоеиздат, 1981.

170. Кушнер Г.Дж. Вероятностные методы аппроксимации в стохастических задачах управления и теории эллиптических уравнений. М.: Наука, 1985.

171. Сильвестров Д.С. Предельные теоремы для сложных случайных функций. Киев: Вища школа, 1974.

172. Монин А.С., Яглом A.M. Статистическая гидромеханика. М.: Наука, 1961.

173. Kraichnan R.H. Diffusion by a random velocity field // Physical Fluids. 1970. - V. 13, N 1. - P. 22 - 31.

174. Мулламаа A.P., Сулев M.A. и др. Стохастическая структура полей облачности и радиации. Тарту, 1972.

175. Коновалов Г.В., Тарасенко Е.М. Импульсные случайные процессы в электросвязи.- М.: Связь, 1973.

176. Рытов С.М., Кравцов Ю.А., Татарский В.И. Введение в статистическую радиофизику. Случайные поля. М.: Наука, 1978.

177. Михайлов Г.А., Сабельфельд К.К. О численном моделировании диффузии примеси в стохастических полях скоростей // Известия АН СССР. Физика атмосферы и океана. 1980. - Т. 16, N 3. - С. 229 - 235.

178. Малышев И.А., Палагин Ю.И. Математическое моделирование векторных случайных полей // Техническая кибернетика. 1980. - N 6. - С. 10 - 20.

179. Тройников B.C. Численное моделирование случайных процессов и полей на основе точечных потоков Пальма в задачах переноса излучения в облачной среде // Известия АН СССР. Физика атмосферы и океана. 1984. - Т. 20, N 4. - С. 274 - 279.

180. Палагин Ю.И., Федотов С.В., Шалыгин А.С. Вероятностное моделирование полей турбулентности атмосферы и морского волнения при исследовании сложных систем // Радиотехника и электроника. 1986. - Вып. 4. - С. 721 - 729.

181. Антипов М.В. Построение моделей полей скорости и концентрации // Численные методы статистического моделирования. Новосибирск, 1987. - С. 141 - 147.

182. Курбанмурадов О.А., Сабельфельд К.К., Чопанов Г. Статистическое моделирование диффузии примеси в случайных полях скоростей. Моделирование случайных полей. Новосибирск, 1988. - 28 с. - (Препринт АН СССР / Сибирское отделение, ВЦ; 775).

183. Кантер P.P., Пригарин С.М. Численное моделирование морского ветрового волнения для исследования поля отраженного оптического излучения. Новосибирск, 1989.- 25 с. (Препринт АН СССР / Сибирское отделение, ВЦ; 829).

184. Пригарин С.М. Спектральные модели векторных однородных полей. Новосибирск, 1992. - 36 с. - (Препринт АН СССР / Сибирское отделение, ВЦ; 945).

185. Каргин Б.А., Пригарин С.М. Имитация поверхности морского волнения и исследование ее оптических свойств методом Монте-Карло // Оптика атмосферы и океана.- 1992. Т. 5, N 3. - С. 285 - 291.

186. Prigarin S.M. Numerical models of random processes and fields and some applications in Monte Carlo methods // Russian Journal of Numerical Analysis and Mathematical Modelling. 1994. - V. 9, N 2. - P. 147 - 177.

187. Каргин Б.А., Пригарин С.М. Имитационное моделирование кучевой облачности для исследования процессов переноса солнечной радиации в атмосфере методом Монте-Карло // Оптика атмосферы и океана. 1994. - Т. 7, N 9. - С. 1275 - 1287.

188. Товстик Т.М. Стационарные случайные процессы с рациональными спектральными плотностями. Изд-во Санкт-Петербургского университета, 2000.

189. Козаченко Ю.В., Ядренко М.И. Локальные свойства выборочных функций случайных полей // Теория вероятностей и математическая статистика. 1976. - Вып. 14. - С. 53 - 66.

190. Козаченко Ю.В., Пашко А.А. Моделирование гауссовских стационарных случайных процессов, представимых в виде стохастических интегралов // Теория и приложения статистического моделирования. Новосибирск, 1988. - С. 10 - 24.

191. Крамер Г., Линдбеттер М. Стационарные случайные процессы. М.: Мир, 1969.

192. Питербарг В.И. Асимптотические методы в теории гауссовских случайных процессов и полей. М.: Изд-во МГУ, 1988.

193. Viskanta R. Radiation heat transfer: interaction with conduction and approximate methods in radiation // Proceedings of VII International Heat transfer conference. New York, 1982. - P. 103 - 121.

194. Howell J.R. Radiative transfer in multidimensional enclosures with participating media // ASME Paper 83-HT-32. 1983.

195. Висканта P. Перенос тепла теплопроводностью n излучением в поглощающих и рассеивающих средах // Теплопередача. 1965. - Т. 87, N 1. - С. 171 - 180.

196. Уэстон, Хаут. Неустановившийся перенос тепла при совместном действии излучения и теплопроводности в поглощающей, рассеивающей и испускающей среде // Теплопередача. 1973. - Т. 95, N 3. - С. 72 - 79.

197. Razzaque М.М., Howell J.R., Klein D.E. Finite element solution of combined radiative, convective and conductive heat transfer problems // Trans. Am. Nucl. Soc. 1981. - V. 38. - P. 334 - 336.

198. Cerstl S.A.W., Zardecki A. Discrete-ordinate finite element method for atmospheric radiative transfer and remote sensing // Appl. Opt. 1985. - V. 24. - P. 81 - 93.

199. Chung T.L., Kim J.Y. Two-dimensional combined-mode heat transfer by conduction, convection and radiation in emitting, absorbing and scattering media solution by finite elements // J. Heat Transfer ASME. - 1984. - V. 106, P. 448 - 452.

200. Fleck J.A., Jr., The calculation of nonlinear radiation transport by a Monte Carlo method // Methods Comput. Phys. 1963. - V. 1. - P. 43 - 65.

201. Fleck J.A., Jr., Commings J.D. An implisit Monte Carlo scheme for caculating time and frequency dependent nonlinear radiation transport // J. Comput. Phys. 1971. - V. 8, N 3. - P. 313 - 342.

202. Хауэлл Дж.Р., Перлмуттер M. Применение метода Монте-Карло для расчета лучистого теплообмена в излучающей среде, заключенной между двумя серыми стенками // Теплопередача. 1964. - N 1. - С. 148 - 157.

203. Хауэлл Дж.Р., Перлмуттер М. Метод Монте-Карло в задаче о лучистой теплопередаче в сером газе между двумя концентрическими цилиндрами // Теплопередача.- 1964. N 2. - С. 46 - 59.

204. Howell J.R. Application of Monte Carlo to heat transfer problems // Advances Heat Transfer. 1968. - N 5. - P. 7 - 67.

205. House L.L., Avery L.L. The Monte Carlo technique applied to radiative heat transfer // J. Quant. Spectrosc. Radiant Transfer. 1969. - V. 9. - P. 1579 - 1591.

206. Применение зональных методов расчета лучистого теплообмена (сборник трудов).- Краснодар, 1970. вып. 24.

207. Ratzell А.С., Howell J.R. Two-dimensional radiative transfer in absorbing, emitting, scattering media using P — N approximation // ASME Paper 82-HT-19. 1982.

208. Махоткин О.А. Моделирование излучения черного тела с распределенной температурой // Методы статистического моделирования. Новосибирск, 1986. - С. 101 -116.

209. Соболь И.М. О моделировании некоторых распределений, сходных с гамма-распределением // Методы Монте-Карло в вычислительной математике и математической физике. Новосибирск, 1976. - С. 24 - 28.

210. Соболь И.М. Метод Монте-Карло для расчета критичности в многогрупповом приближении // Метод Монте-Карло в проблеме переноса излучений. М.: Атомиз-дат, 1967. - С. 232 - 254.

211. Красносельский В.А., Вайникко Г.М., Забрейко П.П., Рутицкий Я.Б., Стеценко В.Я. Приближенное решение операторных уравнений. М.: Наука, 1969.

212. Годунов С.К. Решение систем линейных уравнений. Новосибирск: Наука, 1981.

213. Ченцов Н.Н., Корякин А.И. Оценивание функций и их моментов по наблюдениям в случайных узлах. М., 1985. - 24 с. - (Препринт / ИПМ; 33).

214. Ченцов Н.Н., Корякин А.И. Рандомизированная оценка функций и их моментов с почти оптимальной контролируемой погрешностью на классах W. М., 1987. - 22 с. - (Препринт / ИПМ; 81).

215. Ченцов Н.Н., Корякин А.И. Об оценивании заданной в случайных узлах функции методом наименьших квадратов // Теория вероятностей и ее применения. 1990. -Т. 35, вып. 4. - С. 771 - 774.

216. Михайлов Г.А. К вопросу о построении экономичных алгоритмов моделирования случайных величин // Журнал вычислительной математики и математической физики. 1966. - Т. 6, N 6. - С. 1134 - 1136.

217. Махоткин О.А., Пиримкулов М.И. Использование сплайнов в некоторых задачах статистического моделирования // Теория и приложения статистического моделирования. Новосибирск, 1988. - С. 43 - 53.

218. РОССИЙСКАЯ Г«<*УД*=С~ВЕННАЯ БИБЛИОТЕКАп 10¥S5-¥ -02