Лучшие вопросы
Таймлайн
Чат
Перспективы
Степенной метод
Из Википедии, свободной энциклопедии
Remove ads
Степенной метод, или метод степенных итераций, — итерационный алгоритм поиска собственного значения с максимальной абсолютной величиной и одного из соответствующих собственных векторов для произвольной матрицы.
Алгоритм прост и сходится со скоростью геометрической прогрессии, если все максимальные по модулю собственные значения совпадают, в противном случае сходимости нет. При близких по модулю собственных значениях сходимость может оказаться медленной. В силу того, что алгоритм сводится к последовательному умножению заданной матрицы на вектор, при правильной реализации он хорошо работает для больших разреженных матриц.
Алгоритм предложен в 1929 году Рихардом фон Мизесом и Хильдой Гейрингер[1].
Remove ads
Алгоритм
Суммиров вкратце
Перспектива
В начале алгоритма генерируется случайный вектор [2]. Далее проводятся последовательные вычисления по итеративной формуле:
Если исходный вектор не ортогонален собственному подпространству с наибольшим по модулю собственным значением, то расстояние от элементов данной последовательности до такого подпространства стремится к нулю[4]. Последовательность векторов не всегда сходится, поскольку вектор на каждом шаге может менять знак или в комплексном случае вращаться, но это не мешает выбрать один из векторов в качестве собственного, когда получено достаточно точное собственное значение.
Последовательность
при указанном выше условии сходится к максимальному по модулю собственному значению. Но следует помнить, что не у всех действительных матриц есть действительные собственные значения.
Remove ads
Для нормальных операторов
Суммиров вкратце
Перспектива
В частном, но важном случае нормальных операторов все собственные векторы матрицы взаимно ортогональны. В этом случае степенной метод позволяет найти все собственные значения и векторы матрицы.
Пусть — нормированный собственный вектор с максимальным по модулю собственным значением матрицы нормального оператора. Тогда матрица
сохраняет все собственные векторы матрицы , кроме вектора , и позволяет искать степенным методом следующий собственный вектор с максимальным по модулю собственным значением.
Remove ads
Доказательство сходимости
Упорядочим собственные значения по невозрастанию абсолютной величины и допустим, что [5]. Тогда начальный вектор можно представить как
- ,
где — собственные векторы, вектор обнуляется при первом умножении на матрицу, а по предположению.
Рассмотрим результат умножений матрицы на начальный вектор:
.
Поделив левую и правую часть на , получим
Remove ads
Приложения
Метод применяется в первую очередь для разреженных матриц. Например, Гугл использует его для расчёта рангов страниц в Интернете[6], а Twitter использует его для рекомендаций «за кем следовать»[7].
Примечания
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads