Решение эллиптических краевых задач методом Монте-Карло

Макаров, Роман Николаевич

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

Макаров, Роман Николаевич АВТОР

кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ

Новосибирск МЕСТО ЗАЩИТЫ

2000 ГОД ЗАЩИТЫ

01.01.07 КОД ВАК РФ

Диссертация по математике на тему «Решение эллиптических краевых задач методом Монте-Карло»

Автореферат диссертации на тему "Решение эллиптических краевых задач методом Монте-Карло"

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ОД

На правах ■¿уйЬМнсдТ УДК 519. 245:519. 676

Макаров Роман Николаевич

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

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

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

Новосибирск 2000

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

НАУЧНЫЙ РУКОВОДИТЕЛЬ Михайлов

Геннадий Алексеевич

ОФИЦИАЛЬНЫЕ ОППОНЕНТЫ:

Григорьев

Юрий Николаевич

Плотников Михаил Юрьевич Ведущая организация

— член-корреспондент РАН, профессор, Институт вычислительной математики и математической геофизики СО РАН

— доктор физико-математических наук, Институт вычислительных технологий СО РАН

— кандидат физико-математических наук, Институт теплофизики СО РАН

— Институт теоретической и прикладной механики СО РАН

Защита состоится ........" ............ 2000 г. в .........час. на заседании спе-

циализированного совета К 002.10.01 по присуждению ученой степени кандидата физико-математических наук в Институте вычислительной математики и математической геофизики СО РАН

по адресу: 630090, Новосибирск 90, просп. Академика Лаврентьева, 6.

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

Автореферат разослан "..........." ...........;.............. 2000 г.

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

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

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

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

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

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

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

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

Основные цели работы.

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

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

• Численная проверка возможности параметрического продолжения алгоритмов решения рассматриваемых краевых задач за пределы области ограничения параметров.

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

оценки первых собственных чисел операторов А и Д + с на классе функций, удовлетворяющих второму или третьему краевым условиям. Все результаты диссертации подтверждены численными расчетами. Практическая значимость работы определяется возможностью ее применения при численном решении рассматриваемых задач.

Апробация работы. Результаты, изложенные в диссертации, докладывались и обсуждались на семинарах Отдела статистического моделирования в физике ВЦ СО РАН, на конференциях молодых учёных ВЦ СО РАН (1995-2000 гг.), на 3-ем международном семинаре "Математические методы в стохастическом моделировании и планировании эксперимента" в г. С.-Петербурге (1998 г.). •

Публикации. Основные результаты опубликованы в 8 работах, список которых помещен в конце автореферата.

Структура и объём работы. Диссертация состоит из введения, четырех глав, содержащих 15 разделов, заключения, списка литературы из 48 наименований. Объём работы - 101 машинописная страница, включая 16 таблиц и 1 рисунок.

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

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

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

В параграфе 1.1 вводится основная краевая задача в области ОсЛ"

!Ди — си = — д, гбй,

Он

аи + р— — <р, г е дБ;

даются основные определения, связанные с алгоритмами "блуждания по сферам".

В параграфе 1.2 выводятся формулы разностной аппроксимации второго и третьего краевых условий, и, на основе такой аппроксимации и формулы Грина для шара, совершается переход от дифференциальной задачи к специальному локальному интегральному уравнению 2-го рода щ — Ки\ + /. При выполнении одного из условий: а(г) > ао > 0 или с > 0, доказывается сходимость по норме ряда Неймана для оператора К.

В параграфе 1.3 формулируется определение процесса "блуждания по сферам" с отражением от границы. Рекуррентный вид процесса {г*;}¿-0,1,...,£,, где Ь - номер последнего состояния (момент обрыва траектории), следующий:

{гк + Шк<1{гк), Гк е Б \ Г£, (переход на сферу) г к — НЦЬк), г к € Г£, (отражение от границы)

где к < {о^А:} - последовательность независимых п-мерных

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

