Linear algebra background

Вопросы

• Что такое вектор и матрица?
• Какие основные свойства векторов и матриц?
• Какая сложность базовых операций с векторами и матрицами?
• Какие функции от векторов и матриц существуют?
• Какие типы матриц Вы знаете?

Объекты

• Вектор: $x = (x_1, \ldots, x_n) \in \mathbb{R}^n$
• Матрица: $A = (a_{ij}) \in \mathbb{R}^{m \times n}$, $i=1,\ldots,m$, $j = 1,\ldots,n$
• Система линейных уравнений: $Ax = b$

Свойства

• Определение Набор ненулевых векторов называется линейно зависимым, если существует их линейная комбинация, с хотя бы одним ненулевым коэффициентом, равная нулю
• Определение Рангом матрицы $A$ называется число линейно независимых столбцов
• Определение Матрица $A$ называется положительно-определённой, если для любого ненулевого вектора $x$ выполнено $$ A \succ 0 \iff x^{\top}A x > 0 $$ Аналогично определяется отрицательная определённость и полуопределённость (положительная и отрицательная)

• Определение Матрица называется ортогональной, если $$ AA^{\top} = I $$
• Определение Следом квадратной матрицы $A$ называется сумма диагональных элементов: $$ \mathrm{trace}(A) = \sum_{i=1}^n a_{ii} $$

Теоремы

• Теорема о ранге матрицы: строчной ранг матрицы равен её столбцовому рангу
• Критерий Сильвестра: матрица положительно определена тогда и только тогда, когда все её главные миноры положительны

Операции

• Сложение и вычитание векторов, умножение вектора на скаляр - поэлементно - $O(n)$ операций (flops)
• Скалярное произведение: $$ \langle x, y \rangle = \sum_{i=1}^n x_i y_i - O(n) \text{ операций} $$

• Умножение матрицы на вектор: $$ (Ax)_i = \sum_{k=1}^n a_{ik}x_k, $$ где $A \in \mathbb{R}^{m \times n}$ и $x \in \mathbb{R}^n$:
  • для плотной матрицы $A$ — $O(mn)$
  • для разреженной матрицы $A$ с $N \ll mn$ ненулевыми элементами — $O(N)$
  • для малоранговой матрицы $A = UV^{\top}$, где $U \in \mathbb{R}^{m \times p}, \; V \in \mathbb{R}^{n \times p}$ и $p \ll \min(n, m)$ — $O(p(n + m))$
  • для некоторых специальных типов матриц (Тёплицева матрица, циркулянт, $\mathcal{H}$ и $\mathcal{H}^2$ матрицы) умножение на вектор может быть выполнено быстрее

• Умножение матрицы на матрицу: $$ A = BC \qquad a_{ij} = \sum_{k=1}^p b_{ik}c_{kj}, $$ где $A \in \mathbb{R}^{m \times n}$, $B \in \mathbb{R}^{m \times p}$ и $C \in \mathbb{R}^{p \times n}$
  • для плотных матриц $B$ и $C$ — $O(mnp)$ операций
  • существенно меньше если одна или обе матрицы $B$ и $C$ разреженны

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

Для произвольной квадратной матрицы $A \in \mathbb{R}^{n \times n}$ система линейных уравнений решается за $O(n^3)$ операций

Вопросы

• Когда системы линейных уравнений разрешима?
• Что такое обратная матрица?
• Как решать системы линейных уравнений?
• Для каких матриц система линейных равнений может быть легко решена?

Для каких матриц $A$ система может быть быстро решена?

• Диагональная матрица $A$ — $O(n)$ операций
• Нижне- или верхнетреугольная — $O(n^2)$ операций. Метод называется прямой или обратной подстановкой
• Oртогональная матрица $A$
  • для произвольной ортогональной матрицы - $O(n^2)$ операций
  • если известна структура матрицы (например $A = I - 2uu^{\top}$, $u$ - вектор) — $O(n)$ операций

Вопрос Что геометрически означает умножение матрицы $A = I - 2uu^{\top}$ на вектор?

Метод решения ситемы $Ax = b$ с помощью разложения матрицы $A$

1. Представим матрицу $A$ в виде произведения $k$ "простых" матриц (диагональных, верхне- или нижнетреугольных и др...) $$ A = A_1A_2\ldots A_k $$
2. Для получения $x$ решим $k$ систем вида $$ A_1x_1 = b \quad A_2x_2 = x_1 \quad \ldots \quad A_kx = x_{k-1} $$ Это можно сделать быстро, так как матрицы $A_i$ простые.

Также метод удобен для решения набора систем с одинаковой матрицей и $m$ правыми частями $b_i, \; i=1,\ldots,m$:

• разложить матрицу $A$ в произведение простых матриц необходимо единственный раз
• после чего $m$ раз последовательно решить системы для каждого $b_i$

LU разложение

Теорема. Любая невырожденная матрица $A$ может быть представлена в виде $$ A = PLU, $$ где $P$ — матрица перестановки, $L$ — нижнетреугольная матрица, $U$ — верхнетреугольная матрица

Сложность разложения — $2n^3/3$ операций

Вопрос Какая сложность решения системы $Ax=b$, если дано LU разложение матрицы $A$?

Вопрос Зачем нужна перестановка $P$?

Разложение Холецкого

Теорема. Любая симметричная положительно определённая матрица $A$ может быть представлена в виде $$ A = LL^{\top}, $$ где $L$ — нижнетреугольная матрица.

Сложность вычисления разложения Холецкого — $n^3/3$ операций

Вопрос Какая сложность решения системы $Ax=b$ с использованием разложения Холецкого?

Система линейных уравнений вида $(A + BC)x = b$

• $A$ — "простая" матрица, т.е. $Ax = b$ можно быстро решить
• $BC$ — представление малоранговой матрицы

Как быстро решать такие системы, Вам будет предложено подумать в домашнем задании :)

Собственные векторы и собственые значения

Вопросы

1. Что такое собственые вектора и собственные значения?
2. Когда матрица являются диагонализуемой и унитарно диагонализуемой?
3. Как находить спектр матрицы полностью и частичо?

Определение. Ненулевой вектор $x$ называется собственным вектором преобразования, заданного матрицей $A$, если $$ Ax = \lambda x, $$ где $\lambda$ - собственное значение, соответствующее собственному вектору $x$.

Если у матрицы $A$ есть $n$ линейно незаивисимых собственных векторов, то её можно представить в виде спектрального разложения: $$ A = X\Lambda X^{-1}, $$ где $\Lambda = \mathrm{diag}(\lambda_1, \ldots, \lambda_n)$, а $X = [x_1, \ldots, x_n]$

Теоремы

1. Матрица унитарно диагонализуема тогда и только тогда, когда она нормальна: $$ AA^* = A^*A $$
2. $$ \mathrm{tr}(A) = \sum_{i=1}^n \lambda_i \quad \det(A) = \prod_{i=1}^n \lambda_i $$
3. Матрица положительно определена тогда и только тогда, когда все её собственные значения положительны

Как вычислять?

1. Нахождение всех собственных векторов и собственных значений: $O(n^3)$ - метод Якоби, QR-алгоритм, использование разложения Шура...
2. Однако полное спектральное разложение бывает необходимо редко. Обычно нужно несколько собственных векторов, соответствующих максимальным собственным значениям. Для решения этой задачи используется степенной метод и метод обратной итерации

Резюме

1. Линейная алгебра — один из базовых инструментов в методах оптимизации
2. Операции с векторами и матрицами
3. Решение систем линейных уравнений
4. Нахождение собственных значений и векторов