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

Г'Ги од

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

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

УДК 519.245:519.676

Плотников Михаил Юрьевич

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

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

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

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

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

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

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

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

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

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

Защита состоится .^чг.^л'.].^... 1994 г. в Д... час.

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

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

Автореферат разослан „л." 1993 г.

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

д. ф. - м. н. I ^ ^----ю. И. Кузнецов.

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

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

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

интегральных и дифференциальных уравнений различными алгоритмами метода Монте-Карло.

ПЕЛЬЮ настоящей диссертационной работы является уменьшение трудоемкости решения нелинейных уравнений методом Монте-Карло.

Основные задачи исследования.

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

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

в) Анализ трудоемкости методов Монте-Карло решения модельных нелинейных уравнений на основе методов простой итерации, Ньютона, теории возмущений и продолжения по параметру.

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

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

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

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

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

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

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

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

И. КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ. Во введении дается обзор литературы по изучаемым в дис-

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

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

В §1.1 приводятся определения оценок "по пробегу" и "по столкновениям", описание метода Монте - Карло для решения линейных интегральных уравнений, ряд теорем из теории методов Монте - Карло. Также здесь приводится доказательство ряда вспомогательных асимптотических соотношений для дисперсий рассматриваемых случайных оценок при решении линейных интегральных уравнений методом гисто-грам, в частности утверждения о том, что дисперсия оценки "по столкновениям" с уменьшением шага разбиения h имеет порядок Л-1, а дисперсия оценки "по пробегу" не зависит от шага разбиения пространства.В дальнейшей работе используется следующее соотношение:

~ л'

где ifii - оценка "по пробегу" типа гистограммы на j-ом слое.

В §1.2 рассматривается нелинейное интегральное уравнение вида / = G(f). Предполагается, что решение f*(x) этого уравнения может быть найдено методом итераций, начиная с некоторого приближения /о(я), причем

Линейное интегральное уравнение на каждой итерации решается при помощи оценки "по пробегу" методом "полигона

частот". На основе теорем вложения с использованием некоторых дополнительных предположений построена задача минимизации трудоемкости вида:

Здесь N1 - число траекторий на ¡-той итерации, Л; - шаг сетки. Решение этой задачи дает приближенно оптимальные значения параметров N1 и-ЛРна каждой итерации, а также эволюцию этих параметров по итерациям:

Аналогичные оптимальные соотношения получены и для других рассматриваемых итерационных методов.

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

В §2.1 сформулированы следующие алгоритмы решения нелинейных уравнений.

п-1

—► тт, МЛ

1. Метод простой итерации;

2. Метод Ньютона;

3. Метод теории возмущений;

4. Метод продолжения по параметру.

Проведено исследование их эффективности на некотором аналоге кинетического уравнения Больцмана:

XXX

<р(х) - Ч ! <р(х') * ф{х')ехр1- J ч>(з)<1$]<1х' + ехр\~ J

О г" О

де [од]. (1)

Это уравнение можно трактовать в терминах теории переноса следующим образом : частица двигается из точки

х = 0 вдоль оси х случайными пробегами, распределенных

ми с плотностью 1р(х)ехр(~ / (х > 0). В конце пробега

о

происходит столкновение, в результате которого частица может поглотиться с вероятностью 1 — д; в противном случае она двигается дальше. В точке х = 1 происходит вылет, т. е. обрыв траектории. Функцию <р(х) можно трактовать как плотность столкновения. Непосредственной подстановкой в уравнение (1) можно убедиться, что

х

4>{х) = ежр(-( 1 - д) У ^О5)^).

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

о

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

В §2.2 рассмотрено нелинейное интегральное уравнение для классической задачи о теплопередаче между двумя бесконечными параллельными пластинами с постоянными температурами. При этом состояние газа описывалось кинетическим уравнением БГК для случая максвелловских молекул. Построены итерационные процессы решения этой задачи методами 1,2,4. Проведено численное сравнение этих алгоритмов. Для уменьшения трудоемкости были использованы оптимальные соотношения главы 1.

Третья глава посвящена использованию итерационных процессов 1 -4 и теории оптимизации для решения задачи Дирихле для уравнения Пуассонам с правой частью, зависящей от решения.

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

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

соотношения: __

ь _ и -

•) /).? ■»(—О

Л,- = М, 11 , = " .

где величина с 1 оценивается через верхнюю границу производных третьего порядка от функций /„. Здесь п - число итераций, а <2 — 1 + д} 11 . Таким образом, величины Л,- и

Д; связаны Следующим соотношением:

г.6

2 С!

В §3.3 для методов простой итерации и Ньютона доказаны теоремы сходимости в случае уравнения

ЛГ

Ди(а;) = - + Л(»),

¡=1

« |г= Ф-

при некоторых дополнительных условиях. Далее рассмотрена следующая модельная задача для единичного куба:

Ли = и2 - (а + Ь)* шп^х) вш^тгу)8^^, (2)

причем й(х, у, 1) = (а-I-Ь) зт(7га:) знфгу); на остальных гранях куба и(х,у,г) = 0. Здесь а и Ь - некоторые параметры.Для уравнения (2), доказаны теоремы сходимости итерационных процессов 1-4. Кроме того, описаны результаты численного решения модельного уравнения данными методами с использованием оптимальных соотношений §3.2.

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

ЗАКЛЮЧЕНИЕ.

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

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

2. Для решения нелинейных уравнений методом Монте-Карло на основе методов простой итерации, Ньютона, теории возмущений и продолжения по параметру получены следующие результаты:

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

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

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

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

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

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

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

1.Плотников М.Ю. " Применение полуньютоновского алгоритма для решения модельных кинетических уравнений." Теория и приложения статистического моделирования . Новосибирск,1989 - с. 98-107

2.Плотников М.Ю."Трудоемкость методов Монте-Карло на примере задачи о теплопередаче." Теория и приложения статистического моделирования . - Новосибирск, 1992 -с. 63-70

3.Плотников М.Ю."Сравнение трудоемкости методов Монте-Карло для различных алгоритмов решения модельного нелинейного интегрального уравнения." Вычислительная математика и статистическое моделирование.-Новосибирск, 1993

4.Плотников М.Ю." Вы числение производных по параметру при решении модельного .кинетического уравнения." Вычислительная математика и статистическое моделирование.-Новосибирск, 1993

5.Плотников М.Ю." Решение трехмерной задачи Дирихле для уравнения Пуассона с правой частью, зависящей от решения." Новосибирск,1993 г- -21 с. -(Препринт РАН, Сиб. отд-ние, ВП;1008)

б.Плотников М.Ю."Использование весовых методов Монте-Карло для решения нелинейных интегральных уравнений." Росс, зарубежный журнал по числ. анализу и матем. моделированию. - 1994, том 9,№2.