Метод дополнения Шура - Schur complement method

Эта статья не о Шур дополняет матриц.

В численный анализ, то Метод дополнения Шура, названный в честь Иссай Шур, это основная и самая ранняя версия неперекрывающегося метод декомпозиции домена, также называется итеративное субструктурирование. А заключительный элемент проблема разбивается на неперекрывающиеся подобласти, а неизвестные во внутренних частях подобластей удаляются. Оставшаяся система дополнений Шура на неизвестных, связанных с интерфейсами подобластей, решается с помощью метод сопряженных градиентов.

Метод и реализация

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

${displaystyle -Delta u=f,qquad u|_{partial Omega }=0}$

в некоторой области Ω. Когда мы дискретизируем эту проблему, мы получаем N-мерная линейная система AU = F. Метод дополнения Шура разбивает линейную систему на подзадачи. Для этого разделим Ω на две подобласти Ω₁, Ω₂ которые имеют общий интерфейс Γ. Позволять U₁, U₂ и U_Γ быть степенями свободы, связанными с каждой подобластью и с интерфейсом. Тогда мы можем записать линейную систему как

${displaystyle left[{egin{matrix}A_{11}&0&A_{1Gamma }�&A_{22}&A_{2Gamma }A_{Gamma 1}&A_{Gamma 2}&A_{Gamma Gamma }end{matrix}}ight]left[{egin{matrix}U_{1}U_{2}U_{Gamma }end{matrix}}ight]=left[{egin{matrix}F_{1}F_{2}F_{Gamma }end{matrix}}ight],}$

где F₁, F₂ и F_Γ компоненты вектора нагрузки в каждой области.

В методе дополнения Шура отмечается, что мы можем найти значения на интерфейсе, решая меньшую систему

${displaystyle Sigma U_{Gamma }=F_{Gamma }-A_{Gamma 1}A_{11}^{-1}F_{1}-A_{Gamma 2}A_{22}^{-1}F_{2},}$

для значений интерфейса U_Γ, где мы определяем Дополнение Шура матрица

${displaystyle Sigma =A_{Gamma Gamma }-A_{Gamma 1}A_{11}^{-1}A_{1Gamma }-A_{Gamma 2}A_{22}^{-1}A_{2Gamma }.}$

Важно отметить, что вычисление любых величин, включающих ${displaystyle A_{11}^{-1}}$ или ${displaystyle A_{22}^{-1}}$ включает решение развязанных Задачи Дирихле в каждом домене, и это можно делать параллельно. Следовательно, нам не нужно явно хранить матрицу дополнения Шура; достаточно знать, как на него умножить вектор.

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

${displaystyle A_{11}U_{1}=F_{1}-A_{1Gamma }U_{Gamma },qquad A_{22}U_{2}=F_{2}-A_{2Gamma }U_{Gamma },}$

которые можно выполнять параллельно.

Умножение вектора на дополнение Шура есть дискретный версия Оператор Пуанкаре – Стеклова, также называемый Отображение Дирихле в Неймана.

Преимущества

У этого метода есть два преимущества. Во-первых, устранение внутренних неизвестных на подобластях, то есть решение задач Дирихле, можно проводить параллельно. Во-вторых, переход к дополнению Шура уменьшает количество условий и, таким образом, имеет тенденцию к уменьшению количества итераций. Для проблем второго порядка, таких как Уравнение лапласа или линейная эластичность матрица системы имеет номер условия порядка 1 /час², где час - характерный размер элемента. Однако дополнение Шура имеет номер обусловленности только порядка 1 /час.

Для перформансов метод дополнения Шура сочетается с предварительной подготовкой, по крайней мере, диагональный предварительный кондиционер. В Метод Неймана – Неймана и Метод Неймана – Дирихле. являются методом дополнения Шура с определенными видами предобуславливателей.