Приложение 6: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
[непроверенная версия][непроверенная версия]
(Полностью удалено содержимое страницы)
Строка 1: Строка 1:
 +
= Прогонка, точечный вариант =
  
 +
== Свойства и структура алгоритма ==
 +
 +
=== Общее описание алгоритма ===
 +
 +
'''Прогонка''' - один из вариантов метода исключения неизвестных в приложении к решению СЛАУ<ref name="VOLA">Воеводин В.В. Вычислительные основы линейной алгебры. М.: Наука, 1977.</ref><ref name="MIV">Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. М.: Наука, 1984.</ref> вида <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>
 +
 +
Часто, однако, при изложении сути метода прогонки<ref name="SETKI">Самарский А.А., Николаев Е.С. Методы решения сеточных уравнений. М.: Наука, 1978.</ref> элементы правой части и матрицы системы обозначают и нумеруют по-другому, например СЛАУ может иметь вид (<math>N=n-1</math>)
 +
 +
:<math>
 +
A = \begin{bmatrix}
 +
c_{0} & -b_{0}  & 0      &  \cdots & \cdots & 0 \\
 +
-a_{1} & c_{1}  & -b_{1} &  \cdots & \cdots & 0 \\
 +
0      &  -a_{2} & c_{2} &  \cdots & \cdots & 0 \\
 +
\vdots & \vdots & \ddots & \ddots & \ddots & 0 \\
 +
0 & \cdots & \cdots & -a_{N-1} & c_{N-1}  & -b_{N-1} \\
 +
0 & \cdots & \cdots & 0 & -a_{N}  & c_{N} \\
 +
\end{bmatrix}\begin{bmatrix}
 +
y_{0} \\
 +
y_{1} \\
 +
\vdots \\
 +
y_{N} \\
 +
\end{bmatrix} = \begin{bmatrix}
 +
f_{0} \\
 +
f_{1} \\
 +
\vdots \\
 +
f_{N} \\
 +
\end{bmatrix}
 +
</math>
 +
или, если записывать отдельно по уравнениям, то
 +
:<math>
 +
c_{0} y_{0} - b_{0} y_{1} = f_{0},\\
 +
-a_{i} y_{i-1} + c_{i} y_{i} - b_{i} y_{i+1} = f_{i}, 1 \le i \le N-1, \\
 +
-a_{N} y_{N-1} + c_{N} y_{N} = f_{N}
 +
</math>
 +
 +
Здесь рассматривается тот вариант прогонки, когда проходится вся СЛАУ сверху вниз и обратно. Суть метода - в исключении из уравнений неизвестных, сначала - сверху вниз - под диагональю, а потом - снизу вверх - над диагональю.
 +
 +
[[file:Progonka.png|thumb|right|200px|Рисунок 1. Граф алгоритма прогонки при n=8 без отображения входных и выходных данных. '''/''' - деление, '''''f''''' - операция '''''a+bc''''' или '''''a-bc'''''.]]
 +
 +
=== Математическое описание алгоритма ===
 +
 +
В приведённых обозначениях в прогонке сначала выполняют её прямой ход - вычисляют коэффициенты
 +
 +
:<math>
 +
\alpha_{1} = b_{0}/c_{0},\\
 +
\beta_{1} = f_{0}/c_{0}, \\
 +
\alpha_{i+1} = b_{i}/(c_{i}-a_{i}\alpha_{i}), \quad i = 1, 2, \cdots , N-1, \\
 +
\beta_{i+1} = (f_{i}+a_{i}\beta_{i})/(c_{i}-a_{i}\alpha_{i}), \quad i = 1, 2, \cdots , N.
 +
</math>
 +
после чего вычисляют решение с помощью обратного хода
 +
:<math>
 +
y_{N} = \beta_{N+1}, \\
 +
y_{i} = \alpha_{i+1} y_{i+1} + \beta_{i+1}, \quad i = N-1, N-2, \cdots , 1, 0.
 +
</math>
 +
 +
В литературе<ref name="SETKI" /> указывается, что данные формулы эквивалентны вычислению одного из <math>LU</math>-разложений матрицы системы с последующим решением двухдиагональных систем методом обратной подстановки.
 +
 +
=== Вычислительное ядро алгоритма ===
 +
 +
