Открыть главное меню


Многосеточный метод (МС, англ. multigrid) — метод решения системы линейных алгебраических уравнений, основанный на использовании последовательности уменьшающихся сеток и операторов перехода от одной сетки к другой. Сетки строятся на основе больших значений в матрице системы, что позволяет использовать этот метод при решении эллиптических уравнений даже на нерегулярных сетках.

Основы методаПравить

 
Визуализация итеративного многосеточного алгоритма для сходимости за O(n).

Предположим, что необходимо решить систему вида

 

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

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

  • Последовательность сеток  , причем  .
  • Сеточные операторы  .
  • Операторы интерполяции  .
  • Операторы сглаживания  .

Все эти компоненты многосеточного метода строятся на первом этапе, известном как этап построения

Этап построения
  1. Приравнять  .
  2. Разделить   на непересекающиеся множества   и  .
    1. Приравнять  .
    2. Построить оператор интерполяции  .
  3. Построить  .
  4. Построить если необходимо  .
  5. Если сетка   достаточно мала, приравнять   и остановиться. Иначе   и переход на шаг 2.

Как только этап построения завершен, может быть определен рекурсивный цикл построения решения:

Алгоритм:  
Если  , решить   используя прямой метод.
Иначе:
Применить метод релаксации     раз к  .
Произвести коррекцию на грубой сетке:
Вычислить  .
Вычислить  .
Применить  .
Обновить решение  .
Применить метод релаксации     раз к  .

Вышеприведенный алгоритм описывает   — цикл.

Выбор последовательности сеток и оператора интерполяции являются наиболее важными элементами этапа построения и во многом определяют качество многосеточного метода. Критерием качества являются две измеряемые величины:

  • фактор сходимости — показывающий насколько быстро сходится метод, то есть какое количество итераций требуется для достижения заданной точности;
  • сложность оператора — определяющей количество операций и объем памяти необходимой для каждой итерации метода.

Сложность оператора   рассчитывается как отношение количества ненулевых элементов во всех матрицах   к количеству ненулевых элементов в матрице первого уровня  .

ЛитератураПравить

  • Волков К. Н., Дерюгин Ю. Н., Емельянов В. Н. и др. Глава 2. Геометрические многосеточные методы., Глава 3. Алгебраические многосеточные методы. // Методы ускорения газодинамических расчётов на неструктурированных сетках. М. ФИЗМАТЛИТ, 2014. — С. 75-255. — 535 с. — ISBN 978-5-9221-1542-1.