74. Метод Гаусса решения систем линейных уравнений. Применение метода Гаусса к вычислению определителя и обратной матрицы.

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

Рассмотрим систему линейных уравнений: Предположим, что a₁₁  0. Разделим на a₁₁ первое уравнение системы и с его помощью исключим переменную x₁ из остальных уравнений системы (1). В результате получим

Далее, предполагая a22^(1)0, разделим на этот коэффициент второе уравнение системы (2) и с его помощью исключим переменную x2 из всех уравнений системы (2), кроме первого. Это приведет нас к эквивалентной (1) системе уравнений вида

Проводя аналогичные преобразования, через m шагов придем к системе уравнений с треугольной матрицей

Решение системы (4) не вызывает затруднений, так как компоненты xi могут быть вычислены, начиная с номера m, по следующим формулам

Описанный способ получения системы (4) из системы (1) называют прямым ходом метода Гаусса, а решение системы (4) по формулам (5) - обратным ходом. Оценим количество арифметических операций, необходимых для реализации описанного алгоритма. Анализируя первый этап алгоритма, то есть переход от системы (1) к системе (2), нетрудно подсчитать, что его реализация требует m операций деления, m(m1) операций умножения и (m1)(m2) операций вычитания. При переходе от системы (2) к системе (3) первая строка и первый столбец матрицы системы (2) не преобразуются, поэтому потребуется m1 операция деления, (m1)(m2) операций умножения и (m2)(m3) операций вычитания. Ясно, что тогда общее количество операций, необходимых для реализации прямого хода будет равно Вычисления по формулам (5) потребуют 1+2++(m1) операций умножения и столько же операций вычитания. Таким образом, при больших m общее число операций, необходимых для реализации метода Гаусса, приблизительно равно 2m³/3. Вычисление определителя матрицы с помощью метода Гаусса. Обозначим A - матрицу системы (1), A⁽¹⁾ - матрицу системы (2), A⁽²⁾ - матрицу системы (3) и, наконец, A^(m) - матрицу системы (4). Заметим, что при переходе от системы (1) к (2) единственной операцией, изменяющей значение определителя, была операция деления на a₁₁, при этом A=a₁₁ A⁽¹⁾. Аналогичная ситуация имела место и на всех последующих шагах. Поэтому будут справедливы следующие равенства A   =  a₁₁ A⁽¹⁾  =  a₁₁ a₂₂⁽¹⁾ A⁽¹⁾  =    =  a₁₁ a₂₂⁽¹⁾  a_{m1  m1}^(m1) A^(m) .

Поскольку определитель матрицы A^(m) равен 1, то A   =  a₁₁ a₂₂⁽¹⁾  a_{m1  m1}^(m1) , и для отыскания определителя матрицы достаточно реализовать ту часть прямого хода метода Гаусса, в которой преобразуются элементы матриц A⁽ⁱ⁾. Обращение матриц с помощью метода Гаусса. По определению обратной матрицы A  A^1   =  E. (6) Пусть y^k - вектор, совпадающий с k-тым столбцом матрицы A, а e^k - единичный вектор, совпадающий с k-тым столбцом матрицы E. Тогда матричное равенство (6) можно записать в виде следующих систем линейных уравнений Ay^k=e^k, k=1,2,,m, (7) решение которых, очевидно, эквивалентно отысканию матрицы A^1. Каждую из систем (7) можно решить с помощью метода Гаусса. Однако при организации вычислений следует помнить, что все системы в (7) имеют одну и ту же матрицу A. Поэтому целесообразно прямой ход в методе Гаусса проводить сразу для всех систем, преобразуя элементы матрицы и правые части всех уравнений (7) одновременно. Обратный ход метода Гаусса для каждой системы проводится отдельно. Нетрудно проверить, что число арифметических операций, необходимых для реализации этого алгоритма, остается пропорциональным m³.