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

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

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