WikiSort.ru - Не сортированное

Многосеточный (МС, англ. 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}$ .

Литература

1. Волков К.Н., Дерюгин Ю.Н., Емельянов В.Н. и др. Глава 2. Геометрические многосеточные методы., Глава 3. Алгебраические многосеточные методы. // Методы ускорения газодинамических расчётов на неструктурированных сетках. М. ФИЗМАТЛИТ, 2014. - С. 75-255. - 535 с. - ISBN 978-5-9221-1542-1.

Для улучшения этой статьи по математике желательно: Найти и оформить в виде сносок ссылки на независимые авторитетные источники, подтверждающие написанное. Викифицировать статью.