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

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

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

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

Au = f,

где An \times n матрица с элементами aij. Для удобства сопоставим индексы с узлами сетки, таким образом ui представляет собой значение 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. Разделить Ωk на непересекающиеся множества Ck и Fk.
    1. Приравнять Ωk + 1 = Ck.
    2. Построить оператор интерполяции Pk.
  3. Построить A^{k+1}=\left(P^k\right)^T A^k P^k.
  4. Построить если необходимо Sk.
  5. Если сетка Ωk достаточно мала, приравнять M = k + 1 и остановится. Иначе k = k + 1 и переход на шаг 2.

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

Алгоритм: MGV \left(A^k,\, P^k,\, S^k,\, u^k,\, f^k\right)
Если k = M, решить AMuM = fM используя прямой метод.
Иначе:
Применить метод релаксации Sk μ1 раз к Akuk = fk.
Произвести коррекцию на грубой сетке:
Вычислить rk = fkAkuk.
Вычислить 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).
Обновить решение uk = uk + Pkek + 1.
Применить метод релаксации Sk μ2 раз к Akuk = fk.

Вышеприведенный алгоритм описывает V\left(\mu_1,\,\mu_2\right) — цикл.

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

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

Сложность Оператора Cop, рассчитывается как отношение количества ненулевых элементов во всех матрицах A_k,\, k = 1,\,2,\,\dots,\,n к количеству ненулевых элементов в матрице первого уровня A1 = A.

 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home