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

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

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

В диссертации исследовались способы применения методов МК и КМК для решения систем линейных алгебраических уравнений (СЛАУ). Процесс решения СЛАУ методами МК и КМК может быть связан с моделированием марковских цепей с дискретным временем. В последнее время такого рода подход применялся во многих работах, например [2], [3], [7], [11], [12], [15]. В этих работах результаты были получены при наличии ряда ограничений, накладываемых на класс уравнений, которые могут быть решены с помощью методов МК и КМК.

Одно из ограничений связано с необходимостью выполнения условия мажорантной сходимости. Оно было частично преодолено в работах Ермакова С. М. и Вагнера В. ([4],[5]) и в работе Сабельфельда К. К. и Шалимовой И.А.([13]).

Другое ограничение связано с невысоким порядком убывания погрешности метода МК при линейном увеличении времени расчета. Для достижения точности порядка е требуется проделать порядка 1/е2 операций. Для преодоления этой проблемы применяют методы КМК, поскольку при оценке s-кратных интегралов они в 0(у^г^) точнее методов МК (N — число траекторий, промоделированных для получения одной оценки).

Применение методов КМК для решения СЛАУ приводит к возникновению новой проблемы, а именно, к необходимости использовать квазислучайные векторы большой размерности s для оценки высокой степени матрицы оператора. Это приводит к ухудшению сходимости из-за наличия множителя lns N в числителе оценки скорости убывания остатка КМК. Проблема отмечается многими авторами ([1], [27], [28], [34]).

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

Приводится способ оценки ошибки метода КМК. Это способ имеет важное практическое применение, так как теоретическая оценка погрешности КМК существует для класса функций ограниченной вариации в виде неравенства Коксмы-Хлавки, но на практике получение численного значения верхней оценки является трудной задачей, как это отмечено в работах [1], [12], [13], [14].

1) разработка модификации методов МК и КМК для решения СЛАУ. Разработанная модификация должна преодолеть некоторые трудности, возникающие при применении КМК, в частности, увеличить скорость убывания погрешности метода КМК и ослабить условие мажорантной сходимости, накладываемое на решаемое уравнение;

2) оптимизация параметров предложенных методов;

3) численное исследование предлагаемых методов, в том числе в случае, когда условие мажорантной сходимости для МК и КМК не выполняется;

4) исследование вопроса применения модифицированных методов МК и КМК для решения СЛАУ совместно с одним из методов увеличения скорости сходимости итерационного процесса;

5) разработка стохастического метода для экспериментальной оценки погрешности метода КМК.

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

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

Предлагается и детально описывается стохастический метод для экспериментальной оценки погрешности метода КМК. Теоретические предположения подтверждаются серией проведенных экспериментов.

Вторая глава посвящена модифицированному методу МК для решения СЛАУ. Как отмечалось ранее, существуют определенные ограничения, налагаемые на класс задач, которые могут быть решены путем моделирования траекторий случайных процессов. Во-первых, это естественные ограничения, связанные с возможностью представления решения в виде интеграла по траекториям. Во-вторых, это ограничения, связанные с известным невысоким порядком убывания погрешности стохастических методов — для достижения точности порядка е требуется проследить порядка 1/е1 траекторий.

Чтобы ослабить первое ограничение, в диссертации предлагается модификация метода МК. Идея этой модификации впервые появилась в работе Ермакова С. М. и Вагнера В. Предложенная модификация позволяет ослабить условие мажорантной сходимости, так как суммирование отрезка ряда Неймана происходит в определенном порядке.

Автору диссертации принадлежит применение этой модификации для решения СЛАУ, выбор оптимальных параметров цепи Маркова и исследование стохастической устойчивости модифицированного метода при решении СЛАУ.

В третьей главе предлагается применить описанную во второй главе модификацию метода МК для метода КМК. Исследуется оценка погрешности модифицированного метода КМК. Приводятся результаты экспериментов по сравнению методов МК, КМК, модифицированного МК и модифицированного КМК для решения СЛАУ Делается вывод, что по сравнению с методами.

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

В четвертой главе приводятся численные эксперименты.

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

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

Заключение

.

В результате проведенных исследований в диссертации были получены следующие важные результаты:

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

2) Предложена и изучена модификация методов МК и КМК для решения СЛАУ, применимая в том числе при нарушении условия мажорантной сходимости для методов МК. Указаны методы оптимизации предложенных оценок.

3) Доказано, что предложенная модификация уменьшает конструктивную размерность, что упрощает применение квазислучайных чисел и увеличивает скорость сходимости по сравнению с КМК при решении СЛАУ.

4) Показана эффективность применения методов МК и КМК совместно с аналогом метода верхней релаксации в ряде случаев.

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

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

1) предложенный стохастический метод для экспериментальной оценки погрешности методов КМК является новым;

2) предложенная модификация метода КМК для решения СЛАУ является новым методом, применимым в том числе при нарушении условия мажорантной сходимости для методов МК;

3) успешное применение предложенной модификации МК и КМК совместно с аналогом метода верхней релаксации при нарушении условия мажорантной сходимости для МК также является новым результатом;

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