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

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

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

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

Au=f,{displaystyle Au=f,}

где A{displaystyle A}

  — n×n{displaystyle ntimes n}  матрица с элементами aij{displaystyle a_{ij}} . Для удобства сопоставим индексы с узлами сетки, таким образом ui{displaystyle u_{i}}  представляет собой значение u{displaystyle u}  в узле i{displaystyle i} . Множество узлов сетки обозначим как Ω={1,2,…,n}{displaystyle Omega =left{1,,2,,dots ,,nright}} . Основная идея многосеточных методов состоит в том, что ошибка e{displaystyle e} , которая не может быть устанена методами релаксации, должна быть убрана с помошью коррекции из решения на грубой сетке.

Используя верхний индекс в качестве номера уровня введем следующие обозначения:

• Последовательность сеток Ω=Ω1⊃Ω2⊃⋯⊃ΩM{displaystyle Omega =Omega ^{1}supset Omega ^{2}supset dots supset Omega ^{M}} , при чем Ωk=Ck∪Fk,Ck∩Fk=∅,Ωk+1≡Ck{displaystyle Omega ^{k}=C^{k}cup F^{k},quad C^{k}cap F^{k}=emptyset ,quad Omega ^{k+1}equiv C^{k}} .
• Сеточные операторы A=A1,A2,…,AM{displaystyle A=A^{1},,A^{2},,dots ,,A^{M}} .
• Операторы интерполяции Pk,k=1,2,…,M−1{displaystyle P^{k},k=1,,2,,dots ,,M-1} .
• Операторы сглаживания Sk,k=1,2,…,M−1{displaystyle S^{k},k=1,,2,,dots ,,M-1} .

Все эти компоненты многосеточного метода строятся на первом этапе, известном как этап построения

Этап построения

1. Приравнять k=1{displaystyle k=1} .
2. Разделить Ωk{displaystyle Omega ^{k}}  на непересекающиеся множества Ck{displaystyle C^{k}}  и Fk{displaystyle F^{k}} .
   1. Приравнять Ωk+1=Ck{displaystyle Omega ^{k+1}=C^{k}} .
   2. Построить оператор интерполяции Pk{displaystyle P^{k}} .
3. Построить Ak+1=(Pk)TAkPk{displaystyle A^{k+1}=left(P^{k}right)^{T}A^{k}P^{k}} .
4. Построить если необходимо Sk{displaystyle S^{k}} .
5. Если сетка Ωk{displaystyle Omega ^{k}}  достаточно мала, приравнять M=k+1{displaystyle M=k+1}  и остановится. Иначе k=k+1{displaystyle k=k+1}  и переход на шаг 2.

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

Алгоритм: MGV(Ak,Pk,Sk,uk,fk){displaystyle MGVleft(A^{k},,P^{k},,S^{k},,u^{k},,f^{k}right)} 

Если k=M{displaystyle k=M} , решить AMuM=fM{displaystyle A^{M}u^{M}=f^{M}}  используя прямой метод.

Иначе:

Применить метод релаксации Sk{displaystyle S^{k}}  μ1{displaystyle mu _{1}}  раз к Akuk=fk{displaystyle A^{k}u^{k}=f^{k}} .

Произвести коррекцию на грубой сетке:

Вычислить rk=fk−Akuk{displaystyle r^{k}=f^{k}-A^{k}u^{k}} .

Вычислить rk+1=(Pk)Trk{displaystyle r^{k+1}=left(P^{k}right)^{T}r^{k}} .

Применить MGV(Ak+1,Pk+1,Sk+1,ek+1,rk+1){displaystyle MGVleft(A^{k+1},,P^{k+1},,S^{k+1},,e^{k+1},,r^{k+1}right)} .

Обновить решение uk=uk+Pkek+1{displaystyle u^{k}=u^{k}+P^{k}e^{k+1}} .

Применить метод релаксации Sk{displaystyle S^{k}}  μ2{displaystyle mu _{2}}  раз к Akuk=fk{displaystyle A^{k}u^{k}=f^{k}} .

Вышеприведенный алгоритм описывает V(μ1,μ2){displaystyle Vleft(mu _{1},,mu _{2}right)}

  — цикл.

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

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

Сложность Оператора Cop{displaystyle C_{op}}

 , рассчитывается как отношение количества ненулевых элементов во всех матрицах Ak,k=1,2,…,n{displaystyle A_{k},,k=1,,2,,dots ,,n}  к количеству ненулевых элементов в матрице первого уровня A1=A{displaystyle A^{1}=A} .