Многосеточный метод (МС, ) — метод решения системы линейных алгебраических уравнений, основанный на использовании последовательности уменьшающихся сеток и операторов перехода от одной сетки к другой. Сетки строятся на основе больших значений в матрице системы, что позволяет использовать этот метод при решении эллиптических уравнений даже на нерегулярных сетках.
Основы метода
Предположим, что необходимо решить систему вида
где — матрица с элементами . Для удобства сопоставим индексы с узлами сетки, таким образом представляет собой значение в узле . Множество узлов сетки обозначим как . Основная идея многосеточных методов состоит в том, что ошибка , которая не может быть устранена методами релаксации, должна быть убрана с помощью коррекции из решения на грубой сетке.
Используя верхний индекс в качестве номера уровня введём следующие обозначения: Последовательность сеток , причём . Сеточные операторы . Операторы интерполяции . Операторы сглаживания . Все эти компоненты многосеточного метода строятся на первом этапе, известном как этап построения
Этап построения Приравнять . Разделить на непересекающиеся множества и . Приравнять . Построить оператор интерполяции . Построить . Построить если необходимо . Если сетка достаточно мала, приравнять и остановиться. Иначе и переход на шаг 2.
Как только этап построения завершён, может быть определён рекурсивный цикл построения решения:
Алгоритм: Если , решить используя прямой метод. Иначе: Применить метод релаксации раз к . Произвести коррекцию на грубой сетке: Вычислить . Вычислить . Применить . Обновить решение . Применить метод релаксации раз к .
Вышеприведённый алгоритм описывает — цикл.
Выбор последовательности сеток и оператора интерполяции являются наиболее важными элементами этапа построения и во многом определяют качество многосеточного метода. Критерием качества являются две измеряемые величины: фактор сходимости — показывающий насколько быстро сходится метод, то есть какое количество итераций требуется для достижения заданной точности; сложность оператора — определяющей количество операций и объём памяти необходимой для каждой итерации метода.
Сложность оператора рассчитывается как отношение количества ненулевых элементов во всех матрицах к количеству ненулевых элементов в матрице первого уровня .
Литература Волков К. Н., Дерюгин Ю. Н., Емельянов В. Н. и др. Глава 2. Геометрические многосеточные методы., Глава 3. Алгебраические многосеточные методы. // Методы ускорения газодинамических расчётов на неструктурированных сетках. М. ФИЗМАТЛИТ, 2014. — С. 75-255. — 535 с. — ISBN 978-5-9221-1542-1.
Категория:Дифференциальные уравнения в частных производных Категория:Методы решения СЛАУ