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

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

Степенная итерация - очень простой алгоритм, но он может медленно сходиться. Самая трудоемкая операция алгоритма - это умножение матрицы на вектор, поэтому она эффективна для очень большой разреженной матрицы при соответствующей реализации.${\ displaystyle A}$

Метод [ править ]

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

Алгоритм степенной итерации начинается с вектора , который может быть приближением к доминирующему собственному вектору или случайным вектором. Метод описывается рекуррентным соотношением${\ 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 python3импортировать  numpy  как  npdef  power_iteration ( A ,  num_simulations :  int ):  # В идеале выберите случайный вектор  # Чтобы уменьшить вероятность того, что наш вектор  # ортогонален собственному вектору  b_k  =  np . случайный . Rand ( . форма [ 1 ]) for  _  in  range ( num_simulations ):  # вычислить матричное произведение Ab  b_k1  =  np . точка ( A ,  b_k ) # вычисляем норму  b_k1_norm  =  np . linalg . норма ( b_k1 ) # повторно нормализовать вектор  b_k  =  b_k1  /  b_k1_norm вернуться  b_kpower_iteration ( np . array ([[ 0.5 ,  0.5 ],  [ 0.2 ,  0.8 ]]),  10 )

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

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

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

${\displaystyle \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 по величине. Начальный вектор можно записать как линейную комбинацию столбцов 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 .}$

Предел следует из того факта, что собственное значение меньше единицы по модулю, поэтому${\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 }$

Используя этот факт, можно записать в виде , который подчеркивает его отношения с когда к велико:${\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}}$

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

Пусть λ ₁ , λ ₂ , ..., λ _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] Метод степенной итерации особенно подходит для разреженных матриц , таких как веб-матрица, или в качестве безматричного метода , который не требует явного сохранения матрицы коэффициентов , но вместо этого может обращаться к функции, оценивающей произведение матрица-вектор . Для несимметричных матриц, которые${\displaystyle A}$${\displaystyle Ax}$Хорошо подготовленный метод степенной итерации может превзойти более сложную итерацию Арнольди . Для симметричных матриц метод степенной итерации используется редко, поскольку его скорость сходимости может быть легко увеличена без ущерба для небольших затрат на итерацию; см., например, итерацию Ланцоша и LOBPCG .

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

См. Также [ править ]

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

Ссылки [ править ]