Степеневий метод або метод степеневих ітерацій ітераційний алгоритм пошуку власного значення з найбільшою абсолютною вел

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

Алгоритм простий і збігається зі швидкістю геометричної прогресії якщо всі найбільші за модулем власні значення збігаються, в іншому випадку збіжності немає. За близьких за модулем власних значень збіжність може виявитися повільною. Оскільки алгоритм зводиться до послідовного множення заданої матриці на вектор, за правильної реалізації він добре працює для великих розріджених матриць.

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

Алгоритм

На початку алгоритму генерується випадковий вектор $r_{0}$ . Далі проводяться послідовні обчислення за ітеративною формулою:

r_{k+1}={\frac {Ar_{k}}{\|Ar_{k}\|}}

Якщо початковий вектор не ортогональний власному підпростору з найбільшим за модулем власним значенням, то відстань від елементів даної послідовності до такого підпростору прямує до нуля. Послідовність векторів не завжди збіжна, оскільки вектор на кожному кроці може змінювати знак або, в комплексному випадку, обертатися, але це не заважає вибрати один з векторів як власний, коли отримано достатньо точне власне значення.

Послідовність

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

за зазначеної вище умови збігається до найбільшого за модулем власного значення. Але слід пам'ятати, що не всі дійсні матриці мають дійсні власні значення.

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

У частковому, але важливому випадку нормальних операторів усі власні вектори матриці взаємно ортогональні. У цьому випадку степеневий метод дозволяє знайти всі власні значення і вектори матриці.

Нехай $r_{k}$ — нормований власний вектор з найбільшим за модулем власним значенням матриці $A$ нормального оператора. Тоді матриця

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

зберігає всі власні вектори матриці $A$ крім вектора $r_{k}$ і дозволяє шукати степеневим методом наступний власний вектор з найбільшим за модулем власним значенням.

Доведення збіжності

Впорядкуємо власні значення за незростанням абсолютної величини і допустимо, що $\lambda _{1}>\lambda _{2}\geq ...\geq \lambda _{n}$ . Тоді початковий вектор можна подати як

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

,

де $v_{i}$ — власні вектори, вектор $w$ обнуляється під час першого множення на матрицю, а $v_{1}\neq 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})$ .

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

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

Застосування

Метод застосовується перш за все для розріджених матриць. Наприклад, Гугл використовує його для розрахунку рангів сторінок в Інтернеті, а Twitter — для рекомендування «за ким стежити».

Див. також

Зворотний степеневий метод

Примітки

Richard von Mises and H. Pollaczek-Geiringer, Praktische Verfahren der Gleichungsauflösung, ZAMM — Zeitschrift für Angewandte Mathematik und Mechanik 9, 152—164 (1929).
У деяких випадках є можливість використовувати вже наявне наближення домінівного власного вектора.
Ділення (нормування) в цій формулі потрібне, щоб виключити обнулення або переповнення координат вектора і за орієнтовно відомих власних значень його не обов'язково робити на кожному кроці.
У разі, коли найбільше за модулем власне значення — додатне дійсне число, ця послідовність векторів також збігається до деякого власного вектора.
Допущення зроблено для скорочення викладу. У разі збігу декількох власних значень найбільших за модулем доведення аналогічне.
^[en], and Rebecca M. Wills (5–8 May 2005). 7th IMACS International Symposium on Iterative Methods in Scientific Computing (PDF). Fields Institute, Toronto, Canada.
Pankaj Gupta, Ashish Goel, Jimmy Lin, Aneesh Sharma, Dong Wang, and Reza Bosagh Zadeh WTF: The who-to-follow system at Twitter, Proceedings of the 22nd international conference on World Wide Web

[VonMises-1] Richard von Mises and H. Pollaczek-Geiringer, Praktische Verfahren der Gleichungsauflösung, ZAMM — Zeitschrift für Angewandte Mathematik und Mechanik 9, 152—164 (1929).

[2] У деяких випадках є можливість використовувати вже наявне наближення домінівного власного вектора.

[3] Ділення (нормування) в цій формулі потрібне, щоб виключити обнулення або переповнення координат вектора і за орієнтовно відомих власних значень його не обов'язково робити на кожному кроці.

[4] У разі, коли найбільше за модулем власне значення — додатне дійсне число, ця послідовність векторів також збігається до деякого власного вектора.

[5] Допущення зроблено для скорочення викладу. У разі збігу декількох власних значень найбільших за модулем доведення аналогічне.

[6] [en], and Rebecca M. Wills (5–8 May 2005). 7th IMACS International Symposium on Iterative Methods in Scientific Computing (PDF). Fields Institute, Toronto, Canada.

[twitterwtf-7] Pankaj Gupta, Ashish Goel, Jimmy Lin, Aneesh Sharma, Dong Wang, and Reza Bosagh Zadeh WTF: The who-to-follow system at Twitter, Proceedings of the 22nd international conference on World Wide Web