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

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

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

Рассмотрим систему $m$ линейных уравнений с $n$ неизвестными $x_1, \dots, x_n$ над полем $K$ .

\begin{cases} a_{1,1} x_1 + a_{1,2} x_2 + \dots + a_{1,n} x_n = b_1\\ a_{2,1} x_1 + a_{2,2} x_2 + \dots + a_{2,n} x_n = b_2\\ \vdots \\ a_{m,1} x_1 + a_{m,2} x_2 + \dots + a_{m,n} x_n = b_m \end{cases} \iff A \cdot x = b

В матричной форме эта система записывается как $A \cdot x = b$ , где $A \in K^{m \times n}$ — матрица коэффициентов, $x \in K^n$ — вектор неизвестных, $b \in K^m$ — вектор правых частей системы.

Матрица $A$ задаёт линейное отображение $A : K^n \to K^m$ .

Матрицей системы называется матрица коэффициентов при неизвестных.

A = \begin{pmatrix} a_{1,1} & a_{1,2} & \cdots & a_{1,n} \\ a_{2,1} & a_{2,2} & \cdots & a_{2,n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m,1} & a_{m,2} & \cdots & a_{m,n} \end{pmatrix}

Расширенной матрицей системы называется матрица, полученная путём приписывания к матрице коэффициентов столбца правых частей.

A' = \left( \begin{array}{cccc|c} a_{1,1} & a_{1,2} & \cdots & a_{1,n} & b_1 \\ a_{2,1} & a_{2,2} & \cdots & a_{2,n} & b_2 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ a_{m,1} & a_{m,2} & \cdots & a_{m,n} & b_m \end{array} \right)

Пример. Рассмотрим систему линейных уравнений с двумя неизвестными $A = \begin{pmatrix}1 & 2\\3 & 4\end{pmatrix}$ , $x = \begin{pmatrix}x_1\\x_2\end{pmatrix}$ , $b = \begin{pmatrix}5\\11\end{pmatrix}$ над полем $R$ . Тогда система $A \cdot x = b$ имеет вид

\begin{cases} x_1 + 2x_2 = 5\\ 3x_1 + 4x_2 = 11 \end{cases}

Для решения этой системы можно использовать матричный подход. Мы можем записать её в матричной форме как $A \cdot x = b$ , где

A = \begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix} \quad x = \begin{pmatrix} x_1 \\ x_2 \end{pmatrix} \quad b = \begin{pmatrix} 5 \\ 11 \end{pmatrix}

Пример. Рассмотрим систему линейных уравнений

\begin{cases} 2x_1 - x_2 + 3x_3 = 7\\ 4x_1 + 5x_2 - x_3 = -2 \end{cases}

Эта система имеет вид матричного уравнения с коэффициентами из матрицы $A$ и столбцом правых частей $b$

A = \begin{pmatrix} 2 & -1 & 3 \\ 4 & 5 & -1 \end{pmatrix} \quad b = \begin{pmatrix} 7 \\ -2 \end{pmatrix}

Тогда расширенная матрица этой системы будет выглядеть так

A' = \left( \begin{array}{ccc|c} 2 & -1 & 3 & 7 \\ 4 & 5 & -1 & -2 \end{array} \right)

Совместная, несовместная и эквивалентные системы

Рассмотрим систему линейных уравнений $A \cdot x = b$ , где $A \in K^{m \times n}$ — матрица коэффициентов, $x \in K^n$ — вектор неизвестных, а $b \in K^m$ — вектор правых частей.

Система называется совместной, если существует хотя бы один вектор $x \in K^n$ , при котором выполняется равенство $A \cdot x = b$ .

Система называется несовместной, если не существует такого вектора $x \in K^n$ , при котором выполняется равенство $A \cdot x = b$ .

Две системы $A \cdot x = b$ и $A' \cdot x = b'$ с одинаковыми неизвестными $x \in K^n$ называются эквивалентными, если их множества решений совпадают.

Доказательство в общем виде

Элементарные преобразования строк, то есть перестановка строк, умножение строки на ненулевой скаляр и прибавление к строке другой строки, умноженной на скаляр, не меняют множество решений системы $A \cdot x = b$ .

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

Будем работать с расширенной матрицей $A' = (A \mid b)$ системы $A x = b$ , где $A \in K^{m \times n}$ и $b \in K^m$ .

Напомним три типа элементарных преобразований строк.

Перестановка строк $R_i \leftrightarrow R_j$ — меняем местами i-ю и j-ю строки.
Умножение строки на ненулевое число $R_i \to \lambda \cdot R_i$ , где $\lambda \in K$ и $\lambda \ne 0$ .
Прибавление кратной другой строки $R_i \to R_i + \lambda \cdot R_j$ означает, что к i-й строке прибавляем j-ю строку, умноженную на число $\lambda \in K$ .

Докажем в общем виде, что каждое из этих преобразований не меняет множество решений системы.

Пусть $x \in K^n$ — вектор неизвестных.

1. Перестановка строк. Меняем местами i-ю и j-ю строки матрицы $A'$ . Это лишь меняет порядок уравнений, но не их содержание.

Вектор $x$ удовлетворяет всем уравнениям до перестановки тогда и только тогда, когда он удовлетворяет тем же уравнениям после перестановки, поэтому множество решений не меняется.

2. Умножение строки на ненулевое число. Пусть i-я строка соответствует уравнению

a_{i,1} x_1 + \dots + a_{i,n} x_n = b_i

После преобразования $R_i \to \lambda \cdot R_i$ уравнение принимает вид

\lambda \cdot a_{i,1} x_1 + \dots + \lambda \cdot a_{i,n} x_n = \lambda \cdot b_i

Для $\lambda \ne 0$ эти два уравнения равносильны достаточно домножить или разделить обе части на $\lambda$ . Значит множество векторов $x$ , удовлетворяющих системе, не меняется.

3. Прибавление кратной другой строки. Пусть i-я и j-я строки задают уравнения

\begin{aligned} a_{i,1} x_1 + \dots + a_{i,n} x_n &= b_i \\ a_{j,1} x_1 + \dots + a_{j,n} x_n &= b_j \end{aligned}

После преобразования $R_i \to R_i + \lambda \cdot R_j$ i-я строка соответствует уравнению

(a_{i,1} + \lambda \cdot a_{j,1}) x_1 + \dots + (a_{i,n} + \lambda \cdot a_{j,n}) x_n = b_i + \lambda \cdot b_j

Если вектор $x$ удовлетворяет исходным двум уравнениям, то левая часть нового уравнения равна $b_i + \lambda \cdot b_j$ , следовательно новое уравнение тоже выполнено.

Обратно, если $x$ удовлетворяет новому уравнению и уравнению для строки j, то, вычитая $\lambda$ -кратное j-е уравнение из нового, получаем исходное i-е уравнение, значит, оно тоже выполняется.

Следовательно, вектор $x$ является решением системы до преобразования тогда и только тогда, когда он является решением системы после преобразования.

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

Теперь рассмотрим конкретный пример и проследим все шаги вычислений вручную.

Возьмём систему из четырёх уравнений с тремя неизвестными $x_1, x_2, x_3 \in K$

\begin{cases} x_1 + 2x_2 - x_3 = 1 \\ 2x_1 + 4x_2 - x_3 = 3 \\ -x_1 - 2x_2 + 2x_3 = 0 \\ 3x_1 + 6x_2 - x_3 = 5 \end{cases}

Ей соответствует расширенная матрица $A' = (A \mid b)$

A' = \left( \begin{array}{ccc|c} 1 & 2 & -1 & 1 \\ 2 & 4 & -1 & 3 \\ -1 & -2 & 2 & 0 \\ 3 & 6 & -1 & 5 \end{array} \right)

Сначала применим преобразования $R_2 \to R_2 - 2R_1$ и $R_4 \to R_4 - 3R_1$