Вычислительное ядро алгоритма можно представить из двух частей - прямого и обратного хода. В прямом ходе ядро составляют последовательности операций деления, умножения и сложения/вычитания. В обратном ходе в ядре остаются только последовательности умножения и сложения.
 +
[[file:ProgonkaInv.png|thumb|left|420px|Рисунок 2. Детальный граф алгоритма прогонки с однократным вычислением обратных чисел при n=4 без отображения входных и выходных данных. '''inv''' - вычисление обратного числа, '''mult''' - операция перемножения чисел. Серым выделены операции, повторяющиеся при замене правой части СЛАУ]]
 +
 +
=== Макроструктура алгоритма ===
 +
 +
Кроме представления макроструктуры алгоритма как совокупности прямого и обратного хода, прямой ход также может быть разложен на две макроединицы - разложения матрицы и прямого хода решения двухдиагональной СЛАУ, которые выполняются "одновременно", т.е., параллельно друг другу. При этом решение двухдиагональной СЛАУ использует результаты разложения. 
 +
 +
=== Схема реализации последовательного алгоритма ===
 +
 +
Последовательность исполнения метода следующая:
 +
 +
1. Инициализируется прямой ход прогонки:
 +
 +
:<math>
 +
\alpha_{1} = b_{0}/c_{0},\\
 +
\beta_{1} = f_{0}/c_{0}, \\
 +
</math>
 +
 +
2. Последовательно для всех i от 1 до N-1 выполняются формулы прямого хода:
 +
 +
:<math>
 +
\alpha_{i+1} = b_{i}/(c_{i}-a_{i}\alpha_{i}), \\
 +
\beta_{i+1} = (f_{i}+a_{i}\beta_{i})/(c_{i}-a_{i}\alpha_{i}).
 +
</math>
 +
 +
3. Инициализируется обратный ход прогонки:
 +
 +
:<math>
 +
y_{N} = (f_{N}+a_{N}\beta_{N})/(c_{N}-a_{N}\alpha_{N})
 +
</math>
 +
 +
4. Последовательно для всех i с убыванием от N-1 до 0 выполняются формулы обратного хода:
 +
:<math>
 +
y_{i} = \alpha_{i+1} y_{i+1} + \beta_{i+1}.
 +
</math>
 +
 +
В связи с тем, что почти во всех формулах есть пары делений на одно и то же выражение, можно поменять их на последовательности вычисления обратных чисел с последующими умножениями на них.
 +
 +
=== Последовательная сложность алгоритма ===
 +
 +
Для выполнения прогонки в трёхдиагональной СЛАУ из n уравнений с n неизвестными в последовательном (наиболее быстром) варианте требуется:
 +
 +
* <math>2n-1</math> делений,
 +
* <math>3n-3</math> сложений/вычитаний,
 +
* <math>3n-3</math> умножений.
 +
 +
При классификации по последовательной сложности, таким образом, прогонка относится к алгоритмам ''с линейной сложностью''.
 +
 +
=== Информационный граф ===
 +
 +
Информационный граф прогонки изображён на рис.1. Как видно, он почти последователен: при выполнении прямого хода две ветви (левая - разложение матрицы, центральная - решение первой из двухдиагональных систем) могут выполняться параллельно друг другу. Правая ветвь соответствует обратному ходу. По рисунку видно, что не только математическая суть обработки элементов векторов, но даже структура графа алгоритма и направление потоков данных в нём вполне соответствуют названию "обратный ход".
 +
Вариант с заменой делений даёт граф, который изображён на рис.2.
 +
 +
=== Описание ресурса параллелизма алгоритма ===
 +
 +
Для выполнения прогонки в трёхдиагональной СЛАУ из n уравнений с n неизвестными в параллельном варианте требуется последовательно выполнить следующие ярусы:
 +
 +
* <math>n</math> ярусов делений (в каждом из ярусов, кроме одного, по 2 деления),
 +
* по <math>2n - 2</math> ярусов умножений и сложений/вычитаний (в n-1 ярусах - по 2 операции, в n-1 - по одной).
 +
 +
При классификации по высоте ЯПФ, таким образом, прогонка относится к алгоритмам со сложностью <math>O(n)</math>. При классификации по ширине ЯПФ его сложность будет <math>2</math>.
 +
 +
