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

Когда матрица $A$ действует на вектор $\mathbf{v}$, результат $A\mathbf{v}$ в общем случае — другой вектор: другое направление, другая длина. Но для некоторых специальных векторов $A\mathbf{v}$ указывает в том же направлении, что и $\mathbf{v}$, только растянут или сжат скалярным множителем. Эти векторы называются собственными векторами, а этот скалярный множитель — собственным значением.

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

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

Интуиция: направления, которые не меняются

Рассмотрим матрицу 2×2 и её действие на плоскость. Типичная матрица вращает и масштабирует большинство векторов — вектор $\mathbf{v}$ превращается в $A\mathbf{v}$, указывающий, как правило, в другом направлении.

Для большинства матриц существуют ровно два особых направления (в 2D), вдоль которых матрица только растягивает или сжимает, не вращая. Это направления собственных векторов. Вектор, направленный вдоль направления собственного вектора, остаётся вдоль этого направления после действия матрицы.

Пример 1. Рассмотрим матрицу $A=\left(\begin{array}{cc}3& 0\\ 0& 2\end{array}\right)$.

Вектор ${\mathbf{v}}_1=(1,0)$ удовлетворяет $A{\mathbf{v}}_1=(3,0)=3{\mathbf{v}}_1$. Значит, ${\mathbf{v}}_1$ — собственный вектор с собственным значением 3.

Вектор ${\mathbf{v}}_2=(0,1)$ удовлетворяет $A{\mathbf{v}}_2=(0,2)=2{\mathbf{v}}_2$. Значит, ${\mathbf{v}}_2$ — собственный вектор с собственным значением 2.

Матрица $A$ растягивает ось x в 3 раза и ось y в 2 раза. Эти две оси и есть направления собственных векторов.

Для общих матриц (не диагональных, как в этом примере) собственные векторы не выровнены по стандартным осям — они могут указывать в любом направлении. Но идея та же: существуют особые направления, которые матрица только растягивает.

Формальное определение

Собственный вектор матрицы $A$ — это ненулевой вектор $\mathbf{v}$, такой что

$A\mathbf{v}=\lambda \mathbf{v}$

для некоторого скаляра $\lambda$. Скаляр $\lambda$ — собственное значение, соответствующее $\mathbf{v}$.

Две технические детали:

1. Нулевой вектор исключён — он тривиально удовлетворяет $A0=\lambda 0$ для любого $\lambda$, так что называть его собственным вектором было бы неинтересно.
2. Собственное значение $\lambda$ может быть равно нулю. Собственный вектор с собственным значением ноль — это вектор, который $A$ отображает в нулевой вектор.

Как вычислять собственные значения

Перепишем уравнение $A\mathbf{v}=\lambda \mathbf{v}$ как $A\mathbf{v}-\lambda \mathbf{v}=0$, или $(A-\lambda I)\mathbf{v}=0$.

Для того чтобы это уравнение имело ненулевое решение $\mathbf{v}$, матрица $A-\lambda I$ должна быть выражденной — иметь нулевой определитель.

Характеристическое уравнение:

$\det (A-\lambda I)=0$

Это полиномиальное уравнение по $\lambda$. Решая его, находят собственные значения.

Пример 2. Найти собственные значения матрицы $A=\left(\begin{array}{cc}4& 1\\ 2& 3\end{array}\right)$.

$A-\lambda I=\left(\begin{array}{cc}4-\lambda & 1\\ 2& 3-\lambda \end{array}\right)$

$\det (A-\lambda I)=(4-\lambda )(3-\lambda )-2={\lambda }^2-7\lambda +10=0$

Решаем: $\lambda =\frac{7\pm \sqrt{49-40}}{2}=\frac{7\pm 3}{2}$, значит, $\lambda =5$ или $\lambda =2$.

Собственные значения — 5 и 2.

Как вычислять собственные векторы

Для каждого собственного значения $\lambda$ решаем $(A-\lambda I)\mathbf{v}=0$ относительно $\mathbf{v}$.

Пример 3 (продолжение Примера 2). Найти собственные векторы матрицы $A=\left(\begin{array}{cc}4& 1\\ 2& 3\end{array}\right)$.

Для $\lambda =5$:

$A-5I=\left(\begin{array}{cc}-1& 1\\ 2& -2\end{array}\right)$

Решаем $\left(\begin{array}{cc}-1& 1\\ 2& -2\end{array}\right)\left(\begin{array}{c}x\\ y\end{array}\right)=\left(\begin{array}{c}0\\ 0\end{array}\right)$.

Обе строки дают $x=y$. Значит, собственный вектор — $(1,1)$ (или любой его скалярный кратный).

Для $\lambda =2$:

$A-2I=\left(\begin{array}{cc}2& 1\\ 2& 1\end{array}\right)$

Обе строки дают $2x+y=0$, то есть $y=-2x$. Собственный вектор — $(1,-2)$.

Таким образом, собственные векторы — ${\mathbf{v}}_1=(1,1)$ (собственное значение 5) и ${\mathbf{v}}_2=(1,-2)$ (собственное значение 2). Можно проверить: $A{\mathbf{v}}_1=(5,5)=5{\mathbf{v}}_1$ и $A{\mathbf{v}}_2=(2,-4)=2{\mathbf{v}}_2$. ✓

Диагонализация

Матрица диагонализируема, если у неё есть полный набор собственных векторов — достаточно, чтобы образовать базис.

Для диагонализируемой матрицы $A$:

$A=PD{P}^{-1}$

где $D$ — диагональная матрица с собственными значениями на диагонали, а $P$ — матрица, чьи столбцы — соответствующие собственные векторы.

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

В частности, $A^n=P{D}^n{P}^{-1}$, а вычислять $D^n$ легко — нужно просто возвести каждый диагональный элемент в степень $n$.

Пример 4 (продолжение). Для $A=\left(\begin{array}{cc}4& 1\\ 2& 3\end{array}\right)$:

$P=\left(\begin{array}{cc}1& 1\\ 1& -2\end{array}\right),D=\left(\begin{array}{cc}5& 0\\ 0& 2\end{array}\right),P^{-1}=\frac{1}{-3}\left(\begin{array}{cc}-2& -1\\ -1& 1\end{array}\right)=\left(\begin{array}{cc}2/3& 1/3\\ 1/3& -1/3\end{array}\right)$

Можно проверить, что $A=PD{P}^{-1}$. А чтобы вычислить $A^{10}$, достаточно найти $D^{10}=\left(\begin{array}{cc}{5}^{10}& 0\\ 0& 2^{10}\end{array}\right)$, а затем $A^{10}=P{D}^{10}{P}^{-1}$.

Не каждая матрица диагонализируема. Матрицы с меньшим числом собственных векторов, чем размерность (когда собственные значения имеют геометрическую кратность меньше размерности), диагонализировать нельзя — для них требуется более общее разложение, называемое жордановой канонической формой.

Приложение 1: Метод главных компонент (PCA)

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

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

Проецируя данные на несколько первых главных компонентов (с наибольшими собственными значениями), вы уменьшаете размерность, сохраняя большую часть структуры. Так PCA снижает размерность набора с 1000 признаков до 50, сохраняя содержательные шаблоны.

Приложение 2: Цепи Маркова

Цепь Маркова — это стохастический процесс, переходящий между состояниями с вероятностями, закодированными в переходной матрице $P$. Долговременное поведение цепи определяется собственными значениями и собственными векторами матрицы $P$.

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

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

Приложение 3: Динамические системы

Линейная дискретная динамическая система имеет вид ${\mathbf{x}}_{t+1}=A{\mathbf{x}}_t$. Итерация даёт: ${\mathbf{x}}_n=A^n{\mathbf{x}}_0$.

Долговременное поведение такой системы зависит от собственных значений матрицы $A$:

• Если все собственные значения имеют модуль меньше 1, то ${\mathbf{x}}_n\to 0$. Система устойчива.
• Если какое-либо собственное значение имеет модуль больше 1, ${\mathbf{x}}_n$ неограниченно растёт вдоль соответствующего направления собственного вектора. Система неустойчива.
• Если собственные значения ровно 1, система имеет стационарное состояние.

Непрерывные динамические системы $\dot{\mathbf{x}}=A\mathbf{x}$ анализируются аналогично, но с использованием действительных частей собственных значений.

Приложение 4: Google PageRank

Изначальный алгоритм PageRank, сделавший Google возможным, — это вычисление собственного вектора.

Веб моделируется как граф, где страницы — вершины, а ссылки — направленные рёбра. Определяется переходная матрица, в которой $P_{ij}$ — вероятность перехода со страницы $j$ на страницу $i$ (равномерная по исходящим ссылкам из $j$). Вектор PageRank — вектор значимости для каждой страницы — это доминирующий собственный вектор матрицы $P$ (с собственным значением 1).

По сути: страница важна, если на неё ссылаются другие важные страницы. Это рекурсивное определение приводит к уравнению на собственный вектор, которое можно решить.

Изначальная статья Google (Брин и Пейдж, 1998) по сути является статьёй о вычислении доминирующего собственного вектора очень большой разреженной матрицы.