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

УДК 519.676 На правах рукописи

кописи

КАБЛУКОВА Евгения Геннадьевна

АДАПТИВНЫЕ ДИСКРЕТНО-СТОХАСТИЧЕСКИЕ АЛГОРИТМЫ ЧИСЛЕННОГО ИНТЕГРИРОВАНИЯ

01.01.07 - вычислительная математика

Автореферат

диссертации на соискание ученой степени кандидата физико-математических наук

О 5 ДЕК 2008

Новосибирск, 2008

003456425

Работа выполнена в Институте вычислительной математики и математической геофизики Сибирского отделения РАН (г. Новосибирск).

Научный руководитель: доктор физико-математических наук

Войтишек Антон Вацлавович

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

Васкевич Владимир Леонтьевич

кандидат физико-математических наук Попов Анатолий Степанович

Ведущая организация: Сибирский федеральный

университет, г. Красноярск

Защита состоится 15 января 2009 года в 15 часов на заседании диссертационного совета Д 003.015.04 при Институте математики им. С. Л. Соболева СО РАН по адресу: г. Новосибирск, пр. Академика Коптюга, 4.

С диссертацией можно ознакомиться в библиотеке Института математики им. С. Л. Соболева СО РАН.

Автореферат разослан 26 ноября 2008 года.

Ученый секретарь диссертационного совета Д 003.015.04 кандидат физико-математических наук

В. Л. Мирошниченко

Общая характеристика работы

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

Для интегралов I малых размерностей с гладкими (в обычном или обобщенном смыслах) подынтегральными функциями и относительно простыми областями интегрирования развита теория куба-турных формул. Кубатурная формула в общем случае имеет вид

Г "

1=1 ХСД', (1)

где {хх,..., х„} - заданные детерминированные (и, как правило, регулярные) узлы сетки в Я1, а {сх,... ,сп} - веса. Оптимальный выбор узлов и весов в (1) связан с минимизацией погрешности 6п — \1— 5„| и основан (явно или неявно) на использовании аппроксимаций подынтегральной функции д. Главным достоинством кубатурных формул является возможность получения гарантированной и сравнительно быстрой сходимости 8п к нулю при п —У оо для классов гладких подынтегральных функций д.

К недостаткам «классических» (детерминированных) кубатурных формул на классах подынтегральных функций следует отнести: слабый учет специфики той или иной подынтегральной функции, необходимость разработки специальных численных алгоритмов поиска оптимальных весов и (или) узлов, чувствительность к росту размерности и к гладкости начальных данных (подынтегральной функции д и области интегрирования X), трудности в построении показательных тестовых численных примеров и контроля точности и затрат при практических вычислениях.

Для существенно многомерных задач (т.е. для случая I 1 и даже I оо) достаточно эффективным оказывается стандартный метод Монте-Карло. Этот алгоритм основан на представлении

I = I д(х)/(х) йх = ЕС » ^ О С = 9(0 = (2)

здесь /-мерный случайный вектор £ распределен согласно плотности /. Этот алгоритм имеет следующие положительные свойства. Имеется возможность уменьшения трудоемкости алгоритма за счет удачного (согласованного с видом подынтегральной функции д) выбора весовой функции / (алгоритм выборки по важности) или преобразования исходного интеграла (выделение главной части) и весовой функции (методы математического ожидания и расщепления, выборка по группам и т. п.). Веса имеют простой вид о, = 1 /п, а узлы реализуются согласно выбираемому вероятностному распределению с плотностью /. Эффективность алгоритма (2) относительно слабо зависит от роста размерности / и от отсутствия гладкости начальных данных. Имеется возможность контроля затрат и точности вычислений.

Главным недостатком метода Монте-Карло является относительно низкая (порядка 1 /л/п) скорость сходимости погрешности к нулю при возрастании числа случайных узлов п.

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

По-видимому, одна из первых численных схем подобного рода была представлена Н.С.Бахваловым в начале шестидесятых годов прошлого века. Исходной областью X являлся /-мерный единичный куб (¿1, который разбивался на п равных кубов с вершинами в точках равномерной сетки. В каждом j-ou элементарном кубе выбирался узел XJ кубатурной формулы случайным образом (согласно равномерному распределению). Представленный алгоритм можно считать как кубатурной формулой со случайными узлами, так и предельным случаем выборки по группам в методе Монте-Карло. Н.С.Бахвалов показал, что его алгоритм является оптимальным (по скорости сходимости к нулю погрешности 6п при п —> оо) в пространстве непрерывно дифференцируемых подынтегральных функций С1^;). Для

этого ему потребовалось получать оценки сверху и снизу для оп. Методология работ Н.С.Бахвалова явилась основой для интенсивного развития так называемой теории сложности. В ней изучается вопрос о том, каков максимальный порядок стремления к нулю погрешности ¿а для данного класса вычислительных алгоритмов с количеством операций п.

Упомянутый пример подтверждает целесообразность разработки комбинированных алгоритмов численного интегрирования. Такие численные схемы могут уменьшить оба множителя трудоемкости £ = £ х ЮС метода Монте-Карло (здесь t - среднее время получения одного выборочного значения случайной величины а - дисперсия этой величины). В ряде случаев удается получить эффективные дискретно-стохастические модификации алгоритма (2), приводящие к состоятельным (вообще говоря, смещенным) оценкам.

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

Основные цели работы. Разработать и исследовать эффективные дискретно-стохастические алгоритмы численного интегрирования. Провести тестирование этих алгоритмов на основании построения стохастических систем функций и решения прикладных задач.

Методика исследований базируется на теории методов Монте-Карло и кубатурных формул. Использованы также элементы теории проекционно-сеточных методов.

Научная новизна работы. В диссертации получены следующие новые результаты, выносимые на защиту.

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

2. Разработан двусторонний геометрический метод Монте-Карло. Исследованы вопросы оптимизации этого метода для кусочно-постоянных мажорант и минорант подынтегральной функции.

3. Исследована эффективность дискретно-стохастических состоятельных оценок метода Монте-Карло: взвешенной равномерной выборки и оценки с поправочным множителем. Получены верхние оценки дисперсий и оценены затраты соответствующих дискретио-стохас-

тических численных схем.

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

5. Проведен сравнительный анализ известных аппроксимацион-ных базисов с точки зрения использования их в алгоритмах численного статистического моделирования. Показана целесообразность использования приближений Стренга-Фикса и Бернштейна в дискретно-стохастических численных схемах.

6. Рассмотрены возможности применения траекторий спектральных (гауссовских и негауссовских) моделей случайных функций при тестировании численных алгоритмов интегрирования. Такой подход позволил добиться независимости тестирования, получить требуемые свойства подынтегральных функций (гладкость, «сложность» вычисления и др.), вывести аналитические выражения для средних погрешностей. Исследован вопрос о слабой сходимости используемых негауссовских численных моделей.

Практическая ценность работы. Разработанные в диссертации дискретно-стохастические алгоритмы численного интегрирования могут быть использованы при численном решении прикладных задач «умеренно большой» размерности (от трех до десяти).

Публикации. Основные результаты опубликованы в 24 работах, список которых помещен в конце автореферата. Работы [А1-А5, Б1, В1, ВЗ, В5, Вб, В9, Г1, ГЗ, Г7, Г8] написаны автором совместно с А.В.Войтишеком и Т.Е.Булгаковой. С согласия А.В.Войтишека и Т.Е.Булгаковой совместно полученные в этих работах результаты частично включены в представляемую диссертационную работу. Кроме того, имеется ряд трудов, написанных автором индивидуально и с соавторами-студентами (О. С. Герасимовой, Н. В. Лощиной, А.И.Ефремовым, С.В.Бусыгиным); в последнем случае автор диссертации являлся научным руководителем соответствующих исследований [Б2, В2, В4, В7, В8, Г2, Г4-Г6]. Полученные в этих статьях и тезисах результаты также включены в диссертационную работу.

Апробация работы. Результаты, изложенные в диссертации, были представлены в докладах на международной конференции по вычислительной математике в Новосибирске (июнь 2002 года) [В5]; на Международной конференции по Монте-Карло и квази-Монте-Карло методам (Ульм, Германия, август 2006 года) [ГЗ]; на международных семинарах-совещаниях «Кубатурные формулы и их приложения»: в Красноярске (сентябрь 1999 года) [В1], в Уфе (июль 2001 года) [ВЗ], в Красноярске (август 2003 года) [АЗ, В6], в Улан-Удэ (август 2005 года) [А4, В8], в Уфе (июнь 2007 года) [Г7, Г8]; на конференциях молодых ученых Института вычислительной математики и математической геофизики СО РАН (март 2001 года [В2], март 2002 года [В4], апрель 2004 года [В7]); на Международных студенческих конференциях «Студент и научно-технический прогресс» (Новосибирск, НГУ; апрель 2003 года [Г1], апрель 2004 года [Г2], апрель 2007 года [Г4-Г6]) и неоднократно на семинаре отдела статистического моделирования в физике ИВМиМГ СО РАН.

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

Краткое содержание работы

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

В разделе 1.1 первой главы изучены возможности применения приближений

м

д(х) « Ьмд(х) = ^ (х), (3)

¿=1

на компактном множестве X С Я1 в методах Монте-Карло. В формуле (3) Ьмд обозначает аппроксимацию (или интерполяцию) функции д на сетке у(м~> = {уг,... ,ум}- Базисные функции Е^ = {XI} ■ ■ ■ ,Хм} 11 коэффициенты И7^ = ...,и>м} определенным образом связаны с узлами сетки Отмечено, что приближения

