Уровень алгоритма

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

Материал из Алговики
Перейти к навигации Перейти к поиску


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


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

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

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

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

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

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

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

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

[math]b_{1} x_{1} + a_{1} x_{2} = f_{1}[/math],

[math]c_{i} x_{i-1} + b_{i} x_{i} + a_{i} x_{i+1} = f_{i}, 2 \le i \le n-1[/math],

[math]c_{n} x_{n-1} + b_{n} x_{n} = f_{n}[/math].

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

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

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

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

1.2.1 Прямой ход

Шаг 1

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

[math]c_{i} x_{i-1} + b_{i} x_{i} + a_{i} x_{i+1} = f_{i}[/math]

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

[math]c^{(1)}_{i} x_{i-1} + x_{i} + a^{(1)}_{i} x_{i+1} = f^{(1)}_{i}[/math]

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

[math]c^{(1)}_{i} = c_{i}/b_{i}[/math],

[math]a^{(1)}_{i} = a_{i}/b_{i}[/math],

[math]f^{(1)}_{i} = f_{i}/b_{i}[/math].

Уравнение

[math]b_{1} x_{1} + a_{1} x_{2} = f_{1}[/math]

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

[math]x_{i} + a^{(1)}_{1} x_{2} = f^{(1)}_{1}[/math]:

[math]a^{(1)}_{1} = a_{1}/b_{1}[/math],

[math]f^{(1)}_{1} = f_{1}/b_{1}[/math].

Уравнение

[math]c_{n} x_{n-1} + b_{n} x_{n} = f_{n}[/math]

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

[math]c^{(1)}_{n} x_{n-1} + x_{n} = f^{(1)}_{n}[/math]:

[math]c^{(1)}_{n} = c_{n}/b_{n}[/math],

[math]f^{(1)}_{n} = f_{n}/b_{n}[/math].

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

[math]c_{i} x_{i-1} + b_{i} x_{i} + a_{i} x_{i+1} = f_{i}[/math]

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

[math]c^{(1)}_{i} x_{i-2} + b^{(1)}_{i} x_{i} + a^{(1)}_{i} x_{i+2} = f^{(1)}_{i}[/math]

при этом

[math]c^{(1)}_{i} = - c_{i}c^{(1)}_{i-1}[/math],

[math]a^{(1)}_{i} = - a_{i}a^{(1)}_{i+1}[/math],

[math]b^{(1)}_{i} = b_{i} - c_{i}a^{(1)}_{i-1} - a_{i}c^{(1)}_{i+1}[/math],

[math]f^{(1)}_{i} = f_{i} - c_{i}f^{(1)}_{i-1} - a_{i}f^{(1)}_{i+1}[/math].

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

[math]b^{(1)}_{2} x_{2} + a^{(1)}_{2} x_{4} = f^{(1)}_{2}[/math],

при этом

[math]a^{(1)}_{2} = - a_{2}a^{(1)}_{3}[/math],

[math]b^{(1)}_{2} = b_{2} - c_{2}a^{(1)}_{1} - a_{2}c^{(1)}_{3}[/math],

[math]f^{(1)}_{2} = f_{2} - c_{2}f^{(1)}_{1} - a_{2}f^{(1)}_{3}[/math].

[math]n-2[/math]-е уравнение заменяется на

[math]c^{(1)}_{n-2} x_{n-4} + b^{(1)}_{n-2} x_{n-2} = f^{(1)}_{n-2}[/math]

при этом

[math]c^{(1)}_{n-2} = - c_{n-2}c^{(1)}_{n-3}[/math],

[math]b^{(1)}_{n-2} = b_{n-2} - c_{n-2}a^{(1)}_{n-3} - a_{n-2}c^{(1)}_{n-1}[/math],

[math]f^{(1)}_{n-2} = f_{n-2} - c_{n-2}f^{(1)}_{n-3} - a_{n-2}f^{(1)}_{n-1}[/math].

Следующие шаги

2 Литература

  1. Воеводин В.В. Вычислительные основы линейной алгебры. М.: Наука, 1977.
  2. Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. М.: Наука, 1984.
  3. 3,0 3,1 3,2 Ильин В.П., Кузнецов Ю.И. Трехдиагональные матрицы и их приложения. М.: Наука. Глав-ная редакция физико-математической литературы, 1985г., 208 с.
  4. Фролов А.В., Антонов А.С., Воеводин Вл.В., Теплов А.М. Сопоставление разных методов решения одной задачи по методике проекта Algowiki // Параллельные вычислительные технологии (ПаВТ’2016): труды международной научной конференции (г. Архангельск, 28 марта – 1 апреля 2016 г.). Челябинск: Издательский центр ЮУрГУ, 2016. С. 347-360.