Обратный степенной метод

Обратный степенной метод или метод обратных итераций — итеративный алгоритм вычисления собственных векторов и значений. Позволяет искать собственные вектора и собственные значения произвольной матрицы. Обычно используется для вычисления собственных векторов, если для собственных значений известны достаточно хорошие приближения.

В вычислительном отношении метод похож на степенной метод. Вероятно, первоначально он был разработан для вычисления резонансных частот в механике.

Метод

Пусть имеется квадратная матрица $A$ и её приближённое собственное значение $\mu$ Начальный вектор $b_{0}$ может быть случайным или известным приближением собственного вектора. Метод сводится к последовательному вычислению векторов по формуле

$b_{k+1}={\frac {(A-\mu I)^{-1}b_{k}}{C_{k}}},$

где $C_{k}$ — нормирующие константы. Обычно на каждом шаге просто нормируют вектор $b_{k+1}$ к единичной длине. Последовательность векторов не обязательно сходится, но начиная с некоторого шага любой вектор последовательности является собственным с точностью до ошибок округления при умножении на матрицу. Ему соответствует ближайшее к $\mu$ собственное значение. После того как найден собственный вектор $b$ можно точно вычислить это собственное значение по формуле:

$\mu _{b}={\frac {b^{T}Ab}{b^{T}b}}={\frac {(b,Ab)}{(b,b)}}$

Чем ближе $\mu$ к собственному значению тем быстрее сходимость. Когда известны хорошие приближения собственных значений, может потребоваться всего 2 — 3 итерации.

Обоснование и сходимость

Обратный степенной метод отличается от степенного метода только используемой для умножения матрицей. Поэтому он позволяет найти собственный вектор, соответствующий максимальному по модулю собственному значению матрицы $(A-\mu I)^{-1}$. Собственные значения этой матрицы — $(\lambda _{1}-\mu )^{-1},...,(\lambda _{n}-\mu )^{-1},$ где $\lambda _{i}$ собственные значения матрицы $A$. Наибольшее по модулю собственное значение соответствует наименьшему по модулю значению $(\lambda _{1}-\mu ),...,(\lambda _{n}-\mu ).$

Собственные вектора $A$ и $(A-\mu I)^{-1}$ совпадают, поскольку:

$Av=\lambda v\Leftrightarrow (A-\mu I)v=\lambda v-\mu v\Leftrightarrow (\lambda -\mu )^{-1}v=(A-\mu I)^{-1}v$

В частности, если задать $\mu =0$, а матрица $A$ имеет обратную мы найдём собственный вектор с минимальным по модулю собственным значением.

В плане итераций обратный степенной метод ничем не отличается от степенного метода. Поэтому доказательство его сходимости идентично и метод имеет такую же линейную скорость сходимости.

Если неизвестны приближения собственных значений

Пределы для собственных значений матрицы можно найти с помощью векторно подчинённой нормы матрицы. А именно

$\left\|A\right\|\geq |\lambda |,$ для любого собственного значения $\lambda$.

Если собственные значения матрицы достаточно хорошо разделены, то выбирая на отрезке $[-\left\|A\right\|,\left\|A\right\|]$ начальные значения $\mu$ с достаточно малым шагом можно найти все собственные значения и вектора матрицы. Однако в этом случае более эффективным может оказаться метод итераций Рэлея.