вида (3) могут использоваться при моделировании случайных величин (в частности, при применении гистограмм, полигонов частот и других приближений вероятностных плотностей; при построении

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

а) базисные функции %{(х) и коэффициенты {щ} неотрицательны;

б) выборочные значения согласно вероятностным плотностям, пропорциональным {Хг(х)}> эффективно численно реализуемы;

в) функция д(х) близка к функции Ьмд{~х) в некоторой функциональной норме;

г) аппроксимация (3) устойчива.

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

В разделе 1.2 более подробно исследована возможность применения приближений (3) в алгоритмах численного интегрирования. Сначала рассмотрена дискретно-стохастическая версия алгоритма выборки по важности, в котором плотность / из (2) имеет вид

Дх) = СЬм)д{х) |, (4)

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

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

1 = 1»+1х («(*) ~ »о«) + - ; (5)

м

<7о(х) = Ьмд(х) = ]Г^(уг)х,(х),

где г/о(4) = 9о(0//(£)• При сравнении дискретно-стохастические алгоритмы выборки по важности и выделения главной части особо отмечено, что порядки уменьшения дисперсии по шагу сетки Н одинаковы, а реализация алгоритма (5), как правило, проще (в частности, для ограниченных областей интегрирования X целесообразно использовать плотность / равномерного распределения).

К дискретно-стохастическим схемам численного интегрирования приводят также предельные случаи метода сложной многомерной симметризации, который строится следующим образом. Каждое ребро области интегрирования - единичного куба (¿1 - делится на /х равных частей, а сам куб - на М = ц1 подкубов Хт вида

Хт = {х = (х^,.. .,*<'>) : 0« - 1 < х« <

(г)

i = 1,...,/, ут = Разыгрывается равномерно распреде-

ленная в <Э( точка айв каждом Хт берется по две точки = (}т-е + а)/ци£т^т = Цт-а)/ц, где зт = ■■■ ,Ут), причем }т - целые числа, и е = (1,. ..,1) - единичный вектор. Точки £т и симметричны относительно центра куба Хгп. Кроме того,

точка £т1 может быть получена из £ГП2 с помощью целого числа сдвигов вдоль координат на к = 1//1. Рассмотрим оценку

0(м) = Ь Е «т; «*» = (6)

т=1

В разделе 1.2 получено выражение для трудоемкости алгоритма метода Монте-Карло с оценкой (6) и теоретически и численно показано, что сложная симметризация может дать выигрыш лишь для размерностей, меньших четырех (как и для простейших кубатурных формул типа формулы прямоугольников). Отмечено также, что оценку (6) можно рассматривать как «метод зависимых испытаний» для выборки по группам, а точнее, алгоритма Бахвалова, оптимального (в смысле теории сложности) в пространстве С2 ((¿г), в котором выбор точек и £т 4.гт происходит в каждом подмножестве Хт. Преимущества и недостатки (связанные с выбором большого числа

случайных точек) этого алгоритма подтверждены в численных экспериментах, в том числе, с использованием тестовых функций вида (16).

В разделе 1.3 рассмотрен геометрический метод Монте-Карло, который строится следующим образом. Пусть для функции (} из (2) выполнено соотношение 0 < с/(х) < фир(х). Введем дополнительную координату и в (/+1)-мерном пространстве рассмотрим область С = {(х, : х £ Х;0 < < фир(х)}, а в

ней - случайную точку £ = ,..., | О, , распределенную со-

гласно плотности/(х^,... = /(х,ж'г+1)) = /(х)/фир(х).

Заметим, что в этом случае вектор £ = ..., распределен согласно плотности / компонента условно равномерно распределена в интервале (0,фир(£))- Алгоритм состоит в реализации п значений ^ = ] = 1, ...,п, (I + 1)-мерного случайного вектора £ и в построении оценки вида

п

I» вп = (1 /п)

где Ха ~~ индикатор множества

д = {(х,х(г+1)) : х € X, 0 < х^ < 9(х)}.

При вычислении значения требуется проверять нера-

венство

§,+1) <«(£,)■ (7)

В разделе 1.3 показано, что за исключением «экзотических» случаев, для которых удается реализовать экономичные способы проверки неравенства (7), геометрический метод является неэффективной модификацией стандартного алгоритма (2). Здесь же рассмотрена дискретно-стохастическая версия двустороннего геометрического метода и показано, что этот алгоритм весьма эффективен в случае, когда вычисление значений функции (¡{х) трудоемко. Идея двустороннего метода состоит в построении легко вычислимых (например, кусочно-постоянных) приближений «снизу» и «сверху» для функции д(х) : ?/»/ош(х) < #(х) < фир(х), х € X. При реализации проверки типа (7) сначала сравниваются значения и

Если функции ?/"*сш;(х)> ?(х) и близки, то трудоемкая провер-

ка неравенства (7) происходит достаточно редко, и можно достичь существенного уменьшения общей трудоемкости алгоритма. В разделе 1.3 предложены приближенные алгоритмы построения функций У>(ош(х) и ?/>ир(х) и в простейшем случае интегрирования по единичному кубу (¿1 найдены оптимальные значения для соответствующего шага сетки. Теоретические выводы подтверждены тестовыми расчетами, в том числе, с использованием функций (16).

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

В разделе 2.1 рассмотрена модификация дискретно-стохастической версии выборки но важности (2), (4) для случая интегрирования по единичному кубу - взвешенная равномерная выборка•

I« = Е Я(<*МЫ/Е А»<) = / Е Ьмд(ац), (8)

¡=1 ¿=1 ¿=1 »=1

где / = /д( £мд(х) с1х. Здесь требуется моделировать равномерно распределенный вектор а вместо что дает существенное уменьшение трудоемкости алгоритма (2). Оценка (8) является состоятельной

со смещением =1 + 0 /п^. Главный член дисперсии

для п> 1 имеет вид 1)0п ' ~ (1/п) /д, (?(х)/(х) — //(х))2 <1х. Получена зависимость дисперсии Ив^ от шага сетки Л = 1//х:

+ ^ = (9)

Построены доверительные границы погрешности:

Р < 1е\/С\]п^ > 1 - е; Сх=1 (д(х) - 1Дх))2 ¿х.

Исследована функция затрат

где Т(ц) - время на предварительное вычисление величины /, ¿1 - среднее время вычисления величины Ьмд(сч), а ¿2 - среднее время для вычисления величины д(а{) (затраты на сложение этих величин, на умножение на / и на одно деление в (8) считались малыми и не учитывались); Сх(^) - величина С\ при условии, что плотность / выбирается по формуле (4). Анализ выражения (10) привел к выводу о наличии оптимального значения ц и увеличении этого значения с уменьшением 5. Например, при использовании в качестве Ьм9 кусочно-постоянного приближения имеем ¿1 и ¿2, а время вычисления I равно ¡Н\, и тогда

(, Ч . 1Д/+2)

18Ф )

Другой пример эффективного применения леммы о состоятельных оценках представлен в разделе 2.2. Рассмотрен метод Монте-Карло с поправочным множителем'.

= (;£*«) (яЁ*«.)). <»>

где ЕЯ(£) = 1. Смещение оценки (11) определяется выражением Е<?12) = / - (1/п) ¡х д(х)(1 - Я(х))/(х) (1х. Главный

член дисперсии

для п » 1 имеет вид Ъв(п] и (1/п) /х(д(х) - 1(2 - Я(х)))2/(зс) йх. Если взять Я(х) = 2 —б/(х)//, то

, и можно добиться существенного уменьшения трудоемкости алгоритма (2).

Оптимальный выбор функции Я(х) невозможен (величина I неизвестна). В диссертации предложено использовать дискретные приближения оптимального поправочного множителя. Рассмотрен алгоритм (2) в случае интегрирования по единичному кубу ф/ с плотностью равномерного распределения /(х) = 1; здесь д(х) = д(х). Возьмем Я(х) = 2-Ьмд(х)/1, где Ьмд - приближение Стренга-Фикса из (3). Для этого случая получена зависимость смещения оценки (11) от шага сетки Л = 1//г. Соответствующая граница для дисперсии

шг

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

2.1 и 2.2 подтверждены тестовыми расчетами, в том числе, с использованием функций (16).

В разделе 2.3 рассмотрены различные варианты оценок функционала Ih, — (</>, h) от решения интегрального уравнения второго рода <р = К<р + /. Отмечено, что вместо рандомизации полного ряда Неймана с помощью аппарата обрывающихся с вероятностью единица цепей Маркова можно приближать конечный отрезок ряда. При этом соответствующая оценка функционала Ih получается смещенной. На тестовых примерах показано преимущество использования смещенных оценок, которое связано, в частности, с отсутствием необходимости розыгрыша поглощения на каждом шаге моделирования соответствующей цепи Маркова. Более того, при приближении конечных отрезков ряда Неймана обнаружилась возможность использования эффективных дискретно-стохастических методов численного интегрирования. Показано, что методика оптимизации рассматриваемых смещенных оценок во многом сходна с методикой оптимизации дискретно-стохастических алгоритмов глобального приближения функций, представленных в интегральной форме.

В третьей главе рассмотрены вопросы тестирования алгоритмов численного интегрирования. В качестве тестовых подынтегральных функций предложено использовать траектории численных моделей случайных полей (см. далее описание разделов 3.2 и 3.3). В связи с этим в разделе 3.1 рассмотрены преобразования рандомизированной спектральной модели однородного гауссовского случайного поля

к

= J2akbk] cos(Abx) + T£2) sin(Abx)], Afc ~/(А)/рь (12)

