Алгоритм продольно-поперечной прогонки

1 Свойства и структура алгоритма

1.1 Общее описание алгоритма

Продольно–поперечная схема, которая также носит название метода переменных направлений (ADI – alternate directions implicit method), получила широкое применение для решения многомерных задач, приводящих к уравнениям в частных производных параболического типа (уравнение диффузии, уравнение теплопроводности). Эта схема была предложена в 1955 году Писменом и Рэкфордом.

1.2 Математическое описание алгоритма

Рассмотрим в области

$\begin{align} D_{T}=G\times [0\leq t\leq T], \\ G=[0\leq x\leq l_{x}]\times[0\leq y\leq l_{y}]\end{align}$

двумерное нелинейное уравнение теплопроводности

$\frac{\partial u}{\partial t} = \frac{\partial }{\partial x_{1}}\left ( k_{1}(x_{1}, x_{2}, t)\frac{\partial }{\partial x_{1}} \right ) + \frac{\partial }{\partial x_{2}}\left ( k_{1}(x_{1}, x_{2}, t)\frac{\partial }{\partial x_{2}} \right ) + f\left ( x_{1}, x_{2}, t \right )$

с начальными

$T(x,y,0) = T_{0}(x,y), (x,y)\in G,$

и граничными условиями

1.3 Вычислительное ядро алгоритма

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

1.4 Макроструктура алгоритма

Алгоритм представляет собой совокупность продольной и поперечной прогонки, а также прямого и обратного хода.

1.5 Схема реализации последовательного алгоритма

Последовательность исполнения метода следующая: Осуществляется прогонка вдоль строк, как это изображено на рисунке 1.1 [4]:

Рисунок 1.1– Прогонка вдоль строк

Затем осуществляется прогонка вдоль столбцов, как это представлено на рисунке 1.2 [4]:

Рисунок 1.2- Прогонка вдоль столбцов

1.6 Последовательная сложность алгоритма

Таким образом, при классификации по последовательной сложности продольно–поперечная прогонка относится к алгоритмам с линейной сложностью. При переходе от слоя $j$ к слою $j+1$ требуется $O(\frac{1}{h^{2}})$ арифметических действий. Чтобы найти $y^{j_{0}}$ при $t_{0} = j_{0}\tau$ по начальным данным требуется, очевидно, $O(\frac{1}{h^{2}})j_{0} = O(\frac{1}{\tau h^{2}})$ операций, то есть число операций пропорционально числу используемых узлов пространственно–временной сетки $w_{h\tau}$. Наряду с основными значениями $u_{ij}^{k}$ и $u_{i,j}^{k+1}$ вводится значение на промежуточном слое – $u_{ij}^{k+\frac{1}{2}}$, что фактически является значением $u$ при $t = t_{k+\frac{1}{2}}=t+\frac{\tau}{2}$. Благодаря этому, переход на следующий слой осуществляется в два шага.

1.8 Описание ресурса параллелизма алгоритма

Алгоритм метода переменных направлений обладает естественным параллелизмом: можно организовать независимые вычислительные процессы на каждом временном слое.

1.9 Входные и выходные данные алгоритма

Входные данные: матрица $y$ (элементы $y_{i,j}^{1}, i = 0,...,N_{x}, j = 0,...,N_{y}$).

Конечные значения $y_{(2)}(i_{1}, i_{2})$ являются приближенным решением задачи

Выходные данные: обновленная матрица $y$ (элементы $y_{i,j}^{n+1}, i = 0,...,N_{x}, j = 0,...,N_{y}$).

Объём выходных данных: $(N_{x} + 1) * (N_{y} + 1)$

1.10 Свойства алгоритма

Продольно–поперечная схема является одной из первых экономичных схем. Она сочетает в себе лучшее качество явной схемы – экономичность и неявной – устойчивость. Основной идеей экономичных разностных схем является сведение многомерной задачи к цепочке одномерных задач. Продольно–поперечная схема равномерно и безусловно устойчива по начальным данным, так как при переходе с одного целого слоя на следующий целый слой ошибки начальных данных не нарастают. При переходе с целого слоя на целый погрешность локальной аппроксимации на равномерных сетках есть $O(\tau^{2} + h_{x}^{2} + h_{y}^{2})$ т.е. продольно–поперечная схема имеет второй порядок аппроксимации по всем переменным.