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

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

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

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

Алгоритм

В начале алгоритма генерируется случайный вектор $r_0$. Далее проводятся последовательные вычисления по итеративной формуле:

$r_{k+1}=\frac{A{r}_k}{\Vert A{r}_k\Vert }$

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

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

${\mu }_k=\frac{r_k^{T}A{r}_k}{r_k^T{r}_k}=\frac{(r_k,A{r}_k)}{(r_k,r_k)}$

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

Для нормальных операторов

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

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

$A_1=A-\lambda r_k{r}_k^T$

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

Доказательство сходимости

Упорядочим собственные значения по невозрастанию абсолютной величины и допустим, что ${\lambda }_1>{\lambda }_2\ge ...\ge {\lambda }_n$. Тогда начальный вектор можно представить как

$r_0=\sum _{i=1}^n{v}_i+w$,

где $v_i$ — собственные векторы, вектор $w$ обнуляется при первом умножении на матрицу, а $v_1\ne 0$ по предположению.

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

$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)$.

Поделив левую и правую часть на $\Vert R_k\Vert$, получим

$r_k={\lambda }_1\frac{v_1}{\Vert {\lambda }_1{v}_1\Vert }+O((\frac{{\lambda }_2}{{\lambda }_1}{)}^k).$

Приложения

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