Решение систем линейных уравнений методом Гаусса

Решить систему линейных уравнений значит получить равносильную разрешенную систему линейных уравнений или равносильную несовместную систему линейных уравнений. Способ получения таких систем называется методом Гаусса.

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

Пусть дана система уравнений

Преобразование системы уравнений состоит из ряда последовательных преобразований.

1-ый шаг. Если коэффициент отличен от нуля, разделим первое уравнение на этот коэффициент, а затем вычтем из каждого следующего уравнения первое уравнение, умноженное соответственно на , , . При этом первое уравнение называется разрешающим. Тогда система примет вид:

Заметим, что в полученном виде системы первое уравнение содержит с коэффициентом 1, и в остальные уравнения эта переменная входит с коэффициентами 0. Следовательно, является разрешенной. В данном случае первое уравнение называется разрешающим.

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

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

Такой вид системы (преобразованный по методу Гаусса) называется ступенчатым видом.

Выполняя преобразования Гаусса можно для удобства менять местами строки.

Следствие 1. Совместная система линейных уравнений равносильна разрешенной системе.

Следствие 2. Совместная система линейных уравнений имеет либо одно решение, либо бесчисленное множество решений.

Пример. Преобразовать расширенную матрицу системы к ступенчатому виду

Для удобства поменяем местами первую и вторую строки:

Делаем первый шаг преобразования: вычитаем из второй строки первую, умноженную на 2, из третьей вычитаем первую строку, умноженную на 2, из четвертой строки вычитаем первую:

Делаем второй шаг преобразования: делим вторую строку на -1:

И прибавляем к третьей строке вторую, в четвертой строке ноль уже есть:

На третьем шаге делим третью строку на -1:

И прибавляем к четвертой строке третью:

Из этого вида таблицы можно получить значения всех переменных: .

Пример. Найти базисные решения

Делаем первый шаг преобразования: вычитаем из второй строки первую, умноженную на 2, из третьей вычитаем первую строку, умноженную на 3:

Делаем второй шаг преобразования: делим вторую и третью строки на -1:

Вычитаем из третьей строки вторую, умноженную на 2:

Разделим третью строку на 4:

Далее можно преобразовывать систему таким же способом, как только что было выполнено, выбирая в качестве разрешающего уравнения третье уравнение, а разрешенной переменной сделаем . Вычтем из первого уравнения третье уравнение, умноженное на 3, а из второго – третье, умноженное на 2. Получим:

Затем вычтем из первого уравнения второе уравнение, умноженное на 2:

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

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

Далее прибавим к первой строчке третью строчку, умноженную на 11, а из второй строчки вычтем третью, умноженную на 9:

В таком виде системы - разрешенные (базисные) переменные, а переменная стала свободной переменной. Базисное решение (при ) имеет вид: .

Можно выбрать в качестве базисных переменных любые три переменные данной системы и выполнить преобразования так, чтобы система стала разрешенной относительно них.