\left( \begin{array}{ccc|c} 1 & 2 & -1 & 1 \\ 2 & 4 & -1 & 3 \\ -1 & -2 & 2 & 0 \\ 3 & 6 & -1 & 5 \end{array} \right) \xrightarrow[]{R_2 \to R_2 - 2R_1\ ,\ R_4 \to R_4 - 3R_1} \left( \begin{array}{ccc|c} 1 & 2 & -1 & 1 \\ 0 & 0 & 1 & 1 \\ -1 & -2 & 2 & 0 \\ 0 & 0 & 2 & 2 \end{array} \right)

Это соответствует замене уравнений

второе уравнение становится равносильно $(2x_1 + 4x_2 - x_3) - 2(x_1 + 2x_2 - x_3) = 3 - 2 \cdot 1$ , то есть $x_3 = 1$
четвёртое уравнение становится равносильно $(3x_1 + 6x_2 - x_3) - 3(x_1 + 2x_2 - x_3) = 5 - 3 \cdot 1$ , то есть $2x_3 = 2$ , снова $x_3 = 1$ .

Теперь заменим третью строку на $R_3 \to R_3 + R_1$

\left( \begin{array}{ccc|c} 1 & 2 & -1 & 1 \\ 0 & 0 & 1 & 1 \\ -1 & -2 & 2 & 0 \\ 0 & 0 & 2 & 2 \end{array} \right) \xrightarrow[]{R_3 \to R_3 + R_1} \left( \begin{array}{ccc|c} 1 & 2 & -1 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 2 & 2 \end{array} \right)

Получившееся третье уравнение по-прежнему выражает условие $x_3 = 1$ .

Наконец, выполним преобразования $R_3 \to R_3 - R_2$ и $R_4 \to R_4 - 2R_2$

\left( \begin{array}{ccc|c} 1 & 2 & -1 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 2 & 2 \end{array} \right) \xrightarrow[]{R_3 \to R_3 - R_2\ ,\ R_4 \to R_4 - 2R_2} \left( \begin{array}{ccc|c} 1 & 2 & -1 & 1 \\ 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{array} \right)

Эквивалентная система имеет вид

\begin{cases} x_1 + 2x_2 - x_3 = 1 \\ x_3 = 1 \\ 0 = 0 \\ 0 = 0 \end{cases}

Найдём множество решений явно.

Из второго уравнения $x_3 = 1$ . Подставляя в первое, получаем $x_1 + 2x_2 - 1 = 1$ , то есть $x_1 + 2x_2 = 2$ .

Положим $x_2 = t$ , где $t \in K$ — произвольный параметр, тогда

x_2 = t \quad x_3 = 1 \quad x_1 = 2 - 2t

Множество решений можно записать как

\left\{ \begin{pmatrix} 2 - 2t \\ t \\ 1 \end{pmatrix} \Bigg| t \in K \right\}

Проверим, что каждый такой вектор удовлетворяет исходной системе

(2 - 2t) + 2t - 1 = 1

2(2 - 2t) + 4t - 1 = 3

-(2 - 2t) - 2t + 2 \cdot 1 = 0

3(2 - 2t) + 6t - 1 = 5

Все равенства выполняются при любом $t \in K$ , поэтому множество решений исходной системы совпадает с множеством решений всех систем, полученных из неё элементарными преобразованиями строк, а значит, такие системы действительно эквивалентны.

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

Метод Гаусса

Идея метода

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

В матричной записи это выглядит так. Мы рассматриваем расширенную матрицу $A' = (A \mid b)$ и с помощью элементарных преобразований строк стараемся получить матрицу в треугольном виде, где хорошо видно, какие компоненты вектора $x$ можно выразить через какие. Эта процедура по сути и есть метод Гаусса.

Чтобы формализовать структуру, введём понятие треугольной матрицы. Интуитивно это такой вид, когда ненулевые строки «сдвигаются» вправо как ступени лестницы, а под выбранными опорными элементами стоят нули.

Матрица $R \in K^{m \times n}$ называется треугольной, если выполняются следующие условия

все нулевые строки расположены ниже всех ненулевых
в каждой ненулевой строке первый слева ненулевой элемент стоит правее, чем первый слева ненулевой элемент предыдущей ненулевой строки

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

Пусть $R \in K^{m \times n}$ — треугольная матрица.

Ненулевой элемент матрицы $R$ , стоящий в ведущей позиции некоторой строки, называется ведущим элементом или пивотом этой строки.

Столбец, в котором стоит ведущий элемент, называется ведущим столбцом, а соответствующая неизвестная системы $A \cdot x = b$ называется ведущей или главной переменной.

Неизвестные, которым не соответствует ни один ведущий столбец, называются свободными переменными именно они остаются параметрами в общем решении.

Теперь можно сформулировать идею метода Гаусса более точно. Мы хотим при помощи элементарных преобразований строк превратить расширенную матрицу $A' = (A \mid b)$ в треугольную матрицу, выделить по ней ведущие переменные, а затем выразить все ведущие переменные через свободные.

Алгоритм метода Гаусса

Опишем метод Гаусса в терминах шагов над расширенной матрицей $A' = (A \mid b)$

Выбираем первый по счету ещё не обработанный столбец, соответствующий неизвестным. В этом столбце ищем ненулевой элемент в строках, начиная с текущей и ниже. Если такой элемент есть, переставляем строки так, чтобы он оказался в текущей строке. Этот элемент становится будущим ведущим элементом этой строки.
При желании делим всю текущую строку на этот элемент, чтобы сделать ведущий элемент равным $1$ . Для теории это несущественно, но для ручных вычислений и интерпретации удобно.
Для всех строк ниже вычитаем подходящие кратные текущей строки так, чтобы элементы в выбранном столбце под ведущим элементом стали равны нулю.
Переходим к следующей строке и следующему столбцу справа и повторяем процедуру, пока либо не закончатся строки, либо не останется столбцов, содержащих ненулевые элементы ниже текущей строки.

Выбор главного элемента и численная устойчивость

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

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

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

Чтобы увидеть метод Гаусса в более алгоритмическом виде, запишем его в форме псевдокода. Ниже приведён вариант, который строит частное решение или фиксирует, что система несовместна.

Описанные шаги удобно оформить в виде алгоритма. Ниже приведён псевдокод метода Гаусса, который реализует прямой и обратный ход.

Псевдокод алгоритма

function gaussian_solve(matrix A[m, n], vector b[m]) -> result
    matrix M[m, n + 1]
    for i from 0 to m - 1
        for j from 0 to n - 1
            M[i, j] = A[i, j]
        M[i, n] = b[i]

    pivot_row = 0

    for pivot_col from 0 to n - 1
        pivot_row_candidate = -1
        for i from pivot_row to m - 1
            if M[i, pivot_col] != 0
                pivot_row_candidate = i
                break

        if pivot_row_candidate == -1
            continue

        swap_rows(M, pivot_row, pivot_row_candidate)

        pivot_value = M[pivot_row, pivot_col]
        for j from pivot_col to n
            M[pivot_row, j] = M[pivot_row, j] / pivot_value

        for i from pivot_row + 1 to m - 1
            factor = M[i, pivot_col]
            for j from pivot_col to n
                M[i, j] = M[i, j] - factor * M[pivot_row, j]

        pivot_row = pivot_row + 1

        if pivot_row == m
            break

    for i from 0 to m - 1
        all_zero = true
        for j from 0 to n - 1
            if M[i, j] != 0
                all_zero = false
                break

        if all_zero == true and M[i, n] != 0
            return ("несовместна", нет_решения)

    vector x[n]
    for j from 0 to n - 1
        x[j] = 0

    for i from m - 1 down to 0

        leading_col = -1
        for j from 0 to n - 1
            if M[i, j] != 0
                leading_col = j
                break

        if leading_col == -1
            continue

        sum_known = 0
        for j from leading_col + 1 to n - 1
            sum_known = sum_known + M[i, j] * x[j]

        x[leading_col] = M[i, n] - sum_known

    return ("совместна", x)


function swap_rows(matrix M[m, k], integer i, integer j)
    if i == j
        return
    for col from 0 to k - 1
        temp = M[i, col]
        M[i, col] = M[j, col]
        M[j, col] = temp

