Русская Википедия:Обратный степенной метод
Обратный степенной метод, или метод обратных итераций, — итеративный алгоритм вычисления собственных векторов и значений. Позволяет искать собственные вектора и собственные значения произвольной матрицы. Обычно используется для вычисления собственных векторов, если для собственных значений известны достаточно хорошие приближения.
В вычислительном отношении метод похож на степенной метод. Вероятно, первоначально он был разработан для вычисления резонансных частот в механике[1].
Метод
Пусть имеется квадратная матрица <math>A</math> и её приближённое собственное значение <math>\mu</math> Начальный вектор <math>b_0</math> может быть случайным или известным приближением собственного вектора. Метод сводится к последовательному вычислению векторов по формуле
- <math> b_{k+1} = \frac{(A - \mu I)^{-1}b_k}{C_k}, </math>
где <math>C_k</math> — нормирующие константы. Обычно на каждом шаге просто нормируют вектор <math> b_{k+1} </math> к единичной длине. Последовательность векторов не обязательно сходится, но начиная с некоторого шага любой вектор последовательности является собственным с точностью до ошибок округления при умножении на матрицу. Ему соответствует ближайшее к <math> \mu </math> собственное значение. После того как найден собственный вектор <math> b</math>, можно точно вычислить это собственное значение по формуле:
- <math>\mu_b = \frac{b^{T}Ab}{b^{T}b}= \frac{(b,Ab)}{(b,b)}</math>
Чем ближе <math>\mu</math> к собственному значению, тем быстрее сходимость. Когда известны хорошие приближения собственных значений, может потребоваться всего 2 — 3 итерации.
Обоснование и сходимость
Обратный степенной метод отличается от степенного метода только используемой для умножения матрицей. Поэтому он позволяет найти собственный вектор, соответствующий максимальному по модулю собственному значению матрицы <math>(A - \mu I)^{-1}</math>. Собственные значения этой матрицы — <math>(\lambda_1 - \mu)^{-1},...,(\lambda_n - \mu)^{-1}, </math> где <math> \lambda_i </math> — собственные значения матрицы <math>A</math>. Наибольшее по модулю собственное значение соответствует наименьшему по модулю значению <math>(\lambda_1 - \mu),...,(\lambda_n - \mu). </math>
Собственные вектора <math>A</math> и <math>(A - \mu I)^{-1}</math> совпадают, поскольку:
- <math>
Av=\lambda v \Leftrightarrow (A-\mu I)v = \lambda v - \mu v \Leftrightarrow (\lambda - \mu)^{-1} v = (A-\mu I)^{-1} v </math>
В частности, если задать <math>\mu=0</math>, а матрица <math>A</math> имеет обратную, мы найдём собственный вектор с минимальным по модулю собственным значением.
В плане итераций обратный степенной метод ничем не отличается от степенного метода. Поэтому доказательство его сходимости идентично и метод имеет такую же линейную скорость сходимости.
Если неизвестны приближения собственных значений
Пределы для собственных значений матрицы можно найти с помощью векторно подчинённой нормы матрицы. А именно
- <math>\left \| A \right \| \ge |\lambda|, </math> для любого собственного значения <math>\lambda</math>.
Если собственные значения матрицы достаточно хорошо разделены, то, выбирая на отрезке <math>[-\left \| A \right \|,\left \| A \right \|]</math> начальные значения <math>\mu</math> с достаточно малым шагом, можно найти все собственные значения и вектора матрицы. Однако в этом случае более эффективным может оказаться метод итераций Рэлея.
Примечания
- ↑ Ernst Pohlhausen, Berechnung der Eigenschwingungen statisch-bestimmter Fachwerke, ZAMM — Zeitschrift für Angewandte Mathematik und Mechanik 1, 28-42 (1921).
