Метод Гаусса для решения СЛАУ, вычисления определителей и обращения матриц

Среди прямых методов наиболее простым и популярным при решении систем порядка до 200-400 (в зависимости от быстродействия используемого компьютера) является метод Гаусса, известный под названием метода последовательного исключения переменных или метода Гауссовых исключений.

Основывается он на том, что любую вектор-строку в матрице можно заменить ее линейной комбинацией с любой другой вектор-строкой этой же матрицы (это справедливо и для вектор-столбцов). Вычитая последовательно из каждой j-й строки каждую вышележащую i-ю (i<j), предварительно умноженную на (a_ji/a_ii), мы удалим из неё составляющую вектора x с номерами меньше j. Таким образом, все строки, кроме первой, будут содержать ненулевые элементы только вправо начиная с главной диагонали – матрица превратится в верхнюю треугольную, а в последней строке будет только один элемент, что соответствует уравнению вида c_nnx_n=d_n, из которого можно без труда вычислить x_n.

На этом завершается так называемый прямой ход алгоритма Гаусса. Обратный ход начинается с подстановки значения x_na_n-1,n в строку с номером n-1, вычисления значения x_n-1 и так далее до первой строки и вычисления x₁ и завершения решения.

В связи с наличием в алгоритме операции деления на диагональный элемент перед выполнением этой операции среди строк с номером больше i отыскивается строка с наибольшим по абсолютному значению значением коэффициента в i-м столбце и меняется местами с i-й. Этим исключается опасность деления на нуль и матрица по возможности приближается к диагонально-преобладающей, что повышает устойчивость получаемого решения. Эта операция носит название «выбор главного элемента».

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

Алгоритм Гауссовых исключений с выбором главного элемента можно кратко записать так:

Для k=1 до n-1

найти m³k такое что |a_ik|=max(|a_ik|: i³k)

если a_mk=0, то А – вырождена, вычисления прекратить,

иначе поменять местами a_kj и a_mj (j=k, k+1, …, n),

поменять местами b_k и b_m

Для i=k+1 до n

l_ik=a_ik/a_kk;

для j=k+1 до n

a_ij–=l_ika_kj; b_i–=l_ikb_k.

Существует много вариантов метода Гаусса, из них наиболее эффективен метод Жордана-Гаусса или метод полного исключения. Отличается он тем, что при использовании i-го уравнения для исключения переменных исключение проводят не только для нижележащих, но и для вышележащих строк. Это исключает необходимость в обратном ходе Гаусса и этот метод следует применять, если нет необходимости в «попутном» с решением СЛАУ вычислении определителя матрицы.

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

Процесс Гауссова исключения является также эффективным методом вычисления обратной матрицы. Из определяющего обратную матрицу соотношения AA^-1=E вытекает, что i-й столбец обратной матрицы a_i^-1 может быть получен решением системы Aa_i^-1=e_i, где e_i – i-й столбец единичной матрицы того же порядка, что и A. Для вычисления всей обратной матрицы необходимо решить n систем линейных уравнений, при этом матрица A расширяется справа единичной матрицей nxn. Прямой ход Гаусса при решении полученных систем можно осуществлять для всех систем одновременно.