Итерация мощности

В математике ( степенная итерация также известная как степенной метод ) представляет собой алгоритм собственных значений : задана диагонализуемая матрица $A$, алгоритм выдаст число $\lambda$, которое является наибольшим (по абсолютной величине) собственным значением $A$и ненулевой вектор $v$, который является соответствующим собственным вектором $\lambda$, то есть, $Av=\lambda v$. Алгоритм также известен как фон Мизеса итерация .

Итерация мощности — очень простой алгоритм, но он может сходиться медленно. Самой трудоемкой операцией алгоритма является умножение матрицы $A$ вектором, поэтому он эффективен для очень большой разреженной матрицы с соответствующей реализацией. Скорость сходимости равна $(\lambda _{1}/\lambda _{2})^{k}$(см. следующий раздел ). Другими словами, сходимость является экспоненциальной, а основанием является спектральный разрыв .

Метод

Анимация, визуализирующая алгоритм итерации степени в матрице 2x2. Матрица изображается двумя собственными векторами. Ошибка вычисляется как $||{\text{approximation}}-{\text{largest eigenvector}}||$

Алгоритм итерации мощности начинается с вектора $b_{0}$, который может быть приближением к доминирующему собственному вектору или случайному вектору. Метод описывается рекуррентным соотношением

$b_{k+1}={\frac {Ab_{k}}{\|Ab_{k}\|}}$

Итак, на каждой итерации вектор $b_{k}$ умножается на матрицу $A$ и нормализовано.

Если мы предположим $A$ имеет собственное значение, которое строго больше по величине, чем другие его собственные значения и стартовый вектор $b_{0}$ имеет ненулевой компонент в направлении собственного вектора, связанного с доминирующим собственным значением, то подпоследовательность $\left(b_{k}\right)$ сходится к собственному вектору, связанному с доминирующим собственным значением.

Без двух сделанных выше предположений последовательность $\left(b_{k}\right)$ не обязательно сходится. В этой последовательности

$b_{k}=e^{i\phi _{k}}v_{1}+r_{k}$,

где $v_{1}$ - собственный вектор, связанный с доминирующим собственным значением, и $\|r_{k}\|\rightarrow 0$. Наличие термина $e^{i\phi _{k}}$ подразумевает, что $\left(b_{k}\right)$ не сходится, если $e^{i\phi _{k}}=1$. При двух перечисленных выше предположениях последовательность $\left(\mu _{k}\right)$ определяется

$\mu _{k}={\frac {b_{k}^{*}Ab_{k}}{b_{k}^{*}b_{k}}}$

сходится к доминирующему собственному значению (с коэффициентом Рэлея ).

Это можно вычислить с помощью следующего алгоритма (показанного в Python с NumPy):

#!/usr/bin/env python3

import numpy as np

def power_iteration(A, num_iterations: int):
    # Ideally choose a random vector
    # To decrease the chance that our vector
    # Is orthogonal to the eigenvector
    b_k = np.random.rand(A.shape[1])

    for _ in range(num_iterations):
        # calculate the matrix-by-vector product Ab
        b_k1 = np.dot(A, b_k)

        # calculate the norm
        b_k1_norm = np.linalg.norm(b_k1)

        # re normalize the vector
        b_k = b_k1 / b_k1_norm

    return b_k

power_iteration(np.array([[0.5, 0.5], [0.2, 0.8]]), 10)

Вектор $b_{k}$ сходится к соответствующему собственному вектору. следует использовать коэффициент Рэлея В идеале для получения соответствующего собственного значения .

Этот алгоритм используется для расчета Google PageRank .

Этот метод также можно использовать для расчета спектрального радиуса (собственного значения с наибольшей величиной для квадратной матрицы) путем вычисления коэффициента Рэлея.

$\rho (A)=\max \left\{|\lambda _{1}|,\dotsc ,|\lambda _{n}|\right\}={\frac {b_{k}^{\top }Ab_{k}}{b_{k}^{\top }b_{k}}}={\frac {b_{k+1}^{\top }b_{k}}{b_{k}^{\top }b_{k}}}.$

Анализ

Позволять $A$ разложиться в свою жорданову каноническую форму : $A=VJV^{-1}$, где первый столбец $V$ является собственным вектором $A$ соответствующее доминирующему собственному значению $\lambda _{1}$. Поскольку в общем случае доминирующее собственное значение $A$ уникален, первый иорданский блок $J$ это $1\times 1$ матрица $[\lambda _{1}],$ где $\lambda _{1}$ является наибольшим собственным значением A по величине. Стартовый вектор $b_{0}$ можно записать как линейную комбинацию столбцов V :

