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

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

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

Метод

Пусть имеется квадратная матрица $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\iff (A-\mu I)v=\lambda v-\mu v\iff (\lambda -\mu {)}^{-1}v=(A-\mu I{)}^{-1}v$

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

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

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

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

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

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