Системы уравнений

Все курсы > Линейная алгебра > Занятие 4

Начнем изучать системы линейных уравнений.

Продолжим работать в том же ноутбуке

Обратная матрица

Обратимся к следующей системе.

$$ \begin{bmatrix} 1 & 1 & 3 \\ 1 & 2 & 4 \\ 1 & 1 & 2 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix} = \begin{bmatrix} 15 \\ 21 \\ 13 \end{bmatrix}$$

Перепишем ее в виде

$$ A \mathbf x = \mathbf b $$

Вспомним, что если существует обратная матрица (inverse matrix) $A^{-1}$, то при умножении на матрицу $A$ мы получаем единичную матрицу $I$, т.е. $A^{-1}A = I$. Умножим обе стороны уравнения на $A^{-1}$.

$$ A^{-1}A \mathbf x = A^{-1} \mathbf b $$

$$ I \mathbf x = A^{-1} \mathbf b $$

$$ \mathbf x = A^{-1} \mathbf b $$

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

$$ A \mathbf x = \mathbf b \rightarrow A^{-1} \mathbf b = \mathbf x $$

С точки зрения линейных преобразований матрица A перемещает вектор $ \mathbf x$ на вектор $ \mathbf b$. Обратная же матрица «возращает» вектор $ \mathbf b$ на вектор $ \mathbf x$.

Решим систему уравнений с помощью метода .inv() модуля linalg библиотеки Numpy.

Метод Гаусса

Приведение матрицы к ступенчатому виду

Рассмотрим метод Гаусса (Gaussian Elimination) для решения систем линейных уравнений.

Метод заключается в том, чтобы с помощью ряда элементарных операций привести расширенную матрицу (augmented matrix), т.е. матрицу коэффициентов при неизвестных ($A$) + вектор свободных коэффициентов ($ \mathbf b $), к ступенчатому виду (row-echelon form, ref) путем последовательного исключения коэффициентов (elimination).

Получив ступенчатую матрицу, мы сможем последовательно найти все переменные системы, начиная с последней (back-substitution).

Приведем перечень трех возможных операций:

  • перестановка местами двух строк матрицы
  • умножение на число, отличное от нуля
  • прибавление одной строки к другой, умноженной на константу (вычитание предполагает умножение на $-1$ и сложение)

Приведем пример решения⧉ системы уравнения вручную и пример алгоритма⧉ на Питоне, выполняющего эти операции.

Применим этот алгоритм для решения приведенной в начале системы. Одновременно выведем получившуюся расширенную матрицу в ступенчатом виде.

Важно отметить, что, не зная обратной матрицы, мы нашли решение лишь для конкретного $\mathbf b$.

Упрошенный ступенчатый вид матрицы

С помощью тех же элементарных операций мы можем привести матрицу $A$ в ступенчатом виде к матрице в упрощенном ступенчатом виде (который в данном случае представляет собой единичную матрицу).

$$ \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix} = \begin{bmatrix} 5 \\ 4 \\ 2 \end{bmatrix} $$

В этом можно убедиться, выполнив:

  • $ R_3 \times (-1)$
  • $ -3R_3 + R_1 $
  • $ -1R_3 + R_2 $
  • $ -1R_2 + R_1 $

Если матрица приведена к ступенчатому виду и кроме этого:

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

то говорят, что матрица приведена к упрощенному ступенчатому виду (reduced row echelon form, rref). Ниже для сравнения приведены две матрицы, одна в ступенчатом виде (ref), вторая в упрощенном ступенчатом виде (rref).

сравнение ступенчатого и упрощенного ступенчатого вида матрицы

Заметим, что упрошенный ступенчатый вид матрицы аналогичен единичной матрице тогда и только тогда, когда матрица обратима.

$$ rref(A) = I \quad \iff \quad A \text{ is non-singular} $$

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

Метод Гаусса-Жордана

Приведение матрицы к виду выше (когда слева остается единичная матрица) можно использовать для нахождения обратной матрицы методом Гаусса-Жордана (Gauss–Jordan elimination). Суть метода заключается в том, чтобы (пример взять отсюда⧉):

Во-первых, расширить исходную матрицу с помощью единичной матрицы.

метод Гаусса-Жордана: расширение исходной матрицы

Во-вторых, выполнять элементарные построчные преобразования расширенной (с помощью $I$) матрицы до тех пор, пока матрица $A$ не превратится в единичную.

метод Гаусса-Жордана: элементарные преобразования

Получившаяся справа матрица $B$ будет обратной матрице $A$ ($B = A^{-1}$).

Теперь с обратной матрицей мы можем найти $ \mathbf x$ вне зависимости от значений $ \mathbf b$.

Идея такого преобразования заключается в следующем. Приведенные выше операции с матрицей можно выразить через умножение трансформационной матрицы $Е$ на матрицу $A$. Например, возьмем вектор $ \mathbf b$.

вектор b

Для того чтобы превратить 8 в 4 можно применить следующую трансформационную матрицу.

трансформационная матрица

Эта матрица аналогична операции $ -2R_1 + R_2 $. В целом все операции по приведению матрицы $A$ к виду $I$ можно записать в виде матрицы $Е$. Тогда получаем, что $EA = I$. При этом по определению $E = A^{-1}$.

Найдем обратную матрицу с помощью написанного вручную алгоритма, а затем проверим решение через метод np.linalg.inv().

Подведем итог

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

Перейдем к изучению определителя матрицы.