Алгоритмы метода Монте-Карло для решения уравнений эллиптического типа. тема диссертации и автореферата по ВАК РФ 00.00.00, Елепов, Б. С.

• Елепов, Б. С.
• 1973

Оглавление диссертации Елепов, Б. С.

Введение. . • . . . . . . . . Ц

Глава I. Построение и обоснование алгоритма "блужданий по сферам" для решения первоё краевой задачи для уравнения Гельжгольца . . . . . .15"

§ I. I. Введение и основные обозначения • . . V . . . 15*

§ I. 2. Использование "жаровой" функции Грина для построения алгоритиа . . . . 1?

§ I. 3. Оценка эффективности алгоритиа "блужданий по сферам" для задач с разным числом измерений . •

§ I. Оценка производных от решения методом Монте-Карло .з?>

§ I. 5. Моделирование некоторая случайных величин . . .и

§ I. 6. Использование вероятностного представления решения первой краевой задачи для уравнения

А^ - cu, - - Cj. при построении алгоритма метода Монте-Карло.52.

Глава П. Решение методических и прикладных задач теории потенциала методом Монте-Карло . 5"

§ 2. I. Универсальная схема расчета расстояния от произвольной точки до границы области

§ 2. 2. Решение методических задач ••••. . . •

- 3Стр.

§ 2. 3. Расчет потенциала и траекторий движения электронов в электромагнитном поле электроразрядного насоса о многоячеиотым анодом* »

§ Z. 4. Решение методом Монте-Карло двумерной задачи о пробое электроизолятора . . ц i

Введение диссертации (часть автореферата) на тему «Алгоритмы метода Монте-Карло для решения уравнений эллиптического типа.»

Настоящая диссертация посвящена вопросам построения, обоснования и применения алгоритмов метода Монте-Карло для рвения краевых задач для уравнений эллиптического тина. Эта тема была предложена автору настоящей диссертации в 1966 году Г, А. Михайловым»

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

А ( Л - оператор Лапласа) , Этот процесс в дальнейшем получил название винеровского процесса.

Возможность использования связи дифференциальных уравнений с® случайными процессами для решения краевых задач изучалась многими авторами. Здесь в первую очередь следует отметить работ Р. Куранта, К. Фридрнхса, Леви, И. Г. Петровского, А. Я. Хинчина, Д. Дуба, Е. Б. Дымкина, С. Какутани, А. Д. Венцеля. В работах I. Филипса и Н. Винера [2] я Р. Куранта, I. Фридрнхса и Леви [з] и рассматривалось симметричное случайное блуждание X ^ по узлам плоской решетки; было доказано, что, если решетка в области Ф с граничной функцией | измельчается, то математическое ожидание функции ^ ( Х^) стремится к решению задачи йфихле для уравнения Лапласа в точке .

Здесь С - момент первого выхода блуадающей частицы из сеточ ной области, Х0- начальная точка блуздания.

Эта идея получила глубокое развитие в работе И.Г.Петровского [Л] и монографии А.Я.Хинчина [ 5] , где она применялась к широкому классу случайных блужданий и общим эллиптическим и параболическим дифференциальным уравнениям второго порядка.

Выражение решения задачи Дирихле для уравнения Лапласа, не содержащее предельного перехода и дающее решение непосредственно через траектории винеровского процесса, было получено и изучено Д. Дубом Г б ] . Р. 3. Хасьминским Г ?1и М.И.Фрейд-линым Г 8 ] это выражение было распространено на широкие классы диффузионных процессов и использовалось для исследования задачи Дирихле для различных классов эллиптических дифференциальных уравнений.

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

Вероятностный смысл функций Грина для эллиптических дифференциальных операторов достаточно хорошо известен [ 9] . Общая теория представления решения задачи Дирихле, основанная на вероятностном онределении функции Грина, впервые была построена Е.Б.Дынкиным. аким образом, вероятностное представление решения дифференциального уравнения важно и фочки зрения получения численного решения и для решения различных вопросов теоретического характера (см., например, работы М.Каца [ 10 ] и Р.З.Хасьминского [ ?] ,[п]).

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