=== Входные и выходные данные алгоритма ===
 +
 +
'''Входные данные''': трёхдиагональная матрица <math>A</math> (элементы <math>a_{ij}</math>), вектор <math>b</math> (элементы <math>b_{i}</math>).
 +
 +
'''Выходные данные''': вектор <math>x</math> (элементы <math>x_{i}</math>).
 +
 +
'''Объём выходных данных''': <math>n</math>.
 +
 +
=== Свойства алгоритма ===
 +
 +
Соотношение последовательной и параллельной сложности, как хорошо видно, является ''константой'' (причём менее 2).
 +
 +
При этом вычислительная мощность алгоритма, как отношение числа операций к суммарному объему входных и выходных данных – тоже ''константа''.
 +
 +
Алгоритм в рамках выбранной версии полностью детерминирован.
 +
 +
Обычно прогонка используется для решения СЛАУ с диагональным преобладанием. Тогда гарантируется устойчивость алгоритма.
 +
В случае, когда требуется решение нескольких СЛАУ с одной и той же матрицей, левую ветвь вычислений (см. рисунки с графом алгоритма) можно не повторять. Это связано с тем, что <math>LU</math>-разложение матрицы системы не нужно перевычислять. Тогда предпочтителен вариант с заменой делений.
 +
 +
== Литература ==
 +
 +
<references />

Версия 17:03, 16 сентября 2015

1 Прогонка, точечный вариант

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

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]N=n-1[/math])

[math] A = \begin{bmatrix} c_{0} & -b_{0} & 0 & \cdots & \cdots & 0 \\ -a_{1} & c_{1} & -b_{1} & \cdots & \cdots & 0 \\ 0 & -a_{2} & c_{2} & \cdots & \cdots & 0 \\ \vdots & \vdots & \ddots & \ddots & \ddots & 0 \\ 0 & \cdots & \cdots & -a_{N-1} & c_{N-1} & -b_{N-1} \\ 0 & \cdots & \cdots & 0 & -a_{N} & c_{N} \\ \end{bmatrix}\begin{bmatrix} y_{0} \\ y_{1} \\ \vdots \\ y_{N} \\ \end{bmatrix} = \begin{bmatrix} f_{0} \\ f_{1} \\ \vdots \\ f_{N} \\ \end{bmatrix} [/math]

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

[math] c_{0} y_{0} - b_{0} y_{1} = f_{0},\\ -a_{i} y_{i-1} + c_{i} y_{i} - b_{i} y_{i+1} = f_{i}, 1 \le i \le N-1, \\ -a_{N} y_{N-1} + c_{N} y_{N} = f_{N} [/math]

Здесь рассматривается тот вариант прогонки, когда проходится вся СЛАУ сверху вниз и обратно. Суть метода - в исключении из уравнений неизвестных, сначала - сверху вниз - под диагональю, а потом - снизу вверх - над диагональю.

Рисунок 1. Граф алгоритма прогонки при n=8 без отображения входных и выходных данных. / - деление, f - операция a+bc или a-bc.

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

В приведённых обозначениях в прогонке сначала выполняют её прямой ход - вычисляют коэффициенты

[math] \alpha_{1} = b_{0}/c_{0},\\ \beta_{1} = f_{0}/c_{0}, \\ \alpha_{i+1} = b_{i}/(c_{i}-a_{i}\alpha_{i}), \quad i = 1, 2, \cdots , N-1, \\ \beta_{i+1} = (f_{i}+a_{i}\beta_{i})/(c_{i}-a_{i}\alpha_{i}), \quad i = 1, 2, \cdots , N. [/math]

после чего вычисляют решение с помощью обратного хода

[math] y_{N} = \beta_{N+1}, \\ y_{i} = \alpha_{i+1} y_{i+1} + \beta_{i+1}, \quad i = N-1, N-2, \cdots , 1, 0. [/math]

В литературе[3] указывается, что данные формулы эквивалентны вычислению одного из [math]LU[/math]-разложений матрицы системы с последующим решением двухдиагональных систем методом обратной подстановки.

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

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