где /(A) - соответствующая спектральная плотность,^ = /Afc /(A) d\,

а i — 1,2 - независимые в совокупности стандартные нормальные величины. В тестовых вычислениях использовалась модель (12) с ограниченным спектром, для которой

X = (0,1)', К = т1, /(А) = {1 /А1 при А е (О, А)1] 0 иначе},

Afc = Aki-.k, = [hh,(k1+l)h)x...x[kih,(ki+l)h), ak = </pk = I/Vic,

(13)

здесь h — A/m, ki = 0,..., m — 1 и pk = l/K.

Первый тип изученных преобразований был связан с рассмотрением неслучайных функций от значений поля (12):

(14)

Отмечена возможность воспроизведения произвольных негауссовских одномерных распределений Р с помощью метода обратной функции распределения, для которого ф(у) = Р"1(Ф(у)); здесь Ф - функция распределения стандартной нормальной случайной величины. Изучены случаи монотонных и кусочно-монотонных дифференцируемых функций ф, приведены соответствующие примеры. Рассмотрен вопрос о функциональной сходимости последовательности (14) и доказано

УТВЕРЖДЕНИЕ 3.1. Если последовательность случайных функций {£к, К = 1,2,...} слабо сходится к случайной функции £о при К —> оо, а функция гр (неслучайная) равномерно непрерывна на (—оо, +оо), то последовательность {Ек = слабо сходится

в С(Х) к полю о)-

