Степенной метод: главное собственное значение

Урок про степенной метод — простейший итерационный способ найти наибольшее по модулю собственное значение матрицы.

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

Зачем нужны собственные значения

Собственные значения $\lambda$ и векторы $v$ (для которых $Av = \lambda v$) — это «оси» матрицы, направления, вдоль которых она действует простым растяжением. Они вездесущи: PageRank Google — это поиск собственного вектора матрицы ссылок; метод главных компонент (PCA) в анализе данных — собственные векторы ковариации; устойчивость конструкции и резонансные частоты — собственные значения. Часто нужно не всё, а именно наибольшее собственное значение (например, частота главного резонанса или вес главной компоненты) — и тут степенной метод незаменим своей простотой.

Идея: умножай и нормируй

Возьмём произвольный вектор и будем повторно умножать его на матрицу $A$. Раскладывая вектор по собственным векторам, видим: при каждом умножении компонента вдоль $v_i$ множится на $\lambda_i$. Компонента с наибольшим $|\lambda|$ растёт быстрее всех и вскоре доминирует — вектор разворачивается вдоль главного собственного направления. Чтобы он не улетел в бесконечность (или к нулю), на каждом шаге нормируем. А множитель, на который вырос вектор за шаг, и есть оценка $\lambda_{max}$.

def умножить(A, x):
    return [sum(A[i][j] * x[j] for j in range(len(x))) for i in range(len(A))]

def степенной_метод(A, итераций=20):
    n = len(A)
    x = [1.0] * n                  # произвольный старт
    lam = 0.0
    for k in range(итераций):
        y = умножить(A, x)
        lam = max(y, key=abs)      # компонента наибольшего модуля
        x = [v / lam for v in y]   # нормируем по ней
    return lam, x

A = [[2.0, 1.0],
     [1.0, 3.0]]
lam, v = степенной_метод(A)
import math
print(f"наибольшее собственное значение λ ≈ {lam:.6f}")
print(f"собственный вектор (нормированный) ≈ {[round(c, 4) for c in v]}")
# точное значение для этой 2x2: (5 + sqrt(5)) / 2
print(f"точное λ_max = {(5 + math.sqrt(5)) / 2:.6f}")

Вывод:

наибольшее собственное значение λ ≈ 3.618034
собственный вектор (нормированный) ≈ [0.618, 1.0]
точное λ_max = 3.618034

Двадцать умножений матрицы на вектор — и мы поймали $\lambda_{max} = 3.618034$ с точностью до всех показанных цифр, а заодно и собственный вектор. Никаких характеристических полиномов, только итерации.

Скорость и ограничения

Сходимость степенного метода линейная, со знаменателем $|\lambda_2/\lambda_1|$ — отношением второго по величине собственного значения к первому. Если они близки по модулю, метод сходится медленно; если $\lambda_2$ сильно меньше $\lambda_1$ — быстро. Ограничения: метод находит только одно (доминирующее) собственное значение и работает, лишь когда оно единственно по модулю (не годится, если два наибольших равны по модулю или комплексны).

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

Формально: если $x = \sum c_i \cdot v_i$, то $A^k \cdot x = \sum c_i \cdot \lambda_i^k \cdot v_i = \lambda_1^k \cdot (c_1 v_1 + \sum_{i \ge 2} c_i \cdot (\lambda_i/\lambda_1)^k \cdot v_i)$. Дроби $(\lambda_i/\lambda_1)^k \to 0$ при $i \ge 2$, поэтому остаётся только $v_1$ — вектор стремится к главному собственному направлению. Нормировка лишь убирает множитель $\lambda_1^k$, не давая переполнения. Чтобы найти все собственные значения, степенной метод обобщают: вычитают уже найденные (дефляция) или применяют QR-алгоритм, многократно раскладывая $A = QR$ и переставляя множители. В библиотеке — numpy.linalg.eig(A).

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

• Ждать все собственные значения. Степенной метод даёт только доминирующее; для остального нужны дефляция или QR-алгоритм.
• Не нормировать вектор. Без нормировки компоненты переполнятся (при $|\lambda| \gt 1$) или занулятся (при $|\lambda| \lt 1$).
• Применять при $\lambda_1 \approx \lambda_2$. Сходимость как $|\lambda_2/\lambda_1|^k$ станет мучительно медленной; нужен сдвиг или другой метод.

Итоги

• Степенной метод вытягивает вектор к главному собственному направлению повторным умножением на $A$ с нормировкой.
• Множитель роста за шаг — оценка наибольшего по модулю собственного значения.
• Сходимость линейная со знаменателем $|\lambda_2/\lambda_1|$; находит лишь доминирующее $\lambda$.
• Варианты: обратный (наименьшее $\lambda$), со сдвигом (около $s$); для всех — QR-алгоритм.