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

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

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

МетодПравить

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

$b_{k+1}=\frac{(A-<!--\; -\; -->\mathrm{\mu <!--\; \mu \; -->}I{)}^{-<!--\; -\; -->1}{b}_k}{C_k},$$b_{k+1}={\frac {(A-\mu I)^{-1}b_{k}}{C_{k}}},$ 

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

${\mathrm{\mu <!--\; \mu \; -->}}_b=\frac{b^{T}Ab}{b^{T}b}=\frac{(b,Ab)}{(b,b)}$$\mu _{b}={\frac {b^{T}Ab}{b^{T}b}}={\frac {(b,Ab)}{(b,b)}}$ 

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

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

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

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

$Av=\mathrm{\lambda <!--\; \lambda \; -->}v\iff <!--\; \iff \; -->(A-<!--\; -\; -->\mathrm{\mu <!--\; \mu \; -->}I)v=\mathrm{\lambda <!--\; \lambda \; -->}v-<!--\; -\; -->\mathrm{\mu <!--\; \mu \; -->}v\iff <!--\; \iff \; -->(\mathrm{\lambda <!--\; \lambda \; -->}-<!--\; -\; -->\mathrm{\mu <!--\; \mu \; -->}{)}^{-<!--\; -\; -->1}v=(A-<!--\; -\; -->\mathrm{\mu <!--\; \mu \; -->}I{)}^{-<!--\; -\; -->1}v$$Av=\lambda v\Leftrightarrow (A-\mu I)v=\lambda v-\mu v\Leftrightarrow (\lambda -\mu )^{-1}v=(A-\mu I)^{-1}v$ 

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

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

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

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

$\Vert A\Vert \ge <!--\; \ge \; -->|\mathrm{\lambda <!--\; \lambda \; -->}|,$$\left\|A\right\|\geq |\lambda |,$  для любого собственного значения $\mathrm{\lambda <!--\; \lambda \; -->}$$\lambda$ .

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