$b_{0}=c_{1}v_{1}+c_{2}v_{2}+\cdots +c_{n}v_{n}.$

По предположению, $b_{0}$ имеет ненулевой компонент в направлении доминирующего собственного значения, поэтому $c_{1}\neq 0$.

Полезное в вычислительном отношении рекуррентное соотношение для $b_{k+1}$ можно переписать как:

$b_{k+1}={\frac {Ab_{k}}{\|Ab_{k}\|}}={\frac {A^{k+1}b_{0}}{\|A^{k+1}b_{0}\|}},$

где выражение: ${\frac {A^{k+1}b_{0}}{\|A^{k+1}b_{0}\|}}$ более поддается следующему анализу.

${\begin{aligned}b_{k}&={\frac {A^{k}b_{0}}{\|A^{k}b_{0}\|}}\\&={\frac {\left(VJV^{-1}\right)^{k}b_{0}}{\|\left(VJV^{-1}\right)^{k}b_{0}\|}}\\&={\frac {VJ^{k}V^{-1}b_{0}}{\|VJ^{k}V^{-1}b_{0}\|}}\\&={\frac {VJ^{k}V^{-1}\left(c_{1}v_{1}+c_{2}v_{2}+\cdots +c_{n}v_{n}\right)}{\|VJ^{k}V^{-1}\left(c_{1}v_{1}+c_{2}v_{2}+\cdots +c_{n}v_{n}\right)\|}}\\&={\frac {VJ^{k}\left(c_{1}e_{1}+c_{2}e_{2}+\cdots +c_{n}e_{n}\right)}{\|VJ^{k}\left(c_{1}e_{1}+c_{2}e_{2}+\cdots +c_{n}e_{n}\right)\|}}\\&=\left({\frac {\lambda _{1}}{|\lambda _{1}|}}\right)^{k}{\frac {c_{1}}{|c_{1}|}}{\frac {v_{1}+{\frac {1}{c_{1}}}V\left({\frac {1}{\lambda _{1}}}J\right)^{k}\left(c_{2}e_{2}+\cdots +c_{n}e_{n}\right)}{\left\|v_{1}+{\frac {1}{c_{1}}}V\left({\frac {1}{\lambda _{1}}}J\right)^{k}\left(c_{2}e_{2}+\cdots +c_{n}e_{n}\right)\right\|}}\end{aligned}}$

Выражение выше упрощается как $k\to \infty$

$\left({\frac {1}{\lambda _{1}}}J\right)^{k}={\begin{bmatrix}[1]&&&&\\&\left({\frac {1}{\lambda _{1}}}J_{2}\right)^{k}&&&\\&&\ddots &\\&&&\left({\frac {1}{\lambda _{1}}}J_{m}\right)^{k}\\\end{bmatrix}}\rightarrow {\begin{bmatrix}1&&&&\\&0&&&\\&&\ddots &\\&&&0\\\end{bmatrix}}\quad {\text{as}}\quad k\to \infty .$

Предел следует из того, что собственное значение ${\frac {1}{\lambda _{1}}}J_{i}$ меньше 1 по величине, поэтому

$\left({\frac {1}{\lambda _{1}}}J_{i}\right)^{k}\to 0\quad {\text{as}}\quad k\to \infty .$

Отсюда следует, что:

${\frac {1}{c_{1}}}V\left({\frac {1}{\lambda _{1}}}J\right)^{k}\left(c_{2}e_{2}+\cdots +c_{n}e_{n}\right)\to 0\quad {\text{as}}\quad k\to \infty$

Используя этот факт, $b_{k}$ может быть записано в форме, подчеркивающей его связь с $v_{1}$ когда k велико:

${\begin{aligned}b_{k}&=\left({\frac {\lambda _{1}}{|\lambda _{1}|}}\right)^{k}{\frac {c_{1}}{|c_{1}|}}{\frac {v_{1}+{\frac {1}{c_{1}}}V\left({\frac {1}{\lambda _{1}}}J\right)^{k}\left(c_{2}e_{2}+\cdots +c_{n}e_{n}\right)}{\left\|v_{1}+{\frac {1}{c_{1}}}V\left({\frac {1}{\lambda _{1}}}J\right)^{k}\left(c_{2}e_{2}+\cdots +c_{n}e_{n}\right)\right\|}}\\[6pt]&=e^{i\phi _{k}}{\frac {c_{1}}{|c_{1}|}}{\frac {v_{1}}{\|v_{1}\|}}+r_{k}\end{aligned}}$

