Многосеточный метод

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску


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

Основы метода[править | править код]

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

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

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

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

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

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

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

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

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

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

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

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

Литература

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