р(г) = 1 — J р(г,г')(1г'

1 -д(г), геГЕ,

(<УН0/2)У /?(г) + а(г)еР

где *(со,а) = г/м,и , г ?(г) =

/?(г) + а(г)ег + а(г)Л' й = ¿(г), ег = |6 - г|, 0 < с0 < с.

Для разных способов моделирования получены оценки среднего числа отражений Ей и средней длины траектории ЕЬ\

• блуждания с обрывом в области И: пусть с > 0, со > О, е ~ к2 и > 0, то Ей = 0{ 1/к), ЕЬ = 0(п\\пк\/к) при к -> 0, п —> со.

• блуждания с обрывом в Ге: пусть гп1п(а(Ь)) = «о > 0, со = О,

Ье г

£ ~ /г, то ЕЙ — 0(1/1г), и ЕЬ = 0(п/к) при А ->■ 0 и ?г оо.

• блуждания с обрывом в е-окрестности участка границы Г2: пусть 5 ~ К1, о|г2 = 1, /3|г2 = О, П2 > 0, то ЕЯ = 0{ 1/Л), Е£ = <3(п| 1п Л|/Л) при /г -4 0, п ос.

Здесь рассматриваются вспомогательные задачи: Дг^х — сгох = 0, гу^г = 1,

АШ2 = 0, то^п = 0, «;2|г2 = 1;

_ (Ь) ^ дю2 (Ь)

и величины К\ = шш . >0, Д2 = шш -тгттг-г" > 0.

Ьег ~ Ьег, дг{Ь)

В параграфе 1.4 строятся новые оценки £ метода Монте-Карло решений второй и третьей краевых задач. Запишем "оценку по столкновениям" £(г) для \/г = то £ И в рекуррентном виде:

8(с, 1 - р(г,)'

9(г«) 1 - р(п)'

ъ е D\г£,

(1)

г,- € IV

С вероятностью 1 — вычисляется оценка в следующей

точке цепи и к ней прибавляется оценка свободного элемента. С дополнительной вероятностью р(гг) происходит обрыв цепи.

Доказываются теоремы о конечности математических ожиданий и дисперсий как несмещенной оценки £Г, так и смещенной оценки получаемой заменой в основной оценке функции погрешности нулем. Доказывается теорема о порядке погрешности в Ь^,:

Н*-Ееь||<С4Л.

В этом же параграфе изучается асимптотический порядок трудоемкости 5Е)П, то есть числа арифметических операций, необходимого для получения оценки решения в точке го с заданной ошибкой е. Заметим, что 5£]П ~ ЛГеф£1ПС„, где ДГ£ - число моделируемых траекторий, = ЕЬ - число переходов в цепи до момента

обрыва, С„ хп- число арифметических операций, необходимое для моделирования одного перехода в п-мерном пространстве.

В параграфе 1.5 проводится численное исследование возможности продолжения оценки на случай решения второй и третьей краевых задач для уравнения Ду + си = —д с положительным с.

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

В параграфе 2.1 формулируется разностная задача, аппроксимирующая основную краевую задачу:

uh = Auh + jh,

или, более подробно,

з=1

где — 1,..., М - номера узлов сетки -О^иГ^, р^ > 0, ^ р^ — 1.

з=1

Здесь р^ = —, если г - внутренний узел, а ] - соседний с ним; для г-го граничного узла pij = 1, если з - соседний узел, лежащий на прямой, задаваемой нормалью в граничном узле г, и р^ = 0 в остальных случаях;

Яг =

с?Л2\-1

( с;--1 „ +

П е ГЛ;

2n + c^/i2'

П е £>Л;

/г

# +

При выполнении условий:

с(г) > с0 > 0, а(г) > а0 > О,

У,-, г,- € ГЛ.

доказывается оценка р(Л) < 1 для спектрального радиуса матрицы А.

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

(2)

j=o \к=о /

где ¿о,. ■ - номера узлов случайной траектории цепи Маркова с начальным распределением щ = 5го, вероятностями перехода

Pij и вероятностями обрыва р,- < 1 — веса Qi = —-——; L -

1 Pi

случайный номер, на котором произошел обрыв.

В параграфе 2.2 строятся глобальные оценки решения задачи. Применительно к таким задачам сравниваются два подхода к моделированию цепи. Для различных начальных распределений и различных способов обрыва пепи оценивается среднее число шагов. Для глобальных оценок ü(r), которые получаются линейным восполнением оценок решения в узлах равномерной сетки, решается задача минимизации трудоемкости в смысле необходимого числа операций для достижения требуемой погрешности 5 в оценке решения в метрике пространства Li- Например, задача минимизации трудоемкости для метода с обрывом на границе имеет вид:

S = NtEL min, —7——г -f Сlh2 = б2.

Третья глава посвящена построению оценок первого собственного числа второй и третьей краевых задач.

В параграфе 3.1 для произвольного интегрального уравнения 2-го рода, рассматриваемого в Loo{X), формулируется задача о вычислении параметрических производных

Формулируются необходимые условия существования решения соответствующей векторной системы интегральных уравнений и "оценки по столкновениям", такой что

Е^г)(А) = ^(х,Л) и Е[£^(А)]2 < 4-оо, ¿=1

