Рандомизированные методы решения краевых задач математической физики

• Автор: Моцартова, Надежда Сергеевна
• Шифр специальности: 01.01.07
• Научная степень: Кандидатская
• Год защиты: 2013
• Место защиты: Новосибирск
• Количество страниц: 99 с. : ил.

Оглавление
Введение
1 Рандомизированные алгоритмы для решения больших систем линейных алгебраических уравнений.
1.1 Рандомизация с помощью случайных разреженных матриц
1.2 Итерационные методы решения систем линейных алгебраических уравнений
1.2.1 Метод, основанный на преобразовании спектра
1.2.2 Нестационарный итерационный процесс со случайными параметрами
1.2.3 Рандомизация метода Гаусса-Зейделя
1.3 Дискретные варианты алгоритма блуждания по границе
1.3.1 Алгоритм изотропного случайного блуждания по границе
1.3.2 Дискретная версия метода случайного блуждания по границе
1.4 Численные результаты
2 Рандомизированный алгоритм для сингулярного разложения матриц и его применения к моделированию случайных полей и решению систем линейных алгебраических уравнений.
2.1 Сингулярное разложение матриц
2.2 Варианты рандомизации сингулярного разложения матриц
2.2.1 Метод разреженного сингулярного разложения матриц
2.2.2 Рандомизированный метод главных компонент
2.3 Моделирование случайных полей
2.3.1 Ризложение Кархунена-Лоева
2.3.2 Дискретизация разложения Кархунена-Лоева
2.3.3 Численные эксперименты по моделированию неоднородных случайных полей
2.3.4 Численные результаты сравнения методов рандомизированного
сингулярного разложения
2.4 Алгоритмы блуждания по границе

3 Стохастические граничные методы фундаментальных решений и их приложения.
3.1 Формулировка метода фундаментальных решений
3.2 Уравнение Лапласа
3.3 Уравнения Ламе
3.4 Аппроксимация функции Грина
3.5 Дискретизация интеграла Пуассона
3.6 Метод, основанный на обращении интегральной формулы Пуассона
3.6.1 Система уравнений Ламе
3.7 Сравнительные эксперименты
3.8 Задача о нахождении электроемкости для цепочки сфер
Заключение
Список литературы

Введение
Статистическое моделирование (или метод Монте-Карло) - это численный метод решения математических задач при помощи моделирования случайных величин [1]. Датой рождения метода Монте-Карло принято считать 1949 год, когда была опубликована статья Метрополией и Улама [2]. Однако до появления вычислительных машин этот метод не имел широкого применения из-за трудоемкости моделирования большого числа случайных величин. Таким образом, возникновение и интенсивное развитие методов Монте-Карло стало возможным благодаря появлению вычислительной техники.
Метод Монте-Карло естественно применяется при моделировании любого процесса, на протекание которого влияют случайные факторы, например при решении задач статистической физики, теории турбулентности, теории переноса. Статистическое моделирование используется и для решения многих математических задач, не связанных с какими-либо случайностями, но для которых можно искусственно придумать вероятностную модель, таких как вычисление числа 7г (предложенная Бюффоном в 1777 году), решение линейных интегральных и алгебраических уравнений, обращение матриц [3-5]. В первой работе на эту тему [2] была представлена схема Неймана-Улама, область применения которой ограничена условием сходимости ряда Неймана. Основная идея метода Неймана-Улама состояла в построении случайных оценок членов ряда Неймана на основе цепи Маркова в соответствии с ядром данного линейного уравнения. Применения методов Монте-Карло для решения интегральных уравнений были традиционно ограничены задачами переноса излучения и уравнениями диффузии |6,7]. Для решения применялся метод случайного блуждания по решетке (одни из первых работ по случайному блужданию для решения задач в частных производных в конечномерном пространстве [8,9]). В работе [10] представлены варианты различных модификаций первоначальной схемы Неймана-Улама, направленные на улучшение свойств дисперсии. Следует отметить большое количество других методов [11,12], представляющих собой рандомизированные оценки итераций на основе цепи Маркова. В работе [13] был разработай метод случайного блуждания по сферам, основанный на методе релаксации и методе Гаусса-Зейделя с черно-красной нумерацией.
В 1982 году К. Сабельфельд предложил в своей работе [14,19] первый метод Монте-Карло для решения интегральных уравнений с расходящимся рядом Неймана. Основная идея заключалась в перегруппировке членов ряда Неймана интегрального уравнения и подборе весов, таких, чтобы преобразованный ряд сходился и было возможным его устойчивое вычисление. Это было достигнуто с помощью конформного преобразования спектрального параметра интегрального уравнения, хорошо известного из линейной алгебры [15,16]. Фактически каждое конформное преобразование порождает соответствующий итерационный процесс [17].
Мотивацией при разработке метода, представленного в работе [14], было сконструировать метод Монте-Карло, который позволяет решать граничные интегральные уравнения, представимые в виде потенциалов простого и двойного слоя, плот-

Рандомизированный алгоритм разреженного сингулярного разложения матриц Выбираем некоторое вероятностное распределение {рі,---,рт ■ '}27= іР> = 1} строк -4(1), • • •, -4(т) матрицы А.
1. Фиксируется целое число в, для которого выполнено: г < т и в и /г/е2, где є допустимый уровень погрешности.
2. Для каждого значения _? от 1 до я:
• выбирается случайный номер строки матрицы А в соответствии с вероятностным распределением
• вектор сохраняется в качестве у-й строки матрицы Я
3. Строится матрица /} = Я и вычисляется её сингулярное разложение
где А2 - сингулярные числа, - левые и правые сингулярные вектора симметричной матрицы В.
4. Строки матрицы Нк вычисляются как = ЕР'Ш*'1'1 для j = 1,... ,к.
Найденные Ад,... А* и Я* являются аппроксимацией первых к сингулярных значения и правых сингулярных векторов матрицы А соответственно.
В работе [32] были получены оценки погрешности и трудоемкости для метода разреженного сингулярного разложения матриц. Обозначим Ак наилучшую аппроксимацию ранга к матрицы А и Р = АНкН[ оценку, полученную с использованием алгоритма разреженного сингулярного разложения. Предположим, что вероятностное распределение столбцов матрицы А удовлетворяет рг > /?|Л(г)|2/||Л||^ для некоторого положительного 0 < 1. Выберем некоторое 5 > 0. Для в > 4кЦЗе2 верна следующая оценка:
Для записи вероятностной оценки погрешности рассмотрим некоторое 5 > 0 и г/ = 1 + ^8 о^{1/5)/0. Если в > 4кр2/0г2, тогда с вероятностью 1 — (5 выполнено
Вычислительные затраты для аппроксимации сингулярных чисел и соответствующих правых сингулярных векторов для т х п матрицы А составляют
я[|И - АНкнЩ < \А - Ак\1 + г||Л|[
(2.4)
\А - АНкНІ\% < \А ~ Ак\2Р + г\А\1 .
(2.5)