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

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

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

1 Статистические свойства квазислучайных чисел, оценка погрешности метода КМК

1.1 Основные определения и факты

1.2 Экспериментальное исследование стохастических свойств ква-зислучайных чисел

1.3 Оценка погрешности метода КМК

1.3.1 Пример

1.3.2 Пример

1.3.3 Пример

2 Решение СЛАУ модифицированным методом МК, оптимизация оценок модифицированного метода

2.1 Решение СЛАУ методом МК

2.2 Применение марковских цепей для решения СЛАУ
2.3 Параллелизм метода МК и его сравнительная сложность
2.4 Предлагаемая модификация метода МК
2.5 Выбор оптимальных параметров оценок при использовании модифицированного МК
2.6 Устойчивость модифицированного МК

3 Решение СЛАУ модифицированным методом КМК
3.1 Применение модифицированного КМК
и оценка его погрешности
3.2 Эксперименты по сравнению методов МК, модифицированного МК, КМК и модифицированного КМК
4 Численные эксперименты
4.1 Метод последовательной верхней релаксации
4.2 Применение к уравнению Лапласа
4.3 Устойчивость модифицированного МК, примененного совместно с методом верхней релаксации
4.4 Применение модифицированного КМК при ослаблении условия мажорантной сходимости
4.5 Решение уравнения Навье-Стокса
Заключение
Список литературы

Введение
Методы Монте-Карло(МК) и Квази Монте-Карло(КМК) являются одним из важнейших инструментов для решения задач в многочисленных областях физики, математики, экономики, оптимизации, теории управления и др. В том числе, см. [1]-[4],[7], [11]-[15], [19]-[22], [33]-[34], они применяются для решения основной задачи линейной алгебры - нахождения решения системы линейных алгебраических уравнений (СЛАУ).
Интерес к этим методам обусловлен, в частности, тем, что как показано в работах Ермакова С.М. и Данилова Д.Л.([2],[3]), при большой размерности СЛАУ метод МК обладает меньшей трудоемкостью (в статистическом смысле), чем детерминированные итерационные методы. Также, большое преимущество перед другими методами дает методу МК его естественное свойство параллелизма. В некоторых случаях методы МК и КМК допускают неограниченный параллелизм и, следовательно, полную загрузку оборудования, что особенно важно для решения задач большой размерности, см. [1], [5].
В диссертации исследовались способы применения методов МК и КМК для решения систем линейных алгебраических уравнений (СЛАУ). Процесс решения СЛАУ методами МК и КМК может быть связан с моделированием марковских цепей с дискретным временем. В последнее время такого рода подход применялся во многих работах, например [2], [3], [7], [11], [12], [15]. В этих работах результаты были получены при наличии ряда ограничений, накладываемых на класс уравнений, которые могут быть решены с помощью

рата Дг-
Рисунок 1.10. Сетка узлов
0.0 02 0 4 Об 0

Рисунок 1.11. Зависимость оценки погрешности от числа рандомизированнных оценок и ее оценка доверительного интервала (±3)
На рисунке 1.11 синей линией изображена погрешность рандомизированной оценки 7о ~ 3 — «То — „ 5ГГ=1 **> зелеными линиями изображены границы
УЧ Л
доверительного интервала .То — <7 ± 3. Использованные для построения графика данные представлены в таблице 1.8. Точное значение погрешности оценки 0.03190897.