В параграфе 3.2 исследуются оценки метода Монте-Карло параметрических производных от решений второй и третьей краевых задач для уравнения Д + Аи = —д, где Л = -с. Доказываются теоремы о конечности математических ожиданий и дисперсий как несмещенной оценки так и смещенной оценки по-

лучаемой заменой в основной оценке функции погрешности нулем. Доказывается теорема о порядке погрешности в Х«,:

циМ _ Ее[т)|| < СтЬ, т — 1,2,...

В параграфе 3.3 выписывается конкретный вид оценок На основе соотношения

^(те~1}Ы - , у ' с п

-;—г;—:— —> с + с, Уг0 е V,

и(т)(г0)

изучается метод Монте-Карло для оценивания с*. Здесь -с* -первое собственное число оператора Лапласа для области В на классе функций, удовлетворяющих краевому условию

„ди аи + 0-- = 0. ос

В параграфе 3.4 строятся формулы оценивания первого собственного числа для оператора Д -+- с{г). С этой целью выписываются оценки параметрических производных

^ц(г.Л) .

-^Г-, г = 1,..., т

решения краевой задачи для уравнения (Д+с)и-+Ли = 0, и, далее, используется то обстоятельство, что вычисление параметрических производных реализует итерации резольвентного оператора

[(Д + с) + А]"1

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

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

В параграфе 4.1 рассматривается краевая задача для уравнения

Аи — си = —аип — д

со вторым граничным условием. С целью решения такого рода задач, исследуется новый тип случайного блуждания в области, называемый как процесс "блуждания по сферам и шарам" с ветвлением и отражением от границы. Для такого процесса при выполнении условия па/с < 1 доказывается конечность среднего числа ветвлений, и определяется асимптотический порядок средней длины траектории. При выполнении условия ||д||/с < 1 для полученной "оценки по поглощениям" доказывается конечность её математического ожидания, дисперсии и определяется порядок аппроксимации.

В параграфе 4.2, на основе метода "зависимых испытаний" для оценки решения уравнения Пуассона в двух точках по одним и тем же выборочным траекториям, строятся интегральные соотношения для первых частных производных уравнения Ди — —/(и). На основе таких соотношений могут быть построены оценки частных производных от решений различных краевых задач как в линейном, так и в нелинейном случае. В качестве основного примера рассматривается нелинейная задача Дирихле

Ди -)- ип — 0, щг = ф.

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

В параграфе 4.3 на основе формулы Грина для шара выписываются интегральные соотношения на вторые частные производные u".Xj, от решения уравнения Пуассона., которые могут быть применены к различным краевым задачам. Основные оценки параграфа выписаны применительно к нелинейной задаче Дирихле, записанной выше.

В параграфе 4.4 исследуется задача об параметрическом продолжении оценки £(с) решения задачи

Аис -f и" = 0, ис|Г = сф,

по параметру с > 0, когда параметр приближается к критическому значению. Метод исследования заключается в одновременном оценивании решения ис и значения лапласиана решения Аис на одних и тех же траекториях, а затем в последующей проверке выполнения, в выбранных точках, уравнения Дис + и" = 0, куда вместо ис и Дис подставляются соответствующие оценки.

ЗАКЛЮЧЕНИЕ

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

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

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

3. Построены оценки метода Монте-Карло для параметрических производных решений рассматриваемых краевых задач.

4. Разработаны алгоритмы вычисления первого собственного числа с* для операторов Д и Д + с(г) в области D на классе функций, удовлетворяющих второму или третьему краевому условию.

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

6. Разработаны алгоритмы метода Монте-Карло для вычисления вторых частных производных от решений краевых задач для оператора Лапласа.

7. Осуществлено численное исследование возможности параметрического продолжения оценки решения нелинейной задачи Дирихле.

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

СПИСОК РАБОТ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Макаров Р.Н. Исследования оценок метода Монте-Карло для решения нелинейного уравнения Гельмгольца// Труды Вычислительного центра СО РАН. Серия: Вычислительная математика. - 1996. - Вып. 4. - С.74-82.

2. Makarov R.N. Monte Carlo methods for solving boundary value problems of second and third kinds// Russ. J. Numer. Anal. Math. Modelling. - 1998. - Vol. 13. - №2. - pp. 117-131.

3. Makarov R.N. The Monte Carlo methods for solving many-dimensional boundary value problems of second and third kinds// Proc. of the Third St.Petersburg Workshop on Simulation. - St.Petersburg University Publishing House, 1998. -pp. 95-100.

