Обратная подстановка (вещественный вариант)

Описание свойств и структуры алгоритма

Словесное описание алгоритма

Обратный ход метода Гаусса - решение СЛАУ [math]\displaystyle{ Ux = y }[/math] с правой треугольной матрицей [math]\displaystyle{ U }[/math]. Матрица [math]\displaystyle{ U }[/math] - одна из составляющих матрицы [math]\displaystyle{ A }[/math] и получается либо из [math]\displaystyle{ LU }[/math]-разложения последней каким-либо из многочисленных способов (например, простое разложение Гаусса, разложение Гаусса с выбором ведущего элемента, компактная схема Гаусса, разложение Холецкого и др.), либо из других разложений. В силу треугольности [math]\displaystyle{ U }[/math] решение СЛАУ является одной из модификаций общего метода подстановки и записывается простыми формулами.

Математическое описание

Исходные данные: правая треугольная матрица [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 }[/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]. Другие порядки выполнения суммирования приводят к резкому ухудшению параллельных свойств алгоритма, хотя, к сожалению, остаются кое-где в литературе и пакетах программ.

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

Для обратного хода метода Гаусса порядка n в последовательном (наиболее быстром) варианте требуется:

• [math]\displaystyle{ n }[/math] делений,
• по [math]\displaystyle{ \frac{n^2-n}{2} }[/math] умножений и сложений (вычитаний) — основная часть алгоритма.

При этом использование режима накопления требует совершения умножений и вычитаний в режиме двойной точности (или использования функции вроде DPROD в Фортране), что ещё больше увеличивает долю умножений и сложений/вычитаний во времени, требуемом для выполнения обратного хода метода Гаусса.

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

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

Опишем граф алгоритма как аналитически, так и в виде рисунка.

Граф алгоритма состоит из двух групп вершин, расположенных в целочисленных узлах двух областей разной размерности.

описание

Первая группа вершин расположена в одномерной области, соответствующая ей операция вычисляет функцию деления. Естественно введённая единственная координата каждой из вершин [math]\displaystyle{ i }[/math] меняется в диапазоне от [math]\displaystyle{ 1 }[/math] до [math]\displaystyle{ n }[/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 - b * c }[/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];

Результат срабатывания операции является промежуточным данным алгоритма.

Описанный граф можно посмотреть на рисунке, выполненном для случая [math]\displaystyle{ n = 5 }[/math]. Здесь вершины первой группы обозначены розовым цветом и знаком деления, вершины второй — зелёным цветом и буквой f. Изображена подача только входных данных из вектора [math]\displaystyle{ y_{i} }[/math], подача элементов матрицы [math]\displaystyle{ U }[/math], идущая во все вершины, на рисунке не представлена.