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

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

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

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

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

Исходные данные: правая треугольная матрица $U$ (элементы $u_{ij}$), вектор правой части $y$ (элементы $y_{i}$).

Вычисляемые данные: вектор решения $x$ (элементы $x_{i}$).

Формулы метода:

$\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}$

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

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

Вычислительное ядро обратного хода метода Гаусса можно составить из множественных (всего их $n$) вычислений скалярных произведений строк матрицы $U$ на уже вычисленную часть вектора $x$:

$\sum_{j = i+1}^{n} u_{ij} x_{j}$

в режиме накопления или без него, в зависимости от требований задачи, с их последующим вычитанием из компоненты вектора $y$ и деления на диагональный элемент матрицы $U$. В отечественных реализациях, даже в последовательных, упомянутый способ представления не используется. Дело в том, что даже в этих реализациях метода вычисление сумм типа

$y_{i} - \sum_{j = i+1}^{n} u_{ij} x_{j}$

в которых и встречаются скалярные произведения, ведутся не в порядке «вычислили скалярное произведение, а потом вычли его из элемента», а путём вычитания из элемента покомпонентных произведений, являющихся частями скалярных произведений. Поэтому следует считать вычислительным ядром метода не вычисления скалярных произведений, а вычисления выражений

$y_{i} - \sum_{j = i+1}^{n} u_{ij} x_{j}$

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

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

Как уже записано в описании ядра алгоритма, основную часть метода составляют множественные (всего $n-1$) вычисления сумм

$y_{i} - \sum_{j = i+1}^{n} u_{ij} x_{j}$

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

1.5 Описание схемы реализации последовательного алгоритма

Чтобы понять последовательность исполнения, перепишем формулы метода так:

1. $x_{n} = y_{n}/u_{nn}$

Далее для всех $i$ от $n-1$ до $1$ по убыванию выполняются

2. $x_{i} = \left (y_{i} - \sum_{j = i+1}^{n} u_{ij} x_{j} \right ) / u_{ii}$

Особо отметим, что вычисления сумм вида $y_{i} - \sum_{j = i+1}^{n} u_{ij} x_{j}$ производят в режиме накопления вычитанием из $y_{i}$ произведений $u_{ij} x_{j}$ для $j$ от $n$ до $i + 1$, c убыванием $j$. Другие порядки выполнения суммирования приводят к резкому ухудшению параллельных свойств алгоритма, хотя, к сожалению, остаются кое-где в литературе и пакетах программ.

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

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

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

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

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

описание