Введение

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

Решение на компьютере

Типичный способ сделать это — брать значения функции f через равные интервалы в квадрате [0,1] × [0,1]. Например, можно взять 8 значений в направлении x при x = 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8 и 0.9, и 8 значений в направлении y в аналогичных координатах. Тогда получится 64 значения функции в квадрате, например, в точках (0.2, 0.8) и (0.6, 0.6). Цель компьютерной программы — вычислить значение f в этих 64 точках, что представляется более простым, чем поиск аналитического выражения для функции на всей площади квадрата. Существуют определенные трудности, например, невозможно вычислить вторую производную f по x и y в точке (0.5, 0.5), зная значение f только в 64 точках квадрата. Для преодочения этой проблемы используют различные численные методы аппроксимации производных, такие как метод конечных элементов или метод конечных разностей. Мы не будем рассматривать эти трудности, а сосредоточимся на другом аспекте задачи.

Разложение доменов

Что приводит нас к методам декомпозиции области. Если мы разделим область [0,1] × [0,1] на две подобласти [0,0.5] × [0,1] и [0.5,1] × [0,1], то каждая из них будет содержать только половину точек выборки. Таким образом, мы можем попытаться решить упрощенную версию нашей модельной задачи на каждой подобласти, но теперь каждая подобласть будет содержать всего 32 точки выборки. В заключение, имея решения на каждой подобласти, мы можем попытаться согласовать их, чтобы получить решение исходной задачи на [0,1] × [0,1].

Алгоритм разложения доменных чисел

К сожалению, по техническим причинам обычно невозможно разделить нашу сетку из 64 точек (систему линейных уравнений 64x64) на две сетки из 32 точек (две системы линейных уравнений 32x32) и получить решение системы 64x64. Вместо этого, на практике применяется следующий алгоритм:

1) Начните с приближенного решения системы 64x64. 2) Из системы 64x64 создайте две системы 32x32 для улучшения приближенного решения. 3) Решите две системы 32x32. 4) Объедините два решения 32x32, чтобы улучшить приближенное решение системы 64x64. 5) Если решение пока недостаточно хорошее, повторите с шага 2. Существует два преимущества по сравнению с решением исходной системы 64x64. Во-первых, если число итераций алгоритма невелико, решение двух систем 32x32 может оказаться более эффективным, чем решение системы 64x64. Во-вторых, две системы 32x32 не обязательно решать на одном компьютере, поэтому этот алгоритм можно выполнять параллельно, используя вычислительные ресурсы нескольких компьютеров. Фактически, решение двух систем 32x32 вместо 64x64 на одном компьютере (без использования параллелизма) вряд ли будет эффективным. Однако, если использовать более двух поддоменов, ситуация может измениться. Например, можно использовать четыре задачи 16x16, и существует вероятность, что решение этих задач окажется более выгодным, чем решение одной задачи 64x64, даже если алгоритму декомпозиции области потребуется несколько итераций.