Метод Гаусса даёт нам универсальный алгоритм решения систем линейных уравнений, по расширенной матрице $(A \mid b)$ мы можем выяснить, совместна ли система, и, если да, найти хотя бы одно её решение. Однако сам по себе алгоритм не объясняет, как устроено множество всех решений и почему в одних случаях решение единственно, в других их бесконечно много, а иногда не существует вовсе.

Чтобы понять общую структуру решений, удобно смотреть на систему $A x = b$ через призму линейного оператора $A : K^n \to K^m$ и особенно выделить важный частный случай $b = 0$ — однородные системы.

Однородные и неоднородные системы

Однородная и неоднородная система

Пусть задан линейный оператор $A : K^n \to K^m$ , соответствующий матрице $A \in K^{m \times n}$ , и вектор $b \in K^m$ . Рассмотрим систему $A \cdot x = b$ с неизвестным вектором $x \in K^n$ .

Система называется однородной, если вектор правых частей равен нулю $b = 0$ , то есть если она имеет вид $A \cdot x = 0$ .

Если $b \ne 0$ и система записывается как $A \cdot x = b$ , то такая система называется неоднородной.

Линейный оператор $A$ задаёт отображение $A : K^n \to K^m$ . Множество решений однородной системы $A \cdot x = 0$ совпадает с ядром оператора $A$

\ker A = \{x \in K^n \mid A \cdot x = 0\}

Так как $A$ линейно, то для любых $x_1, x_2 \in \ker A$ и любых чисел $\alpha, \beta \in K$ имеем $A(\alpha \cdot x_1 + \beta \cdot x_2) = \alpha \cdot A x_1 + \beta \cdot A x_2 = 0$ . Следовательно, $\ker A$ является линейным подпространством в $K^n$ .

Пусть теперь система $A \cdot x = b$ неоднородна и совместна, то есть существует некоторое $x_0 \in K^n$ такое, что $A \cdot x_0 = b$ .

Тогда вектор $x \in K^n$ является решением неоднородной системы тогда и только тогда, когда разность $x - x_0$ лежит в ядре $A$

A \cdot x = b \iff A \cdot (x - x_0) = 0

Поэтому множество всех решений имеет вид

\{x \in K^n \mid A \cdot x = b\} = x_0 + \ker A = \{x_0 + y \mid y \in \ker A\}

То есть решения неоднородной системы получаются как сдвиг подпространства $\ker A$ на вектор $x_0$ . Геометрически это множество можно рассматривать как прямую, плоскость или более общую «аффинную» подпространственную фигуру, которая в общем случае не проходит через нуль.

Пример. Рассмотрим систему двух уравнений с двумя неизвестными

\begin{cases} x_1 + x_2 = 1\\ 2x_1 + 2x_2 = 2 \end{cases}

Матрица коэффициентов и столбец правых частей равны

A = \begin{pmatrix} 1 & 1\\ 2 & 2 \end{pmatrix} \quad b = \begin{pmatrix} 1\\ 2 \end{pmatrix}

Сначала найдём решения однородной системы $A \cdot x = 0$ . Уравнения имеют вид

\begin{cases} x_1 + x_2 = 0\\ 2x_1 + 2x_2 = 0 \end{cases}

Второе уравнение является удвоенным первым, поэтому достаточно одного условия $x_1 + x_2 = 0$ . Получаем $x_2 = -x_1$ , и любое решение однородной системы имеет вид

x = \begin{pmatrix} t\\ -t \end{pmatrix} \quad t \in K

то есть $\ker A = \{(t, -t)^{\T} \mid t \in K\}$ .

Теперь вернёмся к неоднородной системе $A \cdot x = b$ . Из первого уравнения имеем $x_1 + x_2 = 1$ . Возьмём, например, $x_1 = 0$ , тогда $x_2 = 1$ и

x_0 = \begin{pmatrix} 0\\ 1 \end{pmatrix}

Проверим, что это решение неоднородной системы

A \cdot x_0 = \begin{pmatrix} 1 & 1\\ 2 & 2 \end{pmatrix} \begin{pmatrix} 0\\ 1 \end{pmatrix} = \begin{pmatrix} 1\\ 2 \end{pmatrix} = b

Общее решение неоднородной системы имеет вид $x = x_0 + y$ , где $y \in \ker A$ . Подставляя найденные выражения, получаем

x = \begin{pmatrix} 0\\ 1 \end{pmatrix} + \begin{pmatrix} t\\ -t \end{pmatrix} = \begin{pmatrix} t\\ 1 - t \end{pmatrix} \quad t \in K

Легко проверить обратную подстановку при любом $t \in K$ выполнено $x_1 + x_2 = 1$ и $2x_1 + 2x_2 = 2$ , значит множество решений действительно совпадает с $x_0 + \ker A$ .

Обобщим полученный результат. Для системы $A \cdot x = b$ множество всех решений либо пусто, либо имеет вид $x_0 + \ker A$ для некоторого решения $x_0$ . Отсюда сразу следуют три возможных случая:

Если вектор $b$ не лежит в образе оператора $A$ , другими словами не существует $x_0$ такого что $A \cdot x_0 = b$ , то система несовместна — решений нет.
Если система совместна и $\ker A = \{0\}$ , то множество решений имеет вид $x_0 + \{0\} = \{x_0\}$ , значит решение единственно.
Если система совместна и $\ker A$ содержит нетривиальные векторы, то множество решений $x_0 + \ker A$ является аффинным подпространством, тогда решений бесконечно много.

Мы описали, как устроено множество решений системы $A x = b$ . В однородном случае это линейное подпространство $\ker A$ , а в неоднородном — его сдвиг вида $x_0 + \ker A$ . Это даёт хорошую геометрическую картинку и качественное понимание того, почему решение может быть единственным, бесконечным множеством или не существовать вовсе.

Однако при практических вычислениях нас интересует не только структура множества решений, но и эффективные алгоритмы их нахождения. В квадратном случае $A \in K^{n \times n}$ особенно удобно «запоминать» прямой ход метода Гаусса в виде разложения матрицы $A$ на произведение треугольных матриц. Такое представление называется LU-разложением и позволяет быстро решать системы с разными правыми частями, вычислять определитель и обратную матрицу.

LU-разложение

Определение и идея

LU-разложение квадратной матрицы

Пусть $A \in K^{n \times n}$ — квадратная матрица. Представление

A = L \cdot U

называется LU-разложением матрицы $A$ , если $L$ — нижнетреугольная матрица с единицами на диагонали, а $U$ — верхнетреугольная матрица.

Интуитивно LU-разложение фиксирует те же преобразования, которые мы делаем в методе Гаусса. Матрица $U$ играет роль матрицы после прямого хода, а матрица $L$ накапливает коэффициенты, которыми мы вычитали строки.

Существование и единственность

Существование и единственность LU-разложения без перестановок

Пусть поле скаляров $K$ , $n \in N$ и $A \in K^{n \times n}$ — квадратная матрица. Для каждого $k = 1, \dots, n$ обозначим через $A_k \in K^{k \times k}$ её верхний левый блок размера $k \times k$ .

Предположим, что все главные угловые миноры матрицы $A$ ненулевые

\lvert A_k \rvert \ne 0 \quad \text{для всех } k = 1, \dots, n

Тогда существует единственная пара матриц $L, U \in K^{n \times n}$ такая, что

A = L U

где $L$ — нижнетреугольная матрица с единицами на диагонали, а $U$ — верхнетреугольная матрица.

Существование. Применим к матрице $A$ прямой ход метода Гаусса без перестановок строк. На шаге $k$ ( $1 \le k \le n - 1$ ) в качестве ведущего используется элемент $a^{k}_{k,k}$ в позиции $(k, k)$ . Ненулевость главного минора $|A_k|$ означает, что подматрица $A_k$ невырождена, а значит $a^{k}_{k,k} \ne 0$ и шаг можно выполнить без перестановки строк.

На шаге $k$ для каждой строки $i > k$ вычитаем кратную строку $k$ с множителем

\ell_{i,k} = \frac{a^{k}_{i,k}}{a^{k}_{k,k}}

