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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Основы метода[править | править исходный текст]

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

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.