Элементарные преобразования строк

Элементарные преобразования строк — это операции над строками матрицы, которые не изменяют множество решений соответствующей системы линейных уравнений (СЛАУ) или, в более общем смысле, не меняют ранг матрицы и её линейные свойства. Эти преобразования являются основой метода Гаусса и его модификаций, используемых для решения систем линейных уравнений, вычисления обратных матриц, нахождения ранга и определителя.

Определение и виды

Элементарные преобразования строк матрицы делятся на три типа:

Перестановка двух строк (транспозиция). Строки \(i\) и \(j\) меняются местами: \(R_i \leftrightarrow R_j\).
Умножение строки на ненулевое число (скалярное умножение). Каждый элемент строки \(i\) умножается на константу \(k \neq 0\): \(R_i \rightarrow k \cdot R_i\).
Прибавление к одной строке другой строки, умноженной на ненулевое число (сложение с масштабированием). К строке \(i\) прибавляется строка \(j\), умноженная на число \(k\): \(R_i \rightarrow R_i + k \cdot R_j\). Частный случай — прибавление без умножения (\(k=1\)).

Эти операции являются обратимыми: для каждой существует обратное преобразование того же типа. Например, обратным к умножению строки на 5 является умножение на 1/5; обратным к прибавлению строки \(j\) с коэффициентом \(k\) является прибавление той же строки с коэффициентом \(-k\).

Свойства и инварианты

Применение элементарных преобразований строк сохраняет ряд фундаментальных характеристик матрицы:

Ранг матрицы — максимальное количество линейно независимых строк (или столбцов) остаётся неизменным.
Линейная зависимость/независимость строк — если исходные строки были линейно зависимы, то после преобразований они останутся зависимыми, и наоборот.
Определитель (для квадратных матриц) — при перестановке строк меняет знак, при умножении строки на число умножается на это число, при прибавлении одной строки к другой не изменяется.
Множество решений СЛАУ — если преобразования применяются к расширенной матрице системы, то решения системы не меняются.

Применение в методе Гаусса

Метод Гаусса (или алгоритм Гаусса — Жордана) использует элементарные преобразования строк для приведения матрицы к ступенчатому виду (или к улучшенному ступенчатому виду — единичной матрице). Процесс состоит из двух этапов:

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

Пример: для системы уравнений \[ \begin{cases} 2x + y = 5 \\ x - y = 1 \end{cases} \] расширенная матрица имеет вид: \[ \begin{pmatrix} 2 & 1 & | & 5 \\ 1 & -1 & | & 1 \end{pmatrix} \] Применяя преобразования:

Переставим строки: \(R_1 \leftrightarrow R_2\) → \(\begin{pmatrix}1 & -1 & | & 1 \\ 2 & 1 & | & 5\end{pmatrix}\).
Вычтем из второй строки первую, умноженную на 2: \(R_2 \rightarrow R_2 - 2R_1\) → \(\begin{pmatrix}1 & -1 & | & 1 \\ 0 & 3 & | & 3\end{pmatrix}\).
Разделим вторую строку на 3: \(R_2 \rightarrow \frac{1}{3}R_2\) → \(\begin{pmatrix}1 & -1 & | & 1 \\ 0 & 1 & | & 1\end{pmatrix}\).
Прибавим ко второй строке вторую: \(R_1 \rightarrow R_1 + R_2\) → \(\begin{pmatrix}1 & 0 & | & 2 \\ 0 & 1 & | & 1\end{pmatrix}\).

Решение: \(x=2, y=1\).

Связь с матрицами элементарных преобразований

Каждому элементарному преобразованию строк соответствует умножение исходной матрицы слева на специальную матрицу — матрицу элементарного преобразования. Эти матрицы получаются из единичной матрицы применением того же преобразования. Например:

Матрица перестановки строк \(i\) и \(j\) — единичная матрица, в которой строки \(i\) и \(j\) поменяны местами.
Матрица умножения строки \(i\) на \(k\) — единичная матрица, в которой элемент на позиции \((i,i)\) заменён на \(k\).
Матрица прибавления строки \(j\) к строке \(i\) с коэффициентом \(k\) — единичная матрица, в которой на позиции \((i,j)\) стоит \(k\).

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

Применение в других задачах

Вычисление обратной матрицы: к матрице \(A\) приписывается единичная матрица \(I\) (расширенная матрица \([A|I]\)). Применяя элементарные преобразования строк, приводят \(A\) к единичной. Тогда на месте \(I\) получится \(A^{-1}\).
Нахождение ранга: матрица приводится к ступенчатому виду, и ранг равен количеству ненулевых строк.
Вычисление определителя: для квадратной матрицы определитель вычисляется как произведение ведущих элементов (с учётом знака от перестановок) после приведения к треугольному виду.
Решение систем линейных уравнений: как описано выше, метод Гаусса — основной алгоритм для решения СЛАУ с любым числом уравнений и неизвестных.

История

Метод, основанный на элементарных преобразованиях строк, был известен ещё в древнем Китае. В трактате «Математика в девяти книгах» (около II века до н. э.) описывается алгоритм, аналогичный методу Гаусса, для решения систем линейных уравнений с помощью манипуляций с коэффициентами на счётной доске. В Европе метод был переоткрыт Карлом Фридрихом Гауссом в начале XIX века и усовершенствован Вильгельмом Йорданом в конце XIX века для приведения матриц к единичному виду.

Критика и ограничения

Элементарные преобразования строк являются точным алгебраическим методом, но при численной реализации на компьютере могут возникать проблемы с округлением. В частности, выбор ведущего элемента (pivot) может привести к росту ошибок, если он очень мал. Для повышения точности применяют стратегии выбора ведущего элемента (частичный или полный выбор). Кроме того, метод Гаусса требует \(O(n^3)\) операций для матрицы размером \(n \times n\), что может быть неэффективно для очень больших разреженных систем, где используются итерационные методы.

Источники

Стренг Г. «Линейная алгебра и её применения». — М.: Мир, 1980.
Гантмахер Ф. Р. «Теория матриц». — М.: Наука, 1967.
Хорн Р., Джонсон Ч. «Матричный анализ». — М.: Мир, 1989.
Беклемишев Д. В. «Курс аналитической геометрии и линейной алгебры». — М.: Физматлит, 2005.
Кнут Д. Э. «Искусство программирования». Том 2. — М.: Вильямс, 2001.

BFOmetr — база данных и аналитика по компаниям России.

На главную BFOmetr →