Все эти множители $\ell_{i,k}$ записываем как элементы матрицы $L$ под диагональю, а результат прямого хода обозначаем через $U$ . Тогда произведение $L U$ воспроизводит последовательность элементарных преобразований, возвращающую исходную матрицу: $A = L U$ . По построению на диагонали $L$ стоят единицы, а $U$ верхнетреугольна.

Единственность. Пусть существуют два разложения

A = L_1 U_1 = L_2 U_2

где $L_1, L_2$ — нижнетреугольные матрицы с единичной диагональю, а $U_1, U_2$ — верхнетреугольные матрицы. Тогда

L_2^{-1} L_1 = U_2 U_1^{-1}

Левая часть — произведение нижнетреугольных матриц с единичной диагональю, значит это тоже нижнетреугольная матрица с единицами на диагонали. Правая часть — произведение верхнетреугольных матриц, то есть верхнетреугольная матрица.

Следовательно, матрица $L_2^{-1} L_1$ одновременно нижнетреугольна и верхнетреугольна, а значит является диагональной. Так как её диагональные элементы равны единице, получаем $L_2^{-1} L_1 = I_n$ , то есть $L_1 = L_2$ . Из равенства $A = L_1 U_1 = L_1 U_2$ следует $U_1 = U_2$ . Тем самым единственность LU-разложения доказана.

Теорема о существовании и единственности LU-разложения отвечает на вопрос «когда» и «в каком виде» матрица $A$ представима как произведение $A = L \cdot U$ с нижнетреугольными и верхнетреугольными множителями. При этом в доказательстве мы опирались на метод Гаусса, где прямой ход даёт матрицу $U$ , а коэффициенты, которыми вычитались строки, образуют матрицу $L$ .

Полезно, однако, уметь строить матрицы $L$ и $U$ по явным формулам для их элементов. Такое описание удобно как для теории, так и для реализации алгоритма в виде кода. Из равенства $A = L \cdot U$ можно поэлементно вывести рекуррентные формулы, позволяющие последовательно вычислять строки $U$ и столбцы $L$ — именно их мы сейчас выпишем.

Рекуррентные формулы построения

Пусть $A = a_{i,j}$ и мы ищем матрицы $L$ и $U$ вида

L = \begin{pmatrix} 1 & 0 & 0 & \cdots & 0 \\ l_{2,1} & 1 & 0 & \cdots & 0 \\ l_{3,1} & l_{3,2} & 1 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ l_{n,1} & l_{n,2} & l_{n,3} & \cdots & 1 \end{pmatrix} \quad U = \begin{pmatrix} u_{1,1} & u_{1,2} & u_{1,3} & \cdots & u_{1,n} \\ 0 & u_{2,2} & u_{2,3} & \cdots & u_{2,n} \\ 0 & 0 & u_{3,3} & \cdots & u_{3,n} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & u_{n,n} \end{pmatrix}

Из равенства $A = L \cdot U$ поэлементно получаются формулы для элементов $U$ и $L$

u_{i,j} = a_{i,j} - \sum\limits_{k=1}^{i-1} l_{i,k} u_{k,j} \quad (i \le j)

l_{i,j} = \frac{a_{i,j} - \sum\limits_{k=1}^{j-1} l_{i,k} u_{k,j}}{u_{j,j}} \quad (i > j)

Сначала по этим формулам вычисляют элементы первой строки $U$ и первого столбца $L$ , затем переходят ко второй строке и второму столбцу и так далее. Условие теоремы обеспечивает $u_{j,j} \ne 0$ , поэтому деления на ноль не возникает.

Пример. Пусть $A = \begin{pmatrix} 2 & 1\\ 4 & 3 \end{pmatrix}$ над полем $R$ . Ищем $L$ и $U$ такого вида

L = \begin{pmatrix} 1 & 0 \\ l_{2,1} & 1 \end{pmatrix} \quad U = \begin{pmatrix} u_{1,1} & u_{1,2} \\ 0 & u_{2,2} \end{pmatrix}

Из равенства $A = L \cdot U$ поэлементно получаем

u_{1,1} = a_{1,1} = 2 \qquad u_{1,2} = a_{1,2} = 1

l_{2,1} = \frac{a_{2,1}}{u_{1,1}} = \frac{4}{2} = 2

u_{2,2} = a_{2,2} - l_{2,1} u_{1,2} = 3 - 2 \cdot 1 = 1

Таким образом, $L = \begin{pmatrix} 1 & 0\\ 2 & 1 \end{pmatrix}$ и $U = \begin{pmatrix} 2 & 1\\ 0 & 1 \end{pmatrix}$ . Проверим, что действительно $A = L \cdot U$

L \cdot U = \begin{pmatrix} 1 & 0\\ 2 & 1 \end{pmatrix} \begin{pmatrix} 2 & 1\\ 0 & 1 \end{pmatrix} = \begin{pmatrix} 1 \cdot 2 + 0 \cdot 0 & 1 \cdot 1 + 0 \cdot 1 \\ 2 \cdot 2 + 1 \cdot 0 & 2 \cdot 1 + 1 \cdot 1 \end{pmatrix} = \begin{pmatrix} 2 & 1 \\ 4 & 3 \end{pmatrix} = A

Решение системы Ax = b через LU-разложение

Пусть матрица $A \in K^{n \times n}$ допускает LU-разложение $A = L \cdot U$ , где $L$ — нижнетреугольная матрица с единицами на диагонали, а $U$ — верхнетреугольная матрица с ненулевыми диагональными элементами $u_{k,k} \ne 0$ для всех $k = 1, \dots, n$ . Рассмотрим систему $A \cdot x = b$ с неизвестным $x \in K^n$ и правой частью $b \in K^n$ . Подставим разложение

L \cdot U \cdot x = b

Обозначим $U \cdot x = y$ , где $y \in K^n$ . Тогда сначала решаем систему $L \cdot y = b$ с нижнетреугольной матрицей, а затем систему $U \cdot x = y$ с верхнетреугольной матрицей.

Для нижнетреугольной системы $L \cdot y = b$ решения находятся прямой подстановкой сверху вниз. Компоненты $y_k$ вычисляются по формулам

y_k = b_k - \sum\limits_{j=1}^{k-1} l_{k,j} y_j \quad k = 1, 2, \dots, n

Затем для системы $U \cdot x = y$ выполняем обратный ход снизу вверх

x_k = \dfrac{y_k - \sum\limits_{j \;\! = \;\! k+1}^{n} u_{k,j} \ x_j}{u_{k,k}} \quad k = n, n-1, \dots, 1

Поскольку $u_{k,k} \ne 0$ , каждое деление корректно, и так решение системы $A \cdot x = b$ разбивается на два простых шага с треугольными матрицами. Когда нужно решить много систем с одной и той же матрицей $A$ и разными правыми частями $b$ , LU-разложение позволяет один раз найти $L$ и $U$ , а затем быстро пересчитывать решения для новых векторов $b$ .

Связь с методом Гаусса и определителя

LU-метод по сути совпадает с методом Гаусса без перестановок строк, но записан в матричной форме. Прямой ход метода Гаусса даёт верхнетреугольную матрицу $U$ и модифицированный столбец правых частей, а коэффициенты, которыми мы вычитали строки, образуют матрицу $L$ . Тем самым LU-разложение просто «запоминает» сделанные элементарные преобразования.

Если разложение $A = L \cdot U$ построено, вычисление определителя упрощается. Поскольку диагональные элементы $L$ равны единице, имеем

\lvert A \rvert = \lvert L \rvert \cdot \lvert U \rvert = 1 \cdot \prod\limits_{i=1}^{n} u_{i,i} = \prod\limits_{i=1}^{n} u_{i,i}

То есть определитель матрицы $A$ равен произведению диагональных элементов матрицы $U$ . В случае разложения с перестановками строк $P \cdot A = L \cdot U$ знак определителя меняется в зависимости от матрицы перестановки $P$ .

LU-разложение также можно использовать для вычисления обратной матрицы. Разложив $A = L \cdot U$ , последовательно решаем системы $A \cdot x_i = e_i$ для стандартных базисных векторов $e_i$ , $i = 1, \dots, n$ . Для каждого $i$ сначала решаем $L \cdot y_i = e_i$ , затем $U \cdot x_i = y_i$ . Столбцы $x_i$ образуют матрицу $A^{-1}$ .

