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

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

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

${\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.