6.8. Алгоритм расчета определителей с использованием исключения неизвестных

При прямом ходе метода Гаусса выполняются следующие эквивалентные преобразования уравнений, не изменяющие решения системы:

1) перестановка столбцов - при перемещении главного элемента строки на главную диагональ матрицы и

2) сложение строки с другой строкой, умноженной на постоянный коэффициент - при обнулении элементов ведущего столбца под главной диагональю.

Сложение строк (2) по свойству определителей 2 (Глава 5) величину определителя не изменяет. В отличие от сложения, перестановка столбцов (1) по свойству определителей 5 (Глава 5) изменяет знак величины определителя, что равносильно умножению его на (-1). Поэтому после завершения прямого хода при решении системы уравнений методом Гаусса определитель матрицы системы равен определителю исходной системы А, умноженному на (-1) в степени, равной числу перестановок столбцов при решении системы.

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

Для того, чтобы получить алгоритм расчета определителя, из прямого хода метода Гаусса необходимо устранить все операции с элементами свободного вектора и вместо вектораР ввести счетчик N перестановок столбцов, у которого начальное значение N =0.

Так как после прямого хода матрица получается треугольной, то ее определитель по свойству определителей 9 (Глава 5) равен произведению ее диагональных элементов. В итоге определитель исходной матрицы равен:

 = (-1)^Na₁₁ a₂₂... a_nn,

где N - число перестановок столбцов, a₁₁, a₂₂,...,a_nn - диагональные элементы преобразованной матрицы, полученной в результате прямого хода.

Примеры 1. Рассчитать по методу Гаусса определитель матрицы порядка 3:

Решение. 1. Начальные присваивания: N =0.

2. Обработка строки 1 и столбца 1. Максимальным по модулю в первой строке является элемент третьего столбца а₃₃=7. Переставляя местами столбцы 1 и 3 и изменяя значение счетчика перестановок, получим:

Для обнуления элементов столбца 1 под главной диагональю ко второй строке прибавляем первую, умноженную на коэффициент (-а₂₁/а₁₁)= -4/7; к третьей строке прибавляем первую, умноженную на коэффициент (-а₃₁/а₁₁)= -3/7:

3. Обработка строки 2 и столбца 2. Максимальным по модулю во второй строке является диагональный элемент а₂₂=23/7. Для обнуления элементов столбца 2 под главной диагональю ко третьей строке прибавляем вторую, умноженную на коэффициент (-а₃₂/а₂₂)= 51/23:

4. Искомая величина определителя исходной матрицы равна:

 = (-1)^Na₁₁ a₂₂ a₃₃ = (-1)¹7 (23/7) (-141/23) = 141.

Трудоемкость рассмотренного алгоритма можно получить из трудоемкости прямого хода метода Гаусса, вычитая из чисел операций: n операций сложения и n умножений, которые затрачиваются на обработку свободного вектора системы и добавляя (n-1) умножение при расчете . В результате получим следующие числа элементарных операций:

- сравнений: c(n) = c_пр(n) = n(n+1)/2;

- сложений : s(n) = s_пр(n) - n = n (n²-1)/3- n = n (n²-4)/3;

- умножений: m(n) = m _пр(n) - n + (n -1)= n (n²-1)/3- 1;

- делений: d(n) = d_пр(n) = (n-1)+(n-2)+ …+0 = n(n-1)/2.

Сложность данного алгоритма расчета определителя – кубическая О(n³).

В отличие от метода Гаусса, в методе Гаусса-Жордана значение определителя исходной матрицы системы линейных уравнений после прямого хода не сохраняется. Его величина может быть получена по формуле, аналогичной методу Гаусса, где N - число перестановок строк, a₁₁, a₂₂,...,a_nn - диагональные элементы, на которые делятся строки матрицы.

Вопросы для проверки знаний.

1. Поясните, почему абсолютное значение определителя после выполнения прямого хода сохраняется ?

2. Почему значение определителя после выполнения прямого хода может изменить знак ?

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

4. Сохраняется ли величина определителя у матрицы системы после выполнения прямого хода по методу Гаусса-Жордана ?

Практическое задание.

1. Рассчитать по методу Гаусса определитель матрицы порядка 3: