Полный метод циклической редукции: различия между версиями
| [непроверенная версия] | [непроверенная версия] |
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 /> | ||
Версия 15:03, 21 апреля 2016
| Циклическая редукция для трёхдиагональной матрицы, точечный вариант | |
| Последовательный алгоритм | |
| Последовательная сложность | [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.2 Математическое описание алгоритма
Лучше всего схема циклической редукции[3] разработана для случая [math]n = 2^{k}-1[/math]. Эта схема состоит из прямого и обратного ходов. Прямой ход состоит из последовательного уменьшения в СЛАУ количества уравнений почти в 2 раза (за счёт подстановки из уравнений с нечётными номерами заменяются уравнения с чётными), пока не останется одно уравнение, обратный - в получении всё большего количества компонент решения исходной СЛАУ. Оба хода - как прямой, так и обратный - разбиты на шаги. Здесь мы приведём тот вариант алгоритма, в котором операции экономятся за счёт предварительной нормировки уравнений, используемых для исключения неизвестных.
1.2.1 Прямой ход
1.2.1.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 Литература
- ↑ Воеводин В.В. Вычислительные основы линейной алгебры. М.: Наука, 1977.
- ↑ Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. М.: Наука, 1984.
- ↑ 3,0 3,1 3,2 Ильин В.П., Кузнецов Ю.И. Трехдиагональные матрицы и их приложения. М.: Наука. Глав-ная редакция физико-математической литературы, 1985г., 208 с.
- ↑ Фролов А.В., Антонов А.С., Воеводин Вл.В., Теплов А.М. Сопоставление разных методов решения одной задачи по методике проекта Algowiki // Параллельные вычислительные технологии (ПаВТ’2016): труды международной научной конференции (г. Архангельск, 28 марта – 1 апреля 2016 г.). Челябинск: Издательский центр ЮУрГУ, 2016. С. 347-360.
