Итерация Арнольди: поиск собственных значений гигантских матриц

Построение ортонормированного базиса подпространства Крылова

Метод Арнольди относится к классу методов в подпространствах Крылова. Идея заключается в том, что мы берем случайный начальный вектор b и начинаем многократно умножать его на исследуемую матрицу A. Полученная последовательность векторов (b, Ab, A^2b, ...) несет в себе колоссальную информацию о собственных значениях матрицы (в первую очередь — о наибольших по модулю). Однако эти векторы быстро становятся почти параллельными, указывая в сторону главного собственного вектора. Гениальность Арнольди заключалась во внедрении процесса ортогонализации Грама-Шмидта на каждом шаге. Новый вектор, получаемый умножением на матрицу A, немедленно очищается от проекций на все предыдущие базисные векторы и нормируется. В результате мы шаг за шагом строим идеальный ортонормированный базис подпространства Крылова.

Матрица Хессенберга и проекция спектра

В процессе построения базиса Арнольди записывает коэффициенты ортогонализации (скалярные произведения) в специальную матрицу H. Из-за структуры алгоритма эта матрица получается не произвольной, а верхней хессенберговой: у нее под главной диагональю находится только одна ненулевая побочная диагональ, а все, что ниже — строгие нули. Если мы выполнили m шагов алгоритма (где m гораздо меньше размерности исходной матрицы n), матрица H будет иметь размер m на m. Теорема Галеркина утверждает, что собственные значения этой крошечной матрицы H (называемые числами Ритца) являются великолепными математическими аппроксимациями крайних (наибольших или наименьших) собственных значений исходной гигантской матрицы A. Мы свели задачу из миллионов измерений к задаче из десятков измерений.

Проблема перезапусков (Restarted Arnoldi)

При практическом применении чистого метода Арнольди возникает серьезная алгоритмическая проблема: с каждым новым шагом количество векторов, на которые нужно ортогонализовать новый вектор, растет. Это приводит к катастрофическому росту потребления оперативной памяти и времени процессора. Чтобы решить эту проблему, используется техника явных или неявных перезапусков (Implicitly Restarted Arnoldi Method, IRAM). Суть метода заключается в том, что алгоритм останавливается на определенном количестве шагов (например, m=50), вычисляет спектр матрицы Хессенберга, «выбрасывает» бесполезные собственные значения (соответствующие шуму или внутренним участкам спектра) и конструирует новый начальный вектор b, который уже обогащен нужными гармониками. Процесс повторяется, удерживая потребление памяти в строгих рамках.

Связь с методом Ланцоша для симметричных задач

Если исходная гигантская матрица A является строго симметричной (или эрмитовой), метод Арнольди кардинально упрощается и превращается в алгоритм Ланцоша (названный в честь венгерского математика Корнелия Ланцоша). В симметричном случае матрица Хессенберга H становится симметричной трехдиагональной матрицей. Это означает, что для ортогонализации нового вектора в подпространстве Крылова нам больше не нужно хранить всю историю предыдущих векторов — достаточно помнить только два последних шага! Трехчленное рекуррентное соотношение алгоритма Ланцоша позволяет вычислять собственные значения матриц миллиардных размерностей, расходуя объем памяти, эквивалентный всего лишь трем векторам, что делает его фундаментом вычислительной квантовой химии и физики твердого тела.