Степенной метод

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

Алгоритм прост и сходится со скоростью геометрической прогрессии, если все максимальные по модулю собственные значения совпадают, в противном случае сходимости нет. При близких по модулю собственных значениях сходимость может оказаться медленной. В силу того, что алгоритм сводится к последовательному умножению заданной матрицы на вектор, при правильной реализации он хорошо работает для больших разреженных матриц.

Алгоритм предложен в 1929 году Рихардом фон Мизесом и Хильдой Гейрингер^[1].

В начале алгоритма генерируется случайный вектор ${\displaystyle r_{0}}$^[2]. Далее проводятся последовательные вычисления по итеративной формуле:

${\displaystyle r_{k+1}={\frac {Ar_{k}}{\|Ar_{k}\|}}}$^[3]

Если исходный вектор не ортогонален собственному подпространству с наибольшим по модулю собственным значением, то расстояние от элементов данной последовательности до такого подпространства стремится к нулю^[4]. Последовательность векторов не всегда сходится, поскольку вектор на каждом шаге может менять знак или в комплексном случае вращаться, но это не мешает выбрать один из векторов в качестве собственного, когда получено достаточно точное собственное значение.

Последовательность

${\displaystyle \mu _{k}={\frac {r_{k}^{T}Ar_{k}}{r_{k}^{T}r_{k}}}={\frac {(r_{k},Ar_{k})}{(r_{k},r_{k})}}}$

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

В частном, но важном случае нормальных операторов все собственные векторы матрицы взаимно ортогональны. В этом случае степенной метод позволяет найти все собственные значения и векторы матрицы.

Пусть ${\displaystyle r_{k}}$ — нормированный собственный вектор с максимальным по модулю собственным значением матрицы ${\displaystyle A}$ нормального оператора. Тогда матрица

${\displaystyle A_{1}=A-\lambda r_{k}r_{k}^{T}}$

сохраняет все собственные векторы матрицы ${\displaystyle A}$, кроме вектора ${\displaystyle r_{k}}$, и позволяет искать степенным методом следующий собственный вектор с максимальным по модулю собственным значением.

Упорядочим собственные значения по невозрастанию абсолютной величины и допустим, что ${\displaystyle \lambda _{1}>\lambda _{2}\geq ...\geq \lambda _{n}}$^[5]. Тогда начальный вектор можно представить как

${\displaystyle r_{0}=\sum _{i=1}^{n}v_{i}+w}$,

где ${\displaystyle v_{i}}$ — собственные векторы, вектор ${\displaystyle w}$ обнуляется при первом умножении на матрицу, а ${\displaystyle v_{1}\neq 0}$ по предположению.

Рассмотрим результат ${\displaystyle k}$ умножений матрицы на начальный вектор:

${\displaystyle R_{k}=A^{k}(\sum _{i=1}^{n}v_{i}+w)=\sum _{i=1}^{n}{\lambda _{i}^{k}v_{i}}={\lambda _{1}}^{k}(v_{1}+O(({\frac {\lambda _{2}}{\lambda _{1}}})^{k})}$.

Поделив левую и правую часть на ${\displaystyle \|R_{k}\|}$, получим

${\displaystyle r_{k}=\lambda _{1}{\frac {v_{1}}{\|\lambda _{1}v_{1}\|}}+O(({\frac {\lambda _{2}}{\lambda _{1}}})^{k}).}$

Метод применяется в первую очередь для разреженных матриц. Например, Гугл использует его для расчёта рангов страниц в Интернете^[6], а Twitter использует его для рекомендаций «за кем следовать»^[7].