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

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

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

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

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

$Au=f,$

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

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

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

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

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

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

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

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

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

Иначе:

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

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

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

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

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

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

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

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

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

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

Сложность оператора $C_{op}$ рассчитывается как отношение количества ненулевых элементов во всех матрицах $A_{k},\,k=1,\,2,\,\dots ,\,n$ к количеству ненулевых элементов в матрице первого уровня $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.