bulgakov

05. Метод Гаусса: ступенчатая и приведённая формы

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

Ведущий элемент и ступень

В ненулевой строке первое слева число, отличное от нуля, называется её ведущим элементом. Например, в строке (0,0,5,2)(0,0,5,2) ведущий элемент — 55 в третьем столбце. В нулевой строке (0,0,0,0)(0,0,0,0) ведущего элемента нет.

Определение 13.1. Матрица имеет ступенчатый вид, если:

  1. ведущий элемент каждой следующей ненулевой строки расположен строго правее ведущего элемента предыдущей;
  2. все нулевые строки стоят ниже ненулевых.

Название отражает расположение ведущих элементов: при движении вниз они образуют ступеньки вправо.

Пример 13.1. Первые две матрицы ступенчатые:

(120005000),(120000000).\begin{pmatrix}1&2&0\\0&0&5\\0&0&0\end{pmatrix}, \qquad \begin{pmatrix}1&2&0\\0&0&0\\0&0&0\end{pmatrix}.

У первой ведущие элементы находятся в столбцах 11 и 33, у второй есть только один ведущий элемент в столбце 11. Нулевые строки стоят внизу. Следующие две матрицы не ступенчатые:

(120005006),(000573000).\begin{pmatrix}1&2&0\\0&0&5\\0&0&6\end{pmatrix}, \qquad \begin{pmatrix}0&0&0\\5&7&3\\0&0&0\end{pmatrix}.

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

Почему метод Гаусса всегда доводит до ступенчатого вида

Теорема 13.1 (Гаусс). Любую матрицу элементарными преобразованиями строк можно привести к ступенчатому виду.

Доказательство и алгоритм. Нулевая матрица уже ступенчатая. В ненулевой матрице найдём первый слева столбец k1k_1, где есть ненулевое число. Переставим строки так, чтобы оно оказалось в первой строке: a1k1≠0a_{1k_1}\ne0. Это первый опорный, или ведущий, элемент.

Для каждой строки s>1s>1 с числом ask1a_{sk_1} выполним

Rs←Rs−ask1a1k1R1.R_s\leftarrow R_s-\frac{a_{sk_1}}{a_{1k_1}}R_1.

Множитель выбран так, чтобы обнулить число в нижней строке под опорным элементом. Умножение первой строки на ask1/a1k1a_{sk_1}/a_{1k_1} делает её элемент в столбце k1k_1 равным ask1a_{sk_1} — тому самому числу, которое нужно вычесть из нижней строки. Поэтому в столбце k1k_1 под опорным элементом теперь нули: ask1−(ask1/a1k1)a1k1=0a_{sk_1}-(a_{sk_1}/a_{1k_1})a_{1k_1}=0. Делитель ненулевой по выбору опорного элемента.

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

Пример работы алгоритма. Начнём с матрицы, у которой в левом верхнем углу нуль:

(024111246).\begin{pmatrix} 0&2&4\\ 1&1&1\\ 2&4&6 \end{pmatrix}.

В первом столбце есть ненулевой коэффициент, поэтому переставим R1R_1 и R2R_2. Затем вычтем из третьей строки удвоенную первую:

(111024246)→R3←R3−2R1(111024024).\begin{pmatrix} 1&1&1\\ 0&2&4\\ 2&4&6 \end{pmatrix} \xrightarrow{R_3\leftarrow R_3-2R_1} \begin{pmatrix} 1&1&1\\ 0&2&4\\ 0&2&4 \end{pmatrix}.

Теперь R3←R3−R2R_3\leftarrow R_3-R_2:

(111024000).\boxed{\begin{pmatrix} 1&1&1\\ 0&2&4\\ 0&0&0 \end{pmatrix}.}

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

Приведённый ступенчатый вид

Обычного ступенчатого вида уже достаточно для решения системы обратной подстановкой. Иногда удобно пойти дальше и получить значения главных неизвестных прямо из строк.

Определение 13.2. Ступенчатая матрица имеет приведённый, или редуцированный, ступенчатый вид (RREF), если каждый ведущий элемент равен 11 и все остальные числа в его столбце равны 00 — как ниже, так и выше него.

Пример 13.2. Матрица

(105080012030000160000001)\begin{pmatrix} 1&0&5&0&8&0\\ 0&1&2&0&3&0\\ 0&0&0&1&6&0\\ 0&0&0&0&0&1 \end{pmatrix}

уже приведена: ведущие единицы стоят в столбцах 1,2,4,61,2,4,6, и в каждом из этих столбцов остальные числа — нули. Числа 5,2,8,3,65,2,8,3,6 допустимы: они стоят в столбцах без ведущих элементов.

Следствие 13.1 (Гаусс — Жордан). Любую матрицу можно привести к RREF. Действительно, после метода Гаусса делим каждую ненулевую строку на её ведущий элемент. Все ведущие элементы станут единицами; деление разрешено, поскольку они ненулевые. Затем, двигаясь от нижней ведущей единицы к верхней, вычитаем кратные её строки из строк выше и обнуляем весь ведущий столбец.

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

Для нашей матрицы из примера сначала умножим вторую строку на 1/21/2, затем вычтем её из первой:

(111012000)→R1←R1−R2(10−1012000).\begin{pmatrix} 1&1&1\\ 0&1&2\\ 0&0&0 \end{pmatrix} \xrightarrow{R_1\leftarrow R_1-R_2} \boxed{\begin{pmatrix} 1&0&-1\\ 0&1&2\\ 0&0&0 \end{pmatrix}.}

В следующем уроке применим оба вида к расширенной матрице [A∣b][A\mid b]. Тогда положение ведущих элементов покажет, существует ли решение и сколько неизвестных можно выбирать свободно.

ПрактикаЗагружаем тест…