QR-алгоритм: мощный метод вычисления собственных значений и векторов матрицы

В линейной алгебре задача нахождения собственных значений и собственных векторов является одной из ключевых. Она применяется в самых разных областях: от квантовой физики и структурного анализа до алгоритмов компьютерного зрения и Google PageRank. Наш онлайн-калькулятор использует QR-алгоритм — наиболее универсальный и эффективный численный метод для вычисления полного спектра (всех собственных значений) произвольной квадратной матрицы.

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

Теоретическая основа: QR-разложение

Фундаментом описываемого алгоритма является QR-разложение (или QR-факторизация). Это представление исходной квадратной матрицы $A$ в виде произведения двух специфических матриц:

A = Q * R

Где:

Q — ортогональная матрица. Её главное свойство заключается в том, что транспонированная матрица равна обратной, то есть $Q^T * Q = I$ (где $I$ — единичная матрица). Столбцы матрицы Q являются ортонормированными векторами.
R — верхнетреугольная (или правотреугольная) матрица. Это означает, что все элементы, лежащие ниже главной диагонали, равны нулю.

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

Суть численного QR-алгоритма

QR-алгоритм — это итерационный процесс. Главная идея заключается в том, чтобы с помощью последовательности преобразований подобия привести исходную матрицу $A$ к такому виду, из которого легко извлечь собственные значения.

Ключевой математический факт: если мы разложим матрицу $A_k = Q_k R_k$, а затем перемножим их в обратном порядке $A_{k+1} = R_k Q_k$, то новая матрица $A_{k+1}$ будет подобна предыдущей матрице $A_k$.

Подобные матрицы имеют одинаковые собственные значения.

В процессе итераций матрица $A_k$ постепенно сходится к верхнетреугольной форме (или блочно-треугольной в случае комплексных корней у вещественной матрицы). Когда процесс сходится, искомые собственные значения становятся равны диагональным элементам полученной матрицы.

Этапы пошагового алгоритма

Для определения полного спектра матрицы $A$ с заданной точностью $\varepsilon$ (эпсилон) выполняются следующие шаги:

Инициализация: Принять $A_0 = A$. Задать счетчик итераций $k = 0$.
QR-разложение: На текущем шаге $k$ выполнить QR-разложение матрицы $A_k$:
```
A_k = Q_k * R_k
```
Перестановка множителей: Сформировать матрицу для следующего шага, умножив $R_k$ на $Q_k$:
```
A_{k+1} = R_k * Q_k
```
Проверка сходимости: Проверить элементы ниже главной диагонали матрицы $A_{k+1}$. Если они стали достаточно малы (меньше заданной точности $\varepsilon$), процесс останавливается. В противном случае увеличить $k$ на 1 и вернуться к шагу 2.
Результат: После остановки алгоритма собственные значения $\lambda_i$ приближенно равны элементам на главной диагонали матрицы $A_{k+1}$.

Примечание: Для вещественных несимметричных матриц, имеющих комплексные собственные значения, алгоритм сходится к блочно-треугольной форме (форма Шура), где на диагонали могут стоять блоки 2×2. Собственные значения таких блоков вычисляются как корни квадратного уравнения.

Вычисление собственных векторов

Классический QR-алгоритм, описанный выше, находит только собственные значения. Для нахождения собственных векторов часто используют накопление произведений матриц $Q_k$ ($Q_{total} = Q_0 * Q_1 * … * Q_k$) в процессе итераций, если матрица сходится к треугольному виду, или применяют метод обратных итераций (степенной метод) для каждого уже найденного собственного значения.

Пример использования QR-алгоритма

Рассмотрим применение одной итерации алгоритма для симметричной матрицы A размерности 2×2. Нам нужно найти собственные значения для:

A = | 5 -2 |
    | -2 2 |

(Истинные собственные значения этой матрицы: 6 и 1).

Шаг 1. QR-разложение матрицы A_0 = A.
Используя метод Хаусхолдера или Грама-Шмидта, получаем (округлим значения для наглядности):

Q_0 ≈ |  0.9285  0.3714 |
       | -0.3714  0.9285 |

R_0 ≈ | 5.3852 -2.5998 |
       | 0       0.7428 |

Проверка: Продукт Q_0 * R_0 действительно дает исходную матрицу A.

Шаг 2. Вычисление A_1 = R_0 * Q_0.
Перемножаем матрицы в обратном порядке:

A_1 ≈ | 5.3852 -2.5998 | * |  0.9285  0.3714 | ≈ | 5.9655  1.2138 |
       | 0       0.7428 |   | -0.3714  0.9285 |   | -0.2759 0.6897 |

Анализ первой итерации:
Мы видим, что матрица A_1 стала «более треугольной»: элемент под диагональю (-0.2759) стал ближе к нулю по сравнению с исходным (-2). Диагональные элементы (5.9655 и 0.6897) начали приближаться к истинным собственным значениям (6 и 1).

Алгоритм продолжит итерации до тех пор, пока внедиагональный элемент не станет меньше заданной погрешности.

Преимущества и особенности QR-алгоритма

Почему QR-алгоритм считается стандартом в вычислительной линейной алгебре?

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

Особенности эксплуатации: Чистый QR-алгоритм может сходиться медленно. В реальных вычислительных библиотеках и в нашем калькуляторе используются оптимизации: предварительное приведение матрицы к форме Хессенберга (для ускорения QR-разложения на каждом шаге) и применение сдвигов (shifts) для кардинального ускорения сходимости.

Заключение

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

Если вам необходимо быстро и точно вычислить собственные значения и векторы, не углубляясь в ручные рутинные расчеты, воспользуйтесь нашим онлайн-калькулятором QR-алгоритма. Это сэкономит ваше время и исключит риск случайных арифметических ошибок.