Русская Википедия:Многосеточный метод
Многосеточный метод (МС, Шаблон:Lang-en) — метод решения системы линейных алгебраических уравнений, основанный на использовании последовательности уменьшающихся сеток и операторов перехода от одной сетки к другой. Сетки строятся на основе больших значений в матрице системы, что позволяет использовать этот метод при решении эллиптических уравнений даже на нерегулярных сетках.
Основы метода
Предположим, что необходимо решить систему вида
<math>Au=f, </math>
где <math> A </math> — <math> n \times n </math> матрица с элементами <math> a_{ij} </math>. Для удобства сопоставим индексы с узлами сетки, таким образом <math> u_i </math> представляет собой значение <math> u </math> в узле <math> i </math>. Множество узлов сетки обозначим как <math> \Omega=\left\{1,\,2,\,\dots,\,n\right\} </math>. Основная идея многосеточных методов состоит в том, что ошибка <math> e </math>, которая не может быть устранена методами релаксации, должна быть убрана с помощью коррекции из решения на грубой сетке.
Используя верхний индекс в качестве номера уровня введём следующие обозначения:
- Последовательность сеток <math> \Omega = \Omega^1 \supset \Omega^2 \supset \dots \supset \Omega^M </math>, причём <math>\Omega^k = C^k \cup F^k,\quad C^k \cap F^k = \emptyset, \quad \Omega^{k+1} \equiv C^k</math>.
- Сеточные операторы <math>A=A^1,\,A^2,\,\dots,\,A^M </math>.
- Операторы интерполяции <math> P^k, k=1,\,2,\,\dots,\,M-1</math>.
- Операторы сглаживания <math> S^k, k=1,\,2,\,\dots,\,M-1</math>.
Все эти компоненты многосеточного метода строятся на первом этапе, известном как этап построения
- Этап построения
- Приравнять <math>k = 1 </math>.
- Разделить <math>\Omega^k </math> на непересекающиеся множества <math>C^k </math> и <math> F^k</math>.
- Приравнять <math> \Omega^{k+1} = C^k</math>.
- Построить оператор интерполяции <math> P^k</math>.
- Построить <math> A^{k+1}=\left(P^k\right)^T A^k P^k</math>.
- Построить если необходимо <math> S^k</math>.
- Если сетка <math>\Omega^k </math> достаточно мала, приравнять <math>M = k+1 </math> и остановиться. Иначе <math> k = k + 1</math> и переход на шаг 2.
Как только этап построения завершён, может быть определён рекурсивный цикл построения решения:
- Алгоритм: <math> MGV \left(A^k,\, P^k,\, S^k,\, u^k,\, f^k\right)</math>
- Если <math>k = M </math>, решить <math>A^M u^M = f^M </math> используя прямой метод.
- Иначе:
- Применить метод релаксации <math>S^k </math> <math>\mu_1 </math> раз к <math>A^k u^k = f^k </math>.
- Произвести коррекцию на грубой сетке:
- Вычислить <math>r^k = f^k - A^k u^k</math>.
- Вычислить <math>r^{k+1} = \left(P^k\right)^T r^k</math>.
- Применить <math>MGV \left(A^{k+1},\, P^{k+1},\, S^{k+1},\, e^{k+1},\, r^{k+1}\right)</math>.
- Обновить решение <math>u^k = u^k + P^k e^{k+1}</math>.
- Применить метод релаксации <math>S^k </math> <math>\mu_2 </math> раз к <math>A^k u^k = f^k </math>.
Вышеприведённый алгоритм описывает <math>V\left(\mu_1,\,\mu_2\right) </math> — цикл.
Выбор последовательности сеток и оператора интерполяции являются наиболее важными элементами этапа построения и во многом определяют качество многосеточного метода. Критерием качества являются две измеряемые величины:
- фактор сходимости — показывающий насколько быстро сходится метод, то есть какое количество итераций требуется для достижения заданной точности;
- сложность оператора — определяющей количество операций и объём памяти необходимой для каждой итерации метода.
Сложность оператора <math>C_{op}</math> рассчитывается как отношение количества ненулевых элементов во всех матрицах <math>A_k,\, k = 1,\,2,\,\dots,\,n</math> к количеству ненулевых элементов в матрице первого уровня <math>A^1 = A</math>.
Литература
- Волков К. Н., Дерюгин Ю. Н., Емельянов В. Н. и др. Глава 2. Геометрические многосеточные методы., Глава 3. Алгебраические многосеточные методы. // Методы ускорения газодинамических расчётов на неструктурированных сетках. М. ФИЗМАТЛИТ, 2014. — С. 75-255. — 535 с. — ISBN 978-5-9221-1542-1.
- Шаблон:Cite book
Шаблон:Rq Шаблон:ВС Шаблон:Методы решения ДУ