Таким образом, LU-разложение служит универсальным инструментом один раз «дорого» разложив матрицу $A$ , мы можем эффективно решать системы $A \cdot x = b$ , находить детерминант и обратную матрицу. В следующих разделах мы увидим, как идеи метода Гаусса и LU-разложения обобщаются на переопределённые и недоопределённые системы.

В случае, когда матрица $A$ допускает разложение $A = L \cdot U$ , многие важные численные характеристики $A$ выражаются через треугольные множители. В частности, определитель можно записать как произведение диагональных элементов матрицы $U$ и по его значению отличать невырождённые матрицы от вырожденных.

Поэтому имеет смысл отдельно ввести понятие определителя, разобрать его основные свойства и геометрический смысл. Это даст компактные критерии обратимости матриц и позволит аккуратно формулировать утверждения вида $\lvert A \rvert = \lvert L \rvert \cdot \lvert U \rvert$ и эквивалентность условий $\lvert A \rvert \ne 0$ и существования обратной матрицы $A^{-1}$ .

Определитель

Определитель квадратной матрицы

Пусть $A \in K^{n \times n}$ — квадратная матрица. Числовым отображением, сопоставляющим каждой такой матрице число $\lvert A \rvert$ , называется определитель, если для любой матрицы $A$ число $\lvert A \rvert$ удовлетворяет трём свойствам

Линейность по строке. Определитель линейно зависит от элементов каждой строки при фиксированных остальных строках.
Обращение в ноль на вырожденных матрицах. Если строки матрицы линейно зависимы, то $\lvert A \rvert = 0$ .
Нормировка. Для единичной матрицы $I_n$ выполняется $\lvert I_n \rvert = 1$ .

Пример. Для матрицы $A = \begin{pmatrix} a & b\\ c & d \end{pmatrix}$ по известной формуле имеем $\lvert A \rvert = ad - bc$ .

Возьмём конкретную матрицу $A = \begin{pmatrix} 1 & 2\\ 3 & 4 \end{pmatrix}$ .

\lvert A \rvert = 1 \cdot 4 - 2 \cdot 3 = 4 - 6 = -2

Для матриц порядка два существует простая явная формула $\left\lvert \begin{smallmatrix} a & b\\ c & d \end{smallmatrix} \right\rvert = ad - bc$ . Для матрицы порядка три определитель часто находят либо по формуле Саррюса, выписывая дополнительные диагонали, либо по правилу разложения по строке или столбцу разлагают $\lvert A \rvert$ по выбранной строке через миноры и алгебраические дополнения.

Для матриц более высокого порядка $n \ge 4$ прямые формулы становятся громоздкими, поэтому на практике определитель обычно вычисляют, приводя матрицу к треугольному виду методом Гаусса или используя LU-разложение, в треугольном случае $\lvert A \rvert$ равен произведению диагональных элементов с учётом знака перестановок строк.

Пример. Определитель через LU-разложение. Рассмотрим матрицу порядка три $A = \begin{pmatrix} 2 & 1 & 1 \\ 4 & 3 & 3 \\ 2 & 3 & 4 \end{pmatrix}$ над полем $R$ . По рекуррентным формулам из раздела про LU-разложение найдём матрицы $L$ и $U$ такие, что $A = L \cdot U$ .

Сначала вычисляем элементы первой строки $U$ и первого столбца $L$

u_{1,1} = a_{1,1} = 2 \quad u_{1,2} = a_{1,2} = 1 \quad u_{1,3} = a_{1,3} = 1

l_{2,1} = \frac{a_{2,1}}{u_{1,1}} = \frac{4}{2} = 2 \quad l_{3,1} = \frac{a_{3,1}}{u_{1,1}} = \frac{2}{2} = 1

Переходим ко второй строке и второму столбцу. По формулам для элементов $U$ и $L$

u_{2,2} = a_{2,2} - l_{2,1} u_{1,2} = 3 - 2 \cdot 1 = 1

u_{2,3} = a_{2,3} - l_{2,1} u_{1,3} = 3 - 2 \cdot 1 = 1

l_{3,2} = \frac{a_{3,2} - l_{3,1} u_{1,2}}{u_{2,2}} = \frac{3 - 1 \cdot 1}{1} = 2

Наконец, найдём элемент $u_{3,3}$

u_{3,3} = a_{3,3} - l_{3,1} u_{1,3} - l_{3,2} u_{2,3} = 4 - 1 \cdot 1 - 2 \cdot 1 = 1

Получаем разложение

L = \begin{pmatrix} 1 & 0 & 0 \\ 2 & 1 & 0 \\ 1 & 2 & 1 \end{pmatrix} \quad U = \begin{pmatrix} 2 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{pmatrix} \quad A = L \cdot U

Определитель тогда легко находится по диагонали матрицы $U$

\lvert A \rvert = \lvert L \rvert \cdot \lvert U \rvert = 1 \cdot (2 \cdot 1 \cdot 1) = 2

Здесь $\lvert L \rvert = 1$ , поскольку $L$ — нижнетреугольная матрица с единицами на диагонали, а $\lvert U \rvert$ равен произведению диагональных элементов $U$ . Для матриц большего порядка тот же алгоритм Гаусса и LU-разложения позволяет вычислять определитель столь же систематично и удобно, в отличие от прямого разложения по строке, где число слагаемых быстро растёт.

Геометрический смысл определителя

В пространствах $\RR^2$ и $\RR^3$ у определителя есть наглядная геометрическая интерпретация. Пусть столбцы матрицы $A$ — координаты векторов $v_1, \dots, v_n$ .

В $\RR^2$ число $\lvert A \rvert$ равно площади параллелограмма, построенного на векторах $v_1, v_2$ .
В $\RR^3$ $\lvert A \rvert$ равно объёму параллелепипеда, построенного на $v_1, v_2, v_3$ .
В общем случае $\lvert A \rvert$ показывает, во сколько раз линейное отображение $A$ изменяет объём и меняет ли оно ориентацию знак определителя отвечает за ориентацию, а модуль — за коэффициент изменения объёма.

Если $\lvert A \rvert = 0$ , то объём параллелепипеда равен нулю векторы $v_1, \dots, v_n$ линейно зависимы и лежат в некотором подпространстве меньшей размерности. Это согласуется с тем, что такая матрица вырождена.

Линейность по строке

Свойство линейности по строке удобно формулировать так. Пусть матрица $A$ отличается от матрицы $A_1$ только одной строкой и в этой строке стоит вектор $\alpha p + \beta q$ вместо вектора $p$ или $q$ .

Тогда определитель можно разложить

\lvert A \rvert = \alpha \cdot \lvert A_p \rvert + \beta \cdot \lvert A_q \rvert

где $A_p$ и $A_q$ получены из $A$ заменой рассматриваемой строки на $p$ и $q$ соответственно.

Общий множитель в одной строке можно вынести за знак определителя
$\left\lvert \begin{pmatrix} \alpha \cdot a_{1,1} & \dots & \alpha \cdot a_{1,n}\\ \ast & \dots & \ast\\ \vdots & & \vdots \end{pmatrix} \right\rvert = \alpha \cdot \left\lvert \begin{pmatrix} a_{1,1} & \dots & a_{1,n}\\ \ast & \dots & \ast\\ \vdots & & \vdots \end{pmatrix} \right\rvert$
Если строка матрицы является суммой нескольких строк, то определитель равен сумме определителей матриц, в которых эта строка по очереди заменяется каждым слагаемым.

Пример. Рассмотрим матрицу $C = \begin{pmatrix} 2 & 4\\ 3 & 1 \end{pmatrix}$ и заметим, что первая строка представима как $2 (1, 2)$ .

\lvert C \rvert = \left\lvert \begin{pmatrix} 2 & 4\\ 3 & 1 \end{pmatrix} \right\rvert = 2 \left\lvert \begin{pmatrix} 1 & 2\\ 3 & 1 \end{pmatrix} \right\rvert

