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

АКАДЕМИЯ НАУК РОССИИ СИБИРСКОЕ ОТДЕЛЕНИЕ ВЫЧИСЛИТЕЛЬНЫЙ ЦЕНТР

На правах рукописи

Мешкова Анна Федоровна

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

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

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

НОВОСИБИРСК-1994

\

Работа выполнена в Новосибирском государственном

университете

Научный руководитель - член-корреспондент РАН

Г.А. Михайлов

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

наук, профессор Ю.Н. Григорьев; кандидат физико-математических наук

М.Ю. Плотников

Ведущая организация - Институт теоретической и прикладной механики СО РАН

Защита состоится 1994 г. в ...... час.

/

на заседании специализированного совета К 002.10.01 по присуждению ученой степени кандидата физико-математических наук в Вычислительном центре СО РАН по адресу: 630090, Новосибирск 90, просп. Академика Лаврентьева, 6.

С диссертацией можно ознакомиться в читальном зале библиотеки ВИ СО РАН (пр. Академика Лаврентьева, 6).

Автореферат разослан "¿Л..." 1997г.

Ученый секретарь специализированного совета д.ф.-м.н.

Ю.И. Кузнецов.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ.

АКТУАЛЬНОСТЬ ТЕМЫ. Исследование ряда задач математической физики приводит к необходимости решения эллиптических уравнений. Разработано множество простых и эффективных численных методов решения таких уравнений. Однако, необходимо отметить, что в случае пространств с большим числом измерений п, данные методы обладают высокой трудоемкостью и требуют больших объемов памяти запоминающего устройства ЭВМ. Использование алгоритмов метода Монте-Карло позволяет значительно снизить трудоемкость решения. Другими преимуществами метода являются также его простота и физическая наглядность, возможность решения многомерных задач со сложной геометрией, получения оценок отдельных функционалов от решения без запоминания значения решения во всей области, возможность оценок производных по координатам и по параметрам. Простое распараллеливание метода делает его особенно эффективным при использовании многопроцессорных ЭВМ. Одно из направлений повышения эффективности решения эллиптических уравнений методом Монте-Карло связано с использованием понятия трудоемкости, то есть времени ЭВМ или среднего числа операций, которое необходимо для достижения заданной погрешности решения 6. На основе использования этого понятия в настоящее время получен ряд оптимизирующих соотношений между объемом случайной выборки и шагом сетки при решении многомерных интегральных и дифференциальных уравнений различными алгоритмами метода Монте-Карло.

ЦЕЛЬЮ данной диссертационной работы является уменьшение трудоемкости алгоритмов метода Монте-Карло для глобальной оценки решения краевой задачи Дирихле для п- мерного уравнения Гельмгольца, а также обоснование несмещенности оценки "блуждания по сферам и шарам" и ограниченности дисперсии для решения уравнения Гельмгольца с переменным параметром, яллиптических систем специального вида и одного интегро-дифференциального

уравнения.

НАУЧНАЯ НОВИЗНА И ПРАКТИЧЕСКАЯ ЦЕННОСТЬ РАБОТЫ. В метриках пространств Ь? и С для глобальной оценки решения п- мерного уравнения Гельмгольца с использованием алгоритма "блуждания по сферам" построены соотношения между числом траекторий N, шагом сетки Л и величиной е, характеризующей смещенность оценки, оптимальные в смысле уменьшения времени ЭВМ для достижения заданной точности.

Долучены оценки дисперсии и трудоемкости алгоритмов "блуждания по решетке". Выведены аналогичные соотношения между И, к и е в метрике пространства Ьч для "прямого" и "сопряженного" методов.

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

Для решения уравнения Гельмгольца с переменным параметром, а также эллиптических систем специального вида и одного интегро-дифференциального уравнения получены условия несмещенности оценок "блуждания по сферам и шарам", а также условия ограниченности дисперсии.

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

ПУБЛИКАЦИИ И АПРОБАЦИИ РАБОТЫ. Все результаты диссертации по мере их получения докладывались на объединенных семинарах отдела Статистического Моделирования в физике ВЦ СО РАН и кафедры Вычислительной математики Новосибирского Государственного Университета. Также результаты докладывались на международной конференции студентов и аспирантов в НГУ (Новосибирск, 1992 г.).

Основные результаты диссертации опубликованы в работах [1] - [3].

СТРУКТУРА И ОБЪЕМ РАБОТЫ. Диссертация состоит из введения, трёх глав, содежащих девять параграфов, заключения и списка литературы из 27 наименований. Объем работы - 57 машинописных страниц, включая 12 таблиц.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ.

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

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

В §1.1 формулируются основные условия задачи. Рассматривается задача Дирихле для уравнения Гельмгольца с постоянным параметром

Аи + си = -д, и|г = V".

в области £) € Д" с границей Г, причем с < с*, где —с*-первое собственное число оператора Лапласа для области I), г = (яь..,«„) € Предполагаются выполненными условия регулярности функций с, д, ф и границы Г, обеспечивающие существование и единственность решения задачи а также его вероятностное и интегральное представление с помощью шаровой функции Грина. Далее приводится описание процесса "блуждания по сферам" с оценкой средней длины траектории.

В §1.2 в явном виде выписывается оценка решения и исследуются условия ограниченности дисперсии. Также здесь получена оценка трудоемкости метода для оценки решения в одной точке. Она определяется величиной:

где п- число измерений, 8- заданная погрешность решения. Далее решается задача минимизации трудоемкости-и определяются оптимальные значения величин И, N и е. Приводятся результаты тестовых расчетов для задачи в пространстве с большим числом измерений (п=4 и п=10), подтверждающие полученные оценки трудоемкости и условия ограниченности дисперсии.

