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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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