Разработка алгоритмов случайного блуждания для решения нестационарных задач математической физики

В последнее время методы статистического моделирования, традиционно используемые в задачах теории переноса и статистической физики (см., например, [15, 16, 32])получили интенсивное развитие при решении многомерных краевых задач математической физики. Большой интерес к данному подходу вызван рядом причин, связанных как с перспективой создания новых эффективных численных методов для решения практических задач, так и с наличием глубоких связей между дифференциальными уравнениями и случайными процессами, требующих всестороннего изучения. Такая связь известна уже давно: теория дифференциальных уравнений широко использовалась в теории вероятностей. Например, А. Н. Колмогоров [21] показал в 1931 г., что переходная функция РС’Ц’эс^Г) — вероятность того, что броуновская частица, вышедшая из точки х, через время «Ь попадает в множество Р, удовлетворяет некоторому параболическому дифференциальному уравнению.

С другой стороны, аппарат теории вероятностей с успехом применялся при исследовании краевых задачотметим, в частности, работы Р. Куранта, К. Фридрихса, Я. Леви [58], К. Дуба[59], Е.Б.Дын-кина [ю], А. Д. Вентцеля [з], и др.

В методах Монте-Карло также использовались вероятностные представления решений краевых задач/в виде континуальных интегралов, при этом соответствующий стахостический процесс аппроксимировался дискретным случайным блужданием (см. например,[7,8]).

Этот подход прост в реализации, не требует большой памяти ЭВМ, но является сравнительно трудоемким из-за необходимости моделирования «длинных» случайных траекторий. Существуют и другие, отличные от алгоритма"основанного на моделировании дискретных случайных блужданий, приближенные методы вычисления континуальных интегралов — как детерминированные (см., например,[б, 7,57]), так и методы Монте-Карло, использующие, например, другие аппроксимации винеровского процесса (см. например,[44, 54]).

В случае уравнения Лапласа специфика винеровских интегралов позволяет для их оценки строить траектории менее подробно, например, достаточно моделировать выход винеровского процесса на границу области. Обоснование такого метода, известного под названием алгоритма блуждания по сферам, впервые описанном, по-видимому, Брауном в [2], было дано в [61]. После появления этих работ начаты интенсивные исследования по построению и изучению алгоритмов метода Монте-Карло, основанных на использовании соотношения о среднем и формул Грина (см., например, [12,13,14,17,22,24,28, 35,37,42,43,48,50,51,52.]).

Г. А. Михайловым и Б. С. Елеповым [12] впервые предложен подход, основанный на сведении исходной дифференциальной задачи к специальному интегральному уравнению с обобщенным ядром, что дало возможность использовать развитый аппарат методов Монте-Карло, для решения линейных и нелинейных интегральных уравнений 2-го рода [15,16]. Именно этот подход позволил разработать методы статистического моделирования для решения методом Монте-Карло, более общих уравнений и систем (см., например,[43,47,48,52]). Первая монография [14] на эту тему опубликована в 1980 г.

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

