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

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

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

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

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

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

Возьмём произвольный вектор и будем повторно умножать его на матрицу A. Раскладывая вектор по собственным векторам, видим: при каждом умножении компонента вдоль v_i множится на λ_i. Компонента с наибольшим |λ| растёт быстрее всех и вскоре доминирует — вектор разворачивается вдоль главного собственного направления. Чтобы он не улетел в бесконечность (или к нулю), на каждом шаге нормируем. А множитель, на который вырос вектор за шаг, и есть оценка λ_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

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

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

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

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

Формально: если x = Σ c_i·v_i, то A^k·x = Σ c_i·λ_i^k·v_i = λ₁^k·(c₁v₁ + Σ_{i≥2} c_i·(λ_i/λ₁)^k·v_i). Дроби (λ_i/λ₁)^k → 0 при i ≥ 2, поэтому остаётся только v₁ — вектор стремится к главному собственному направлению. Нормировка лишь убирает множитель λ₁^k, не давая переполнения. Чтобы найти все собственные значения, степенной метод обобщают: вычитают уже найденные (дефляция) или применяют QR-алгоритм, многократно раскладывая A = QR и переставляя множители. В библиотеке — numpy.linalg.eig(A).

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

• Ждать все собственные значения. Степенной метод даёт только доминирующее; для остального нужны дефляция или QR-алгоритм.
• Не нормировать вектор. Без нормировки компоненты переполнятся (при |λ|>1) или занулятся (при |λ|<1).
• Применять при λ₁ ≈ λ₂. Сходимость как |λ₂/λ₁|^k станет мучительно медленной; нужен сдвиг или другой метод.

Итоги

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