\left\lvert \begin{pmatrix} 1 & 2\\ 3 & 1 \end{pmatrix} \right\rvert = 1 \cdot 1 - 2 \cdot 3 = -5

\lvert C \rvert = 2 \cdot (-5) = -10

Сложение строки с другой строкой

Прибавление к строке другой строки

Если к некоторой строке матрицы прибавить другую строку, умноженную на число, то определитель не изменится.

Пусть в матрице $A$ заменили $i$ -ю строку на $a_i + \lambda \cdot a_j$ , где $i \ne j$ , и получили матрицу $A'$ .

По линейности по строке

\lvert A' \rvert = \lvert A \rvert + \lambda \cdot \lvert A_j \rvert

где $A_j$ — матрица, в которой $i$ -я строка заменена на $a_j$ . В матрице $A_j$ строки $a_j$ и $a_j$ совпадают, значит они линейно зависимы и $\lvert A_j \rvert = 0$ . Следовательно, $\lvert A' \rvert = \lvert A \rvert$ .

Пример. Пусть $A = \begin{pmatrix} 1 & 2\\ 3 & 4 \end{pmatrix}$ , и из второй строки вычитаем первую умноженную на $3$

A' = \begin{pmatrix} 1 & 2\\ 3 & 4 \end{pmatrix} \xrightarrow[]{R_2 \to R_2 - 3 R_1} \begin{pmatrix} 1 & 2\\ 0 & -2 \end{pmatrix}

Вычислим оба определителя

\lvert A \rvert = 1 \cdot 4 - 2 \cdot 3 = -2

\lvert A' \rvert = 1 \cdot (-2) - 2 \cdot 0 = -2

В соответствии с теоремой значение определителя не изменилось.

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

Мы увидели, что определитель отражает сразу несколько важных свойств матрицы: по нему можно судить о вырожденности и удобно вычислять его с помощью метода Гаусса или LU-разложения. Естественно возникает вопрос, как это связано с возможностью «обратить» линейное преобразование, то есть восстановить входной вектор по его образу.

Оказывается, определитель как раз и даёт критерий обратимости: квадратная матрица обратима тогда и только тогда, когда её определитель отличен от нуля. В следующем разделе мы сформулируем это более строго, введём понятие обратной матрицы и покажем, как на практике находить $A^{-1}$ с помощью метода Гаусса.

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

Пусть $A \in K^{n \times n}$ — квадратная матрица над полем $K$ . Матрица $A^{-1} \in K^{n \times n}$ называется обратной к $A$ , если выполняется

A A^{-1} = A^{-1} A = I_n = 1

где $I_n$ — единичная матрица порядка $n$ . Матрица $A$ называется невырождённой, если обратная матрица существует.

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

Критерий обратимости через определитель

Пусть $A \in K^{n \times n}$ . Тогда эквивалентны следующие утверждения

Матрица $A$ невырождена, то есть существует $A^{-1}$ такая, что $A A^{-1} = A^{-1} A = I_n = 1$
Определитель матрицы $A$ ненулевой $\lvert A \rvert \ne 0$

Предположим, что матрица $A$ обратима. Тогда отображение $A : K^n \to K^n$ является биекцией, для любого $b \in K^n$ уравнение $A x = b$ имеет единственное решение $x = A^{-1} b$ .

Если бы строки матрицы $A$ были линейно зависимы, то существовал бы ненулевой вектор $x \ne 0$ и $A x = 0$ , то есть однородная система имела бы нетривиальное решение. Это противоречит биективности. Значит строки линейно независимы, матрица невырождена, и по свойству определителя получаем $\lvert A \rvert \ne 0$ .

Пусть теперь $\lvert A \rvert \ne 0$ . По определению определителя это означает, что строки матрицы $A$ линейно независимы. Аналогично, линейно независимы и столбцы матрицы $A$ определитель не меняется при транспонировании матрицы.

Рассмотрим линейный оператор $A : K^n \to K^n$ , действующий на столбцы-веторы. Его столбцы $a_1, \dots, a_n$ — это образы стандартного базиса $e_1, \dots, e_n$ : $A e_i = a_i$ .

Так как столбцы $a_1, \dots, a_n$ линейно независимы и их ровно $n$ , они образуют базис в пространстве $K^n$ . Значит, любой вектор $y \in K^n$ можно единственным образом представить в виде линейной комбинации этих столбцов

y = x_1 a_1 + \dots + x_n a_n

Для вектора коэффициентов $x = (x_1, \dots, x_n)^{\T}$ это равенство равносильно уравнению $A x = y$ . Таким образом, для любого $y$ существует единственный вектор $x$ такой, что $A x = y$ .

Итак, оператор $A$ биективен, он он взаимно однозначно отображает $K^n$ на $K^n$ . Для биективного линейного оператора существует обратный оператор $A^{-1} : K^n \to K^n$ , удовлетворяющий $A^{-1} A = A A^{-1} = I_n = 1$ . Матрица этого оператора в стандартном базисе и есть обратная матрица $A^{-1}$ .

Таким образом, условие $\lvert A \rvert \ne 0$ полностью эквивалентно существованию обратной матрицы и даёт удобный числовой критерий обратимости.

Пример. Пусть $A = \begin{pmatrix} 1 & 2\\ 3 & 4 \end{pmatrix}$ над полем $R$ .

Сначала найдём определитель

\lvert A \rvert = 1 \cdot 4 - 2 \cdot 3 = 4 - 6 = -2

Так как $\lvert A \rvert \ne 0$ , матрица обратима. Для матрицы размера $2 \times 2$ обратную можно найти по явной формуле

A^{-1} = \frac{1}{\lvert A \rvert} \begin{pmatrix} d & -b\\ -c & a \end{pmatrix} \quad \text{для } A = \begin{pmatrix} a & b\\ c & d \end{pmatrix}

В нашем случае $a = 1,\ b = 2,\ c = 3,\ d = 4$ , поэтому

A^{-1} = \frac{1}{-2} \begin{pmatrix} 4 & -2\\ -3 & 1 \end{pmatrix} = -\frac{1}{2} \begin{pmatrix} 4 & -2\\ -3 & 1 \end{pmatrix}

Проверим одно из равенств $A A^{-1} = I_2$

A A^{-1} = \begin{pmatrix} 1 & 2\\ 3 & 4 \end{pmatrix} \cdot \left( -\frac{1}{2} \begin{pmatrix} 4 & -2\\ -3 & 1 \end{pmatrix} \right) = -\frac{1}{2} \begin{pmatrix} 4 - 6 & -2 + 2\\ 12 - 12 & -6 + 4 \end{pmatrix}

A A^{-1} = -\frac{1}{2} \begin{pmatrix} -2 & 0\\ 0 & -2 \end{pmatrix} = \begin{pmatrix} 1 & 0\\ 0 & 1 \end{pmatrix} = I_2

Значит найденная матрица действительно является обратной к $A$ .

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

Метод Жордана–Гаусса для вычисления обратной матрицы

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

T_m \dots T_2 T_1 A = I_n = 1

то

A^{-1} = T_m \dots T_2 T_1

На практике удобно рассматривать расширенную матрицу

D = (A \mid I_n)

и выполнять элементарные преобразования строк одновременно над обеими половинами, пока левая часть не превратится в единичную матрицу. Тогда правая часть становится $A^{-1}$

(A \mid I_n) \sim (I_n \mid A^{-1})

Пример. Найдём обратную матрицу для $A = \begin{pmatrix} 1 & 2\\ 3 & 4 \end{pmatrix}$ с помощью метода Гаусса.

Рассмотрим расширенную матрицу

(A \mid I_2) = \begin{pmatrix} 1 & 2 & 1 & 0\\ 3 & 4 & 0 & 1 \end{pmatrix}

Вычтем из второй строки первую, умноженную на $3$

\begin{pmatrix} 1 & 2 & 1 & 0\\ 3 & 4 & 0 & 1 \end{pmatrix} \xrightarrow[]{R_2 \to R_2 - 3 R_1} \begin{pmatrix} 1 & 2 & 1 & 0\\ 0 & -2 & -3 & 1 \end{pmatrix}