где $e^{i\phi _{k}}=\left(\lambda _{1}/|\lambda _{1}|\right)^{k}$ и $\|r_{k}\|\to 0$ как $k\to \infty$

Последовательность $\left(b_{k}\right)$ ограничен, поэтому содержит сходящую подпоследовательность. Обратите внимание, что собственный вектор, соответствующий доминирующему собственному значению, уникален только с точностью до скаляра, поэтому, хотя последовательность $\left(b_{k}\right)$ может не сойтись, $b_{k}$ является почти собственным вектором A для больших k .

Альтернативно, если A диагонализуемо результат , то следующее доказательство дает тот же

Пусть λ ₁ , λ ₂ , ..., λ _m — m собственных значений (подсчитанных с кратностью) оператора A , и пусть v ₁ , v ₂ , ..., v _m — соответствующие собственные векторы. Предположим, что $\lambda _{1}$ является доминирующим собственным значением, так что $|\lambda _{1}|>|\lambda _{j}|$ для $j>1$.

Начальный вектор $b_{0}$ можно написать:

$b_{0}=c_{1}v_{1}+c_{2}v_{2}+\cdots +c_{m}v_{m}.$

Если $b_{0}$ выбирается случайно (с равномерной вероятностью), тогда c ₁ ≠ 0 с вероятностью 1 . Сейчас,

${\begin{aligned}A^{k}b_{0}&=c_{1}A^{k}v_{1}+c_{2}A^{k}v_{2}+\cdots +c_{m}A^{k}v_{m}\\&=c_{1}\lambda _{1}^{k}v_{1}+c_{2}\lambda _{2}^{k}v_{2}+\cdots +c_{m}\lambda _{m}^{k}v_{m}\\&=c_{1}\lambda _{1}^{k}\left(v_{1}+{\frac {c_{2}}{c_{1}}}\left({\frac {\lambda _{2}}{\lambda _{1}}}\right)^{k}v_{2}+\cdots +{\frac {c_{m}}{c_{1}}}\left({\frac {\lambda _{m}}{\lambda _{1}}}\right)^{k}v_{m}\right)\\&\to c_{1}\lambda _{1}^{k}v_{1}&&\left|{\frac {\lambda _{j}}{\lambda _{1}}}\right|<1{\text{ for }}j>1\end{aligned}}$

С другой стороны:

$b_{k}={\frac {A^{k}b_{0}}{\|A^{k}b_{0}\|}}.$

Поэтому, $b_{k}$ сходится к (кратному) собственному вектору $v_{1}$. Сходимость геометрическая с отношением

$\left|{\frac {\lambda _{2}}{\lambda _{1}}}\right|,$

где $\lambda _{2}$ обозначает второе доминирующее собственное значение. Таким образом, метод сходится медленно, если существует собственное значение, близкое по величине к доминирующему собственному значению.

Приложения

Хотя метод степенной итерации аппроксимирует только одно собственное значение матрицы, он остается полезным для некоторых вычислительных задач . Например, Google использует его для расчета PageRank документов в своей поисковой системе. и Twitter использует его, чтобы показывать пользователям рекомендации, которым следует следовать. Метод степенной итерации особенно подходит для разреженных матриц , таких как веб-матрица, или в качестве безматричного метода , не требующего хранения матрицы коэффициентов. $A$ явно, но вместо этого может получить доступ к функции, оценивающей произведения матрицы-вектора $Ax$. Для несимметричных матриц, которые хорошо обусловлены, метод степенной итерации может превзойти более сложную итерацию Арнольди . Для симметричных матриц метод степенной итерации используется редко, поскольку его скорость сходимости можно легко увеличить, не жертвуя при этом небольшой стоимостью итерации; см., например, итерацию Ланцоша и LOBPCG .

Некоторые из более продвинутых алгоритмов собственных значений можно понимать как вариации степенной итерации. Например, метод обратной итерации применяет степенную итерацию к матрице $A^{-1}$. Другие алгоритмы рассматривают все подпространство, порожденное векторами. $b_{k}$. Это подпространство известно как подпространство Крылова . Его можно вычислить с помощью итерации Арнольди или итерации Ланцоша . Итерация грамма это суперлинейный и детерминированный метод вычисления наибольшей собственной пары.

См. также

• Итерация фактора Рэлея
• Обратная итерация