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

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

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

Метод

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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