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

На початку алгоритму генерується випадковий вектор ${\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].

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