В §1.3 исследуется трудоемкость алгоритма "блуждания по сферам" для глобальной оценки решения в метриках пространств Li и С. Для снижения трудоемкости в метрике пространства С используется метод зависимых испытаний. Получены следующие оценки трудоемкости. В метрике пространства Li'-

в метрике пространства С:

S2 ж п2|1п<5гг"н|<ГЛ-2.

Для минимизации трудоемкости в Li решается следующая задача:

5] = Nt\h~nEl -» min, ^ + CJi2m + blc2 = 6\ N,h,e N

При ее решении получены соответствующие оптимальные значения:

, ¿у/т

с =-j-

[|lni|bi(2m+n)]»

( П \

k ~ \(2m + п)С\) 'Sn

_ d\{2m + п) 2т6*

_ ¿|di(2m + n)[(2rra + n)Cin)^ |1пД| 1 ~ 2т '

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

Вторая глава посвящена анализу трудоемкости методов Монте-Карло для решения n-мерного уравнения Гельмгольца с постоянным параметром с использованием оценки "блуждания по решетке".

В §2.1 изложен способ замены исходной дифференциальной задачи разностным аналогом. Описан алгоритм "блуждания по решетке" для решения разностных уравнений, а также сформулированы два способа построения оценок решения с использованием данного алгоритма: "прямой метод" и "сопряженный метод".

В §2.2 проводится оценка дисперсий данных методов. Доказывается, что дисперсия "прямого метода" не зависит от шага сетки Л, а дисперсия "сопряженного метода" имеет порядок величины 0(/1-(Л-2)).

В §2.3 проводится анализ трудоемкости методов для глобальной оценки решения в метрике пространства Получена следующая оценка трудоемкости для обоих методов:

5 х ¿-"/2-2

Для минимизации трудоемкости построена соответствующая задача на условный минимум. При ее решении получены следующие оптимальные значения для "прямого-метода":

и > п с1

= + ^ ¿1(4 +п) _ 6_ф

= + * ¿1^(4 + п) 5_2.

для "сопряженного метода" также выведены аналогичные соотношения. Далее проводится сравнительный анализ трудоемкости алгоритмов "блуждания по решетке" и "блуждания по сферам". Рассматриваются результаты решения тестовой задачи "прямым" и "сопряженным" методами.

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

В §3.1 описывается алгоритм "блуждания по сферам и шарам", основанный на интегральном представлении решения с помощью шаровой функции Грина. Используемая оценка реализует вероятностное представление ряда Неймана для полученного интегрального уравнения. Исследуются условия сходимости данного ряда и конечности дисперсии оценки. Доказаны следующие утверждения: Лемма 1. Если выполняются условия

Со > |с(г)| И С0 < 2пС*/Од,

где с*- минимальное собственное число оператора Лапласа, ап- первый положительный корень функции Бесселя •/(п_2)/2(ж), то ряд Неймана для данного интегрального уравнения сходится.

Лемма 2. Если выполняются условия

^ I / М с» ^ ,1 \ ■ /2п (л

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

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

В §3.2 новый алгоритм используется для получения оценок производных от решения по координатам и параметрических производных в случае постоянного параметра с.

В §3.3 алгоритм "блуждания по сферам и шарам" используется для решения эллиптических систем вида:

т

Д";(г) + сч(г)и;(г) = ~5;(г)1 "¡(г)!г = ФМ, » = 1, ..,т, ¿=1

а также для решения интегро-дифференциального уравнения:

Ди(г, А) = - I и(г, А')с(г, А, \')<1\' - д(г, А), и(г, А)|г = Ф(г, А), л

Для данных уравнений построены соответствующие скалярные и векторные оценки. Утверждения лемм 1-2 остаются справедливыми с заменой условия с(г) < Со на следующие условия:

т ■ |с;у(г)| < с0, г, ] = 1, ...т, для скалярной оценки решения системы;

для оценки решения интегро-дифференциального уравнения, здесь р(г, А, Л1)- некоторая переходная плотность.

Перечислим основные результаты диссертационной работы.

1. Получены оценки погрешности и трудоемкости алгоритма "блуждания по сферам" для глобальной оценки решения гг-мерного уравнения Гельмгольца в метриках пространств Ьо и С. Определены оптимальные соотношения величин к,

2. Получены оценки дисперсий, погрешностей и трудоемкости алгоритмов "блуждания по решетке" для решения разностных уравнений. Определены оптимальные соотношения величин Н, N и е в метрике пространства для "прямого" и "сопряженного" методов.

3. Лля решения уравнения Гельмгольца и эллиптических систем с переменными параметрами получены следующие результаты.

3.1 Для решения уравнения Гельмгольца получены условия несмещенности оценки "блуждания по сферам и шарам" и условия ограниченности дисперсии.

3.2 Разработаны скалярные и векторные алгоритмы решения эллиптических систем специального вида и одного

ЗАКЛЮЧЕНИЕ.

N И £.

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

• Автор выражает искреннюю благодарность своему научному руководителю чл.-корр. РАН Г.А. Михайлову за постоянное внимание и руководство работой.

Основные результаты диссертации опубликованы в работах:

1. Михайлов Г.А., Чешкова А.Ф. Решение задачи Дирихле для эллиптических систем с переменными параметрами методом Монте-Карло.- //Доклады РАН.- 1994, Т.336, №6, с.737-740.

2. Чешкова А.Ф. Глобальные алгоритмы метода Монте-Карло для решения разностных уравнений.- //Труды ВП СО РАН. Выч. математика, 1.- Новосибирск, 1993, с.75-84.

3. Cheshkova A.F. "Walk on spheres" algorithms for solving Helholtz equation in the n-dimensional Euclidean space.- //Bull. Nov. Сотр. Center,- Num. Anal.,- 4(1993), p.7-18.