Итерация мощности - Power iteration

В математика, итерация мощности (также известный как силовой метод) является алгоритм собственных значений: учитывая диагонализуемый матрица ${displaystyle A}$, алгоритм выдаст число ${displaystyle lambda}$, что является наибольшим (по абсолютной величине) собственное значение из ${displaystyle A}$, и ненулевой вектор ${displaystyle v}$, что является соответствующим собственный вектор из ${displaystyle lambda}$, это, ${displaystyle Av = лямбда v}$.Алгоритм также известен как Итерация фон Мизеса.^[1]

Степенная итерация - очень простой алгоритм, но он может медленно сходиться. Самая трудоемкая операция алгоритма - это умножение матрицы ${displaystyle A}$ вектором, поэтому он эффективен для очень больших разреженная матрица при соответствующей реализации.

Метод

Анимация, которая визуализирует алгоритм степенной итерации на матрице 2x2. Матрица изображается двумя собственными векторами. Ошибка вычисляется как ${displaystyle || {ext {приближение}} - {ext {наибольший собственный вектор}} ||}$

Алгоритм степенной итерации начинается с вектора ${displaystyle b_ {0}}$, который может быть приближением к доминирующему собственному вектору или случайному вектору. Метод описывается отношение повторения

${displaystyle b_ {k + 1} = {frac {Ab_ {k}} {| Ab_ {k} |}}}$

Итак, на каждой итерации вектор ${displaystyle b_ {k}}$ умножается на матрицу ${displaystyle A}$ и нормализованный.

Если мы предположим ${displaystyle A}$ имеет собственное значение, которое строго больше, чем его другие собственные значения, и начальный вектор ${displaystyle b_ {0}}$ имеет ненулевую компоненту в направлении собственного вектора, связанного с доминирующим собственным значением, тогда подпоследовательность ${displaystyle left (b_ {k} ight)}$ сходится к собственному вектору, связанному с доминирующим собственным значением.

Без двух приведенных выше предположений последовательность ${displaystyle left (b_ {k} ight)}$ не обязательно сходится. В этой последовательности

${displaystyle b_ {k} = e ^ {iphi _ {k}} v_ {1} + r_ {k}}$,

где ${displaystyle v_ {1}}$ - собственный вектор, связанный с доминирующим собственным значением, а ${displaystyle | r_ {k} | ightarrow 0}$. Наличие термина ${displaystyle e ^ {iphi _ {k}}}$ подразумевает, что ${displaystyle left (b_ {k} ight)}$ не сходится, если ${displaystyle e ^ {iphi _ {k}} = 1}$. При двух перечисленных выше предположениях последовательность ${displaystyle left (mu _ {k} ight)}$ определяется

${displaystyle mu _ {k} = {frac {b_ {k} ^ {*} Ab_ {k}} {b_ {k} ^ {*} b_ {k}}}}$

сходится к главному собственному значению.^{[требуется разъяснение ]}

Это можно вычислить с помощью следующего алгоритма (показанного на Python с NumPy):

#! / usr / bin / env python3импорт тупой так как нпdef power_iteration(А, num_simulations: int):    # В идеале выбираем случайный вектор    # Чтобы уменьшить вероятность того, что наш вектор    # Ортогонален собственному вектору    b_k = нп.случайный.ранд(А.форма[1])    за _ в ассортимент(num_simulations):        # вычисляем матричное произведение Ab        b_k1 = нп.точка(А, b_k)        # вычисляем норму        b_k1_norm = нп.линалг.норма(b_k1)        # повторно нормализовать вектор        b_k = b_k1 / b_k1_norm    вернуть b_kpower_iteration(нп.массив([[0.5, 0.5], [0.2, 0.8]]), 10)

Вектор ${displaystyle b_ {k}}$ в связанный собственный вектор. В идеале следует использовать Фактор Рэлея чтобы получить соответствующее собственное значение.

Этот алгоритм используется для расчета Google PageRank.

Метод также можно использовать для расчета спектральный радиус (собственное значение с наибольшей величиной для квадратной матрицы) путем вычисления отношения Рэлея

${displaystyle ho (A) = max left {| lambda _ {1} |, dotsc, | lambda _ {n} | ight} = {frac {b_ {k} ^ {op} Ab_ {k}} {b_ {k}) } ^ {op} b_ {k}}} = {frac {b_ {k + 1} ^ {op} b_ {k}} {b_ {k} ^ {op} b_ {k}}}.}$

Анализ

Позволять ${displaystyle A}$ разложить на Иорданская каноническая форма: ${displaystyle A = VJV ^ {- 1}}$, где первый столбец ${displaystyle V}$ является собственным вектором ${displaystyle A}$ соответствующее доминирующему собственному значению ${displaystyle lambda _ {1}}$. Поскольку доминирующее собственное значение ${displaystyle A}$ уникальна, первая жорданова блок ${displaystyle J}$ это ${displaystyle 1 imes 1}$ матрица ${displaystyle [lambda _ {1}],}$ где ${displaystyle lambda _ {1}}$ является наибольшим собственным значением А по величине. Стартовый вектор ${displaystyle b_ {0}}$ можно записать как линейную комбинацию столбцов V:

${displaystyle b_ {0} = c_ {1} v_ {1} + c_ {2} v_ {2} + cdots + c_ {n} v_ {n}.}$

По предположению, ${displaystyle b_ {0}}$ имеет ненулевую компоненту в направлении доминирующего собственного значения, поэтому ${displaystyle c_ {1} экв 0}$.

Вычислительно полезный отношение повторения за ${displaystyle b_ {k + 1}}$ можно переписать как:

${displaystyle b_ {k + 1} = {frac {Ab_ {k}} {| Ab_ {k} |}} = {frac {A ^ {k + 1} b_ {0}} {| A ^ {k + 1) } b_ {0} |}},}$

где выражение: ${displaystyle {frac {A ^ {k + 1} b_ {0}} {| A ^ {k + 1} b_ {0} |}}}$ более поддается следующему анализу.

${displaystyle {egin {align} b_ {k} & = {frac {A ^ {k} b_ {0}} {| A ^ {k} b_ {0} |}} & = {frac {left (VJV ^ {-1} ight) ^ {k} b_ {0}} {| left (VJV ^ {- 1} ight) ^ {k} b_ {0} |}} & = {frac {VJ ^ {k} V ^ {- 1} b_ {0}} {| VJ ^ {k} V ^ {- 1} b_ {0} |}} & = {frac {VJ ^ {k} V ^ {- 1} left (c_ {1} v_ {1} + c_ {2} v_ {2} + cdots + c_ {n} v_ {n} ight)} {| VJ ^ {k} V ^ {- 1} влево (c_ {1} v_ {1} + c_ {2} v_ {2} + cdots + c_ {n} v_ {n} ight) |}} & = {frac {VJ ^ {k} left (c_ {1} e_ {1} + c_ {2} e_ {2} + cdots + c_ {n} e_ {n} ight)} {| VJ ^ {k} left (c_ {1} e_ {1} + c_ {2} e_ {2} + cdots + c_ {n} e_ {n} ight) |}} & = left ({frac {lambda _ {1}} {| lambda _ {1} |}} ight) ^ {k} {frac {c_ {1 }} {| c_ {1} |}} {frac {v_ {1} + {frac {1} {c_ {1}}} Vleft ({frac {1} {lambda _ {1}}} Jight) ^ { k} left (c_ {2} e_ {2} + cdots + c_ {n} e_ {n} ight)} {left | v_ {1} + {frac {1} {c_ {1}}} Vleft ({frac {1} {lambda _ {1}}} Jight) ^ {k} left (c_ {2} e_ {2} + cdots + c_ {n} e_ {n} ight) ight |}} конец {выровнено}}}$

Выражение выше упрощается как ${displaystyle k o infty}$

${displaystyle left ({frac {1} {lambda _ {1}}} Jight) ^ {k} = {egin {bmatrix} [1] &&&& & left ({frac {1} {lambda _ {1}}} J_ {2} ight) ^ {k} &&& && ddots & &&& left ({frac {1} {lambda _ {1}}} J_ {m} ight) ^ {k} end {bmatrix}} ightarrow {egin {bmatrix } 1 &&&& & 0 &&& && ddots & &&& 0 end {bmatrix}} quad {ext {as}} quad k o infty.}$

Предел следует из того, что собственное значение ${displaystyle {frac {1} {lambda _ {1}}} J_ {i}}$ меньше единицы по величине, поэтому

${displaystyle left ({frac {1} {lambda _ {1}}} J_ {i} ight) ^ {k} o 0quad {ext {as}} quad k o infty.}$

Это следует из того:

${displaystyle {frac {1} {c_ {1}}} Vleft ({frac {1} {lambda _ {1}}} Jight) ^ {k} left (c_ {2} e_ {2} + cdots + c_ { n} e_ {n} ight) o 0quad {ext {as}} quad k o infty}$

Используя этот факт, ${displaystyle b_ {k}}$ можно записать в форме, подчеркивающей его связь с ${displaystyle v_ {1}}$ когда k большой:

${displaystyle {egin {align} b_ {k} & = left ({frac {lambda _ {1}} {| lambda _ {1} |}} ight) ^ {k} {frac {c_ {1}} {| c_ {1} |}} {frac {v_ {1} + {frac {1} {c_ {1}}} Vleft ({frac {1} {lambda _ {1}}} Jight) ^ {k} left ( c_ {2} e_ {2} + cdots + c_ {n} e_ {n} ight)} {left | v_ {1} + {frac {1} {c_ {1}}} Vleft ({frac {1} { лямбда _ {1}}} Jight) ^ {k} left (c_ {2} e_ {2} + cdots + c_ {n} e_ {n} ight) ight |}} [6pt] & = e ^ {iphi _ {k}} {frac {c_ {1}} {| c_ {1} |}} {frac {v_ {1}} {| v_ {1} |}} + r_ {k} end {align}}}$