4. Makarov R.N. Solving boundary value problems for nonlinear elliptic equations by Monte Carlo methods,// Russ. J. Numer. Anal. Math. Modelling. - 1999. - Vol. 14. - №5. - pp. 453-467.

5. Михайлов Г.А., Макаров Р.Н. Решение краевых задач второго и третьего рода методом Монте-Карло// Сибирский математический журнал. - 1997. - Т. 38. - №3. - С.603-614.

6. Михайлов Г.А., Макаров Р.Н. Решение краевых задач методом "блуждания по сферам" с отражением от границы// Доклады РАН. - 1997. - Т. 353. - №6. - С.720-722.

7. Михайлов Г.А., Макаров Р.Н. Параметрическое дифференцирование и оценки собственных чисел методом Монте-Карло// Сибирский математический журнал. - 1998. - Т. 39. - №4. - С.931-941.

8. Михайлов Г.А., Макаров Р.Н. Оценки свободных чисел оператора Д + с(г) путем вычисления параметрических производных методом Монте-Карло// Доклады РАН. - 1998. - Т. 362. - №5. - С.598-601.

Содержание диссертации автор исследовательской работы: кандидата физико-математических наук, Макаров, Роман Николаевич

Введение

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

1.1. Основная задача и определения

1.2. Вывод интегрально-разностного уравнения

1.3. Случайный процесс "блуждания по сферам" с отражением от границы.

1.4. Оценки решений второй и третьей краевых задач, для уравнения А и — си = —д методом Монте-Карло.

1.5. Продолжение оценок на случай уравнения А и + си — —д

Глава 2. Глобальные алгоритмы решений второй и третьей краевых задач

2.1. Случайные блуждания по решетке

2.2. Глобальные алгоритмы метода Монте-Карло и задача минимизации трудоемкости.

Глава 3. Оценки собственных чисел для вторых и третьих краевых задач

3.1. Оценки параметрических производных от решений интегральных уравнений 2-го рода.

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

3.3. Вычисление собственных значений

3.4. Оценка первого собственного числа для оператора Д + с(г)

Глава 4. Решение краевых задач для нелинейных эллиптических уравнений

4.1. Решение второй краевой задачи для нелинейного уравнения

4.2. Оценки частных производных от решений краевых задач

4.3. Оценки вторых частных производных от решений краевых задач.

4.4. Параметрическое продолжение оценки решения нелинейной задачи Дирихле.

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

Методы Монте-Карло, ставшие классическими в задачах теории переноса [12, 32, 38], в последнее время получили интенсивное развитие в области численного решения разнообразных задач математической физики. Как известно, основными преимуществами метода являются его простота и физическая наглядность, возможность решения многомерной задачи со сложной геометрией и оценивания отдельных функционалов от решения без запоминания значений решения во всей области, одновременное оценивание вероятностной погрешности оценки решения и простое распараллеливание метода. Кроме того, использование весовых модификаций позволяет вычислять кратные параметрические производные и, на этой основе, собственные значения краевых задач. Следовательно, важной задачей является расширение области применения алгоритмов метода Монте-Карло, особенно на случай нелинейных краевых задач. Численное решение таких уравнений обычно связано со значительными трудностями.

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

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

Подход II включает методы, основанные на использовании не локальных, как в подходе I, а глобальных интегральных уравнений. Это означает, что рассматривается интегральное уравнение либо на границе, либо по области, либо одновременно по области и границе, причем уравнение может быть записано как на само решение исходной задачи, так и на некоторую вспомогательную функцию. Последний случай реализуется, например, при построении случайного блуждания по границе на основе граничных интегральных уравнений теории потенциала [37].

Настоящая диссертация посвящена построению, обоснованию и применению методов Монте-Карло в рамках первого подхода с целью приближенного решения второй и третьей краевых задач для некоторых линейных и нелинейных эллиптических уравнений вида: —Ли = f(u) + р, а также для приближенного вычисления первых собственных чисел рассматриваемых линейных эллиптических краевых задач. Здесь используется модификация винеровского процесса, называемая иногда процессом "блуждания по сферам" или "сферическим процессом."

Впервые алгоритм "блуждания по сферам" был предложен Дж. Брауном [3] для приближенного решения задачи Дирихле для уравнения Лапласа. Позднее строгое обоснование алгоритма "блужданий по сферам" было дано в [48], где изучался также вопрос об эффективности такого метода. Алгоритм "блуждания по сферам" основан на моделировании точек последовательного выхода винеровского процесса из максимальных сфер, целиком лежащих в рассматриваемой области. В работах [7, 9, 13, 37] для широкого класса границ Г была получена логарифмическая оценка для среднего числа переходов в цепи "блужданий по сферам" до момента попадания в е-окрестность границы:

Е£<Сг|1п(е)|. 5

Кроме того для больших значений п размерности пространства верна [48] линейная зависимость ЕЬ ~ п. Дальнейшее развитие алгоритмы "блужданий по сферам" получили в работах Михайлова Г.А. и Еле-пова Б.С. В работе [8] был предложен алгоритм для решения задачи Дирихле для уравнения Гемгольца, использующий вероятностное представление решения. Позднее в [9] был построен алгоритм для решения этой задачи, исходя из специального интегрального уравнения 2-го рода. В этой работа была впервые предложена схема, основанная на сведении исходной дифференциальной задачи к специальному интегральному уравнению с обобщенным ядром, что дало возможность использовать развитой аппарат методов Монте-Карло [12] для решения интегральных уравнений 2-го рода. Данный подход позволил разработать алгоритмы статистического моделирования для решения более общих уравнений и систем (см., например, [13, 30, 37, 43, 46, 47])

Таким образом, к настоящему моменту теория оценок метода Монте-Карло, использующих сферический процесс, хорошо развита. Но в основном эта теория нацелена на решение первой краевой задачи для разнообразных эллиптических уравнений и их систем. В настоящей диссертации изучаются методы решения второй и третьей краевых задач, на основе синтеза сферического процесса и конечно-разностной аппроксимации граничного условия. Ранее такие методы не были исследованы так широко, за исключением работы [15], где рассматривался метод решения смешанной краевой задачи для уравнения Пуассона. Среди других методов Монте-Карло решения второй и третьей краевых задач следует особо выделить алгоритмы блуждания по границе [37], реализованные в рамках второго подхода к решению краевых задач методами Монте-Карло. Не умаляя положительных свойств алгоритмов блуждания по границе, следует отметить, что алгоритмы блуждания внутри области, в частности сферический процесс, более просты в реализации и менее критичны к геометрии границы области. Кроме того, алгоритмы блуждания внутри области распространяются на случай переменных коэффициентов.

При определенных условиях алгоритмы блуждания внутри области распространяются на решение первой краевой задачи для уравнения с полиномиальной нелинейность Аи + ип = 0 [28]. При этом оценка решения краевой задачи строится на сферическом процессе с ветвлением [13, 28]. В настоящей диссертации предлагается модифицировать такой процесс для решения нелинейных задач со вторым и третьим краевым условием. При этом рассматривается не обрывающийся в окрестности границы ветвящийся процесс, а отражающийся внутрь области с вероятностью 1. Несмотря на то, что ветви траектории обрываются только внутри области, среднее число ветвлений мажорируется конечной величиной, не зависящей от параметров алгоритма.

Следует упомянуть еще об одном подходе к решению краевых задач, широко применяемом в практических расчетах в силу своей простоты и сравнительной универсальности. Речь идет о методе блуждания по решетке, которое может интерпретироваться как дискретный вариант подходов I, II. Этот подход прост в реализации, не требует большой памяти ЭВМ, но является сравнительно трудоемким из-за необходимости моделирования длинных случайных траекторий [30, 38]. Применительно к рассматриваемым задачам, в настоящей работе с целью построения глобальной оценки решения исследуются случайные блуждания по решетке с "отскоком" от границы. При этом приходится решать вопросы повышения эффективности метода, а именно решать задачу выбора оптимального распределения начальной точки траектории, и задачу выбора оптимальных параметров, минимизирующих трудоемкость метода, т.е. среднее число операций, необходимое для достижения заданной погрешности е глобальной оценки решения [44].

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

В настоящей работе, применительно к задаче оценивания первого собственного числа (—с*) операторов А и Д+с( г) на классе функций, удовлетворяющих второму или третьему краевому условию, рассматривается подход, основанный на вычислении параметрических производных решения. Известно [5], что вычисление параметрических производных от решения краевой задачи для уравнения Ьи + \и = О, реализует итерации резольвентного оператора (Ь + Л)-1 при однородных граничных условиях. Это дает возможность использовать для вычисления с* соотношение

Впервые в методах Монте-Карло подобная техника была использована в [25] для интегральных уравнений 2-го рода. На взгляд автора такой подход к вычислению с* является простым и экономичным в сравнении, например, с подходом работы [14], использующей метод поколений.

Далее следует краткое содержание диссертации по главам.

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

