Метод дополнения Шура

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

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

Способ и реализация

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

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

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

$\left[{\begin{matrix}A_{11}&0&A_{1\Gamma }\\0&A_{22}&A_{2\Gamma }\\A_{\Gamma 1}&A_{\Gamma 2}&A_{\Gamma \Gamma }\end{matrix}}\right]\left[{\begin{matrix}U_{1}\\U_{2}\\U_{\Gamma }\end{matrix}}\right]=\left[{\begin{matrix}F_{1}\\F_{2}\\F_{\Gamma }\end{matrix}}\right],$

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

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

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

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

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

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

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

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

что можно делать параллельно.

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

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

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

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

Когда используется быстрая функция, особенно в недорогих параллельных компьютерах, метод дополнения Шура относительно эффективен.