Теория и практика параллельных вычислений
Прямой ход алгоритма Гаусса
Прямой ход метода Гаусса состоит в последовательном исключении неизвестных в уравнениях решаемой системы линейных уравнений. На итерации i, 0i<n-1, метода производится исключение неизвестной i для всех уравнений с номерами k, большими i (т.е. i<kn-1). Для этого из этих уравнений осуществляется вычитание строки i, умноженной на константу (aki/aii), с тем чтобы результирующий коэффициент при неизвестной xi в строках оказался нулевым – все необходимые вычисления могут быть определены при помощи соотношений:
(следует отметить, что аналогичные вычисления выполняются и над вектором b).
Поясним выполнение прямого хода метода Гаусса на примере системы линейных уравнений вида:
На первой итерации производится исключение неизвестной x0 из второй и третьей строки. Для этого из этих строк нужно вычесть первую строку, умноженную соответственно на 2 и 1. После этих преобразований система уравнений принимает вид:
В результате остается выполнить последнюю итерацию и исключить неизвестную x1 из третьего уравнения. Для этого необходимо вычесть вторую строку, и в окончательной форме система имеет следующий вид:
На рис. 8.1 представлена общая схема состояния данных на i-й итерации прямого хода алгоритма Гаусса. Все коэффициенты при неизвестных, расположенные ниже главной диагонали и левее столбца i, уже являются нулевыми. На i-й итерации прямого хода метода Гаусса осуществляется обнуление коэффициентов столбца i, расположенных ниже главной диагонали, путем вычитания строки i, умноженной на нужную ненулевую константу. После проведения (n-1) подобной итерации матрица, определяющая систему линейных уравнений, становится приведенной к верхнему треугольному виду.
Рис. 8.1. Итерация прямого хода алгоритма Гаусса
При выполнении прямого хода метода Гаусса строка, которая используется для исключения неизвестных, носит наименование ведущей, а диагональный элемент ведущей строки называется ведущим элементом. Как можно заметить, выполнение вычислений является возможным только, если ведущий элемент имеет ненулевое значение. Более того, если ведущий элемент ai,i имеет малое значение, то деление и умножение строк на этот элемент может приводить к накоплению вычислительной погрешности и вычислительной неустойчивости алгоритма.
Возможный способ избежать подобной проблемы может состоять в следующем: при выполнении каждой очередной итерации прямого хода метода Гаусса следует определить коэффициент с максимальным значением по абсолютной величине в столбце, соответствующем исключаемой неизвестной, т.е.
и выбрать в качестве ведущей строку, в которой этот коэффициент располагается (данная схема выбора ведущего значения носит наименование метода главных элементов).
Вычислительная сложность прямого хода алгоритма Гаусса с выбором ведущей строки имеет порядок O(n3).
