Приложение 3
Обратная подстановка метода Гаусса (вещественный вариант)
Свойства и структура алгоритма
Общее описание алгоритма
Обратная подстановка - решение системы линейных алгебраических уравнений (СЛАУ) [math]\displaystyle{ Ux = y }[/math] с верхней треугольной матрицей [math]\displaystyle{ U }[/math]. Матрица [math]\displaystyle{ U }[/math] может быть одной из составляющих матрицы [math]\displaystyle{ A }[/math] в каких-либо разложениях и получается либо из [math]\displaystyle{ LU }[/math]-разложения последней каким-либо из многочисленных способов (например, простое разложение Гаусса, разложение Гаусса с выбором ведущего элемента, компактная схема Гаусса, разложение Холецкого и др.), либо из других (например из QR-разложения). В силу треугольности [math]\displaystyle{ U }[/math] решение СЛАУ является одной из модификаций общего метода подстановки и записывается простыми формулами.
В[1] методом обратной подстановки назван также и метод решения СЛАУ с нижней треугольной матрицей. Там же отмечено, что в литературе иногда под обратной подстановкой имеют в виду, как и здесь, только решения СЛАУ с верхней треугольной матрицей, а решение нижних треугольных систем называют прямой подстановкой. Такой же системы названий будем придерживаться и здесь, во избежание одноимённого названия разных алгоритмов. Кроме того, обратная подстановка, представленная здесь, одновременно может быть частью метода Гаусса для решения СЛАУ, а именно - его обратным ходом, чего нельзя сказать про прямую подстановку.
Существует метод со сходным названием - Обратная подстановка с нормировкой. При том, что он решает, по существу, ту же задачу, что и простая обратная подстановка, его схема несколько сложнее. Это связано со специальными мерами по уменьшению влияния ошибок округления на результат. Обратная подстановка с нормировкой на данной странице не рассматривается.
Математическое описание алгоритма
Исходные данные: верхняя треугольная матрица [math]\displaystyle{ U }[/math] (элементы [math]\displaystyle{ u_{ij} }[/math]), вектор правой части [math]\displaystyle{ y }[/math] (элементы [math]\displaystyle{ y_{i} }[/math]).
Вычисляемые данные: вектор решения [math]\displaystyle{ x }[/math] (элементы [math]\displaystyle{ x_{i} }[/math]).
Формулы метода:
- [math]\displaystyle{ \begin{align} x_{n} & = y_{n}/u_{nn} \\ x_{i} & = \left (y_{i} - \sum_{j = i+1}^{n} u_{ij} x_{j} \right ) / u_{ii}, \quad i \in [1, n - 1]. \end{align} }[/math]
Существует также блочная версия метода, однако в данном описании разобран только точечный метод.
Вычислительное ядро алгоритма
Вычислительное ядро обратной подстановки можно составить из множественных (всего их [math]\displaystyle{ n-1 }[/math]) вычислений скалярных произведений подстрок матрицы [math]\displaystyle{ U }[/math] на уже вычисленную часть вектора [math]\displaystyle{ x }[/math]:
- [math]\displaystyle{ \sum_{j = i+1}^{n} u_{ij} x_{j} }[/math]
в режиме накопления или без него, в зависимости от требований задачи, с их последующим вычитанием из компоненты вектора [math]\displaystyle{ y }[/math] и деления на диагональный элемент матрицы [math]\displaystyle{ U }[/math]. В отечественных реализациях, даже в последовательных, упомянутый способ представления не используется. Дело в том, что даже в этих реализациях метода вычисление сумм типа
- [math]\displaystyle{ y_{i} - \sum_{j = i+1}^{n} u_{ij} x_{j} }[/math]
в которых и встречаются скалярные произведения, ведутся не в порядке «вычислили скалярное произведение, а потом вычли его из элемента», а путём вычитания из элемента покомпонентных произведений, являющихся частями скалярных произведений. Поэтому следует считать вычислительным ядром метода не вычисления скалярных произведений, а вычисления выражений
- [math]\displaystyle{ y_{i} - \sum_{j = i+1}^{n} u_{ij} x_{j} }[/math]
в режиме накопления или без него, в зависимости от требований задачи, плюс деления результатов этих вычислений на диагональные элементы матрицы.
Макроструктура алгоритма
Как уже записано в описании ядра алгоритма, основную часть метода обратной подстановки составляют множественные (всего [math]\displaystyle{ n-1 }[/math]) вычисления сумм
- [math]\displaystyle{ y_{i} - \sum_{j = i+1}^{n} u_{ij} x_{j} }[/math]
в режиме накопления или без него, плюс деления результатов этих вычислений на диагональные элементы матрицы.
Схема реализации последовательного алгоритма
Последовательность исполнения такова:
1. [math]\displaystyle{ x_{n} = y_{n}/u_{nn} }[/math]
Далее для всех [math]\displaystyle{ i }[/math] от [math]\displaystyle{ n-1 }[/math] до [math]\displaystyle{ 1 }[/math] по убыванию выполняются
2. [math]\displaystyle{ x_{i} = \left (y_{i} - \sum_{j = i+1}^{n} u_{ij} x_{j} \right ) / u_{ii} }[/math]
Особо отметим, что вычисления сумм вида [math]\displaystyle{ y_{i} - \sum_{j = i+1}^{n} u_{ij} x_{j} }[/math] производят в режиме накопления вычитанием из [math]\displaystyle{ y_{i} }[/math] произведений [math]\displaystyle{ u_{ij} x_{j} }[/math] для [math]\displaystyle{ j }[/math] от [math]\displaystyle{ n }[/math] до [math]\displaystyle{ i + 1 }[/math], c убыванием [math]\displaystyle{ j }[/math]. Другие порядки выполнения суммирования приводят к резкому ухудшению параллельных свойств алгоритма, хотя, к сожалению, остаются кое-где в литературе и пакетах программ. В качестве примера такого порядка можно привести фрагмент программы из[2], где обратная подстановка является обратным ходом в методе Гаусса, а возрастание индекса суммирования связано, в основном, с ограничениями используемого авторами книги старого диалекта Фортрана.
Последовательная сложность алгоритма
Для обратной подстановки в случае решения линейной системы с верхней треугольной матрицей порядка [math]\displaystyle{ n }[/math] в последовательном (наиболее быстром) варианте требуется:
- [math]\displaystyle{ n }[/math] делений,
- [math]\displaystyle{ \frac{n^2-n}{2} }[/math] сложений (вычитаний),
- [math]\displaystyle{ \frac{n^2-n}{2} }[/math] умножений.
Умножения и сложения (вычитания) — основная часть алгоритма.
При этом использование режима накопления требует совершения умножений и вычитаний в режиме двойной точности (или использования функции вроде DPROD в Фортране).
При классификации по последовательной сложности, таким образом, метод обратной подстановки относится к алгоритмам со сложностью [math]\displaystyle{ O(n^2) }[/math].
Информационный граф
Опишем граф алгоритма как аналитически, так и в виде рисунка.
Граф алгоритма обратной подстановки состоит из двух групп вершин, расположенных в целочисленных узлах двух областей разной размерности.
Первая группа вершин расположена в одномерной области, соответствующая ей операция вычисляет функцию деления. Естественно введённая единственная координата каждой из вершин [math]\displaystyle{ i }[/math] меняется в диапазоне от [math]\displaystyle{ n }[/math] до [math]\displaystyle{ 1 }[/math], принимая все целочисленные значения.
Делимое в этой операции:
- при [math]\displaystyle{ i = n }[/math] — элемент входных данных, а именно [math]\displaystyle{ y_{n} }[/math];
- при [math]\displaystyle{ i \lt n }[/math] — результат срабатывания операции, соответствующей вершине из второй группы, с координатами [math]\displaystyle{ i }[/math], [math]\displaystyle{ i+1 }[/math].
Делитель для этой операции - элемент входных данных, а именно [math]\displaystyle{ u_{nn} }[/math].
Результат срабатывания операции является выходным данным [math]\displaystyle{ x_{i} }[/math].
Вторая группа вершин расположена в двумерной области, соответствующая ей операция [math]\displaystyle{ a-bc }[/math]. Естественно введённые координаты области таковы:
- [math]\displaystyle{ i }[/math] — меняется в диапазоне от [math]\displaystyle{ n-1 }[/math] до [math]\displaystyle{ 1 }[/math], принимая все целочисленные значения;
- [math]\displaystyle{ j }[/math] — меняется в диапазоне от [math]\displaystyle{ n }[/math] до [math]\displaystyle{ i+1 }[/math], принимая все целочисленные значения.
Аргументы операции следующие:
- [math]\displaystyle{ a }[/math]:
- при [math]\displaystyle{ j = n }[/math] элемент входных данных [math]\displaystyle{ y_{i} }[/math];
- при [math]\displaystyle{ j \lt n }[/math] — результат срабатывания операции, соответствующей вершине из второй группы, с координатами [math]\displaystyle{ i, j+1 }[/math];
- [math]\displaystyle{ b }[/math] — элемент входных данных, а именно [math]\displaystyle{ u_{ij} }[/math];
- [math]\displaystyle{ c }[/math] — результат срабатывания операции, соответствующей вершине из первой группы, с координатой [math]\displaystyle{ j }[/math].
Результат срабатывания операции является промежуточным данным алгоритма.
Описанный граф можно посмотреть на рис. 1, выполненном для случая [math]\displaystyle{ n = 5 }[/math]. Здесь вершины первой группы обозначены жёлтым цветом и знаком деления, вершины второй — зелёным цветом и буквой f. Изображена подача только входных данных из вектора [math]\displaystyle{ y }[/math], подача элементов матрицы [math]\displaystyle{ U }[/math], идущая во все вершины, на рисунке не представлена.
Ресурс параллелизма алгоритма
Для обратной подстановки в случае решения линейной системы с верхней треугольной матрицей порядка [math]\displaystyle{ n }[/math] в параллельном варианте требуется последовательно выполнить следующие ярусы:
- [math]\displaystyle{ n }[/math] ярусов делений (в каждом из ярусов одно деление),
- по [math]\displaystyle{ n - 1 }[/math] ярусов умножений и сложений/вычитаний (в каждом из ярусов — линейное количество операций, от [math]\displaystyle{ 1 }[/math] до [math]\displaystyle{ n-1 }[/math].
Таким образом, в параллельном варианте, в отличие от последовательного, вычисления делений будут определять довольно значительную долю требуемого времени. При реализации на конкретных архитектурах наличие в отдельных ярусах ЯПФ отдельных делений может породить и другие проблемы. Например, при реализации метода обратной подстановки на ПЛИСах остальные вычисления (умножения и сложения/вычитания) могут быть конвейеризованы, что даёт экономию и по ресурсам на программируемых платах; деления из-за их изолированности приведут к занятию ресурсов на платах, которые будут простаивать большую часть времени.
При этом использование режима накопления требует совершения умножений и вычитаний в режиме двойной точности, а в параллельном варианте это означает, что практически все промежуточные вычисления для выполнения алгоритма в режиме накопления должны быть двойной точности. В отличие от последовательного варианта это означает некоторое увеличение требуемой памяти.
При классификации по высоте ЯПФ, таким образом, метод обратной подстановки относится к алгоритмам с линейной сложностью. При классификации по ширине ЯПФ его сложность также будет линейной.
Входные и выходные данные алгоритма
Входные данные: верхняя треугольная матрица [math]\displaystyle{ U }[/math] (элементы [math]\displaystyle{ u_{ij} }[/math]), вектор правой части [math]\displaystyle{ y }[/math] (элементы [math]\displaystyle{ y_{i} }[/math]).
Объём входных данных: :[math]\displaystyle{ \frac{n (n + 3)}{2} }[/math] (в силу треугольности достаточно хранить только ненулевые элементы матрицы [math]\displaystyle{ U }[/math]).
Выходные данные: вектор решения [math]\displaystyle{ x }[/math] (элементы [math]\displaystyle{ x_{i} }[/math]).
Объём выходных данных: :[math]\displaystyle{ n~. }[/math]
Свойства алгоритма
Соотношение последовательной и параллельной сложности в случае неограниченных ресурсов, как хорошо видно, является линейным (отношение квадратической к линейной).
При этом вычислительная мощность алгоритма обратной подстановки, как отношение числа операций к суммарному объему входных и выходных данных – всего лишь константа.
При этом алгоритм обратной подстановки полностью детерминирован. Использование другого порядка выполнения ассоциативных операций в данной версии нами не рассматривается, поскольку в корне меняет структуру алгоритма и меняет сложность с линейной на квадратичную.
Наличие линейного количества ярусов ЯПФ, состоящих из одного-единственного деления, потенциально замедляющее параллельные реализации алгоритма, является его характерным "узким местом", особенно в сравнении со схожей по решаемой математической задаче прямой подстановке, где диагональные элементы единичны. В связи с этим для решения СЛАУ предпочтительны такие разложения, содержащие треугольные матрицы, где в треугольных матрицах диагональные элементы единичны. В тех же случаях, когда получаются неособенные треугольные матрицы, их желательно предварительно, до решения СЛАУ с ними, преобразовать в произведение диагональной и треугольной с единичными диагональными элементами.
У алгоритма обратной подстановки существует несколько блочных вариантов. Граф некоторых из них совпадает с графом точечного варианта, различия связаны в основном с порядком прохождения основных циклов алгоритма, а именно - с их развёртыванием и перестановкой. Эти приёмы могут помочь в оптимизации обменов на конкретных вычислительных системах.