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

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

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

Алгоритм запропонували 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 — для рекомендування «за ким стежити».

Див. також

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