Рисунок 2. Детальный граф алгоритма прогонки с однократным вычислением обратных чисел при n=4 без отображения входных и выходных данных. inv - вычисление обратного числа, mult - операция перемножения чисел. Серым выделены операции, повторяющиеся при замене правой части СЛАУ

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

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

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

Последовательность исполнения метода следующая:

1. Инициализируется прямой ход прогонки:

[math] \alpha_{1} = b_{0}/c_{0},\\ \beta_{1} = f_{0}/c_{0}, \\ [/math]

2. Последовательно для всех i от 1 до N-1 выполняются формулы прямого хода:

[math] \alpha_{i+1} = b_{i}/(c_{i}-a_{i}\alpha_{i}), \\ \beta_{i+1} = (f_{i}+a_{i}\beta_{i})/(c_{i}-a_{i}\alpha_{i}). [/math]

3. Инициализируется обратный ход прогонки:

[math] y_{N} = (f_{N}+a_{N}\beta_{N})/(c_{N}-a_{N}\alpha_{N}) [/math]

4. Последовательно для всех i с убыванием от N-1 до 0 выполняются формулы обратного хода:

[math] y_{i} = \alpha_{i+1} y_{i+1} + \beta_{i+1}. [/math]

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

1.1.6 Последовательная сложность алгоритма

Для выполнения прогонки в трёхдиагональной СЛАУ из n уравнений с n неизвестными в последовательном (наиболее быстром) варианте требуется:

  • [math]2n-1[/math] делений,
  • [math]3n-3[/math] сложений/вычитаний,
  • [math]3n-3[/math] умножений.

При классификации по последовательной сложности, таким образом, прогонка относится к алгоритмам с линейной сложностью.

1.1.7 Информационный граф

Информационный граф прогонки изображён на рис.1. Как видно, он почти последователен: при выполнении прямого хода две ветви (левая - разложение матрицы, центральная - решение первой из двухдиагональных систем) могут выполняться параллельно друг другу. Правая ветвь соответствует обратному ходу. По рисунку видно, что не только математическая суть обработки элементов векторов, но даже структура графа алгоритма и направление потоков данных в нём вполне соответствуют названию "обратный ход". Вариант с заменой делений даёт граф, который изображён на рис.2.

1.1.8 Описание ресурса параллелизма алгоритма

Для выполнения прогонки в трёхдиагональной СЛАУ из n уравнений с n неизвестными в параллельном варианте требуется последовательно выполнить следующие ярусы:

  • [math]n[/math] ярусов делений (в каждом из ярусов, кроме одного, по 2 деления),
  • по [math]2n - 2[/math] ярусов умножений и сложений/вычитаний (в n-1 ярусах - по 2 операции, в n-1 - по одной).

При классификации по высоте ЯПФ, таким образом, прогонка относится к алгоритмам со сложностью [math]O(n)[/math]. При классификации по ширине ЯПФ его сложность будет [math]2[/math].

1.1.9 Входные и выходные данные алгоритма

Входные данные: трёхдиагональная матрица [math]A[/math] (элементы [math]a_{ij}[/math]), вектор [math]b[/math] (элементы [math]b_{i}[/math]).

Выходные данные: вектор [math]x[/math] (элементы [math]x_{i}[/math]).

Объём выходных данных: [math]n[/math].

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

Соотношение последовательной и параллельной сложности, как хорошо видно, является константой (причём менее 2).

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

Алгоритм в рамках выбранной версии полностью детерминирован.

Обычно прогонка используется для решения СЛАУ с диагональным преобладанием. Тогда гарантируется устойчивость алгоритма. В случае, когда требуется решение нескольких СЛАУ с одной и той же матрицей, левую ветвь вычислений (см. рисунки с графом алгоритма) можно не повторять. Это связано с тем, что [math]LU[/math]-разложение матрицы системы не нужно перевычислять. Тогда предпочтителен вариант с заменой делений.

1.2 Литература

  1. ↑ Воеводин В.В. Вычислительные основы линейной алгебры. М.: Наука, 1977.
  2. ↑ Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. М.: Наука, 1984.
  3. ↑ 3,0 3,1 Самарский А.А., Николаев Е.С. Методы решения сеточных уравнений. М.: Наука, 1978.
Источник — https://algowiki-project.org/w/ru/index.php?title=Приложение_6&oldid=2524