Второй тип преобразований был связан с комбинациями поля (12) со случайными величинами г) известного распределения:

Например, для суммы £/<"(х) и г/ получаются свертки соответствующих распределений. Изучены также численные реализации случайных функций, представимых в виде сумм независимых случайных функций.

Модели (12)—(15) применены в разделе 3.2 при построении тестовой системы функций, используемой далее для изучения свойств дискретно-стохастических алгоритмов численного интегрирования (1), (2). Сформулирован ряд требований к тестовой системе и показано, что эти требования выполнены для функций (12)—(15). Приведем краткий анализ этих требований.

1). Чтобы соблюсти <?независимость» тестирования, нужно добиваться того, чтобы вид (график) подынтегральной функции д из (1) был случайным, заранее непредсказуемым. Если взять

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

Саг(х) =д(£к(х),т)).

(15)

<7(х) = ЛгЫх), х £ X,

(16)

нормальных случайных величин {7^ , 3 = 1,2}, а также случайны точки {А<;}. Для расширения класса подынтегральных функций можно использовать описанные выше преобразования (14), (15).

2). Для рассмотрения случаев «сложных» подынтегральных функций д нужно, чтобы имелась возможность контролировать вычислительные затраты на получате одного значения функции. Варьировать эти затраты для функции (16) можно за счет изменения числа слагаемых (параметра К) в сумме (12).

3). Нужно, чтобы хотя бы в простейших ситуациях можно было проверить расчеты аналитически. Например, для функции (16) в одномерном случае (I = 1) имеем

Г / ч Л Г1 ле / Л Л А V* ^ 8к1Л* - № (созЛ* - !) /о 9{Х)ЛХ = /о -£-•

4). В связи с тем, что сходимость многих кубатурных формул обусловлена требованиями вида д € В(Х), должна присутствовать возможность контроля свойств подынтегральной функции д (в частности, свойств гладкости). Для простоты снова рассмотрим одномерный случай. Выражение для д-й производной случайной функции А£к(х) по х имеет вид:

к {— 9 1

дЫ(х) = ^(аг) = А £ ( А® со8(А**+27га*,2+фг/2).

(17)

При достаточно большом А в сумме (17) возникнут большие коэффициенты А« (во всяком случае, для к, близких к К - для модели с разбиением спектра), причем эти коэффициенты растут с ростом q степенным образом. Хотя формально функция (16) является бесконечно дифференцируемой по х, можно считать, что д = А£к £ СГ(Х), если < для д < г и > 0} для д> г, где О - заданное

достаточно большое положительное число (т. е. на практике разумно полагать, что производная не существует, если ее значение по модулю превышает заданный уровень С)). Варьируя А и задавая <Э, можно добиваться принадлежности функции = пространству СГ(Х) для требуемого г.

Следующее требование рассмотрено в разделе 3.3.

5). Для изучения теоретической эффективности алгоритмов численного интегрирования нужно, чтобы имелась возможность

получать уточненные верхние границы для погрешностей используемых численных методов интегрирования с заданными множествами функций g и областей X. Достаточно простой вид подынтегральных функций (12), (13) позволяет получать верхние границы средних погрешностей алгоритмов интегрирования. Это продемонстрировано на примере исследования простейших квадратурных формул. В качестве примера приведем

УТВЕРЖДЕНИЕ 3.2. Если функция g имеет вид (16), то для

средней погрешности Д1 = Е Y^iLi d(xi)H ~ Jo 9ix) dx формулы прямоугольников

/•1 м

1= g{x)dx^^2g(xi)H, H = l/M, Xi = (г - \)Н + Я/2

J° г=1

справедливо неравенство

д < (К + 1)(2К + 1)

1 ~ 144л/2 К'2

Проведено численное тестирование простейших квадратурных формул, подтвердившее характер зависимости погрешностей этих формул от параметров А я К. Следует особо отметить, что аналоги утверждения 3.2 доказаны в главе 1 для исследуемых дискретно-стохастических алгоритмов численного интегрирования.

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

Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований (проект 07-01-00024а).

Публикации по теме диссертации

А. Статьи в журналах из Перечня ВАК

1. Voytishek А. V., Dyatlova (Kablukova) E.G., Mezentseva (Bulgakova) Т. E. Transformation of the spectral models of the Gaussian random fields // Russian Journal of Numerical Analysis and Mathematical Modelling. 2000. V. 15, № 6. P. 507-519.

2. Voytishek A. V., Kablukova E. G. Usage of approximation functional basises in Monte Carlo methods // Russian Journal of Numerical Analysis and Mathematical Modelling. 2003. V. 18, № 6. P. 521-542.

3. Войтишек A.B., Каблукова Е.Г., Булгакова Т.Е. Использование спектральных моделей случайных полей при исследовании алгоритмов

численного интегрирования // Вычислительные технологии. 2004. Т. 9, специальный выпуск. С. 50-61.

4. Войтишек A.B., Каблукова Е.Г., Герасимова О. С. Сравнение различных вариантов рандомизации метода последовательных приближений // Вычислительные технологии. 2006. Т. 11, спец. выпуск. С. 27-35.

5. Бусыгин С. В., Войтишек А. В., Каблукова Е. Г., Ефремов А. И. Дискретно-стохастические состоятельные оценки метода Монте-Карло // Журнал вычислительной математики и математической физики. 2008. Т. 48, № 9. С. 1543-1555.

