2. Вычисление определителя.

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

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

Из сказанного выше следует, что для вычисления определителя нужно перемножить ведущие элементы и посчитать количество перестановок строк. Если количество перестановок нечетно, то полученное произведение следует умножить на (-1). При четном числе перестановок или в случае, когда перестановки не требуются, определитель равен произведению ведущих элементов.

В рассмотренном примере произведение ведущих элементов равно 48, а строки переставляются 4 раза, поэтому определитель  = 48.

Отметим, что количество арифметических операций, необходимых для вычисления определителя, можно существенно сократить, если ограничиться получением нулей только в строках, расположенных ниже или выше ведущих элементов. Для вычисления определителя достаточно привести матрицу к треугольному виду.

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

3. Совместная система с прямоугольной матрицей.

Теперь рассмотрим систему, в которой число неизвестных больше числа уравнений.

3Х₁ + Х₂ - 2Х₃ + Х₄ - Х₅ = 1,

2Х₁ - Х₂ + 7Х₃ - 3Х₄ + 5Х₅ = 2,

Х₁ + 3Х₂ - 2Х₃ + 5Х₄ - 7Х₅ = 3, (5)

13Х₁ - 2Х₂ + 7Х₃ - 5Х₄ + 8Х₅ = 3.

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

Gauss Method. Transformation to e - matrix.

4 6 1

3.000 1.000 -2.000 1.000 -1.000 1.000

2.000 -1.000 7.000 -3.000 5.000 2.000

1.000 3.000 -2.000 5.000 -7.000 3.000

13.000 -2.000 7.000 -5.000 8.000 3.000

1 1 3.000

1.000 .333 -.667 .333 -.333 .333

.000 -1.667 8.333 -3.667 5.667 1.333

.000 2.667 -1.333 4.667 -6.667 2.667

.000 -6.333 15.667 -9.333 12.333 -1.333

2 2 -1.667

1.000 .000 1.000 -.400 .800 .600

.000 1.000 -5.000 2.200 -3.400 -.800

.000 .000 12.000 -1.200 2.400 4.800

.000 .000-16.000 4.600 -9.200 -6.400

3 3 12.000

1.000 .000 .000 -.300 .600 .200

.000 1.000 .000 1.700 -2.400 1.200

.000 .000 1.000 -.100 .200 .400

.000 .000 .000 3.000 -6.000 .000

4 4 3.000

1.000 .000 .000 .000 .000 .200

.000 1.000 .000 .000 1.000 1.200

.000 .000 1.000 .000 .000 .400

.000 .000 .000 1.000 -2.000 .000

-180.000 - Result of Multiplication of the main elements.

Determinant = -180.000.

Последняя матрица содержит общее решение системы (5), которое можно переписать в виде

Х₁ = .200,

Х₂ = 1.200 - Х₅,

Х₃ = .400,

Х₄ = 2.000Х₅.

Здесь Х₁, Х₂, Х₃, Х₄ - базисные переменные, а Х₅ – свободная переменная, которая может принимать произвольные значения, порождая бесконечное множество решений.

Базисным переменным Х₁, Х₂, Х₃, Х₄ соответствуют столбцы