Полный метод циклической редукции: различия между версиями
| [непроверенная версия] | [непроверенная версия] |
Frolov (обсуждение | вклад) |
Frolov (обсуждение | вклад) Нет описания правки |
||
| Строка 25: | Строка 25: | ||
Лучше всего схема циклической редукции<ref name="IK3d" /> разработана для случая <math>n = 2^{k}-1</math>. Эта схема состоит из прямого и обратного ходов. | Лучше всего схема циклической редукции<ref name="IK3d" /> разработана для случая <math>n = 2^{k}-1</math>. Эта схема состоит из прямого и обратного ходов. | ||
Прямой ход состоит из последовательного уменьшения в СЛАУ количества уравнений почти в 2 раза (за счёт подстановки из уравнений с нечётными номерами заменяются уравнения с чётными), пока не останется одно уравнение, обратный - в получении всё большего количества компонент решения исходной СЛАУ. Оба хода - как прямой, так и обратный - разбиты на шаги. | Прямой ход состоит из последовательного уменьшения в СЛАУ количества уравнений почти в 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>c_{i} x_{i-1} + b_{i} x_{i} + a_{i} x_{i+1} = f_{i}</math> | ||
| Строка 39: | Строка 81: | ||
при этом | при этом | ||
<math>c^{(1)}_{i} = - c_{i} | <math>c^{(1)}_{i} = - c_{i}c^{(1)}_{i-1}</math>, | ||
<math>a^{(1)}_{i} = - a_{i} | <math>a^{(1)}_{i} = - a_{i}a^{(1)}_{i+1}</math>, | ||
<math>b^{(1)}_{i} = b_{i} - c_{i} | <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} | <math>f^{(1)}_{i} = f_{i} - c_{i}f^{(1)}_{i-1} - a_{i}f^{(1)}_{i+1}</math>. | ||
Для 2го уравнения выполняется его замена на уравнение | Для 2го уравнения выполняется его замена на уравнение | ||
| Строка 53: | Строка 95: | ||
при этом | при этом | ||
<math>a^{(1)}_{2} = - a_{2} | <math>a^{(1)}_{2} = - a_{2}a^{(1)}_{3}</math>, | ||
<math>b^{(1)}_{2} = b_{2} - c_{2} | <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} | <math>f^{(1)}_{2} = f_{2} - c_{2}f^{(1)}_{1} - a_{2}f^{(1)}_{3}</math>. | ||
<math>n-2</math>-е уравнение заменяется на | <math>n-2</math>-е уравнение заменяется на | ||
| Строка 65: | Строка 107: | ||
при этом | при этом | ||
<math>c^{(1)}_{n-2} = - c_{n-2} | <math>c^{(1)}_{n-2} = - c_{n-2}c^{(1)}_{n-3}</math>, | ||
<math>b^{(1)}_{n-2} = b_{n-2} - c_{n-2} | <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_{ | <math>f^{(1)}_{n-2} = f_{n-2} - c_{n-2}f_^{(1)}{n-3} - a_{n-2}f^{(1)}_{n-1}</math>. | ||
== Литература == | == Литература == | ||
<references /> | <references /> | ||
Версия от 12:03, 21 апреля 2016
| Циклическая редукция для трёхдиагональной матрицы, точечный вариант | |
| Последовательный алгоритм | |
| Последовательная сложность | [math]\displaystyle{ O(n) }[/math] |
| Объём входных данных | [math]\displaystyle{ 4n-2 }[/math] |
| Объём выходных данных | [math]\displaystyle{ n }[/math] |
| Параллельный алгоритм | |
| Высота ярусно-параллельной формы | [math]\displaystyle{ O(log n) }[/math] |
| Ширина ярусно-параллельной формы | [math]\displaystyle{ O(n) }[/math] |
Основные авторы описания: А.В.Фролов.
Свойства и структура алгоритма
Общее описание алгоритма
Циклическая редукция - один из вариантов метода исключения неизвестных в приложении к решению СЛАУ[1][2] вида [math]\displaystyle{ Ax = b }[/math], где
- [math]\displaystyle{ 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]\displaystyle{ 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]\displaystyle{ b_{1} x_{1} + a_{1} x_{2} = f_{1} }[/math],
[math]\displaystyle{ c_{i} x_{i-1} + b_{i} x_{i} + a_{i} x_{i+1} = f_{i}, 2 \le i \le n-1 }[/math],
[math]\displaystyle{ c_{n} x_{n-1} + b_{n} x_{n} = f_{n} }[/math].
Циклическая редукция, как и все варианты прогонки, заключается [3][4] в исключении из уравнений неизвестных, однако, в отличие от них, в ней исключение ведут одновременно по всей СЛАУ. В принципе, её можно считать вариантом метода редукции, выполняемого максимально возможное для данной СЛАУ число раз.
Математическое описание алгоритма
Лучше всего схема циклической редукции[3] разработана для случая [math]\displaystyle{ n = 2^{k}-1 }[/math]. Эта схема состоит из прямого и обратного ходов. Прямой ход состоит из последовательного уменьшения в СЛАУ количества уравнений почти в 2 раза (за счёт подстановки из уравнений с нечётными номерами заменяются уравнения с чётными), пока не останется одно уравнение, обратный - в получении всё большего количества компонент решения исходной СЛАУ. Оба хода - как прямой, так и обратный - разбиты на шаги. Здесь мы приведём тот вариант алгоритма, в котором операции экономятся за счёт предварительной нормировки уравнений, используемых для исключения неизвестных.
Прямой ход
Шаг 1
Для каждого из уравнений
[math]\displaystyle{ c_{i} x_{i-1} + b_{i} x_{i} + a_{i} x_{i+1} = f_{i} }[/math]
с нечётными [math]\displaystyle{ i }[/math] выполняется его замена на уравнение
[math]\displaystyle{ c^{(1)}_{i} x_{i-1} + x_{i} + a^{(1)}_{i} x_{i+1} = f^{(1)}_{i} }[/math]
с помощью деления уравнения на [math]\displaystyle{ b_{i} }[/math]:
[math]\displaystyle{ c^{(1)}_{i} = c_{i}/b_{i} }[/math],
[math]\displaystyle{ a^{(1)}_{i} = a_{i}/b_{i} }[/math],
[math]\displaystyle{ f^{(1)}_{i} = f_{i}/b_{i} }[/math].
Уравнение
[math]\displaystyle{ b_{1} x_{1} + a_{1} x_{2} = f_{1} }[/math]
меняется на уравнение
[math]\displaystyle{ x_{i} + a^{(1)}_{1} x_{2} = f^{(1)}_{1} }[/math]:
[math]\displaystyle{ a^{(1)}_{1} = a_{1}/b_{1} }[/math],
[math]\displaystyle{ f^{(1)}_{1} = f_{1}/b_{1} }[/math].
Уравнение
[math]\displaystyle{ c_{n} x_{n-1} + b_{n} x_{n} = f_{n} }[/math]
меняется на уравнение
[math]\displaystyle{ c^{(1)}_{n} x_{n-1} + x_{n} = f^{(1)}_{n} }[/math]:
[math]\displaystyle{ c^{(1)}_{n} = c_{n}/b_{n} }[/math],
[math]\displaystyle{ f^{(1)}_{n} = f_{n}/b_{n} }[/math].
Для каждого же из уравнений
[math]\displaystyle{ c_{i} x_{i-1} + b_{i} x_{i} + a_{i} x_{i+1} = f_{i} }[/math]
с чётными [math]\displaystyle{ i }[/math] (кроме [math]\displaystyle{ 2 }[/math] и [math]\displaystyle{ n-2 }[/math]) выполняется его замена на уравнение
[math]\displaystyle{ c^{(1)}_{i} x_{i-2} + b^{(1)}_{i} x_{i} + a^{(1)}_{i} x_{i+2} = f^{(1)}_{i} }[/math]
при этом
[math]\displaystyle{ c^{(1)}_{i} = - c_{i}c^{(1)}_{i-1} }[/math],
[math]\displaystyle{ a^{(1)}_{i} = - a_{i}a^{(1)}_{i+1} }[/math],
[math]\displaystyle{ b^{(1)}_{i} = b_{i} - c_{i}a^{(1)}_{i-1} - a_{i}c^{(1)}_{i+1} }[/math],
[math]\displaystyle{ f^{(1)}_{i} = f_{i} - c_{i}f^{(1)}_{i-1} - a_{i}f^{(1)}_{i+1} }[/math].
Для 2го уравнения выполняется его замена на уравнение
[math]\displaystyle{ b^{(1)}_{2} x_{2} + a^{(1)}_{2} x_{4} = f^{(1)}_{2} }[/math],
при этом
[math]\displaystyle{ a^{(1)}_{2} = - a_{2}a^{(1)}_{3} }[/math],
[math]\displaystyle{ b^{(1)}_{2} = b_{2} - c_{2}a^{(1)}_{1} - a_{2}c^{(1)}_{3} }[/math],
[math]\displaystyle{ f^{(1)}_{2} = f_{2} - c_{2}f^{(1)}_{1} - a_{2}f^{(1)}_{3} }[/math].
[math]\displaystyle{ n-2 }[/math]-е уравнение заменяется на
[math]\displaystyle{ c^{(1)}_{n-2} x_{n-4} + b^{(1)}_{n-2} x_{n-2} = f^{(1)}_{n-2} }[/math]
при этом
[math]\displaystyle{ c^{(1)}_{n-2} = - c_{n-2}c^{(1)}_{n-3} }[/math],
[math]\displaystyle{ b^{(1)}_{n-2} = b_{n-2} - c_{n-2}a^{(1)}_{n-3} - a_{n-2}c^{(1)}_{n-1} }[/math],
[math]\displaystyle{ f^{(1)}_{n-2} = f_{n-2} - c_{n-2}f_^{(1)}{n-3} - a_{n-2}f^{(1)}_{n-1} }[/math].
Литература
- ↑ Воеводин В.В. Вычислительные основы линейной алгебры. М.: Наука, 1977.
- ↑ Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. М.: Наука, 1984.
- ↑ 3,0 3,1 3,2 Ильин В.П., Кузнецов Ю.И. Трехдиагональные матрицы и их приложения. М.: Наука. Глав-ная редакция физико-математической литературы, 1985г., 208 с.
- ↑ Фролов А.В., Антонов А.С., Воеводин Вл.В., Теплов А.М. Сопоставление разных методов решения одной задачи по методике проекта Algowiki // Параллельные вычислительные технологии (ПаВТ’2016): труды международной научной конференции (г. Архангельск, 28 марта – 1 апреля 2016 г.). Челябинск: Издательский центр ЮУрГУ, 2016. С. 347-360.