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

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

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

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

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

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

[math]\displaystyle{ \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} }[/math]

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

[math]\displaystyle{ \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 ) }[/math]

с начальными

[math]\displaystyle{ T(x,y,0) = T_{0}(x,y), (x,y)\in G, }[/math]

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

[math]\displaystyle{ T(x,y,t)|_{S_{T}} = \mu (x,y,t), (x,y,t)\in S_{T}\equiv \partial D_{T} }[/math]

Введем в области [math]\displaystyle{ G }[/math] сетку узлов [math]\displaystyle{ \bar{\omega_{h}} = \left \{ x^{i}=i\cdot h_{x}, i=0,1,...,N_{x}, N_{x}\cdot h_{x}=l_{x},y^{j}=j\cdot h_{y}, j=0,1,...,N_{y}, N_{y}\cdot h_{y}=l_{y} \right \} }[/math], а на отрезке [math]\displaystyle{ [0\leq t\leq T] }[/math] сетку узлов [math]\displaystyle{ \omega_{\tau } = \left \{ t_{j}=n\tau, n=0,1,...,k, k\tau=T \right \}. }[/math]. Запишем разностную схему для заданной задачи ([math]\displaystyle{ k_{1} = k_{2} = \lambda }[/math]):

[math]\displaystyle{ \left\{\begin{matrix} \frac{y_{i,j}^{n+\frac{1}{2}} - y_{i,j}^{n}}{\tau} = \frac{1}{2}\left ( \frac{\lambda_{i+\frac{1}{2}, j}(y_{i+1,j}^{n+\frac{1}{2}} - y_{i,j}^{n+\frac{1}{2}}) - \lambda_{i-\frac{1}{2}, j}(y_{i,j}^{n+\frac{1}{2}} - y_{i-1,j}^{n+\frac{1}{2}})}{h_{x}^{2}} \right ) + \frac{1}{2}\left ( \frac{\lambda_{i, j+\frac{1}{2}}(y_{i,j+1}^{n} - y_{i,j}^{n}) - \lambda_{i, j-\frac{1}{2}}(y_{i,j}^{n} - y_{i,j-1}^{n})}{h_{y}^{2}} \right ), \\ \frac{y_{i,j}^{n+1} - y_{i,j}^{n+\frac{1}{2}}}{\tau} = \frac{1}{2}\left ( \frac{\lambda_{i+\frac{1}{2}, j}(y_{i+1,j}^{n+\frac{1}{2}} - y_{i,j}^{n+\frac{1}{2}}) - \lambda_{i-\frac{1}{2}, j}(y_{i,j}^{n+\frac{1}{2}} - y_{i-1,j}^{n+\frac{1}{2}})}{h_{x}^{2}} \right ) + \frac{1}{2}\left ( \frac{\lambda_{i, j+\frac{1}{2}}(y_{i,j+1}^{n+1} - y_{i,j}^{n+1}) - \lambda_{i, j-\frac{1}{2}}(y_{i,j}^{n+1} - y_{i,j-1}^{n+1})}{h_{y}^{2}} \right ) \end{matrix}\right. }[/math]

где [math]\displaystyle{ \lambda _{i\pm \frac{1}{2}, j} = \frac{\lambda _{i\pm 1, j} + \lambda _{i, j}}{2}, }[/math] [math]\displaystyle{ \lambda _{i, j\pm \frac{1}{2}} = \frac{\lambda _{i, j\pm 1} + \lambda _{i, j}}{2}. }[/math]

Зафиксировав в первом из уравнений системы [math]\displaystyle{ j }[/math], получим систему уравнений относительно значений [math]\displaystyle{ y_{i,j}^{n+\frac{1}{2}} }[/math], где [math]\displaystyle{ j = 1,...,N_{x}-1 }[/math], состоящую из ([math]\displaystyle{ N_{x}-1 }[/math]) линейного уравнения, которую можно решить методом прогонки. В целом систему на каждом половинном временном слое можно представить как ([math]\displaystyle{ N_{x}-1 }[/math]) независимую задачу (для каждого фиксированного [math]\displaystyle{ j }[/math]), решаемую методом прогонки. Аналогично решение второго из уравнений системы на каждом слое [math]\displaystyle{ t_{n+1} }[/math] представляет собой решение ([math]\displaystyle{ N_{x}-1 }[/math]) независимой задачи при фиксированном [math]\displaystyle{ i }[/math]. Каждая из указанных задач является системой линейных уравнений относительно значений сеточной функции по неявному направлению и решается методом прогонки. Сеточная функция , является приближенным решением задачи. По каждому из неявных направлений разностная схема является линейной и может быть записана в следующем виде:

[math]\displaystyle{ A_{i,j}y_{i-1,j}^{n+\frac{1}{2}} + C_{i,j}y_{i,j}^{n+\frac{1}{2}} + B_{i,j}y_{i+1,j}^{n+\frac{1}{2}} = F_{i,j}^{n} }[/math]

[math]\displaystyle{ A_{i,j} = \frac{\lambda_{i-\frac{1}{2},j}}{-2h_{y}^{2}}, B_{i,j} = \frac{\lambda_{i+\frac{1}{2},j}}{-2h_{y}^{2}}, C_{i,j} = \frac{1}{\tau} - A_{i,j} - B_{i,j}, }[/math]

[math]\displaystyle{ F_{i,j}^{n+\frac{1}{2}} = \frac{y_{i,j}^{n+\frac{1}{2}}}{\tau} + \frac{\lambda _{i+\frac{1}{2}, j}(y_{i+1, j}^{n+\frac{1}{2}} - y_{i, j}^{n+\frac{1}{2}}) - \lambda _{i-\frac{1}{2}, j}(y_{i,j}^{n+\frac{1}{2}} - y_{i-1, j}^{n+\frac{1}{2}})}{h_{y}^{2}} }[/math]

и соответственно

[math]\displaystyle{ A_{i,j}y_{i,j-1}^{n+1} + C_{i,j}y_{i,j}^{n+1} + B_{i,j}y_{i,j+1}^{n+1} = F_{i,j}^{n+\frac{1}{2}}. }[/math]

Для решения уравнений воспользуемся формулами прогонки. Значения прогоночных коэффициентов находятся по рекуррентным формулам:

где [math]\displaystyle{ k }[/math] – индекс неявного направления. Из граничных условий при [math]\displaystyle{ k=0 }[/math] и [math]\displaystyle{ k=N }[/math] определяются значения прогоночных коэффициентов. При этом [math]\displaystyle{ \alpha _{0} }[/math] и [math]\displaystyle{ \alpha _{N} }[/math] равны нулю, а значения [math]\displaystyle{ \beta _{0} }[/math] и [math]\displaystyle{ \beta _{N} }[/math] определяются из соответствующих краевых условий.

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

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

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

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

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

Последовательность исполнения метода следующая: Осуществляется прогонка вдоль строк, как это изображено на рисунке 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] т.е. продольно–поперечная схема имеет второй порядок аппроксимации по всем переменным.