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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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