Теория и практика параллельных вычислений
Обратный ход алгоритма Гаусса
После приведения матрицы коэффициентов к верхнему треугольному виду становится возможным определение значений неизвестных. Из последнего уравнения преобразованной системы может быть вычислено значение переменной xn-1, после этого из предпоследнего уравнения становится возможным определение переменной xn-2 и т.д. В общем виде выполняемые вычисления при обратном ходе метода Гаусса могут быть представлены при помощи соотношений:
Поясним, как и ранее, выполнение обратного хода метода Гаусса на примере рассмотренной в п. 8.2.1.1 системы линейных уравнений
Из последнего уравнения системы можно определить, что неизвестная x2 имеет значение 3. В результате становится возможным разрешение второго уравнения и определение значение неизвестной x1=13, т.е.
На последней итерации обратного хода метода Гаусса определяется значение неизвестной x0, равное -44.
С учетом последующего параллельного выполнения можно отметить, что вычисление получаемых значений неизвестных может выполняться сразу во всех уравнениях системы (и эти действия могут выполняться в уравнениях одновременно и независимо друг от друга). Так, в рассматриваемом примере после определения значения неизвестной x2 система уравнений может быть приведена к виду
Вычислительная сложность обратного хода алгоритма Гаусса составляет O(n2).
