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

Алгоритм собственных значений

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

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

Метод

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

Алгоритм итерации мощности начинается с вектора , который может быть приближением к доминирующему собственному вектору или случайному вектору. Метод описывается рекуррентным соотношением ${\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_iterations :  int ):  # В идеале выберите случайный вектор  # Чтобы уменьшить вероятность того, что наш вектор  # ортогонален собственному вектору  b_k  =  np . случайный . ранд ( A . форма [ 1 ]) for  _  in  range ( num_iterations ):  # вычисление произведения матрицы на вектор Ab  b_k1  =  np . точка ( A ,  b_k ) # вычисляем норму  b_k1_norm  =  np . линалг . норма ( 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}}$

Этот алгоритм используется для расчета PageRank 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 .}$

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

Смотрите также

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

Рекомендации

1. Рихард фон Мизес и Х. Поллачек-Гейрингер, Praktische Verfahren der Gleichungsauflösung , ZAMM - Zeitschrift für Angewandte Mathematik und Mechanik 9, 152-164 (1929).
2. Ипсен, Ильза и Ребекка М. Уиллс (5–8 мая 2005 г.). «7-й Международный симпозиум IMACS по итеративным методам научных вычислений» (PDF) . Институт Филдса, Торонто, Канада.{{cite news}}: CS1 maint: multiple names: authors list (link)
3. Панкадж Гупта, Ашиш Гоэл, Джимми Лин, Аниш Шарма, Донг Ван и Реза Босаг Заде WTF: Система «за кем следить» в Твиттере, Материалы 22-й международной конференции по Всемирной паутине
4. Делатр, Б.; Бартелеми, К.; Араужо, А.; Аллаузен, А. (2023), «Эффективная оценка константы Липшица для сверточных слоев путем итерации по Граму», Материалы 40-й Международной конференции по машинному обучению