Б. Статьи в рецензируемых зарубежных журналах

1. Voytishek А.V., Dyatlova (Kablukova) E.G., Mezentseva (Bulgakova) Т. E. Geometrical Monte Carlo method and it's modifications // Monte Carlo Methods and Applications. 2000. V. 6, № 2. P. 131-139.

2. Kablukova E.G. Investigation of methods of numerical integration with optimal convergence speed // Monte Carlo Methods and Applications. 2005. V. 11, № 4. P. 397-406.

В. Статьи в сборниках

1. Войтишек A.B., Дятлова (Каблукова) Е.Г., Мезенцева (Булгакова) Т. Е. Геометрический метод Монте-Карло и его модификации // Материалы V международного семинара-совещания «Кубатурные формулы и их приложения». Красноярск: КГТУ, 2000. С. 46-54.

2. Каблукова Е. Г. Исследование адаптивных алгоритмов численного интегрирования // Материалы конференции молодых ученых. Новосибирск: ИВМиМГ СО РАН 2001. С. 94-103.

3. Войтишек А. В., Каблукова Е. Г. Исследование адаптивных дискретно-стохастических алгоритмов численного интегрирования // Материалы VI международного семинара-совещания «Кубатурные формулы и их приложения». Уфа: ИМВЦ УНЦ, 2001. С. 46-52.

4. Каблукова Е. Г. Двусторонний геометрический метод Монте-Карло // Материалы конференции молодых ученых. Новосибирск: ИМВиМГ, 2002. С. 76-81.

5. Kablukova Е. G., Shvets V. V., Voytishek А. V., Golovko N. G. Function approximations as probabilistic densities // Proceedings of the International Conference on Computational Mathematics. Новосибирск: ИВМиМГ CO PAH, 2002. P. 211-215.

6. Булгакова Т. E., Войтишек А. В., Каблукова E. Г. Использование стохастической системы функций при исследовании алгоритмов численного интегрирования // Материалы VII Международного семинара-совещания «Кубатурные формулы и их приложения». Красноярск: КГТУ, 2003. С. 26-32.

7. Каблукова Е. Г. Исследование методов численного интегрирования с оптимальной скоростью сходимости // Труды конференции молодых уче-

вых. Новосибирск: ИВМиМГ СО РАН, 2004. С. 67-77.

8. Каблукова Е. Г., Герасимова О. С. Исследование математической модели переноса частиц с анизотропным рассеянием / / Материалы VIII международного семинара-совещания «Кубатурные формулы и их приложения». Улан-Удэ: ВСГТУ, 2005. С. 49-52.

9. Войтишек А. В., Каблукова Е. Г. Исследование метода сложной симметризации // Труды 9-го Международного семинара-совещания «Кубатурные формулы и их приложения». Уфа: ИМВЦ УНЦ РАН, 2007. С. 61-75.

Г. Тезисы конференций

1. Каблукова Е. Г., Булгакова Т. Е. О некоторых применениях численной стохастической системы функций // Материалы XLI Международной студенческой конференции «Студент и научно-технический прогресс». Математика. Новосибирск: НГУ, 2003. С. 118-119.

2. Каблукова Е.Г. Исследование методов численного интегрирования с оптимальной скоростью сходимости // Материалы XLII Международной студенческой конференции «Студент и научно-технический прогресс». Математика. Новосибирск: НГУ, 2004. С. 126.

3. Voytishek А. V., Kablukova Е. G., Gerasimova О. S. Randomization of the consistent approach method for solution of the integral equation of the second kind // Abstracts of the 7-th International Conference on Monte and Quasi-Monte Carlo Methods in Scientific Computing. Ulm University (Germany), 2006. P. 143.

4. Лощина H.В., Каблукова Е.Г. Асимптотика метода сложной симметризации // Материалы XLV Международной студенческой конференции «Студент и научно-технический прогресс». Математика. Новосибирск: НГУ, 2007. С. 204-205.

5. Ефремов А. И., Каблукова Е. Г. Дискретно-стохастический метод взвешенной равномерно выборки // Там же. С. 202-203.

6. Бусыгин C.B., Каблукова Е.Г. Дискретно-стохастический метод Монте-Карло с поправочным множителем // Там же. С. 201-202.

7. Войтишек А. В., Каблукова Е. Г., Бусыгин С. В., Ефремов А. И. Использование дискретно-стохастических состоятельных оценок в численном интегрировании // Сборник материалов Уфимской международной математической конференции, посвященной памяти А.Ф.Леонтьева. Т. 1. Уфа: ИМВЦ УНЦ РАН, 2007. С. 50-51.

8. Войтишек A.B., Каблукова Е.Г., Лощина Н.В. Исследование метода сложной симметризации // Там же. С. 52 53.

Каблукова Е.Г.

Лицензия ИД № 02202 от 30 июня 2000 г. Подписано в печать 21 октября 2008 г. Формат бумаги 60 х 841/хб Объем 1,0 п. л. 0,9 уч.-изд. л. Тираж 100 экз. Заказ 136

ООО «Омега Принт», Новосибирск-90, пр. Лаврентьева, 6

Введение.

0.1. Детерминированные и стохастические кубатурные формулы.

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

Формулы Бахвалова и теория сложности.

0.3. Цель и структура диссертации.

0.4. О публикациях по теме диссертации.

0.5. Краткое описание рассматриваемых в диссертации численных схем.

0.6. Тестирование алгоритмов численного интегрирования.

0.7. Апробация работы.

Глава 1. Дискретно-стохастические несмещенные оценки в алгоритмах численного интегрирования.

1.1. Использование функциональных базисов в методах Монте-Карло.

1.1.1. Моделирование случайных величин.

1.1.2. Функциональные оценки.

1.1.3. Выбор функционального базиса.

1.1.4. Моделируемость аппроксимации Стренга-Фикса.

1.1.5. Моделируемость аппроксимации Бернштейна.

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

1.2.1. Дискретно-стохастическая версия метода выборки по важности.

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

1.2.3. Сложная многомерная симметризация.

1.2.4. Дискретно-стохастическая версия метода выборки по группам

1.3. Двусторонний геометрический метод Монте-Карло.

1.3.1. Геометрический метод И. М. Соболя.

1.3.2. Модификация геометрического метода.

1.3.3. Дискретно-стохастическая версия двустороннего геометрического метода.

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

2.1. Дискретно-стохастическая версия метода взвешенной равномерной выборки.