В параграфе 1.1 вводится основная краевая задача для эллиптического уравнения в области Б С Яп

Аи — си = —д, г 6 I), ди аи+(3— = (р, г € сШ; даются основные определения, связанные с алгоритмами "блуждания по сферам".

В параграфе 1.2 выводится разностная аппроксимация граничных условий второго и третьего типа, и, на основе такой аппроксимации и формулы Грина, совершается переход от дифференциальной задачи к специальному локальному интегральному уравнению 2-го рода щ = Кщ + /. При выполнении определенных условий, доказывается сходимость по норме ряда Неймана для оператора К.

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

В параграфе 1.4 строятся новые оценки £ метода Монте-Карло решений второй и третьей краевых задач для уравнения А и — си = —д. Доказываются теоремы о конечности математических ожиданий и дисперсий как несмещенной оценки £г, так и смещенной оценки £Г)/>, получаемой заменой в основной оценке функции погрешности нулем. Доказывается теорема о порядке погрешности в Ь^:

-ВД<С4Л.

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

В параграфе 1.5 проводится численное исследование возможности продолжения оценки на случай решения второй и третьей краевых задач для уравнения Аи + си = —д с положительным с.

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

Третья глава посвящена построению оценок первого собственного числа для второй и третьей краевых задач.

В параграфе 3.1 для произвольного интегрального уравнения 2-го рода, рассматриваемого в Ь^Х), формулируется задача о вычислении параметрических производных

Формулируются условия существования решения соответствующей векторной системы интегральных уравнений и "оценки по столкновениям", такой что

Е£«(А) = А) и Е[#(А)]2 < +ос, г = 1,.,т.

В параграфе 3.2 исследуются оценки метода Монте-Карло параметрических производных от решений второй и третьей краевых задач для уравнения А + Хи = —д, где А = —с. Доказываются теоремы о конечности математических ожиданий и дисперсий как несмещенной оценки так и смещенной оценки получаемой заменой в основной оценке функции погрешности нулем. Доказывается теорема о порядке погрешности в Ь^: гг т) " Е^т)|| < Ст/г, т = 1,2,.

В параграфе 3.3 выписывается конкретный вид оценок На основе соотношения г,) изучается метод Монте-Карло для оценивания с* по формуле

Сг-и I /-»

7 \ — С.

Е«<?(с)

Здесь (—с*) - первое собственное число оператора Лапласа для области И на классе функций, удовлетворяющих краевому условию пди аи + ^ д! =

В параграфе 3.4 строятся формулы оценивания первого собственного числа для оператора А + с(г). С этой целью выписываются оценки параметрических производных дги(г, А) г = 1,. ,т 11 решения краевой задачи для уравнения (Д + с)и + Ли = 0, и, далее, используется то обстоятельство, что вычисление параметрических производных реализует итерации резольвентного оператора

А + с) + А]"1 при однородных граничных условиях. Для построения оценок в данном параграфе реализуется так называемая цепь "блуждания по сферам и шарам". В связи с этим исследуются условия конечности длины траектории.

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

В параграфе 4.1 рассматривается краевая задача для уравнения

Аи — си = —аип — д со вторым граничным условием. С целью решения такого рода задач, исследуется новый тип случайного блуждания в области, называемый как процесс "блуждания по сферам и шарам" с ветвлением и отражением от границы. Для такого процесса доказывается конечность среднего числа ветвлений, и определяется асимптотический порядок средней длины траектории. Для полученной "оценки по поглощениям" доказывается конечность её математического ожидания, дисперсии и определяется порядок аппроксимации.

В параграфе 4.2, на основе метода "зависимых испытаний" для оценки решения уравнения Пуассона в двух точках по одним и тем же выборочным траекториям, строятся интегральные соотношения для первых частных производных уравнения А и = —/(и). Для такого уравнения могут быть построены оценки частных производных от решения различных краевых задач как в линейном, так и в нелинейном случае. В качестве основного примера рассматривается задача

Аи -\-ип = 0, г/|Г = ф.

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

В параграфе 4.3 на основе формулы Грина выписываются интегральные соотношения на вторые частные производные и"х.х , от решения уравнения Пуассона, которые могут быть применены к различным краевым задачам. Основные оценки параграфа выписаны применительно к нелинейной задаче Дирихле, записанной выше.

В параграфе 4.4 исследуется задача об параметрическом продолжении оценки £(с) решения задачи

