Вычисление собственных векторов и значений: Метод обратных степенных итераций

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

Этот численный алгоритм используется для вычисления конкретного, заранее выбранного собственного значения и соответствующего ему собственного вектора квадратной матрицы. Главное преимущество метода — возможность найти собственное значение, ближайшее к заданному числу (сдвигу), или найти собственные значения с наименьшим модулем (близкие к нулю).

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

Суть метода и использование сдвига

Метод основан на применении классического степенного метода к обратной матрице. Математически доказано, что собственные значения обратной матрицы $A^{-1}$ равны $1/\lambda_i$, где $\lambda_i$ — собственные значения исходной матрицы $A$. Следовательно, наибольшее значение для $A^{-1}$ соответствует наименьшему значению для $A$.

Для поиска собственного значения, близкого к произвольному числу $\sigma$ (сигма), используется модификация со сдвигом. Алгоритм применяется к матрице $(A — \sigma I)^{-1}$, где $I$ — единичная матрица. Это позволяет «нацелить» метод на конкретную область спектра матрицы.

Алгоритм метода обратных степенных итераций со сдвигом

Пусть дана квадратная матрица $A$, точность вычислений $\epsilon$ (epsilon), предполагаемое (приближенное) собственное значение $\sigma$ (сдвиг) и произвольный начальный ненулевой вектор $x^{(0)}$.

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

Подготовка: Формируется матрица $M$ и нормализуется начальный вектор:
$$M = A — \sigma I$$

$$x^{(0)} = \frac{x^{(0)}}{||x^{(0)}||}$$
Итерационный процесс: Для $k = 1, 2, 3, …$ до сходимости выполняются следующие шаги:
- а) Решение СЛАУ: Находится вспомогательный вектор $y^{(k)}$, решая систему:
  $$M \cdot y^{(k)} = x^{(k-1)}$$
  
  (Это эквивалентно умножению на обратную матрицу: $y^{(k)} = (A — \sigma I)^{-1} \cdot x^{(k-1)}$)
- б) Нормализация: Вычисляется новый приближенный собственный вектор $x^{(k)}$ путем нормировки (рекомендуется евклидова норма):
  $$x^{(k)} = \frac{y^{(k)}}{||y^{(k)}||}$$
- в) Проверка на сходимость: Если разница между текущим и предыдущим вектором меньше заданной погрешности $\epsilon$, итерации прекращаются:
  $$||x^{(k)} — x^{(k-1)}|| < \epsilon$$
Вычисление итоговых значений:
- Найденный вектор $x^{(k)}$ является приближенным собственным вектором.
- Приближенное собственное значение $\lambda$ исходной матрицы $A$ вычисляется через отношение Релея (знаменатель равен 1 из-за нормализации):
  $$\lambda \approx (x^{(k)})^T \cdot A \cdot x^{(k)}$$

Пример вычисления собственного вектора и значения

Рассмотрим нахождение собственного вектора и значения для матрицы $A$, ближайшего к сдвигу $\sigma = 2$, при точности $\epsilon = 0.01$ и начальном векторе $x^{(0)} = [1, 1, 1]^T$.

$$A = \begin{pmatrix} 6 & -2 & 1 \\ -2 & 4 & 1 \\ 1 & 1 & 4 \end{pmatrix}$$

Шаг 1: Подготовка

Вычисляем матрицу $M = (A — 2I)$:

$$M = \begin{pmatrix} 4 & -2 & 1 \\ -2 & 2 & 1 \\ 1 & 1 & 2 \end{pmatrix}$$

Нормализуем $x^{(0)}$ (где евклидова норма $||x^{(0)}|| = \sqrt{3} \approx 1.732$):

$$x^{(0)} \approx \begin{bmatrix} 0.577 \\ 0.577 \\ 0.577 \end{bmatrix}$$

Итерация $k = 1$

Решаем СЛАУ $M \cdot y^{(1)} = x^{(0)}$. Получаем $y^{(1)} \approx [0.288, 0.577, -0.144]^T$.
Нормализуем $y^{(1)}$ ($||y^{(1)}|| \approx 0.661$): $x^{(1)} \approx [0.436, 0.873, -0.218]^T$.
Проверка сходимости: $||x^{(1)} — x^{(0)}|| \approx 0.88 > \epsilon$. Продолжаем.

Итерация $k = 2$

Решаем СЛАУ $M \cdot y^{(2)} = x^{(1)}$. Получаем $y^{(2)} \approx [0.182, 0.873, -0.345]^T$.
Нормализуем $y^{(2)}$ ($||y^{(2)}|| \approx 0.956$): $x^{(2)} \approx [0.190, 0.913, -0.361]^T$.
Проверка сходимости: $||x^{(2)} — x^{(1)}|| \approx 0.30 > \epsilon$. Продолжаем.

Допустим, на итерации $k=5$ достигнута сходимость (вектор перестал значительно меняться).

Приближенный собственный вектор:

$$x \approx \begin{bmatrix} 0.190 \\ 0.913 \\ -0.361 \end{bmatrix}$$

Вычисляем собственное значение $\lambda$ через отношение Релея:

$$\lambda \approx x^T \cdot A \cdot x \approx 2.44$$

(Действительно, это собственное значение является ближайшим к заданному сдвигу 2).

Область применения и ограничения

Метод обратных итераций со сдвигом является чрезвычайно мощным инструментом, особенно в сочетании с другими методами (например, после того как QR-алгоритм нашел приближенные значения всего спектра, этот метод используется для быстрого и точного нахождения соответствующих векторов).

Преимущества:

Очень быстрая (кубическая) скорость сходимости при хорошем приближении сдвига $\sigma$ к реальному $\lambda$.
Возможность изолировать и найти конкретный собственный вектор.

Ограничения:

Необходимо решать СЛАУ на каждой итерации, что вычислительно дорого для полных матриц большой размерности.
Если сдвиг $\sigma$ в точности равен собственному значению, матрица $(A — \sigma I)$ становится вырожденной, и СЛАУ не имеет однозначного решения (хотя в численных методах это часто приводит к очень сильному росту вектора в нужном направлении, что полезно для поиска).