- Многосеточный метод
-
Многосеточный (МС, англ. multigrid) метод — метод решения системы линейных алгебраических уравнений, основанный на использовании последовательности уменьшающихся сеток и операторов перехода от одной сетки к другой. Сетки строятся на основе больших значений в матрице системы, что позволяет использовать этот метод при решении эллиптических уравнений даже на нерегулярных сетках.
Основы метода
Предположим, что необходимо решить систему вида
где — матрица с элементами . Для удобства сопоставим индексы с узлами сетки, таким образом представляет собой значение в узле . Множество узлов сетки обозначим как . Основная идея многосеточных методов состоит в том, что ошибка , которая не может быть устранена методами релаксации, должна быть убрана с помощью коррекции из решения на грубой сетке.
Используя верхний индекс в качестве номера уровня введем следующие обозначения:
- Последовательность сеток , причем .
- Сеточные операторы .
- Операторы интерполяции .
- Операторы сглаживания .
Все эти компоненты многосеточного метода строятся на первом этапе, известном как этап построения
- Этап построения
- Приравнять .
- Разделить на непересекающиеся множества и .
- Приравнять .
- Построить оператор интерполяции .
- Построить .
- Построить если необходимо .
- Если сетка достаточно мала, приравнять и остановится. Иначе и переход на шаг 2.
Как только этап построения завершен, может быть определен рекурсивный цикл построения решения:
- Алгоритм:
- Если , решить используя прямой метод.
- Иначе:
- Применить метод релаксации раз к .
- Произвести коррекцию на грубой сетке:
- Вычислить .
- Вычислить .
- Применить .
- Обновить решение .
- Применить метод релаксации раз к .
Вышеприведенный алгоритм описывает — цикл.
Выбор последовательности сеток и оператора интерполяции являются наиболее важными элементами этапа построения и во многом определяют качество многосеточного метода. Критерием качества являются две измеряемые величины:
- фактор сходимости — показывающий насколько быстро сходится метод, то есть какое количество итераций требуется для достижения заданной точности;
- сложность оператора — определяющей количество операций и объем памяти необходимой для каждой итерации метода.
Сложность оператора рассчитывается как отношение количества ненулевых элементов во всех матрицах к количеству ненулевых элементов в матрице первого уровня .
Для улучшения этой статьи по математике желательно?: - Найти и оформить в виде сносок ссылки на авторитетные источники, подтверждающие написанное.
- Викифицировать статью.
Категории:- Линейная алгебра
- Вычислительная математика
Wikimedia Foundation. 2010.