Дгхс-}-и" = 0, ис|Г = сф} по параметру с > 0, когда параметр приближается к критическому значению. Метод исследования заключается в одновременном оценивании решения ис и значения лапласиана решения Аис на одних и тех же траекториях, а затем в последующей проверке выполнения, в выбранных точках, уравнения Аис -}- и™ = 0, куда вместо ис и Аис подставляются соответствующие оценки.

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

На защиту выносятся следующие основные результаты.

4. Разработаны алгоритмы вычисления первого собственного числа с* для операторов А и А + с(г) в области D на классе функций, удовлетворяющих второму или третьему краевому условию.

Результаты, изложенные в диссертации, докладывались и обсуждались на семинаре Отдела статистического моделирования в физике ИВМиМФ СО РАН, на конференциях молодых ученых ВЦ СО РАН (1995-1999 гг.), на 3-м международном семинаре по математическому моделированию в г. С.-Петербурге (1998 г.).

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

Заключение диссертации по теме "Вычислительная математика"

Заключение

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

4. Разработаны алгоритмы вычисления первого собственного числа с* для операторов ДиА + с(г)в области В на классе функций, удовлетворяющих второму или третьему краевому условию.

Список источников диссертации и автореферата по математике, кандидата физико-математических наук, Макаров, Роман Николаевич, Новосибирск

1. Анищенко A.M. Теоремы существования и метод последовательных приближения для некоторых нелинейных задач// Изв. вузов. Математика. - 1971. - №5. - С. 56-64.

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

3. Браун Дж. Методы Монте-Карло// Современная математика для инженеров. М.: Изд-во иностр. лит., 1959. - С.275-301.

4. Гилбарг Д., Трудингер М. Эллиптические дифференциальные уравнения с частными производными второго порядка. М. Наука, 1989, - 464 с.

5. Данфорд Н., Шварц Дж. Т. Линейные операторы (общая теория).- М.: Изд-во иностр. лит., 1962.

6. Дядъкин И.Г., Стариков В.Н. Об одной возможности экономии машинного времени при решении уравнения Лапласа методом Монте-Карло// Журн. вычисл. матем. и матем. физики. 1965.- №5. С.936-938.

7. Елепов Б.С., Кронберг A.A., Михайлов Г.А., Сабелъфелъд К.К., Решение краевых задач методом Монте-Карло. Новосибирск: Наука, 1980.

8. Елепов Б.С., Михайлов Г.А. О решении задачи Дирихле для уравнения А и + си = —д моделированием "блужданий по сферам"// Журн. вычисл. матем. и матем. физики. 1969. - №3. -С.647-654.

9. Елепов B.C., Михайлов Г.А. Алгоритмы "блуждания по сферам" для уравнения А и — си = —д// Доклады АН СССР. 1973. - Т. 212. - №1. С.15-18.

10. Елепов Б.С., Михайлов Г.А. К теории оценок метода Монте-Карло, связанных с "блужданием по сферам"// Сибирский математический журнал. 1995. - Т. 36. - №3. С.544-550.

11. Ермаков С.М. Об аналоге схемы Неймана Улама в нелинейном случае// Журн. вычисл. матем. и матем. физ. - 1973. - Т. 13. -№3. - С.564-573.

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

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

14. Каштанов Ю.Н., Метод поколений для оценки первого собственного значения задачи Неймана// Журн. вычисл. матем. и матем. физ. 1997. - Т. 37. - №9. - С.1105-1111.

15. Кронберг A.A. Об алгоритмах статистического моделирования решения краевых задач эллиптического типа // Журн. вычисл. матем. и матем. физики. 1984. - Т. 24. - №10. - С. 1531-1537.

16. Курант Р. Уравнения с частными производными. М.: Мир, 1964, - 830 с.

17. Макаров Р.Н. Исследования оценок метода Монте-Карло для решения нелинейного уравнения Гельмгольца// Труды Вычислительного центра СО РАН. Серия: Вычислительная математика. 1996. - Вып. 4. - С.74-82.

18. Makarov R.N. Monte Carlo methods for solving boundary value problems of second and third kinds// Russ. J. Numer. Anal. Math. Modelling. 1998. - Vol. 13. - Ж. - pp. 117-131.

19. Makarov R.N. The Monte Carlo methods for solving many-dimensional boundary value problems of second and third kinds// Proc. of the Third St.Petersburg Workshop on Simulation. -St.Petersburg University Publishing House, 1998. pp. 95-100.

20. Makarov R.N. Solving boundary value problems for nonlinear elliptic equations by Monte Carlo methods,// Russ. J. Numer. Anal. Math. Modelling. 1999. - Vol. 14. - №5. - pp. 453-467.

