Численная линейная алгебра: вычисление собственных значений и векторов

Скрытые резонансы: проблема спектрального анализа

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

Физический и инженерный смысл этой задачи колоссален. Собственные значения описывают частоты свободных (резонансных) колебаний механических систем: от гитарной струны и подвески автомобиля до мостов и небоскребов. Совпадение внешней нагрузки с этими частотами вызывает разрушительный резонанс. В квантовой механике собственные значения оператора Гамильтона определяют дискретные уровни энергии атомов (отсюда происходит термин «спектр»). В теории графов и анализе социальных сетей анализ спектра матриц смежности позволяет находить скрытые кластеры и самых влиятельных участников.

Степенной метод для поиска доминирующего значения

Аналитически собственные значения находятся путем решения так называемого характеристического уравнения (поиска корней полинома, степень которого равна размерности матрицы). Однако, как мы знаем из теоремы Абеля-Руффини, для матриц размером 5x5 и больше точных формул корней не существует. Поэтому в реальности собственные значения всегда ищут только итерационными численными методами.

Самым простым подходом является степенной метод (итерации фон Неймана). Он позволяет найти наибольшее по модулю (доминирующее) собственное значение. Идея поразительно проста: мы берем случайный начальный вектор и начинаем многократно умножать его на нашу матрицу. На каждом шаге вектор будет поворачиваться в сторону собственного вектора, соответствующего максимальному собственному значению. После достаточного количества итераций (и периодической нормализации вектора, чтобы числа не ушли в бесконечность) процесс сходится к искомому главному собственному вектору. Именно этот простой принцип лежит в основе первоначального алгоритма PageRank, созданного Ларри Пейджем и Сергеем Брином для ранжирования веб-страниц в поисковой системе Google, где матрицей выступает граф ссылок всего интернета.

Алгоритм QR-разложения для нахождения всего спектра

Степенной метод хорош, если нам нужно только одно максимальное значение. Но что делать, если инженеру нужен весь спектр частот (все собственные значения)? Для этого в 1961 году Джоном Фрэнсисом и Верой Кублановской был независимо разработан QR-алгоритм, который считается одним из 10 самых важных численных алгоритмов 20-го века.

Алгоритм основан на факторизации (разложении) матрицы. На каждом шаге исходная матрица A представляется в виде произведения ортогональной матрицы Q и верхнетреугольной матрицы R (A = QR). Затем эти матрицы умножаются в обратном порядке: строится новая матрица A1 = RQ. Удивительный математический факт состоит в том, что новая матрица A1 имеет точно такие же собственные значения, что и исходная матрица A (они подобны). Если повторять этот процесс итеративно (находя QR-разложение и перемножая в обратном порядке), то матрица постепенно стремится к диагональному (или блочно-диагональному) виду, где все ее собственные значения просто стоят на главной диагонали. С применением предварительного приведения к форме Хессенберга и стратегий сдвигов, QR-алгоритм работает феноменально быстро и стабильно, являясь сегодня ядром библиотек линейной алгебры, таких как LAPACK, встроенных в Python, MATLAB и R.