5.2.2. Обратный ход

Мы достигли поставленной цели – все элементы, расположенные ниже главной диагонали, равны 0 (матрица приведена к верхней треугольной форме). Теперь можно переходить ко второй части вычислительной процедуры – обратному ходу. Последнее уравнение системы после проделанных преобразований имеет вид: a_nn x_n = b_n ((–1)x₃ = – 3). Это одно уравнение с одним неизвестным, откуда легко найти x_n = b_n/a_nn (x₃ = 1)_. Далее, в предпоследнем уравнении

((–2) x₂ + 0 x₃ = – 4) (20)

мы уже определили x_n (x₃), следовательно, (20) – опять уравнение с одним неизвестным x_n-1, которое легко можно найти. Таким образом, двигаясь пошагово по уравнениям вверх и решая на каждом этапе одно уравнение с одним неизвестным, мы определим все неизвестные и решим систему, т. е. найдем ее единственное решение (напомним, что по завершении вычислений обратного хода необходимо восстановить номера неизвестных, т. е. восстановить исходный порядок столбцов, если мы их переставляли).

5.3. Случай прямоугольной матрицы (системы порядка m n)

Отметим прежде всего, что основной интерес представляет случай m < n (число уравнений меньше числа неизвестных). В самом деле, если m > n (число строк основной матрицы больше числа столбцов), то среди m строк матрицы независимых не больше n, т. к. строки содержат по n элементов, а пространство строк длины n имеет размерность n. Пусть число независимых уравнений k = n < m, и мы переставили независимые строки на первые k мест. Тогда любая из оставшихся строк основной матрицы есть некоторая линейная комбинация первых k строк. Если соответствующая правая часть есть такая же комбинация первых k правых частей, то соответствующее уравнение можно исключить – оно есть следствие первых k уравнений. Например, в системе

третье уравнение является суммой первых двух и его можно просто исключить. Если же соответствующая правая часть не есть такая же комбинация первых k правых частей, то рассматриваемое уравнение очевидно противоречит первым k уравнениям, и система несовместна (если бы правая часть третьего уравнения в рассмотренном выше примере была бы, скажем, 10, то вычитая из третьего уравнения первые два получили бы (проверьте!) 0 = – 8).

Таким образом, случай m > n либо приводит к несовместной системе, либо, после исключения зависимых уравнений, получим, что независимых уравнений будет либо n, либо m < n. Первый из этих случаев разобран в предыдущем пункте, а к рассмотрению случая m < n мы приступаем.

5.3.1. Прямой ход

Итак, пусть дана система уравнений, в которой число уравнений меньше числа неизвестных. Как и в случае квадратной матрицы, проводим процедуру Гаусса, т. е. используя элементарные преобразования, добиваемся, чтобы матрица в верхнем левом углу приняла верхний треугольный вид. При этом сначала все элементы первого столбца становятся равными нулю, кроме первого, затем все элементы второго столбца становятся равными нулю, кроме первых двух, и т. д. Как и ранее, если в процессе вычислений получается, что все элементы i-ой строки стали равными нулю, а соответствующая правая часть b_i при этом не равна нулю, значит система несовместна, и на этом процедура прекращается.

Если же в 0 обратились все элементы некоторой i-ой строки матрицы , включая правую часть уравнения b_i, то такая строка исключается из матрицы, и процедура выполняется дальше:

(21)

В приведенном примере в 0 обратились все элементы третьей строки. Эта строка исключена из матрицы, а номера всех последующих строк сдвинулись на единицу, – четвертая строка стала третьей, пятая – четвертой и т. д. Общее число уравнений сократилось на единицу.

Продолжая таким же образом, в случае совместной системы мы придем к системе k уравнений с n неизвестными, k < n. Причем верхний левый угол матрицы размером k  k превратится в верхнюю треугольную матрицу порядка k:

. (22)

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

Заметим, что к подобной ситуации приходит задача с любым числом уравнений, если система совместна и число независимых уравнений m меньше числа неизвестных n. Процедура Гаусса позволяет в этой ситуации выделить независимые уравнения, построить базисный минор и установить, что исходная система является неопределенной.