Аддитивный метод Блэка

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

Обзор

Уравнения в частных производных (ЧДУ) используются во всех науках для моделирования явлений. Для изложения приведем пример физической задачи и сопутствующей ей краевой задачи (БВП). Даже если читатель не знаком с обозначениями, цель состоит в том, чтобы просто показать, как выглядит BVP в записанном виде.

(Модельная задача) Распределение тепла в квадратной металлической пластине, при котором левый край сохраняется под углом 1 градус, а другие края - под углом 0 градусов, после длительного пребывания в таком положении удовлетворяет следующей краевой задаче:

ж _хх ( Икс , y ) + ж _yy ( Икс , y ) знак равно 0

ж (0, у ) = 1; ж ( Икс ,0) знак равно ж ( Икс ,1) знак равно ж (1, y ) знак равно 0

где f — неизвестная функция , f _xx и f _yy обозначают вторые частные производные по x и y соответственно.

Здесь областью определения является квадрат [0,1] × [0,1].

Эту конкретную задачу можно решить именно на бумаге, поэтому компьютер не нужен. Однако это исключительный случай, и большинство БВП не могут быть решены точно. Единственная возможность — использовать компьютер для нахождения приближенного решения.

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

Типичный способ сделать это — выборка f через равные промежутки времени в квадрате [0,1] × [0,1]. Например, мы могли бы взять 8 выборок в направлении x в точках x = 0,1, 0,2, ..., 0,8 и 0,9 и 8 выборок в направлении y в аналогичных координатах . Тогда у нас будет 64 образца квадрата в таких местах, как (0,2,0,8) и (0,6,0,6). Целью компьютерной программы будет вычисление значения f в этих 64 точках, что кажется проще, чем поиск абстрактной функции квадрата.

Есть некоторые трудности, например, невозможно вычислить f _xx (0,5,0,5), зная f только в 64 точках квадрата. Чтобы преодолеть это, используется своего рода численная аппроксимация производных, см., например, метод конечных элементов или конечные разности . Мы игнорируем эти трудности и концентрируемся на другом аспекте проблемы.

Решение линейных задач

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

2а + 5б = 12 (*)

6 а - 3 б = -3

Это система двух уравнений с двумя неизвестными ( а и б ). Если мы решим БВП предложенным выше способом, нам нужно будет решить систему из 64 уравнений с 64 неизвестными. Это несложная задача для современных компьютеров, но если мы используем большее количество образцов, даже современные компьютеры не смогут решить БВП очень эффективно.

Декомпозиция домена

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

Размер проблем

Что касается линейных систем, мы пытаемся разделить систему из 64 уравнений с 64 неизвестными на две системы из 32 уравнений с 32 неизвестными. Это было бы явным выигрышем по следующей причине. Оглядываясь назад на систему (*), мы видим, что существует 6 важных фрагментов информации. Это коэффициенты при a и b (2,5 в первой строке и 6,−3 во второй строке) и правая часть (которую мы пишем как 12,−3). С другой стороны, если мы возьмем две «системы» 1 уравнения с 1 неизвестным, это может выглядеть так:

Система 1: 2 а = 12

Система 2: -3 b = -3

Мы видим, что в этой системе есть только 4 важных фрагмента информации. Это означает, что компьютерной программе будет легче решить две системы 1×1, чем одну систему 2×2, поскольку пара систем 1×1 проще, чем одна система 2×2. Хотя системы 64×64 и 32×32 слишком велики, чтобы их можно было здесь проиллюстрировать, по аналогии мы могли бы сказать, что система 64×64 содержит 4160 элементов информации, тогда как каждая из систем 32×32 содержит по 1056, или примерно четверть информации. Система 64×64.

Алгоритм декомпозиции домена

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

1) Начнем с приближенного решения системы 64×64.

2) Из системы 64×64 создайте две системы 32×32 для улучшения приближенного решения.

3) Решите две системы 32×32.

4) Соедините два решения 32×32 «вместе», чтобы улучшить приближенное решение системы 64×64.

5) Если решение пока не очень хорошее, повторите со 2.

Есть два способа, которыми это может быть лучше, чем решение базовой системы 64×64. Во-первых, если количество повторений алгоритма невелико, решение двух систем 32×32 может быть более эффективным, чем решение системы 64×64. Во-вторых, две системы 32×32 не обязательно решать на одном компьютере, поэтому этот алгоритм можно запускать параллельно, чтобы использовать мощность нескольких компьютеров.

Фактически, решение двух систем 32×32 вместо системы 64×64 на одном компьютере (без использования параллелизма) вряд ли будет эффективным. Однако если мы используем более двух поддоменов, картина может измениться. Например, мы могли бы использовать четыре задачи 16×16, и есть вероятность, что их решение будет лучше, чем решение одной задачи 64×64, даже если алгоритму декомпозиции области придется выполнить несколько итераций.

Технический пример

Здесь мы предполагаем, что читатель знаком с уравнениями в частных производных.

Мы будем решать уравнение в частных производных

ты _хх + ты _уу = ж (**)

Мы налагаем ограниченность на бесконечности.

Разложим область R² на две перекрывающиеся подобласти H ₁ = (− ∞,1] × R и H ₂ = [0,+ ∞) × R . В каждом поддомене мы будем решать BVP вида:

в ^{( Дж )}_хх + ты ^{( Дж )}_yy = f в H _j

в ^{( Дж )}( Икс _j , y ) знак равно грамм ( y )

где x ₁ = 1 и x ₂ = 0 и в качестве другого граничного условия принимается ограниченность на бесконечности. Обозначим решение u ^{( Дж )} вышеуказанной проблемы с помощью S( f , g ). Обратите внимание, что S билинейна.

Алгоритм Шварца действует следующим образом:

Начните с приближенных решений u ^{( 1 )}₀ и ты ^{( 2 )}₀ PDE в поддоменах H ₁ и H ₂ соответственно. Инициализируйте k значением 1.
Рассчитай тебя ^{( Дж )}_{k + 1} = S( ж , ты ^{(3 - j )}_k ( x _j )) с j = 1,2.
Увеличьте k на единицу и повторяйте 2, пока не будет достигнута достаточная точность.

См. также

Ссылки

Барри Смит, Петтер Бьерстад, Уильям Гропп, Разложение области, Параллельные многоуровневые методы для эллиптических уравнений в частных производных, Cambridge University Press, 1996
Андреа Тоселли и Олоф Видлунд, Методы декомпозиции области - алгоритмы и теория, Серия Спрингера по вычислительной математике, Vol. 34, 2004 г.

Внешние ссылки

Официальная страница методов декомпозиции домена