Полный метод циклической редукции

Циклическая редукция для трёхдиагональной матрицы, точечный вариант
Последовательный алгоритм
Последовательная сложность	$O(n)$
Объём входных данных	$4n-2$
Объём выходных данных	$n$
Параллельный алгоритм
Высота ярусно-параллельной формы	$O(log n)$
Ширина ярусно-параллельной формы	$O(n)$

Основные авторы описания: А.В.Фролов.

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

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

Циклическая редукция - один из вариантов метода исключения неизвестных в приложении к решению СЛАУ вида $Ax = b$, где

$A = \begin{bmatrix} a_{11} & a_{12} & 0 & \cdots & \cdots & 0 \\ a_{21} & a_{22} & a_{23}& \cdots & \cdots & 0 \\ 0 & a_{32} & a_{33} & \cdots & \cdots & 0 \\ \vdots & \vdots & \ddots & \ddots & \ddots & 0 \\ 0 & \cdots & \cdots & a_{n-1 n-2} & a_{n-1 n-1} & a_{n-1 n} \\ 0 & \cdots & \cdots & 0 & a_{n n-1} & a_{n n} \\ \end{bmatrix}, x = \begin{bmatrix} x_{1} \\ x_{2} \\ \vdots \\ x_{n} \\ \end{bmatrix}, b = \begin{bmatrix} b_{1} \\ b_{2} \\ \vdots \\ b_{n} \\ \end{bmatrix}$

Бывает, однако, что при изложении сути методов решения трёхдиагональных СЛАУ элементы правой части и матрицы системы обозначают и нумеруют по-другому, например СЛАУ может иметь вид

$A = \begin{bmatrix} b_{1} & a_{1} & 0 & \cdots & \cdots & 0 \\ c_{2} & b_{2} & a_{2} & \cdots & \cdots & 0 \\ 0 & c_{3} & b_{3} & \cdots & \cdots & 0 \\ \vdots & \vdots & \ddots & \ddots & \ddots & 0 \\ 0 & \cdots & \cdots & c_{n-1} & b_{n-1} & a_{n-1} \\ 0 & \cdots & \cdots & 0 & c_{n} & b_{n} \\ \end{bmatrix}\begin{bmatrix} x_{1} \\ x_{2} \\ \vdots \\ x_{n} \\ \end{bmatrix} = \begin{bmatrix} f_{1} \\ f_{2} \\ \vdots \\ f_{n} \\ \end{bmatrix}$

или, если записывать отдельно по уравнениям, то

$b_{1} x_{1} + a_{1} x_{2} = f_{1}$,

$c_{i} x_{i-1} + b_{i} x_{i} + a_{i} x_{i+1} = f_{i}, 2 \le i \le n-1$,

$c_{n} x_{n-1} + b_{n} x_{n} = f_{n}$.

Циклическая редукция, как и все варианты прогонки, заключается в исключении из уравнений неизвестных, однако, в отличие от них, в ней исключение ведут одновременно по всей СЛАУ. В принципе, её можно считать вариантом метода редукции, выполняемого максимально возможное для данной СЛАУ число раз.

Рисунок 1. Граф алгоритма циклической редукции при n=15.

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

Лучше всего схема циклической редукции разработана для случая $n = 2^{k}-1$. Эта схема состоит из прямого и обратного ходов. Прямой ход состоит из последовательного уменьшения в СЛАУ количества уравнений почти в 2 раза (за счёт подстановки из уравнений с нечётными номерами заменяются уравнения с чётными), пока не останется одно уравнение, обратный - в получении всё большего количества компонент решения исходной СЛАУ. Оба хода - как прямой, так и обратный - разбиты на шаги. Здесь мы приведём тот вариант алгоритма, в котором операции экономятся за счёт предварительной нормировки уравнений, используемых для исключения неизвестных.

1.2.1 Прямой ход

1.2.1.1 Шаг 1

Для каждого из уравнений

$c_{i} x_{i-1} + b_{i} x_{i} + a_{i} x_{i+1} = f_{i}$

с нечётными $i$ выполняется его замена на уравнение

$c^{(1)}_{i} x_{i-1} + x_{i} + a^{(1)}_{i} x_{i+1} = f^{(1)}_{i}$

с помощью деления уравнения на $b_{i}$:

$c^{(1)}_{i} = c_{i}/b_{i}$,

$a^{(1)}_{i} = a_{i}/b_{i}$,

$f^{(1)}_{i} = f_{i}/b_{i}$.

Уравнение

$b_{1} x_{1} + a_{1} x_{2} = f_{1}$

меняется на уравнение

$x_{i} + a^{(1)}_{1} x_{2} = f^{(1)}_{1}$:

$a^{(1)}_{1} = a_{1}/b_{1}$,

$f^{(1)}_{1} = f_{1}/b_{1}$.

Уравнение

$c_{n} x_{n-1} + b_{n} x_{n} = f_{n}$

меняется на уравнение

$c^{(1)}_{n} x_{n-1} + x_{n} = f^{(1)}_{n}$:

$c^{(1)}_{n} = c_{n}/b_{n}$,

$f^{(1)}_{n} = f_{n}/b_{n}$.

Для каждого же из уравнений

$c_{i} x_{i-1} + b_{i} x_{i} + a_{i} x_{i+1} = f_{i}$

с чётными $i$ (кроме $2$ и $n-2$) выполняется его замена на уравнение

$c^{(1)}_{i} x_{i-2} + b^{(1)}_{i} x_{i} + a^{(1)}_{i} x_{i+2} = f^{(1)}_{i}$

при этом

$c^{(1)}_{i} = - c_{i}c^{(1)}_{i-1}$,

$a^{(1)}_{i} = - a_{i}a^{(1)}_{i+1}$,

$b^{(1)}_{i} = b_{i} - c_{i}a^{(1)}_{i-1} - a_{i}c^{(1)}_{i+1}$,

$f^{(1)}_{i} = f_{i} - c_{i}f^{(1)}_{i-1} - a_{i}f^{(1)}_{i+1}$.

Для 2го уравнения выполняется его замена на уравнение

$b^{(1)}_{2} x_{2} + a^{(1)}_{2} x_{4} = f^{(1)}_{2}$,

при этом

$a^{(1)}_{2} = - a_{2}a^{(1)}_{3}$,

$b^{(1)}_{2} = b_{2} - c_{2}a^{(1)}_{1} - a_{2}c^{(1)}_{3}$,

$f^{(1)}_{2} = f_{2} - c_{2}f^{(1)}_{1} - a_{2}f^{(1)}_{3}$.

$n-2$-е уравнение заменяется на

$c^{(1)}_{n-2} x_{n-4} + b^{(1)}_{n-2} x_{n-2} = f^{(1)}_{n-2}$

при этом

$c^{(1)}_{n-2} = - c_{n-2}c^{(1)}_{n-3}$,

$b^{(1)}_{n-2} = b_{n-2} - c_{n-2}a^{(1)}_{n-3} - a_{n-2}c^{(1)}_{n-1}$,

$f^{(1)}_{n-2} = f_{n-2} - c_{n-2}f^{(1)}_{n-3} - a_{n-2}f^{(1)}_{n-1}$.