Теперь умножим вторую строку на $-\tfrac{1}{2}$ , чтобы получить единицу на диагонали

\begin{pmatrix} 1 & 2 & 1 & 0\\ 0 & -2 & -3 & 1 \end{pmatrix} \xrightarrow[]{R_2 \to -\tfrac{1}{2} R_2} \begin{pmatrix} 1 & 2 & 1 & 0\\ 0 & 1 & \tfrac{3}{2} & -\tfrac{1}{2} \end{pmatrix}

Вычтем из первой строки вторую, умноженную на $2$ , чтобы занулить элемент над единицей

\begin{pmatrix} 1 & 2 & 1 & 0\\ 0 & 1 & \tfrac{3}{2} & -\tfrac{1}{2} \end{pmatrix} \xrightarrow[]{R_1 \to R_1 - 2 R_2} \begin{pmatrix} 1 & 0 & -2 & 1\\ 0 & 1 & \tfrac{3}{2} & -\tfrac{1}{2} \end{pmatrix}

Левая часть превратилась в $I_2$ , правая часть и есть матрица $A^{-1}$

A^{-1} = \begin{pmatrix} -2 & 1\\ \tfrac{3}{2} & -\tfrac{1}{2} \end{pmatrix}

Квадратные невырождённые системы

В предыдущем разделе мы показали, что для квадратной матрицы $A \in K^{n \times n}$ условия $\lvert A \rvert \ne 0$ и существование обратной матрицы $A^{-1}$ эквивалентны. Теперь используем это, чтобы описать поведение системы $A x = b$ в невырождённом случае.

Система с квадратной невырождённой матрицей

Пусть $A \in K^{n \times n}$ и $\lvert A \rvert \ne 0$ . Тогда для любого $b \in K^n$ система $A \cdot x = b$ имеет единственное решение.

Из эквивалентности $\lvert A \rvert \ne 0$ и обратимости следует, что существует матрица $A^{-1}$ и линейный оператор $A : K^n \to K^n$ биективен.

Умножим систему $A \cdot x = b$ слева на $A^{-1}$

A^{-1} A \cdot x = A^{-1} b

I_n \cdot x = A^{-1} b

x = A^{-1} b

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

Пример. Возьмём матрицу $A = \begin{pmatrix} 1 & 2\\ 3 & 4 \end{pmatrix}$ и вектор $b = \begin{pmatrix} 5\\ 11 \end{pmatrix}$ , как в самом начале статьи.

Мы уже нашли $A^{-1}$ , поэтому решение можно записать как

x = A^{-1} b = -\frac{1}{2} \begin{pmatrix} 4 & -2\\ -3 & 1 \end{pmatrix} \begin{pmatrix} 5\\ 11 \end{pmatrix}

x = -\frac{1}{2} \begin{pmatrix} 4 \cdot 5 + (-2) \cdot 11\\ -3 \cdot 5 + 1 \cdot 11 \end{pmatrix} = -\frac{1}{2} \begin{pmatrix} 20 - 22\\ -15 + 11 \end{pmatrix} = -\frac{1}{2} \begin{pmatrix} -2\\ -4 \end{pmatrix}

x = \begin{pmatrix} 1\\ 2 \end{pmatrix}

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

Мы уже знаем, что для невырождённой матрицы $A \in K^{n \times n}$ существует обратная матрица $A^{-1}$ и система $A x = b$ имеет единственное решение $x = A^{-1} b$ . Однако в явном виде элементы $A^{-1}$ можно выразить через определители. Из этих формул получается классическое правило Крамера, позволяющее выписывать компоненты решения непосредственно через определители.

Правило Крамера

Пусть $A \in K^{n \times n}$ невырождена ( $\lvert A \rvert \neq 0$ ) и система $A \cdot x = b$ совместна. Тогда каждую компоненту решения можно вычислить по формуле Крамера

x_i = \frac{\Delta_i}{\lvert A \rvert} \qquad \Delta_i = \lvert A_i \rvert

где $A_i$ — матрица, полученная заменой $i$ -го столбца матрицы $A$ столбцом правых частей $b$ .

Пример. Для системы

\begin{cases} x_1 + 2x_2 = 5\\ 3x_1 + 4x_2 = 11 \end{cases}

матрица коэффициентов и столбец правых частей равны

A = \begin{pmatrix} 1 & 2\\ 3 & 4 \end{pmatrix} \quad b = \begin{pmatrix} 5\\ 11 \end{pmatrix}

Найдём определитель

\lvert A \rvert = 1 \cdot 4 - 2 \cdot 3 = -2

Теперь матрицы $A_1$ и $A_2$

A_1 = \begin{pmatrix} 5 & 2\\ 11 & 4 \end{pmatrix} \qquad A_2 = \begin{pmatrix} 1 & 5\\ 3 & 11 \end{pmatrix}

\Delta_1 = \lvert A_1 \rvert = 5 \cdot 4 - 2 \cdot 11 = 20 - 22 = -2

\Delta_2 = \lvert A_2 \rvert = 1 \cdot 11 - 5 \cdot 3 = 11 - 15 = -4

По правилу Крамера

x_1 = \frac{\Delta_1}{\lvert A \rvert} = \frac{-2}{-2} = 1

x_2 = \frac{\Delta_2}{\lvert A \rvert} = \frac{-4}{-2} = 2

Получили то же решение, что и через обратную матрицу.

В невырождённом квадратном случае поведение системы полностью понятно — для любого b есть единственное решение. Чтобы описать все остальные случаи, нужна более общая характеристика — ранг матрицы.

Ранг и теорема Кронекера–Капелли

Ранг матрицы

Рангом матрицы $A$ называется максимальное число линейно независимых строк или столбцов этой матрицы. Обозначение $\rank A$ .

Пример. Рассмотрим матрицу

A = \begin{pmatrix} 1 & 2 & 3\\ 2 & 4 & 6\\ 1 & 0 & 1 \end{pmatrix}

Вторая строка равна первой, умноженной на $2$ , поэтому они линейно зависимы. Строки $(1, 2, 3)$ и $(1, 0, 1)$ линейно независимы. Значит $\operatorname{rank} A = 2$ .

То же можно увидеть методом Гаусса

\begin{pmatrix} 1 & 2 & 3\\ 2 & 4 & 6\\ 1 & 0 & 1 \end{pmatrix} \xrightarrow[]{R_2 \to R_2 - 2 R_1} \begin{pmatrix} 1 & 2 & 3\\ 0 & 0 & 0\\ 1 & 0 & 1 \end{pmatrix} \xrightarrow[]{R_3 \to R_3 - R_1} \begin{pmatrix} 1 & 2 & 3\\ 0 & 0 & 0\\ 0 & -2 & -2 \end{pmatrix}

В треугольном виде видно две ненулевые строки, значит ранг равен $2$ .

Теорема Кронекера–Капелли

Система $A \cdot x = b$ совместна тогда и только тогда, когда

\rank A = \rank A'

где $A'$ — расширенная матрица системы.

Критерий по приведённой матрице

Пусть расширенная матрица $A'$ приведена элементарными преобразованиями строк к треугольному виду.

Тогда система несовместна тогда и только тогда, когда в приведённой матрице появляется строка вида $(0, 0, \dotsc, 0 \mid 1)$ , то есть все коэффициенты при известных равны нулю, а свободный член нет.

Пример. Рассмотрим системы

\begin{cases} x_1 + x_2 = 1\\ 2x_1 + 2x_2 = 2 \end{cases} \qquad \begin{cases} x_1 + x_2 = 1\\ 2x_1 + 2x_2 = 3 \end{cases}

Для первой системы расширенная матрица и её треугольный вид таковы

A'_1 = \begin{pmatrix} 1 & 1 & 1\\ 2 & 2 & 2 \end{pmatrix} \xrightarrow[]{R_2 \to R_2 - 2 R_1} \begin{pmatrix} 1 & 1 & 1\\ 0 & 0 & 0 \end{pmatrix}

Строки вида $(0, 0 \mid 1)$ нет, значит система совместна.

Для второй системы