В [бо! получена логарифмическая оценка среднего числа блуждания по сферам до выхода в ¿—окрестность границы. Отметим, что в работе [61] подробно исследовался вопрос трудоемкое-ти в зависимости от размерности пространства, однако логарифмическая оценка в ней не приводится.

Независимо от [60] в [13 ] Б. С. Елеповым и Г. А. Михайловым логарифмическая оценка и конечность дисперсии были получены на основе полуэвристической оценки дяя плотности среднего числа, сфер вблизи границы. Обобщение логарифмической. оценки на случай невыпуклых областей осуществлено. в работах Г. А. Михайлова [16], А. А. Кронберга [23] и автора [26].

Следует отметить, что во всех вышеперечисленных работах алгоритмы метода Монте-Карло строились в рамках предположения о сходимости ряда Неймана, в связи с чем не было попыток использовать представление решений стационарных задач в виде потенциалов простого и двойного слоя, плотность которых удовлетворяет интегральным уравнениям со спектральным радиусом, равным единице. На преодоление этих трудностей направлены две следующие группы работ, использующие два различных подхода. В заметке К. К. Сабельфельда [42] для решения граничных интегральных уравнений теории потенциала предложен алгоритм «блуждания по границеV основанный на аналитическом продолжении резольвенты этих уравнений. В работах К. К. Сабельфельда и Н. А. Симонова [46,47] дана оценка трудоемкости, проведено обобщение на случай системы Ламе. Второй подход связан с переходом к нестационарным задачам и применением метода установления (см., например,[зо]): дело в том, что при использовании тепловых потенциалов интегральные уравнения душ плотности имеют’нулевой спектральный радиус (уравнения Вольтерра по времени), и здесь можно применять развитую технику решения интегральных уравнений методом Монте-Карло. Данный подход был использован в работах [27,30,45], где ососбое внимание было уделено разработке алгоритмов статистического моделирования для решения нестационарных задач.

Остановимся вкратце на особенностях алгоритма блуждания по границе. Во — первых, важным свойством этого метода является его «глобальность», т. е. возможность на одной траектории случайного блуждания получать оценки решения одновременно в произвольном множестве точек. Следует отметить, что существует и «глобальный» метод блуждания по сферам, предложенный в [48), однако он применим лишь для простейших уравнений с однородными граничными условиями и симметричной функцией Грина.

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

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

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

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

Следует отметить, что методы статистического моделирования применялись в основном для решения стационарных задач математической физикиимеется небольшое число работ, посвященных развитию метода Монте-Карло для решения нестационарных задач, отметим здесь работы А. Хаджи-Шейха, Спэрроу, А. З. Веселовской, А. С. Сипина, Е. О. Яжетываева и К. К. Сабелъфельда [4, 9, 17, 55]. В [55] автор исходил из вероятностного представления решения и обобщил метод блуждания по сферам для уравнения теплопроводности. В работах |~4, 9] применяются интегральные преобразования типа Лапласа для перехода к стационарному случаю, а затем строятся специальные коррелированные оценки при обращении образов.

Обобщение алгоритма блуждания по сферам осуществлено А. С. Сипиным [17] и основано на соотношениях о среднем, полученных в [24]. В работе [28] проведено дальнейшее обобщение этого метода и его усовершенствование.

Итак, можно выделить три подхода, используемые в методах Монте-Карло для решения краевых задач:

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

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

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

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

Далее для полноты следует упомянуть еще об одном подходе, широко применяемом в практических расчетах в силу своей простоты и сравнительной универсальности. Речь идет о методе блуждания по решетке. Однако его можно отнести к подходу I, поскольку этот метод представляет собой частный случай дискретного приближения континуальных интегралов.

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

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

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

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

Перейдем к изложению содержания диссертации по главам.

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

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

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

Следующий, третий параграф, посвящен обобщению алгоритма из § 1.2 на неоднородные уравнения с нулевыми начальными данными на основе решения задачи Коши или функции Грина с последующим использованием двойной рандомизации.

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

В пятом параграфе первой главы на основе одного метода представления решения однородной задачи Дирихле в виде потенциала простого слоя (см., [31 ] стр. 464), строится оценка как самого решения, так и ее производных. Причем дисперсия этих оценок конечна и в граничных точках, что не справедливо для обычных оценок, рассмотренных в предыдущих параграфах.

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

В первом параграфе этой главы выводится соотношение о среднем для уравнения теплопроводности, которое является обобщением соответствующей теоремы из работы [24] .

Во втором параграфе предлагается модификация алгоритма блуждания по шароидам А. С. Еипина, основанного на соотношении о среднем, полученном в §-2Л данной главы. В этой модификации случайное блуждание в ряде случаев заканчивается существенно быстрее.

Третий параграф содержит обобщение вышеупомянутого алгоритма на случай уравнения гц —Ди-*сс*с ограниченным коэффициентом.

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

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

ГГ — М. дис*"-Ь) + ссх,-ии = (I).

В первом параграфе выводится соотношение о среднем для уравнений типа (I).

Во втором параграфе излагаются два алгоритма для решения задачи Коши для уравнения (I).

В третьем параграфе данной главы строится алгоритм блуждания, по сферам для решения первой краевой задачи для уравнения (I).

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

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

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

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

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

Настоящая работа выполнена в Новосибирском Государственном Университете им. Ленинского комсомола. Изложенные в ней результаты были представлены и докладывались на У и У1 Всесоюзных совещаниях по методам Монте-Карло в вычислительной математике и математической физике (Новосибирск, 1976, 1979), на Всесоюзном семинаре по диффузии (Новосибирск, 1983) и на семинарах по методам Монте-Карло Вычислительного центра СО АН СССР. Основные результаты диссертации опубликованы в работах [25 — 30, 45].

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

ЗАКЛЮЧЕНИЕ

.

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

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

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

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

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