В математике , мощность итерация (также известная как метод мощности ) является собственным значением алгоритма : дан диагонализируема матрицей , алгоритм будет производить ряд , который является самым большим (по абсолютной величине) собственное значение из , и вектора отличен от нуля , который представляет собой что соответствует собственному вектору из , то есть . Алгоритм также известен как итерация фон Мизеса . [1]
Степенная итерация - очень простой алгоритм, но он может медленно сходиться. Самая трудоемкая операция алгоритма - это умножение матрицы на вектор, поэтому она эффективна для очень большой разреженной матрицы при соответствующей реализации.
Анимация, которая визуализирует алгоритм степенной итерации на матрице 2x2. Матрица изображается двумя собственными векторами. Ошибка вычисляется как
Алгоритм степенной итерации начинается с вектора , который может быть приближением к доминирующему собственному вектору или случайным вектором. Метод описывается рекуррентным соотношением
Итак, на каждой итерации вектор умножается на матрицу и нормализуется.
Если мы предполагаем, что имеет собственное значение, которое строго больше по величине, чем его другие собственные значения, а начальный вектор имеет ненулевую компоненту в направлении собственного вектора, связанного с доминирующим собственным значением, то подпоследовательность сходится к собственному вектору, связанному с доминирующим собственным значением.
Без двух приведенных выше предположений последовательность не обязательно сходится. В этой последовательности
- ,
где - собственный вектор, связанный с доминирующим собственным значением, и . Наличие термина подразумевает, что не сходится разве что . При двух предположениях, перечисленных выше, последовательность, определяемая
сходится к доминирующему собственному значению (с фактором Рэлея ). [ требуется разъяснение ]
Это можно вычислить с помощью следующего алгоритма (показанного на Python с NumPy):
#! / usr / bin / env python3импортировать numpy как npdef power_iteration ( A , num_simulations : int ): # В идеале выберите случайный вектор # Чтобы уменьшить вероятность того, что наш вектор # ортогонален собственному вектору b_k = np . случайный . Rand ( . форма [ 1 ]) for _ in range ( num_simulations ): # вычислить матричное произведение Ab b_k1 = np . точка ( A , b_k ) # вычисляем норму b_k1_norm = np . linalg . норма ( b_k1 ) # повторно нормализовать вектор b_k = b_k1 / b_k1_norm вернуться b_kpower_iteration ( np . array ([[ 0.5 , 0.5 ], [ 0.2 , 0.8 ]]), 10 )
Вектор связанного собственного вектора. В идеале следует использовать фактор Рэлея , чтобы получить соответствующее собственное значение.
Этот алгоритм используется для расчета рейтинга страниц в Google .
Этот метод также можно использовать для вычисления спектрального радиуса (собственное значение с наибольшей величиной для квадратной матрицы) путем вычисления отношения Рэлея
Позвольте быть разложен в его каноническую форму Жордана :, где первый столбец является собственным вектором, соответствующим доминирующему собственному значению . Поскольку доминирующее собственное значение уникально, первый жорданов блок матрицы представляет собой матрицу, где - наибольшее собственное значение матрицы A по величине. Начальный вектор можно записать как линейную комбинацию столбцов V :
По предположению имеет ненулевую составляющую в направлении доминирующего собственного значения, поэтому .
Вычислительно полезное рекуррентное соотношение для можно переписать как:
где выражение: более поддается следующему анализу.
Выражение выше упрощается как
Предел следует из того факта, что собственное значение меньше единицы по модулю, поэтому
Следует, что:
Используя этот факт, можно записать в виде , который подчеркивает его отношения с когда к велико:
где и как
Последовательность ограничена, поэтому она содержит сходящуюся подпоследовательность. Обратите внимание, что собственный вектор, соответствующий доминирующему собственному значению, уникален только с точностью до скаляра, поэтому, хотя последовательность может не сходиться, она почти является собственным вектором A для больших k .
В качестве альтернативы, если является диагонализируемы , тогда следующее доказательство дает тот же результат
Пусть λ 1 , λ 2 , ..., λ m - m собственных значений (с учетом кратности) матрицы A, и пусть v 1 , v 2 , ..., v m - соответствующие собственные векторы. Предположим, что это главное собственное значение, так что для .
Начальный вектор можно записать:
Если выбрано случайно (с равномерной вероятностью), то c 1 ≠ 0 с вероятностью 1 . Сейчас,
С другой стороны:
Следовательно, сходится к (кратному) собственному вектору . Сходимость геометрическая , с соотношением
где обозначает второе доминирующее собственное значение. Таким образом, метод сходится медленно, если имеется собственное значение, близкое по величине к доминирующему собственному значению.
Приложения [ править ]
Хотя метод степенной итерации приближает только одно собственное значение матрицы, он остается полезным для некоторых вычислительных задач . Например, Google использует его для расчета PageRank документов в своей поисковой системе [2], а Twitter использует его, чтобы показать пользователям рекомендации, которым следует следовать. Метод степенной итерации особенно подходит для разреженных матриц , таких как веб-матрица, или в качестве безматричного метода , который не требует явного сохранения матрицы коэффициентов , но вместо этого может обращаться к функции, оценивающей произведение матрица-вектор . Для несимметричных матриц, которыеХорошо подготовленный метод степенной итерации может превзойти более сложную итерацию Арнольди . Для симметричных матриц метод степенной итерации используется редко, поскольку его скорость сходимости может быть легко увеличена без ущерба для небольших затрат на итерацию; см., например, итерацию Ланцоша и LOBPCG .
Некоторые из более продвинутых алгоритмов собственных значений можно понимать как вариации степенной итерации. Например, метод обратной итерации применяет степенную итерацию к матрице . Другие алгоритмы смотрят на все подпространство, порожденное векторами . Это подпространство известно как подпространство Крылова . Его можно вычислить итерацией Арнольди или итерацией Ланцоша .
См. Также [ править ]
- Итерация фактора Рэлея
- Обратная итерация
Ссылки [ править ]
- ^ Рихард фон Мизес и Х. Поллачек-Гейрингер, Praktische Verfahren der Gleichungsauflösung , ZAMM - Zeitschrift für Angewandte Mathematik und Mechanik 9, 152-164 (1929).
- ↑ Ипсен, Ильзе и Ребекка М. Уиллс (5–8 мая 2005 г.). «7-й Международный симпозиум IMACS по итерационным методам в научных вычислениях» (PDF) . Институт Филдса, Торонто, Канада.CS1 maint: multiple names: authors list (link)
|
- Плавающая запятая
- Численная стабильность
|
- Система линейных уравнений
- Матричные разложения
- Умножение матриц ( алгоритмы )
- Расщепление матрицы
- Редкие проблемы
|
- Кеш процессора
- TLB
- Алгоритм без кеширования
- SIMD
- Многопроцессорность
|
- MATLAB
- Подпрограммы базовой линейной алгебры (BLAS)
- ЛАПАК
- Специализированные библиотеки
- Программное обеспечение общего назначения
|