2.1.1. Лемма о состоятельных оценках.

2.1.2. Взвешенная равномерная выборка.

2.1.3. Использование аппроксимации Стренга-Фикса.

2.1.4. Зависимость дисперсии от шага сетки.

2.1.5. Построение доверительных границ и оптимизация оценки 9п ^.

2.1.6. Результаты тестовых численных экспериментов.

2.2. Дискретно-стохастическая версия метода Монте-Карло с поправочным множителем.

2.2.1. Оценка с поправочным множителем.

2.2.2. Приближение оптимального множителя. Зависимость смещения и дисперсии от шага сетки.

2.2.3. Построение доверительных границ и оптимизация оценки в.

2.2.4. Результаты тестовых численных экспериментов.

2.3. Рандомизация метода последовательных приближений.

2.3.1. Итерационный процесс с интегральным оператором.

2.3.2. Приближения функционала.

2.3.3. Тестовая задача.

2.3.4. Использование специального функционала.

2.3.5. Пример согласованного выбора параметров

Глава 3. Стохастическая тестовая система функций.

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

3.1.1. Численные спектральные модели гауссовских случайных полей.

3.1.2. Тестовая спектральная модель.

3.1.3. Преобразования гауссовских моделей: использование функций многих переменных.

3.1.4. Использование комбинаций со случайными величинами.

3.1.5. Функциональная сходимость преобразованных моделей.

3.1.6. Группировка слагаемых в моделируемой сумме.

3.2. Тестовая система функций.

3.2.1. Использование модельных траекторий случайных функций.

3.2.2. Выполнение требований (0.1а)-(0.1д).

3.3. Средние оценки погрешностей простейших квадратурных формул.

0.1. Детерминированные и стохастические кубатурные формулы. С развитием вычислительной техники возрастает интерес к численным методам решения прикладных задач. Математическое описание исследуемого процесса сводится, как правило, к рассмотрению неизвестной функции многих переменных, для которой записывается система дифференциальных уравнений (см., например, [1]). Одним из способов приближенного решения этой системы является построение разностной схемы и сведение задачи к решению системы линейных уравнений для значений неизвестной функции в узлах сетки (см., например, [2-4]). Часто также оказывается целесообразным сведение (или постановка) задачи к интегральной форме, когда исследуемая функция представляет собой многократный интеграл, зависящий от параметра, или является решением интегрального уравнения (см., например, [1]). В последнем случае при возникновении интегрального уравнения Фредгольма второго рода соответствующий интегральный оператор предполагается сжимающим, и решение записывается в виде ряда Неймана, представляющего собой сумму параметрических интегралов бесконечно возрастающей кратности (см., например, [5]). Далее используются численные методы приближенного вычисления получаемых многократных интегралов на ЭВМ. При разработке этих методов решается

ЗАДАЧА 0.1. Построить алгоритм вычисления интеграла здесь X - замыкание тех х € Д', для которых <у(х) ф 0.

Для интегралов I малых размерностей I с гладкими (в обычном или обобщенном смыслах) подынтегральными функциями д и относительно простыми областями интегрирования X развита теория квадратурных (для случая I = 1) и кубатурных (для I > 1) формул (см., например, [4, 6]). Кубатурная формула в общем случае имеет вид где {х1,. ,хп} - заданные детерминированные (и, как правило, регулярные) узлы сетки в В1, а {с1,.,с71} - веса. Вычисление интеграла (0.1) по формуле (0.2) будем называть АЛГОРИТМОМ 0.1. В качестве X в данной работе будем использовать, как правило, простые компактные подмножества в В} (чаще всего - /-мерный единичный куб = {х = (жь . . . , £;) : 0 < Хг < 1; 2 = 1,., /}).

Оптимальный выбор узлов и весов связан с минимизацией погрешности 5п = \1 — 5П| и основан (явно или неявно) на использовании аппроксимаций подынтегральной функции д. Главным достоинством кубатурных формул является возможность получения гарантированной и сравнительно быстрой сходимости 5п к нулю при п —У оо для классов гладких подынтегральных функций д.

К недостаткам «классических» (детерминированных) кубатурных формул на классах подынтегральных функций следует отнести:

- слабый учет специфики той или иной подынтегральной функции;

- необходимость разработки специальных численных алгоритмов поиска оптимальных весов и (или) узлов;

- чувствительность к росту размерности и к гладкости начальных данных (подынтегральной функции д и области X);

0.1) п

0.2)

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

Для существенно многомерных задач 0.1 (т.е. для случая ¿>1и даже I —V сю) достаточно эффективным оказывается стандартный метод Монте-Карло (см., например, [7-9]). Этот алгоритм основан на представлении

1 = 1 д(х)Дх) ¿х = ЕС, С = <7®, д(х) = </(х)//(х). (0.3)

Для выполнения (0.3) достаточно потребовать /(х) ф 0 при х 6 X. Весовая функция / является вероятностной плотностью в Я1, т. е. /(х) > 0 и //(х)сЬс = 1, а /-мерный случайный вектор £ распределен согласно плотности /.

АЛГОРИТМ 0.2 [7-9]. 1. Реализуем п значений случайного вектора . , £п.

2. Вычисляем приближенное значение интеграла (0.1):

3=1 3=1

