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

В математике степенная итерация (также известная как степенной метод ) — это алгоритм собственных значений : при наличии диагонализуемой матрицы алгоритм произведет число , которое является наибольшим (по абсолютной величине) собственным значением , и ненулевой вектор , который является соответствующим собственным вектором , то есть . Алгоритм также известен как итерация фон Мизеса . ^[1]${\displaystyle А}$${\displaystyle \лямбда}$${\displaystyle А}$${\displaystyle v}$${\displaystyle \лямбда}$${\displaystyle Av=\лямбда v}$

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

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

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

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

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

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

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

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

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

сходится к доминирующему собственному значению (с отношением Рэлея ). ^{[ необходимо разъяснение ]}

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

#!/usr/bin/env питон3импортировать  numpy  как  npdef  power_iteration ( A ,  num_iterations :  int ):  # В идеале выбрать случайный вектор  # Чтобы уменьшить вероятность того, что наш вектор  # будет ортогонален собственному вектору  b_k  =  np . random . rand ( A . shape [ 1 ]) for  _  in  range ( num_iterations ):  # вычислить произведение матрицы на вектор Ab  b_k1  =  np . dot ( A ,  b_k )  # вычислить норму b_k1_norm  =  np.linalg.norm ( b_k1 )​​ # повторно нормализуем вектор  b_k  =  b_k1  /  b_k1_norm вернуться  б_кpower_iteration ( np . array ([[ 0.5 ,  0.5 ],  [ 0.2 ,  0.8 ]]),  10 )

Вектор сходится к ассоциированному собственному вектору. В идеале следует использовать отношение Рэлея , чтобы получить ассоциированное собственное значение.${\displaystyle b_{k}}$

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

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

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

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

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

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

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

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

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

${\displaystyle {\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}}}$

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

${\displaystyle \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 .}$

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

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

Из этого следует, что:

${\displaystyle {\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 }$

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

${\displaystyle {\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}}}$

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

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

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

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

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

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

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

${\displaystyle {\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}}}$

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

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

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

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

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

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

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

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