Русская Википедия:Степенной метод
Степенной метод, или метод степенных итераций, — итерационный алгоритм поиска собственного значения с максимальной абсолютной величиной и одного из соответствующих собственных векторов для произвольной матрицы.
Алгоритм прост и сходится со скоростью геометрической прогрессии, если все максимальные по модулю собственные значения совпадают, в противном случае сходимости нет. При близких по модулю собственных значениях сходимость может оказаться медленной. В силу того, что алгоритм сводится к последовательному умножению заданной матрицы на вектор, при правильной реализации он хорошо работает для больших разреженных матриц.
Алгоритм предложен в 1929 году Рихардом фон Мизесом и Хильдой Гейрингер[1].
Алгоритм
В начале алгоритма генерируется случайный вектор <math>r_0</math>[2]. Далее проводятся последовательные вычисления по итеративной формуле:
- <math> r_{k+1} = \frac{Ar_k}{\|Ar_k\|} </math>[3]
Если исходный вектор не ортогонален собственному подпространству с наибольшим по модулю собственным значением, то расстояние от элементов данной последовательности до такого подпространства стремится к нулю[4]. Последовательность векторов не всегда сходится, поскольку вектор на каждом шаге может менять знак или в комплексном случае вращаться, но это не мешает выбрать один из векторов в качестве собственного, когда получено достаточно точное собственное значение.
Последовательность
- <math>\mu_{k} = \frac{r_{k}^{T}Ar_{k}}{r_{k}^{T}r_{k}}= \frac{(r_k,Ar_k)}{(r_k,r_k)}</math>
при указанном выше условии сходится к максимальному по модулю собственному значению. Но следует помнить, что не у всех действительных матриц есть действительные собственные значения.
Для нормальных операторов
В частном, но важном случае нормальных операторов все собственные векторы матрицы взаимно ортогональны. В этом случае степенной метод позволяет найти все собственные значения и векторы матрицы.
Пусть <math> r_k </math> — нормированный собственный вектор с максимальным по модулю собственным значением матрицы <math> A </math> нормального оператора. Тогда матрица
- <math> A_1 = A - \lambda r_k r_k^T</math>
сохраняет все собственные векторы матрицы <math> A </math>, кроме вектора <math> r_k </math>, и позволяет искать степенным методом следующий собственный вектор с максимальным по модулю собственным значением.
Доказательство сходимости
Упорядочим собственные значения по невозрастанию абсолютной величины и допустим, что <math>\lambda_1 > \lambda_2 \ge...\ge \lambda_n</math>[5]. Тогда начальный вектор можно представить как
- <math>r_0=\sum_{i=1}^n v_i + w </math>,
где <math> v_i </math> — собственные векторы, вектор <math>w</math> обнуляется при первом умножении на матрицу, а <math>v_1 \neq 0</math> по предположению.
Рассмотрим результат <math> k </math> умножений матрицы на начальный вектор:
<math>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)</math>.
Поделив левую и правую часть на <math>\|R_k\|</math>, получим
- <math>r_k=\lambda_1 \frac{v_1}{\|\lambda_1 v_1 \|}+O((\frac{\lambda_2}{\lambda_1})^k).</math>
Приложения
Метод применяется в первую очередь для разреженных матриц. Например, Гугл использует его для расчёта рангов страниц в Интернете[6], а Twitter использует его для рекомендаций «за кем следовать»[7].
Примечания
Шаблон:ПримечанияШаблон:Нет ссылок
- ↑ Richard von Mises and H. Pollaczek-Geiringer, Praktische Verfahren der Gleichungsauflösung, ZAMM — Zeitschrift für Angewandte Mathematik und Mechanik 9, 152—164 (1929).
- ↑ В некоторых случаях есть возможность использовать уже имеющееся приближение доминирующего собственного вектора.
- ↑ Деление (нормировка) в этой формуле нужно, чтобы исключить обнуление или переполнение координат вектора и при ориентировочно известных собственных значениях его не обязательно делать на каждом шаге.
- ↑ В случае, когда наибольшее по модулю собственное значение — положительное вещественное число, данная последовательность векторов также сходится к некоторому собственному вектору.
- ↑ Допущение сделано для сокращения выкладок. В случае нескольких совпадающих собственных значений максимальных по модулю доказательство аналогично.
- ↑ Шаблон:Cite news
- ↑ Pankaj Gupta, Ashish Goel, Jimmy Lin, Aneesh Sharma, Dong Wang, and Reza Bosagh Zadeh WTF: The who-to-follow system at Twitter Шаблон:Wayback, Proceedings of the 22nd international conference on World Wide Web