Первое основано на предварительном сведении краевой задачи к конечно-разностной. Далее рассматривается случайное блуждан ие по решетке, узлами которой являются узлы разностной сетки; строится дискретная случайная величина, математическое ожидание которой дает оценку решения в заданной точке области. В качестве примера рассмотрим задачу Дирихле для уравнения Лапласа в плоской области ф с граничной функцией £ . Нанесем на область Ю квадратную сетку с шагом К . Узел Р^ , имеющий четыре соседние Р1ч, лежащие в $ , буде« называть внутренний; в противно» случае назовем его граничным. В граничных узлах Р^ оценка решения ц, определяется по следующему правилу: и.(Р\ = £((?), где - ближайшая к Р точка границы. Вайетин, что значения функции в граничные узлы можно переносить различны» способами; от этого зависит точность получаемого решения.

Во внутренних узлах оценка решения определяется системой разностных уравнений

С этой системой можно связать симметричное случайное блуждание с обрывом в граничных узлах. Если построить а/ траекторий блужданий из точки Р0 и в точках обрыва вычислить величину ( С! ), то оценку решения можно получить по формуле

I 4

N ^

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

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

Одно аз достоинств метода Монте * Кар® заключается в тон, что он обеспечивает одновременный учет всевозможных граничных условий. Независимость блуждания от граничных условий позволяет использовать одни и те же граничные точки для получения ревений с разными граничными условиями. С другой точки зрения число блужданий, заканчивающихся в заданной граничной точке 0{ пропорционально Я (Р, О ^ )-- вероятности окончания блуждания из Р в (1/1 . Так как ч * 1 то ясно, что приближенное распределение коночных точек является фундаментальным решением во отношению к общему решению с произвольными граничными условиями. Ззгнкция эквивалентна функции Грина для рассматриваемой области Ю .

Заметим, что можно рассматривать более общие эллиптические дифференциальные уравнения и наряду с задачей Дирихле ставить задачу Неймана. Из работ в этом направлении следует отметить исследования Кроне Г12 ] ,0. Филииии[ 13], Д. Ликиано [141 , [1бК Основным недостатком такого подхода является использование разностной апроксимации дифференциального оператора. В этом случае кроме статистической погрешности имеется погрешность апроксимации, зависящая от вага сетки к .

Второе направление основано на представлении решения краевс вой задачи интегралом но мере Винера. В работе И. М. Гель-фа дд а, А. 0. Фролова и Н, Н. Ченцова Г] рассмотрен общий алгоритм приближенной оценки винеровских интегралов методом Монте - Карло, основанный на последовательном моделировании положений винеровокой траектории в фиксированные моменты времени с шагом &t. Количес тво арифметических операций для достижения погрешности £ в оценке интеграла имеет порядок величины £ . Недостатком такого метода оценки винеровских интегралов является существенное увеличение времени расчетов на ЭВМ при üt-О . дж. Брауном [ 17'1 был предложен алгоритм "блужданий по сферам" для решения задачи Дирихле для уравнения Лапласа, Строгое о efe снование и развитие этой идеи Брауна содержится в работе М.Е.Нал-лера [ 18 ] , Алгоритм "блужданий но сферам" основан на моделировании точек последовательного выхода винеровской траектории из максимальных сфер, целиком лежащих в области.

В настоящей диссертации "блуждание по сферам" использовано для решения краевых задач в случае уравнения Гельм-гольца ли.-cu.:при с >0 . Предлагаемые алгоримы построены на оенове вероятностного представления решения соответствующего интегрального уравнения второго рода с вырозденньш ядром. Такой подход позволил существенно разработать различные теоретические и прикладные аспекты методики. В частности, показано, что количество арифметических операций, необходимое для получения погрешности £ в оценке решения имеет порядок величины -^т-^где С (к.^- константа, зависящая от размерности задачи. Разработаны алгоритмы непосредственной оценки градиента потенциала, которые позволяют по одним и тем же "выборочным" траекториям оценивать потенциал и сосвавлящие градиента потенциала, Решен ряд методических и практичесак задач.

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

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

В следущем, втором параграфе рассматривается специальное интегральное уравнение е вырожденным ядром, форма которого определяется "шаровой" функцией Грина для дифференциального оператора 4 - С , где А - оператор Лапласа, с > 0 • На основе этого уравнения строится и обосновывается алгоритм метода Монте- Карло для оценки решения задачи Дирихле для уравнения Гельмгольца. Рассматриваются вопросы сходимости ряда Неймана для полученного интегрального уравнения.

Такой подход к построению и обоснованию алгоритмов метода Монте-Карло позволяет в данном случае применить модификации, разработанные для интегральных уравнений Фредгольма 2-го рода; особенность ядра при этом включается в плотность перехода моделируемой цепи Маркова [19]. Далее показано, что случайная оценка ревения краевой задачи в произвольной точке области имеет конечную дисперсию, ограниченную при ¿-О Этот факт дает возможность использовать центральную предельную теорему для построения доверительного интеграла, то есть оценить погрешность.

Третий параграф первой главы посвящен вопросу оценки эффективности алгоритма "блужданий по сферам". Строятся специальные интегральные уравнения, решение которых дает оценку среднего числа сфер до попадания в околограничную полосу ширины £ • Яоказано, что количество арифметических опера-ци й, необходимое для получения погрешности £ в оценке решения, не превосходит величины С (М ' " * ^£ ^— , где С - константа, зависящая от размерности задачи не сильнее, чем линейно.

В следующем, четвертом параграфе стрзятся алгоритмы метода Монте-Карло для оценки производных от решения задачи Дирихле для уравнений Лапласа и Пуассона. Это особенно важно при решении прикладных задач, например, задач электронно-ионной оптики, где наряду с вычислением потенциала необходимо решать уравнения движения заряженных частиц. В эти уравнения входят составляющие градиента потенциала. В работе Й.Г.Дядъкина и В.Н.Старикова [ 20 } получено выражение "весового" множителя для оценки решения уравнения Лапласа в двух точках по одним и тем же "выборочным" траекториям. Это выражение в настоящей работе использовано для посазрое-ния алгоритма непосредственной оценки производных потенциала в произвольной точке; при этом решение и его производные вычисляются по одним и тем же траекториям.

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

В пятом параграфе первой главы рассматривается вопрос о моделировании некоторых случайных величин. Разработан эффективный алгоритм моделирования случайной точки в сфере соответственно "шаровой" функции Грина. Алгоритм реализован в виде программы для ЭВМ БЭСМ - 6. В случае С -0 распределение расстояния случайной точки от центра сферы (единичного радиуса) совпадает с распределением 2-ой порядковой статистики из трех выборочных значений случайной величины, равномерно распределенной в интервале [0,1] . Далее получена экономичная формула моделирования случайной точки в сфере, являющаяся в некотором смысле "наилучшей" для оценки производных потенциала,

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

Результата первой главы опубликованы в /2.1, 2,<иВ,2А£5/.

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

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

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

Во второй части параграфа приводятся результаты расчетов электрического поля на оси цилиндрической линзы. Здесь, наряду с граничными условиями Дирихле, рассматриваются условия Неймана, соответствующие отражению "блуждающей" частицы от границы по направлению внутренней нормали к граничной поверхности [ 3 ] . Численные результаты хорошо согласуются с известным аналитическим решением.

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

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

Результаты второй главы опубликованы в ([211] В приложении изучается вопрос о сочетании разностных итерационных методов решения задачи Дирихле для уравнения Гельмгольца с методом Монте-Карло, который используетея для предварительного вычисления неизвестной функции в отдельных узлах разностной сетки. Рассматриваются два возможных аргумента в пользу такого комбинирования.

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

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

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

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

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

Заключение диссертации по теме «Другие cпециальности», Елепов, Б. С.

ЗАКЛЮЧЕНИЕ

Кратко сформулируем основные результаты: 1« С помощью введения специального интегрального уравнения с вырожденным ядром разработан алгоритм оценки решения задачи Дирихле для уравнения Гельмгольца; доказана сходимость ряда Неймана для данного уравнения* 2* Доказана теорема о равномерной ограниченности по £ дисперсии построенной случайной оценки* 3. Построены алгоритмы метода Монте-Карло для оценки составляющих градиента потенциала и производной по параметру с от решения первой краевой задачи для уравнения Гельмгольца* 4* Сформулированы возможности решения обратных задач теории потенциала*

5* Оценена эффективность алгоритма "блужданий по сферам"*

6* На основе представления решения первой краевой задачи для уравн нения Гельмгольца в заданной точке интеграл© по мере Винера построен алгоритм оценки искомого решения методом Монте-Карло* 7* Построены алгоритмы моделирования некоторых случайных величин* 8* Разработан эффективный алгоритм определения расстояния от точки до границы области* 9* Решен ряд методических и прикладных задач*

Список литературы диссертационного исследования Елепов, Б. С., 1973 год

1. А. СЬд.чдлА, К, ^ H. ¿tu*^. ÍUtt cUtjwi.tu.Uui dU,f жлаМии*tlvc(u,K, РЦдД, JlUtt. Jkk,., loo (1Ш) ы-УА

2. И.Г.Петровский. UilH. йфь^чА^Мси-о, iUtfc.,1. ЛK/fv.j Log(iS3^, ms-m.

3. А.ЯДинчин. Ассимптотические законы теории вероятностей,1. ОНТИ, i.-Л., 1936.1. TtcuK.s. Лж/Л. HftlL 86.

4. Р.З.Хасьминский. Диффузионные процессы и эллиптическиедифференциальные уравнения, вырождающиеся на границе области, Теория вероятностей и ее применения, 3 (1958), 430 451.

5. М.й.фрейдлин. Диффузионные процессы с отражением и задачас косой производной на многообразии с краем, Теория вероятностей и ее применения, 8 (1963).9. <Г.Л* WvukA. Он. J&4HV.ÍIvve. jWeAloK,^ 11. Рчос* ЛА.ЛиЯ, Sel. 11.11

6. Д1с<хл.1сжд. сШ, *л\коАл 'йг К и. оШс.ик.~

7. ЦаЛ Ли, Щао е11Л\ло, кгюА. ^И^кда иса£ еа ли^ко, ин.

8. И.М.Гельфанд, А.С.Фролов, Н.Н.Ченцов. Вычисление континуальных интегралов методом Монте-Карло, Изв. вузов, сер. матем. №5 (1958), 32 45.

9. АМаЖа. ЛЦА1и. и^Мл о1Ц1Ьй1 ьот^икьЧ-Ь , нХ% I Ш.

10. Дж. Браун. Методы Монте-Карло, Сб. "Современная математика для инженерови, ил (1959), 275 301.

11. Л* «МлсКи,. $ осоиД^иХ1ои,к СькЛомчЛАоЖь ¡лн, Ли*.о

12. Г.А.Михайлов. Статистическое моделирование процессовпереноса излучения в атмосфере, докторская диссертация, ВЦ СО АН СССР, 1970.-8 920. И.Г.Дядькин, В.Н.Стариков. Об одной возможности экономии * машинного времени при решении уравнения

13. Лапласа методом Монте-Карло, Журнал вычисл. матем. и матем. физ., 5 Ш5 (1965), 936-938.

14. Б.С.Елепов, Г.А.Михайлов, Г.Р.Стефанюк. Алгоритмы метода

15. Монте-Карло для решения задачи Дирихле в сложных областях с одновременной оценкой градиента потенциала, Труды I Межвузовской конф., Алма-Ата,1970), 151 -153.

16. Б.С.Елепов. Алгоритм и программа для решения уравнения

17. Пуассона методом Монте-Карло, отчет ВЦ СО АН СССР, 1967.

18. Б.С.Елепов, Г.А.Михайлов. Использование фундаментальныхрешений эллиптических уравнений для построения алгоритмов метода Монте-Карло, Журнал вычисл. матем. и матем. физ., 14, 12 (1974).

19. Е.Б.Дынкин, М.А.Юшкевич. Теоремы иБадачи о процессах1. Маркова, М., Наука, 1967.

20. Фридман. Уравнения с чаетными производными параболического типа, И1 (1968).1. Наука, I97I.

21. Г.А.Михайлов. Использование приближенных решений сопряженной задачи для улучшения алгоритмов метода Монте-Карло, Журнал вычисл. матем. и матем. физ., 9, i 5 (1969), 1145 1152.

22. Г.Й.Марчук. Лекции по методам вычислений.

23. J.Ufc tu,tít*c. JU/Clo{ClKjU ytw^Un^ j^Hfihi,puoliJUli^ dtaKliuiloM и-ailtooUo| ¡¡U^CHiwj*, , д!еи>--Л til, J. <UML Sok*, ta, 1HÍ.

24. Г.А.Михайлов. О моделировании случайных величин дляодного класса законов распределения, Теория вероятностей и ее применения. 10, Ш 4 (1965), 749 751.

25. Б.Б.Дынкин. Марковские процессы, 1., Физматгиз, 1962.

26. I, GUauUÍv > P^uifli. PiÁ^t jíouUCL^je. IímlK

27. QLML ЦОКЛИ* tlJHt$ iHsOufl-Hib,*- и-toílcK LK.1.cl Уо, Cfccuct tWulotj иайЛличх, o| tfa. iCUH^k jlCuikf|*M• ДнаЧ», JtaJUu Sec.) Юз аЬ У|-Ч50

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

29. Н.А.Капдов. Электроника, М., Роетехиздат, 1956.

30. И.М.Блейвас, Б.С.Елепов, Г.Р.Стефанюк. Программа решения методом Монте-Карло уравнения Пуассона * для сложных граничных уеловий, Методырасчета Электронно-оптических систем, Новосибирск, ВЦ СО АН СССР, 1973, 42-51.

31. В.П.Йльин, Б.С.Елепов. О комбинировании разностныхалгоритмов с методом Монте-Карло, Журнал вычиел. матем. и матем. физ., (в печати).

32. В.П.Ильин. Разностные методы решения эллиптическихуравнений, Новосибирск, НГУ, 1970.Ж