Степеневий метод або метод степеневих ітерацій — ітераційний алгоритм пошуку власного значення з найбільшою абсолютною величиною і одного з відповідних власних векторів для довільної матриці.
Алгоритм простий і збігається зі швидкістю геометричної прогресії якщо всі найбільші за модулем власні значення збігаються, в іншому випадку збіжності немає. За близьких за модулем власних значень збіжність може виявитися повільною. Оскільки алгоритм зводиться до послідовного множення заданої матриці на вектор, за правильної реалізації він добре працює для великих розріджених матриць.
Алгоритм запропонували 1929 року Ріхард фон Мізес і Гільда ГейрінгерRichard von Mises and H. Pollaczek-Geiringer, Praktische Verfahren der Gleichungsauflösung, ZAMM — Zeitschrift für Angewandte Mathematik und Mechanik 9, 152—164 (1929)..
Алгоритм На початку алгоритму генерується випадковий вектор У деяких випадках є можливість використовувати вже наявне наближення домінівного власного вектора.. Далі проводяться послідовні обчислення за ітеративною формулою:
Ділення (нормування) в цій формулі потрібне, щоб виключити обнулення або переповнення координат вектора і за орієнтовно відомих власних значень його не обов'язково робити на кожному кроці.
Якщо початковий вектор не ортогональний власному підпростору з найбільшим за модулем власним значенням, то відстань від елементів даної послідовності до такого підпростору прямує до нуляУ разі, коли найбільше за модулем власне значення — додатне дійсне число, ця послідовність векторів також збігається до деякого власного вектора.. Послідовність векторів не завжди збіжна, оскільки вектор на кожному кроці може змінювати знак або, в комплексному випадку, обертатися, але це не заважає вибрати один з векторів як власний, коли отримано достатньо точне власне значення.
Послідовність
за зазначеної вище умови збігається до найбільшого за модулем власного значення. Але слід пам'ятати, що не всі дійсні матриці мають дійсні власні значення.
Для нормальних операторів У частковому, але важливому випадку нормальних операторів усі власні вектори матриці взаємно ортогональні. У цьому випадку степеневий метод дозволяє знайти всі власні значення і вектори матриці.
Нехай — нормований власний вектор з найбільшим за модулем власним значенням матриці нормального оператора. Тоді матриця
зберігає всі власні вектори матриці крім вектора і дозволяє шукати степеневим методом наступний власний вектор з найбільшим за модулем власним значенням.
Доведення збіжності Впорядкуємо власні значення за незростанням абсолютної величини і допустимо, що Допущення зроблено для скорочення викладу. У разі збігу декількох власних значень найбільших за модулем доведення аналогічне.. Тоді початковий вектор можна подати як
,
де — власні вектори, вектор обнуляється під час першого множення на матрицю, а за припущенням.
Розглянемо результат множень матриці на початковий вектор:
.
Поділивши ліву і праву частину на , одержимо
Застосування Метод застосовується перш за все для розріджених матриць. Наприклад, Гугл використовує його для розрахунку рангів сторінок в Інтернеті, а Twitter — для рекомендування «за ким стежити»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.
Див. також Зворотний степеневий метод
Примітки