где ${displaystyle e ^ {iphi _ {k}} = left (lambda _ {1} / | lambda _ {1} | ight) ^ {k}}$ и ${displaystyle | r_ {k} | o 0}$ так как ${displaystyle k o infty}$

Последовательность ${displaystyle left (b_ {k} ight)}$ ограничен, поэтому он содержит сходящуюся подпоследовательность. Обратите внимание, что собственный вектор, соответствующий доминирующему собственному значению, уникален только с точностью до скаляра, поэтому, хотя последовательность ${displaystyle left (b_ {k} ight)}$ может не сходиться,${displaystyle b_ {k}}$ является почти собственным вектором А для больших k.

В качестве альтернативы, если А является диагонализуемый, то следующее доказательство дает тот же результат

Пусть λ₁, λ₂, ..., λ_м быть м собственные значения (с учетом кратности) А и разреши v₁, v₂, ..., v_м - соответствующие собственные векторы. Предположим, что ${displaystyle lambda _ {1}}$ является доминантным собственным значением, так что ${displaystyle | lambda _ {1} |> | lambda _ {j} |}$ за ${displaystyle j> 1}$.

Начальный вектор ${displaystyle b_ {0}}$ можно написать:

${displaystyle b_ {0} = c_ {1} v_ {1} + c_ {2} v_ {2} + cdots + c_ {m} v_ {m}.}$

Если ${displaystyle b_ {0}}$ выбирается случайно (с равномерной вероятностью), то c₁ ≠ 0 с вероятность 1. Сейчас же,

${displaystyle {egin {align} A ^ {k} b_ {0} & = c_ {1} A ^ {k} v_ {1} + c_ {2} A ^ {k} v_ {2} + cdots + c_ { m} A ^ {k} v_ {m} & = c_ {1} лямбда _ {1} ^ {k} v_ {1} + c_ {2} лямбда _ {2} ^ {k} v_ {2} + cdots + c_ {m} lambda _ {m} ^ {k} v_ {m} & = c_ {1} lambda _ {1} ^ {k} left (v_ {1} + {frac {c_ {2}}) {c_ {1}}} слева ({frac {lambda _ {2}} {lambda _ {1}}} ight) ^ {k} v_ {2} + cdots + {frac {c_ {m}} {c_ { 1}}} left ({frac {lambda _ {m}} {lambda _ {1}}} ight) ^ {k} v_ {m} ight) & o c_ {1} lambda _ {1} ^ {k } v_ {1} && left | {frac {lambda _ {j}} {lambda _ {1}}} ight | <1 {ext {for}} j> 1end {выровнено}}}$

С другой стороны:

${displaystyle b_ {k} = {frac {A ^ {k} b_ {0}} {| A ^ {k} b_ {0} |}}.}$

Следовательно, ${displaystyle b_ {k}}$ сходится к (кратному) собственному вектору ${displaystyle v_ {1}}$. Сходимость геометрический, с соотношением

${displaystyle left | {frac {lambda _ {2}} {lambda _ {1}}} ight |,}$

где ${displaystyle lambda _ {2}}$ обозначает второе доминирующее собственное значение. Таким образом, метод сходится медленно, если имеется собственное значение, близкое по величине к доминирующему собственному значению.

Приложения

Хотя метод степенной итерации приближает только одно собственное значение матрицы, он остается полезным для некоторых вычислительные проблемы. Например, Google использует его для расчета PageRank документов в их поисковой системе,^[2] и Twitter использует его, чтобы показать пользователям рекомендации, которым следует следовать.^[3] Метод степенной итерации особенно подходит для разреженные матрицы, например веб-матрицу или безматричный метод не требующий хранения матрицы коэффициентов ${displaystyle A}$ явно, но вместо этого может получить доступ к функции, оценивающей произведение матрица-вектор ${displaystyle Ax}$. Для несимметричных матриц, которые хорошо кондиционированный метод степенной итерации может превзойти более сложные Итерация Арнольди. Для симметричных матриц метод степенных итераций используется редко, поскольку его скорость сходимости может быть легко увеличена без ущерба для небольших затрат на итерацию; см., например, Итерация Ланцоша и LOBPCG.

Некоторые из более продвинутых алгоритмов собственных значений можно рассматривать как вариации степенной итерации. Например, обратная итерация метод применяет степенную итерацию к матрице ${displaystyle A ^ {- 1}}$. Другие алгоритмы смотрят на все подпространство, созданное векторами ${displaystyle b_ {k}}$. Это подпространство известно как Крыловское подпространство. Его можно вычислить Итерация Арнольди или Итерация Ланцоша.

Смотрите также

• Итерация фактора Рэлея
• Обратная итерация

использованная литература