Степенной метод: находим главное направление

Многократно умножая случайный вектор на матрицу, он сам «притягивается» к главному собственному направлению — на этом стоит степенной метод.

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

Решать характеристическое уравнение для больших матриц непрактично. Зато есть удивительно простая численная идея: возьми любой вектор, умножай его на матрицу снова и снова, нормируя — и он сойдётся к главному собственному вектору. Это и есть сердце таких алгоритмов, как PageRank.

Почему это работает

Разложим стартовый вектор по собственным векторам: $\vec{v}_0 = c_1\vec{u}_1 + c_2\vec{u}_2 + \dots$. При умножении на $A$ каждая компонента множится на своё $\lambda$: после $k$ шагов $A^k\vec{v}_0 = c_1\lambda_1^k\vec{u}_1 + c_2\lambda_2^k\vec{u}_2 + \dots$. Если $|\lambda_1| \gt |\lambda_2| \ge \dots$, то слагаемое с $\lambda_1$ растёт быстрее всех и забивает остальные. Нормировка не даёт числам улететь в бесконечность, и в пределе остаётся только направление $\vec{u}_1$.

def matvec(A, v):
    return [sum(A[i][j] * v[j] for j in range(len(v)))
            for i in range(len(A))]

def norm_inf(v):
    return max(abs(x) for x in v)

A = [[2, 1], [1, 2]]  # собственные значения 3 и 1
v = [1, 0]
lam = 0
for _ in range(30):
    w = matvec(A, v)
    lam = norm_inf(w)
    v = [x / lam for x in w]

print("доминирующее собственное значение ~", round(lam, 4))
print("собственный вектор ~", [round(x, 4) for x in v])

Вывод:

доминирующее собственное значение ~ 3.0
собственный вектор ~ [1.0, 1.0]

Сошлось к теории

Из урока про характеристическое уравнение мы знаем: у $\begin{bmatrix} 2 & 1 \\ 1 & 2 \end{bmatrix}$ собственные значения $3$ и $1$. Степенной метод за 30 итераций нашёл доминирующее $\lambda = 3$ и его собственный вектор $(1, 1)$ — численность подтвердила аналитику. Никаких квадратных уравнений: только умножения и деления.

Как работает под капотом

На каждом шаге мы умножаем вектор на матрицу (matvec) и тут же делим на его наибольшую по модулю координату (norm_inf) — это и есть нормировка, удерживающая компоненты в разумных пределах. Множитель, на который мы делим, сходится к доминирующему собственному значению $\lambda_1$, а сам вектор — к собственному направлению. Скорость сходимости зависит от отношения $|\lambda_2| / |\lambda_1|$: чем оно меньше, тем быстрее метод сходится. Если же два старших собственных значения близки по модулю, сходимость замедляется. Именно этот алгоритм (в варианте для огромных разреженных матриц) Google применял для ранжирования веб-страниц.

Частые ошибки

Стартовать с вектора, случайно ортогонального главному собственному направлению ($c_1 = 0$). Тогда метод сойдётся не туда; на практике берут случайный старт.
Забывать нормировать. Без нормировки координаты либо взрываются, либо обнуляются из-за ограничений арифметики.
Ждать сходимости, когда $|\lambda_1| = |\lambda_2|$. При равных по модулю старших значениях простой степенной метод может не сойтись.

Итог

Степенной метод находит доминирующее собственное значение и вектор повторным умножением на матрицу.
Работает, потому что компонента с наибольшим $|\lambda|$ растёт быстрее всех.
Нормировка на каждом шаге удерживает числа и выдаёт само $\lambda$.
Скорость сходимости определяется отношением $|\lambda_2|/|\lambda_1|$; это основа PageRank.