Развитие методов Монте-Карло для решения нелинейных уравнений

• Автор: Тимофеев, Константин Алексеевич
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2008
• Место защиты: Санкт-Петербург
• Количество страниц: 157 с. : ил.

Оглавление
Введение

1 Общие сведения

1.1 Введение

1.2 Методы решения нелинейных алгебраических уравнений

1.2.1 Метод сжимающих отображений.

1.2.2 Метод НыотоиаКанторовича.

1.2.3 Метод последовательной линеаризации решения уравнений с квадратичной нелинейностью

1.2.4 Рандомизированный метод Ньютона.

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

1.4 Методы МонтеКарло для решения систем линейных алгебраических уравнений.

2 Решение алгебраических уравнений с квадратичной нелинейностью методами МонтеКарло
2.1 Введение
2.2 Рандомизация итерационных методов для решения нелинейных
уравнений.
2.3 Метод искусственного хаоса
2.3.1 Общий случай .
2.3.2 Случай алгебраических уравнений.
2.4 Рандомизированный метод искусственного хаоса
2.4.1 Сходимость рандомизированного метода искусственного хаоса в смысле вторых моментов.
2.4.2 Замечания к практическому применению рандомизированного метода искусственного хаоса
2.4.3 Алгоритм моделирования
2.4.4 Требования к вычислительным ресурсам. Сравнение с методом Ньютона
2.5 Вычислительные эксперименты.
2.5.1 Условия сходимости
2.5.2 Скорость сходимости сравнение различных методов . .
2.6 Выводы
3 Решение обыкновенных дифференциальных уравнений методом МонтеКарло
3.1 Введение
3.2 Рандомизированный метод Эйлера
3.2.1 Примеры .
3.3 Параллелизм
3.4 Локально оптимальные параметры.
4 Вычислительные эксперименты
4.1 Введение.
4.2 Постановка задачи
4.2.1 Уравнение НавьеСтокса.
4.2.2 Уравнение НавьеСтокса с искусственной сжимаемостью
4.2.3 Построение разностной аппроксимации
4.3 Алгоритмы решения
4.4 Описание программного комплекса
4.5 Результаты вычислительных расчетов.
4.5.1 Сходимость
4.5.2 Мелкозернистый параллелизм .
4.5.3 Крупнозернистый параллелизм.
4.5.4 Существенная и квазисущественная выборка
4.5.5 Расчет оценки решения уравнения НавьсСтокса в переменных скоростьдавление.
4.5.6 Сравнение трудоемкости с методом Эйлера.
4.5.7 Расчет задач большой размерности
4.6 Использование квазисл у чайных чисел.
4.7 Выводы.
Заключение
Список иллюстраций
Список таблиц
Список литературы


У И — fi^l “Ь ^ ^ aijVjl “I" З'/ ^ ^ ^ijkVjki У il = ijl = 1, • • • , Т. В ряде случаев оказывается, что решению у = ||^j|llj=i построенной системы соответствует решение X ИСХОДНОЙ СИС'ГСМЫ. Л)у где ^ = (фу. В диссертации предлагается несколько способов расчета хп+1 при известном значении упЛЛ. XI Узк) ’ г = 1,. Доказана следующая теорема, описывающая достаточное условие сходимости метода. Теорема 1. М2г —> Мг (см. К3х)і = ? Тогда для любого 6, 0 < 6 < 1 — ш, существует такое малое число р > 0, что для всех векторов х° Є Ег таких, что ||ж —ж°|| < р будет выполняться. При этом скорость сходимости будет линейной: хп — ж|| < (ш + 5)||жп'’1 — х\. При этом доказывается, что, в частности, преобразование (3) удовлетворяет первому условию теоремы. Важно отметить, что размерность линейного уравнения (2), решаемого на втором шаге алгоритма, равна г2, что является препятствием на пути его решения детерминистическими методами. Тем не менее при решении этого линейного уравнения методами Монте-Карло и при использовании на третьем шаге преобразования (3) метод становится сравнимым по трудоемкости и требованиям к памяти с рандомизированным методом Ньютона, так как достаточно оценивать значения г + 1 линейного функционала от решения. В главе приводится и доказывается теорема, которая показывает, что при выполнении ряда условий оценки, получаемые рандомизированным методом искусственного хаоса, сходятся в смысле вторых моментов к точному решению. Во введении она не приводится из-за громоздкости се формулировки. Эта теорема показывает, что при расчетах рандомизированным методом искусственного хаоса можно успешно применять как мелкозернистый параллелизм (за счет применения методов Монте-Карло для оценок решения СЛАУ (2)), так и крупнозернистый — за счет усреднения оценок после нескольких итераций. Была проделана работа по разработке эффективного алгоритма моделирования оценок по столкновениям и поглощению применительно к решаемой задаче, были применены различные методы уменьшения дисперсии и был проработан вопрос локальной оптимизации процесса моделирования вспомогательных дискретных распределений. Алгоритм построения оценок приводится в тексте диссертации. В главе осуществляется экспериментальное сравнение указанных в начале раздела методов. СЛАУ. В частности, демонстрируется, что применение рандомизированного метода искусственного хаоса в ряде случаев более предпочтительно, чем применение прочих рандомизированных методов. В третьей главе рассматриваются методы Монте-Карло решения эволюционных уравнений, основанные на методе Эйлера. Ь) = (г>г(*), —, г»т(? Г, /(*, г») = (/г(г,г>),. Г. Отображение / может быть конечно-разностной аппроксимацией дифференциального оператора в частных производных. Часто в практически интересных случаях число га превосходит °. Прием, описанный ниже (рандомизация), позволяет в ряде случаев уменьшить вычислительную работу и указать простую процедуру распараллеливания алгоритма. Рассмотрим систему дифференциальных уравнений (4). Д?/(Л? V0 = -у0, /(? К/(? V) (смысл приближенного равенства уточняется в тексте диссертации). Если удается выбрать семейство случайных векторов / так, что время моделирования правой части выражения (6) меньше времени расчета правой части (5), то достигается выигрыш по скорости расчетов. При этом, во-первых, случайные оценки Vй оказываются смещенными относительно оценок Vй и относительно решения г>(Д? Процесс построения оценок легко распараллеливается. Если для расчетов использовать Ь вычислителей с независимыми датчиками случайных чисел, то можно в Ь раз уменьшить дисперсии компонент оценки путем усреднения Ь независимых оценок уп, построенных для фиксированного п на этих вычислителях (крупнозернистый параллелизм). При этом можно строить доверительные интервалы для оценок. Можно проводить также усреднение оценок на каждом шаге п (мелкозернистый параллелизм). Очевидно, что при расчетах обоими способами можно добиться использования до 0% вычислительных ресурсов параллельной вычислительной системы. Р1^,^),. Т] и у 6 М7П задаст распределение па {1 ,.