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

Основы метода

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

${\displaystyle Au=f,}$

где ${\displaystyle A}$ — ${\displaystyle n\times n}$ матрица с элементами ${\displaystyle a_{ij}}$ . Для удобства сопоставим индексы с узлами сетки, таким образом ${\displaystyle u_{i}}$ представляет собой значение ${\displaystyle u}$ в узле ${\displaystyle i}$ . Множество узлов сетки обозначим как ${\displaystyle \Omega =\left\{1,\,2,\,\dots ,\,n\right\}}$ . Основная идея многосеточных методов состоит в том, что ошибка ${\displaystyle e}$ , которая не может быть устранена методами релаксации, должна быть убрана с помощью коррекции из решения на грубой сетке.

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

• Последовательность сеток ${\displaystyle \Omega =\Omega ^{1}\supset \Omega ^{2}\supset \dots \supset \Omega ^{M}}$ , причём ${\displaystyle \Omega ^{k}=C^{k}\cup F^{k},\quad C^{k}\cap F^{k}=\emptyset ,\quad \Omega ^{k+1}\equiv C^{k}}$ .
• Сеточные операторы ${\displaystyle A=A^{1},\,A^{2},\,\dots ,\,A^{M}}$ .
• Операторы интерполяции ${\displaystyle P^{k},k=1,\,2,\,\dots ,\,M-1}$ .
• Операторы сглаживания ${\displaystyle S^{k},k=1,\,2,\,\dots ,\,M-1}$ .

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

Этап построения

1. Приравнять ${\displaystyle k=1}$ .
2. Разделить ${\displaystyle \Omega ^{k}}$ на непересекающиеся множества ${\displaystyle C^{k}}$ и ${\displaystyle F^{k}}$ .
   1. Приравнять ${\displaystyle \Omega ^{k+1}=C^{k}}$ .
   2. Построить оператор интерполяции ${\displaystyle P^{k}}$ .
3. Построить ${\displaystyle A^{k+1}=\left(P^{k}\right)^{T}A^{k}P^{k}}$ .
4. Построить если необходимо ${\displaystyle S^{k}}$ .
5. Если сетка ${\displaystyle \Omega ^{k}}$ достаточно мала, приравнять ${\displaystyle M=k+1}$ и остановиться. Иначе ${\displaystyle k=k+1}$ и переход на шаг 2.

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

Алгоритм: ${\displaystyle MGV\left(A^{k},\,P^{k},\,S^{k},\,u^{k},\,f^{k}\right)}$

Если ${\displaystyle k=M}$ , решить ${\displaystyle A^{M}u^{M}=f^{M}}$ используя прямой метод.

Иначе:

Применить метод релаксации ${\displaystyle S^{k}}$ ${\displaystyle \mu _{1}}$ раз к ${\displaystyle A^{k}u^{k}=f^{k}}$ .

Произвести коррекцию на грубой сетке:

Вычислить ${\displaystyle r^{k}=f^{k}-A^{k}u^{k}}$ .

Вычислить ${\displaystyle r^{k+1}=\left(P^{k}\right)^{T}r^{k}}$ .

Применить ${\displaystyle MGV\left(A^{k+1},\,P^{k+1},\,S^{k+1},\,e^{k+1},\,r^{k+1}\right)}$ .

Обновить решение ${\displaystyle u^{k}=u^{k}+P^{k}e^{k+1}}$ .

Применить метод релаксации ${\displaystyle S^{k}}$ ${\displaystyle \mu _{2}}$ раз к ${\displaystyle A^{k}u^{k}=f^{k}}$ .

Вышеприведённый алгоритм описывает ${\displaystyle V\left(\mu _{1},\,\mu _{2}\right)}$ — цикл.

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

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

Сложность оператора ${\displaystyle C_{op}}$ рассчитывается как отношение количества ненулевых элементов во всех матрицах ${\displaystyle A_{k},\,k=1,\,2,\,\dots ,\,n}$ к количеству ненулевых элементов в матрице первого уровня ${\displaystyle A^{1}=A}$ .

Литература

• Волков К. Н., Дерюгин Ю. Н., Емельянов В. Н. и др. Глава 2. Геометрические многосеточные методы., Глава 3. Алгебраические многосеточные методы. // Методы ускорения газодинамических расчётов на неструктурированных сетках. М. ФИЗМАТЛИТ, 2014. — С. 75-255. — 535 с. — ISBN 978-5-9221-1542-1 .
• Press, W. H. Section 20.6. Multigrid Methods for Boundary Value Problems // Numerical Recipes: The Art of Scientific Computing / W. H. Press, S. A. Teukolsky, W. T. Vetterling … [ и др. ] . — 3rd. — New York : Cambridge University Press, 2007. — ISBN 978-0-521-88068-8 .