21. Михайлов Г.А., Макаров P.H. Решение краевых задач второго и третьего рода методом Монте-Карло// Сибирский математический журнал. 1997. - Т. 38. - №3. - С.603-614.

22. Михайлов Г.А., Макаров Р.Н. Решение краевых задач методом "блуждания по сферам" с отражением от границы// Доклады РАН. 1997. - Т. 353. - №6. - С.720-722.

23. Михайлов Г.А., Макаров Р.Н. Параметрическое дифференцирование и оценки собственных чисел методом Монте-Карло// Сибирский математический журнал. 1998. - Т. 39. - №4. - С. 931941.

24. Михайлов Г.А., Макаров Р.Н. Оценки свободных чисел оператора А + с(г) путем вычисления параметрических производных методом Монте-Карло// Доклады РАН. 1998. - Т. 362. - №5. -С.598-601.

25. Михайлов Г.А. Новый алгоритм метода Монте-Карло для оценки максимального собственного значения интегрального оператора// Доклады АН СССР. 1970. - Т. 191. - №5. - С.993-996.

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

27. Михайлов Г.А., Рекуррентные формулы и принцип Беллмана в методе Монте-Карло// Российский зарубежный журнал по численному анализу и математическому моделированию. 1994.- Т. 9. №3. С.281-300.

28. Михайлов Г.А. Решение задачи Дирихле для нелинейного эллиптического уравнения методом Монте-Карло// Сибирский математический журнал. 1994. - Т. 35. - №5. - С.1085-1093.

29. Михайлов Г.А., Лотова Г.З. Оценки вероятностных моментов критических значений параметров уравнения переноса частиц в стохастической среде// Доклады РАН. 1997. - Т.356. - №2. -С.166-169.

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

31. Михайлов Г.А., Чешкова А.Ф. Решение разностной задачи Дирихле для многомерного уравнения Гельмгольца методом Монте-Карло // Журн. вычисл. матем. и матем. физики. 1996. - Т. 38.- №1. С.99-106.

32. Memoд Монте-Карло в проблеме переноса излучений. Сб. статей. Под ред. Г.И. Марчука. М.: Атомиздат, 1967.

33. Миранда К. Уравнения с частными производными эллиптического типа. М.: Изд-во иностр. лит., 1957, - 233 с.

34. Похожаев С.И., О задаче Дирихле для уравнения А и = и2.// Доклады АН СССР. 1960. - Т. 134. - №4. - С.769-773.

35. Похожаев С.И., О некоторых нелинейных уравнениях, Диссертация на соискание ученой степени доктора физико-математических наук. М., 1970.

36. Расу лов А. С. Метод Монте-Карло для решения нелинейных задач. Ташкент: Фан, 1992, 104 с.

37. Сабелъфелъд К.К. Методы Монте-Карло в краевых задачах. Новосибирск: Наука. Сиб. от-ние, 1989. 280 с.

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

39. Фаддеев Д.К., Фаддеева В.Н. Вычислительные методы линейной алгебры. М.: Физматгиз, 1963, - 734 с.

40. Cheshkova A.F. "Walk on spheres" algorithms for solving Helmholtz equation in the n-dimensional Euclidean space // Bulletin of the Novosibirsk Computing Center. Series: Numeral Analysis. Issue: 4 (1993). - pp. 7-18.

41. Curtiss J.H. Monte Carlo methods for the iteration of linear operators.// J. Math. Phys. 1954 - V. 32. - pp. 209-232.

42. Freidlin M. Functional Integration and Partial Differential Equations. Princeton: Princeton Univ. Press., 1985 (Ann. of Math. Stud., 109).

43. Mikhailov G.A. Minimization of computational cost of nonanalogue Monte Carlo methods. Singapore New Jersey - London - Hong Kong: Wold Scientific, 1991.

44. Mikhailov G.A. Cost of Monte Carlo methods for global estimation of solutions to multidimensional problems// Sov. J. Numer. Anal. Math. Modelling. 1991. - V. 6. - pp. 131-150.

45. Mikhailov G.A. "Walk on spheres" algorithms for solving Helmholtz equations// Russ. J. Numer. Anal. Math. Modelling. 1992. - V. 7. - №6. - pp. 515-536.

46. Mikhailov G.A. New Monte Carlo methods with estimating derivatives. Utrecht; Tokyo: VSP,1995.

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

48. Müller M.E. Some continuous Monte Carlo methods for the Dirichlet problem// Ann. Math. Stat. 1956. - V. 27. - №3. - pp. 569-589.