1.7. Метод Гаусса. Математическая часть
Рассмотрим
систему уравнений относительно
неизвестных
(1.1)
Ее
решениями являются такие наборы значений
переменных
,
которые превращают каждое уравнение
системы в тождество. Система (1.1) однозначно
определяет «расширенную» матрицу
с
столбцами, в которой матрицы
и
просто расположены рядом. В то же время
любой матрице с
столбцами можно сопоставить систему
линейных уравнений с
переменными: для этого достаточно
считать элемент на позиции
коэффициентом при переменной
в
-м
уравнении, если
,
и свободным членом
-го
уравнения, если
.
В этих случаях матрицу и систему будем
называть соответствующими. Строку
расширенной матрицы будем называть
противоречивой, если последний ее
элемент отличен от нуля, а остальные
элементы нулевые.
Утверждение 1.1. Если расширенная матрица содержит хотя бы одну противоречивую строку, то соответствующая ей система линейных уравнений не имеет решения.
Аналогично элементарным преобразованиям векторов можно рассмотреть элементарные преобразования строк матрицы:
- умножение строки на любое ненулевое число (элементарное преобразование типа 1);
- прибавление к одной из строк другой, умноженной на любое число (элементарное преобразование типа 2).
Утверждение 1.2. Элементарные преобразования строк расширенных матриц не изменяют множества решений соответствующей системы уравнений.
Если
удалить из расширенной матрицы
последний столбец, а затем все нулевые
строки (если таковые имеются), то получим
так называемую приведенную матрицу
.
Пусть
приведенная матрица
имеет размер
(
).
Если в
существует
столбцов, в которых ровно по одному
ненулевому элементу, причем никакие
два их этих ненулевых элементов не
находятся в одной строке, то переменные,
соответствующие эти столбцам, называются
базисными, остальные переменные –
свободными. Базисные переменные
составляют так называемый базис
переменных.
Пример.
Составим расширенную матрицу этой системы:
.
Нетрудно
увидеть, что данная система имеет два
базиса переменных:
.
Решим эту систему, например, относительно
первого базиса:
;
здесь переменные
,
- свободные и могут принимать произвольные
значения, по которым затем определяются
значения базисных переменных.
Этот пример помогает заметить следующее очевидное утверждение: если система имеет базис переменных, то она разрешима относительно этого базиса, при этом при наличии свободных переменных система будет иметь бесконечно много решений, а при их отсутствии значения базисных переменных определяются однозначно.
Метод Гаусса, описанный ниже, позволяет с помощью элементарных преобразований привести систему к виду, содержащему базис переменных, либо установить отсутствие решения.
Шагом алгоритма Гаусса будем считать переход от системы линейных уравнений к равносильной системе, имеющей большее число столбцов с единственным ненулевым элементом. Для удобства пользования вместо системы уравнений будем преобразовывать соответствующую ей матрицу. Ниже приведено описание шага алгоритма. Алгоритм прекращает работу при установлении неразрешимости системы или при невозможности выполнения очередного шага.