Если в (0.4) трактовать как набор независимых одинаково распределенных случайных векторов с плотностью распределения /, то случайные величины (1 = 9(^1), -■■)(п ~ я{€п) будут также независимыми одинаково распределенными с математическим ожиданием I (см. соотношение (0.3)) и дисперсией

БС = а2 = Бд(0 - I ?2(х) Дх) ¿х - /2 = I ¿х ~ 1\ (0.5)

Если величина (0.5) конечна, то в силу закона больших чисел (см., например, [10]) формула (0.4) верна для достаточно больших п.

Сразу заметим, что для /(х) = 1 (т. е. для равномерного распределения = формула (0.4) является частным случаем формулы (0.2) для с\ = . — сп = 1/п и ^ = Таким образом, разница между алгоритмами 0.1 и 0.2 с постоянными весами связана с выбором узлов - детерминированным или стохастическим. Отметим также, что и для «детерминированного» алгоритма 0.1 введение весовой функции типа / и связанного с ней набора узлов позволяет улучшать качество кубатурных формул (0.2).

Алгоритм 0.2 имеет следующие положительные свойства:

- возможность уменьшения трудоемкости алгоритма за счет, уда.'чного (согласованного с видом подынтегральной функции д) выбора весовой функции / (алгоритм выборки по важности) или преобразования исходного интеграла (выделение главной части) и весовой функции (методы математического ожидания и расщепления, выборка по группам и т.п.) - см. далее подразд. 0.5;

- веса имеют простой вид, а узлы реализуются согласно выбираемому вероятностному распределению с плотностью /;

- относительно слабая чувствительность к росту размерности I и к гладкости начальных данных (подынтегральной функции д и области X);

- возможность контроля затрат и точности вычислений.

Последнее свойство обусловлено тем, что затраты 5 алгоритма 0.2 можно подсчитать по простой формуле 5 = пЬ, где t - среднее время получения одного выборочного значения случайной величины С (это время, в свою очередь, связано со «сложностью» вычисления функции д и со средними затратами на реализацию одного выборочного значения вектора £). Далее, в силу центральной предельной теоремы (см., например, [10]) для достаточно больших п имеет место соотношение

При фиксированном уровне погрешности число случайных узлов п прямо пропорционально дисперсии а2 случайной величины и вместо я в качестве величины, отражающей затраты стандартного метода Монте-Карло, можно ввести число которое называется трудоемкостью алгоритма 0.2 [7-9]. Рассмотрение величины (0.7) вместо 5 является более удобным при оптимальном выборе весовой функции /, т. к. величина 51 в явном виде содержит вероятностную характеристику (дисперсию) случайной величины С, которая, в свою очередь, определяется через /. Неизвестное значение (0.5) можно приближенно вычислить по набору выборочных значений . [7-9]:

1 V 1 (у^У (ой а8)

Формула (0.6) отражает также и главный недостаток алгоритма 0.2 - относительно низкую (порядка 1/у/п) скорость сходимости погрешности к нулю при возрастании числа узлов п. К примеру, для / = 1 и д € С2(Х) простейшая формула прямоугольников имеет порядок погрешности 1/п2 (см., например, [4]). Это обуславливает использование алгоритма 0.2 только для достаточно больших размерностей I.

0.2. Дискретно-стохастические методы численного интегрирования. Формулы Бахвалова и теория сложности. Эффективными могут оказаться и смешанные, комбинированные процедуры численного интегрирования, сочетающие в себе элементы алгоритмов 0.1 и 0.2. Как правило, эти схемы содержат «детерминированную» составляющую, связанную с регулярной дискретизацией области X, а также «стохастическую» составляющую, связанную с применением метода Монте-Карло. Поэтому, вслед за А.В.Войтишеком [11], мы будем называть такие алгоритмы дискретно-стохастическими.

По-видимому, одна из первых численных схем подобного рода была представлена в работе Н. С. Бахвалова [12] (см. также [4] и подраздел 1.2.4 данной работы). Исходной областью X являлся ¿-мерный единичный куб (¿1, который разбивался на п равных кубов с вершинами в точках равномерной сетки. В каждом ^'-ом элементарном кубе выбирался узел кубатурной формулы (0.2) случайным образом (согласно равномерному распределению). Представленный алгоритм можно считать как кубатурной формулой (0.2) со случайными узлами (такой термин для подобных конструкций имеется, например, в [8]), так и предельным случаем выборки по группам в методе Монте-Карло [7-9]. Н. С. Бахвалов показал в [12], что его алгоритм является оптимальным (по скорости сходимости к нулю погрешности 5п при п —> со) в пространстве непрерывно дифференцируемых подынтегральных функций С1(Х). Для этого ему потребовалось получать оценки сверху и снизу для 5п.

Методология работы [12] явилась основой для интенсивного развития так называемой теории сложности (см. [13] и сопутствующие этой монографии работы). Эту теорию можно назвать «философией вычислительных алгоритмов». В ней изучается вопрос о том, каков максимальный порядок стремления к нулю погрешности 5й для

0.6)

0.7) данного класса вычислительных алгоритмов с количеством вычислительных операций п.

Проблема численного интегрирования (задача 0.1) является наиболее удобной и часто используемой иллюстрацией в теории сложности. В работах по теории сложности рассмотрены вопросы оптимальности кубатурных формул (0.2) для различных пространств В(Х) подынтегральных функций. При построении соответствующих нижних границ для 5п требуется строить конкретную численную схему типа (0.2). В некоторых (достаточно редких) случаях эти алгоритмы имеют вид, вполне пригодный для практических вычислений. Например, для В(Х) = С2(Х) в работе [12] Н. С. Бахвалов построил оптимальный алгоритм, в котором, в дополнение к алгоритму для д € С1{Х), кроме узла х^ выбирается точка х7, симметричная х^ относительно центра ?-го элементарного куба (см. подраздел 1.2.4 настоящей работы).

С точки зрения теории сложности алгоритм 0.2 решения задачи 0.1 является не слишком интересным, так как, в силу соотношения (0.6), имеет неулучшаемый порядок сходимости 1 /у/п. Поэтому в связи с задачей 0.1 в теории сложности распространено обращение к случаю использования так называемых квази-случайных узлов кубатур-ной формулы (0.2) [13]. Здесь теория кубатурных формул смыкается со специальным нетривиальным разделом теории чисел. Наиболее эффективный алгоритм построения квази-случайных узлов представлен в [7] (это ЛПГ-последовательность Соболя). Вопросы использования квази-случайных чисел в численном интегрировании в данной работе не рассматриваются.

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

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

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

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

Заключение

В работе получены следующие результаты.

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

• Разработан двусторонний геометрический метод Монте-Карло. Исследованы вопросы оптимизации этого метода для кусочно-постоянных мажорант и минорант подынтегральной функции.

• Исследована эффективность дискретно-стохастических состоятельных оценок метода Монте-Карло: взвешенной равномерной выборки и оценки с поправочным множителем. Получены верхние оценки дисперсий и оценены затраты соответствующих дискретно-стохастических численных схем.

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

• Проведен сравнительный анализ известных аппроксимационных базисов с точки зрения использования их в алгоритмах численного статистического моделирования. Показана целесообразность использования приближений Стренга-Фикса и Бернштейна в дискретно-стохастических численных схемах.

• Рассмотрены возможности применения траекторий спектральных (гауссовских и негауссовских) моделей случайных функций при тестировании численных алгоритмов интегрирования. Такой подход позволил добиться независимости тестирования, получить требуемые свойства подынтегральных функций (гладкость, «сложность» вычисления и др.), вывести аналитические выражения для средних погрешностей. Исследован вопрос о слабой сходимости используемых негауссовских численных моделей.

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

1. Владимиров B.C. Уравнения математической физики. М.: Наука, 1981.2| Березин И. С., Жидков Н.П. Методы вычислений. М.: Физматгиз, 1962.

2. Марчук Г. PI. Методы вычислительной математики. М.: Наука, 1980.

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

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

5. Соболев С. JL, Васкевич B.JI. Кубатурные формулы. Новосибирск: ИМ СО РАН, 1996.

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

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

8. Михайлов Г. А., Войтишек A.B. Численное статистическое моделирование. Методы Монте-Карло. М.: Издательский центр «Академия», 2006.

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

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

11. Войтишек A.B., Дятлова (Каблукова) Е.Г., Мезенцева (Булгакова) Т.Е. Геометрический метод Монте-Карло и его модификации // Материалы V международного семинара-совещания «Кубатурные формулы и их приложения». Красноярск: КГТУ, 2000. С. 46-54.

12. Voytishek А.V., Dyatlova (Kablukova) E.G., Mezentseva (Bnlgakova) Т.Е. Geometrical Monte Carlo method and it's modifications // Monte Carlo Methods and Applications. 2000. V. 6, № 2. P. 131-1Î39.

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

14. Войтишек A.B., Каблукова E.Г. Исследование адаптивных дискретно-стохастических алгоритмов численного интегрирования // Материалы VI международного семинара-совещания «Кубатурные формулы и их приложения». Уфа: ИМВЦ УНЦ, 2001. С. 46-52.

15. Kablukova E. G., Shvets V. V., Voytishek A. V., Golovko N. G. Function approximations as probabilistic densities // Proceedings of the International Conference on Computational Mathematics. Новосибирск: ИВМиМГ CO PAH, 2002. P. 211-215.

16. Каблукова E. Г., Булгакова Т.Е. О некоторых применениях численной стохастической системы функций // Материалы XLI Международной студенческой конференции «Студент и научно-технический прогресс». Математика. Новосибирск: НГУ, 2003. С. 118-119.

17. Voytishek А. V., Kablukova E.G. Usage of approximation functional basises in Monte Carlo methods // Russian Journal of Numerical Analysis and Mathematical Modelling. 2003. V. 18, jV* 6. P. 521-542.

18. Войтишек А. В., Каблукова E. Г., Булгакова Т. Е. Использование спектральных моделей случайных полей при исследовании алгоритмов численного интегрирования // Вычислительные технологии. 2004. Т. 9, специальный выпуск. С. 50-61.

19. Войтишек А. В., Каблукова E. Г., Герасимова О. С. Сравнение различных вариантов рандомизации метода последовательных приближений // Вычислительные технологии. 2006. Т. 11, специальный выпуск. С. 27-35.

20. Войтишек А. В., Каблукова Е. Г., Лощина Н. В. Исследование метода сложной симметризации // Там же. С. 52-53.

21. Войтишек А. В., Каблукова Е. Г. Исследование метода сложной симметризации // Труды 9-го Международного семинара-совещания «Кубатурные формулы и их приложения». Уфа: ИМВЦ УНЦ РАН, 2007. С. 61-75.

22. Бусыгин С. В., Войтишек А. В., Каблукова Е.Г., Ефремов А.И. Дискретно-стохастические состоятельные оценки метода Монте-Карло // Журнал вычислительной математики и математической физики. 2008. Т. 48, № 9. С. 1543-1555.

23. Каблукова Е. Г. Исследование адаптивных алгоритмов численного интегрирования // Материалы конференции молодых ученых. Новосибирск: ИВМиМГ СО РАН, 2001. С. 94-103.

24. Каблукова Е. Г. Двусторонний геометрический метод Монте-Карло // Материалы конференции молодых ученых. Новосибирск: ИВМиМГ СО РАН, 2002. С. 76-81.

25. Каблукова Е. Г. Исследование методов численного интегрирования с оптимальной скоростью сходимости // Материалы XLII Международной студенческой конференции «Студент и научно-технический прогресс» . Математика. Новосибирск: НГУ, 2004. С. 126.

26. Каблукова Е. Г. Исследование методов численного интегрирования с оптимальной скоростью сходимости // Труды конференции молодых ученых. Новосибирск: ИВМиМГ СО РАН, 2004. С. 67-77.

27. Kablukova Е. G. Investigation of methods of numerical integration with optimal convergence speed // Monte Carlo Methods and Applications. 2005. V. 11, № 4. P. 397406.

28. Каблукова E. Г., Герасимова О. С. Исследование математической модели переноса частиц с анизотропным рассеянием // Материалы VIII международного семинара-совещания «Кубатурные формулы и их приложения». Улан-Удэ: ВСГТУ, 2005. С. 49-52.

29. Лощина Н. В., Каблукова Е. Г. Асимптотика метода сложной симметризации // Материалы XLV Международной студенческой конференции «Студент и научно-технический прогресс». Математика. Новосибирск: НГУ, 2007. С. 204-205.

30. Ефремов А. И., Каблукова Е. Г. Дискретно-стохастический метод взвешенной равномерно выборки // Там же. С. 202-203.

31. Бусыгин C.B., Каблукова Е. Г. Дискретно-стохастический метод Монте-Карло с поправочным множителем // Там же. С. 201-202.

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

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

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

35. Handscomb D.C. Remarks on a Monte Carlo integration method // Numerical mathematics. 1964. V. 6, № 4. P. 261-268.

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

37. Пригарин С. M. Введение в численное моделирование случайных процессов и полей. Части I, И. Новосибирск: НГУ, 1999.

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

39. Вентцель Е. С. Теория вероятностей. М.: Наука, 1962.

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

41. Бахвалов Н. С., Лапин А. В., Чижонков Е. В. Численные методы в задачах и упражнениях. М.: Высшая школа, 2000.

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

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

44. Войтишек A.B., Мясников А.П., Санеев Л.Э. Использование алгоритмов численного моделирования порядковых статистик // Журнал вычислительной математики и математической физики. 2008. Т. 48, № 12.

45. Фихтенгольц Г.М. Курс дифференциального и интегрального исчисления. Т. 1-3. М.: ОГИЗ, 1948.

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

47. Боровков A.A. Математическая статистика. Оценка параметров, проверка гипотез. М.: Наука, 1984.

48. Горбачева Н.Б., Соболь И.М., Трикузов А. И. О множителях, уменьшающих дисперсию при вычислении интегралов методов Монте-Карло // Журнал вычислительной математики и математической физики. 2001. Т. 41, № 9. С. 1310-1314.

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

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

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

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