A'_2 = \begin{pmatrix} 1 & 1 & 1\\ 2 & 2 & 3 \end{pmatrix} \xrightarrow[]{R_2 \to R_2 - 2 R_1} \begin{pmatrix} 1 & 1 & 1\\ 0 & 0 & 1 \end{pmatrix}

Строка $(0, 0 \mid 1)$ соответствует уравнению $0 = 1$ , невозможному для любых $x_1, x_2$ , поэтому система несовместна.

Теорема Кронекера–Капелли даёт критерий совместности системы любой формы. Теперь посмотрим, как она проявляется в двух важных конфигурациях — когда уравнений больше неизвестных и наоборот.

Переопределённые и недоопределённые системы

Переопределённая и недоопределённая системы

Пусть над некоторым полем $K$ , где $m, n \in N$ и $A \in K^{m \times n}$ — матрица линейного оператора $A : K^n \to K^m$ . Рассмотрим систему линейных уравнений $A \cdot x = b$ с неизвестным $x \in K^n$ и правой частью $b \in K^m$ .

Система $A \cdot x = b$ называется переопределённой, если число уравнений больше числа неизвестных, то есть $m > n$ . В таком случае для произвольного $b$ система, вообще говоря, может не иметь точного решения, и естественно рассматривать задачи поиска приближённого решения.
Система $A \cdot x = b$ называется недоопределённой, если число уравнений меньше числа неизвестных, то есть $m < n$ . При совместности такой системы множество решений, как правило, бесконечно, и возникает задача выбрать наиболее простой вектор решения.

В случае $m = n$ систему называют квадратной, и она не относится ни к переопределённым, ни к недоопределённым.

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

Псевдообратная матрица Мура—Пенроуза

Пусть $A \in K^{m \times n}$ . Матрица $A^+ \in K^{n \times m}$ называется псевдообратной в смысле Мура—Пенроуза, если выполняются четыре условия:

A \cdot A^+ \cdot A = A

A^+ \cdot A \cdot A^+ = A^+

(A \cdot A^+)^{\T} = A \cdot A^+

(A^+ \cdot A)^{\T} = A^+ \cdot A

Здесь $^{\T}$ обозначает транспонирование (в комплексном случае обычно берут сопряжённое транспонирование). Если такая матрица существует, она единственна.

В частных случаях псевдообратная записывается через обычную обратную матрицу.

Если $A \in K^{m \times n}$ имеет полный столбцовый ранг ( $\rank A = n \le m$ ), то
$A^+ = (A^{\T} \cdot A)^{-1} \cdot A^{\T}$
Если $A \in K^{m \times n}$ имеет полный строковый ранг ( $\rank A = m \le n$ ), то
$A^+ = A^{\T} \cdot (A \cdot A^{\T})^{-1}$

Метод наименьших квадратов

Задача наименьших квадратов

Пусть $A \in \RR^{m \times n}$ и $b \in \RR^m$ , обычно $m > n$ (переопределённая система). Задача наименьших квадратов состоит в поиске вектора $x' \in \RR^n$ , минимизирующего норму остатка

x' = \argmin\limits_{x \;\! \in \;\! \RR^n} \lVert A \cdot x - b \rVert_2

то есть мы подбираем $x$ так, чтобы $A \cdot x$ как можно лучше приближало вектор наблюдений $b$ в евклидовой норме.

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

Нормальные уравнения

Пусть $A \in \RR^{m \times n}$ , $b \in \RR^m$ и матрица $A$ имеет полный столбцовый ранг $\rank A = n$ . Тогда задача наименьших квадратов имеет единственное решение $x'$ , которое удовлетворяет системе

A^{\T} \cdot A \cdot x' = A^{\T} \cdot b

Рассмотрим функцию $f(x) = \lVert A \cdot x - b \rVert_2^2$ . Раскроем квадрат:

f(x) = (A \cdot x - b)^{\T} \cdot (A \cdot x - b) = x^{\T} \cdot A^{\T} \cdot A \cdot x - 2 \cdot x^{\T} \cdot A^{\T} \cdot b + b^{\T} \cdot b

Это квадратичная функция по $x$ . Вектор-градиент равен

\nabla f(x) = 2 \cdot A^{\T} \cdot A \cdot x - 2 \cdot A^{\T} \cdot b

В точке минимума градиент равен нулю, поэтому получаем уравнение $A^{\T} \cdot A \cdot x' = A^{\T} \cdot b$ . Матрица $A^{\T} \cdot A$ невырождена благодаря полноранговости $A$ , значит решение единственно.

Геометрическая интерпретация

Рассмотрим линейный оператор $A : \RR^n \to \RR^m$ и его образ $\operatorname{Im} A \subset \RR^m$ . Вектор $A \cdot x$ всегда лежит в $\operatorname{Im} A$ , а $b$ вообще говоря, не обязан туда попадать.

Решение задачи наименьших квадратов можно описать так: $A \cdot x'$ — это ортогональная проекция вектора $b$ на подпространство $\operatorname{Im} A$ .

Действительно, вектор остатка $r' = b - A \cdot x'$ при этом ортогонален всему подпространству $\operatorname{Im} A$

\forall\, y \in \operatorname{Im} A \quad \langle r' y \rangle = 0

Так как любой $y \in \operatorname{Im} A$ имеет вид $y = A \cdot z$ , условие ортогональности эквивалентно $A^{\T} \cdot (b - A \cdot x') = 0$ , то есть нормальным уравнениям $A^{\T} \cdot A \cdot x' = A^{\T} \cdot b$ .

Связь с псевдообратной матрицей

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

x' = A^+ \cdot b

Если $\rank A = n \le m$ , то $A^+ = (A^{\T} \cdot A)^{-1} \cdot A^{\T}$ и из нормальных уравнений сразу получаем

x' = (A^{\T} \cdot A)^{-1} \cdot A^{\T} \cdot b = A^+ \cdot b

Это решение единственно и даёт вектор минимальной нормы, если решений задачи наименьших квадратов несколько.

В случае недоопределённой системы $A \cdot x = b$ при $m < n$ , когда решений (при совместности) бесконечно много, псевдообратная матрица также выделяет «наиболее короткое» решение:

x' = A^+ \cdot b

это единственное решение минимальной нормы $\lVert x' \rVert_2 = \min\limits \{\lVert x \rVert_2 \mid A \cdot x = b\}$ .

Таким образом, псевдообратная матрица Мура—Пенроуза и метод наименьших квадратов дают единый язык для описания переопределённых и недоопределённых систем: в обоих случаях вектор $A^+ \cdot b$ играет роль «наилучшего» решения — либо в смысле минимизации ошибки $\lVert A \cdot x - b \rVert$ , либо в смысле минимальной нормы среди всех точных решений.

Пример. Пусть

A = \begin{pmatrix} 1 & 0\\ 1 & 1\\ 1 & 2 \end{pmatrix}, \quad b = \begin{pmatrix} 1\\ 2\\ 2 \end{pmatrix}

Это переопределённая система в $\RR^3$ с двумя неизвестными. Решим её методом наименьших квадратов.

Составим нормальные уравнения:

A^{\T} \cdot A = \begin{pmatrix} 3 & 3\\ 3 & 5 \end{pmatrix} \quad A^{\T} \cdot b = \begin{pmatrix} 5\\ 6 \end{pmatrix}

A^{\T} \cdot A \cdot x = A^{\T} \cdot b \iff \begin{cases} 3 x_1 + 3 x_2 = 5\\ 3 x_1 + 5 x_2 = 6 \end{cases}

Вычитаем первое уравнение из второго $2 \cdot x_2 = 1$ , значит $x_2 = \tfrac{1}{2}$ . Подставляя обратно, получаем $3 \cdot x_1 + 3 \cdot \tfrac{1}{2} = 5$ , откуда $x_1 = \tfrac{7}{6}$ .

x' = \begin{pmatrix} \tfrac{7}{6}\\[2pt] \tfrac{1}{2} \end{pmatrix}

Вектор $A \cdot x'$ есть ортогональная проекция $b$ на $\Im} A$ , а сам $x'$ совпадает с $A^+ \cdot b$ для данной матрицы $A$ с полным столбцовым рангом.