Метод Якоби-Дэвидсона: итерационный поиск внутренних собственных значений

Подход Дэвидсона и расширение подпространства

Метод основан на идее проекции Галеркина. На каждом шаге у нас есть ортонормированный базис некоего небольшого подпространства V. Мы проецируем огромную исходную матрицу A на это подпространство, получаем крошечную матрицу M = V^T * A * V, и находим ее собственные значения (числа Ритца). Выбрав нужное число Ритца и соответствующий вектор Ритца u, мы вычисляем вектор невязки r = A*u - theta*u. В классическом методе Арнольди мы бы просто добавили этот вектор r к нашему базису. Но химик Эрнест Дэвидсон еще в 1975 году понял, что для ускорения сходимости базис нужно расширять не самой невязкой, а вектором, полученным умножением невязки на диагональный предобуславливатель (D - theta*I)^(-1). Это отлично работало для матриц с сильным преобладанием диагонали в квантовой химии, но терпело крах на общих несимметричных задачах.

Уравнение коррекции Якоби: суть метода

Слейпен и ван дер Ворст исправили фундаментальный недостаток метода Дэвидсона, обратившись к идеям Карла Густава Якоба Якоби (1846 год). Они математически доказали, что новое направление для расширения подпространства должно искаться строго в ортогональном дополнении к текущему вектору Ритца u. Для этого формулируется знаменитое уравнение коррекции Якоби-Дэвидсона: (I - u*u^T) * (A - theta*I) * (I - u*u^T) * t = -r. Это уравнение ищет поправочный вектор t, который строго ортогонален текущему приближению u. Геометрически оператор (I - u*u^T) является проектором, который отсекает все компоненты, параллельные u, заставляя алгоритм искать новую информацию в совершенно неизведанных направлениях многомерного пространства.

Точное и приближенное решение уравнения коррекции

Решать уравнение коррекции Якоби-Дэвидсона точно с помощью прямых методов (LU-разложение) не нужно и даже вредно (это слишком дорого). Алгоритмическая красота метода заключается в том, что уравнение коррекции можно решить лишь приблизительно (с малой точностью), используя несколько итераций метода GMRES или BiCGSTAB. Даже грубое, приближенное решение вектора t обеспечивает экспоненциальное ускорение сходимости всего внешнего цикла. Более того, внутрь этого уравнения легко и естественно встраивается любой алгебраический предобуславливатель (Preconditioner), что позволяет использовать физические знания о системе (например, матрицы жесткости без учета малых деформаций) для мгновенного наведения алгоритма на цель.

Применение: магнитогидродинамика и акустика

Метод Якоби-Дэвидсона стал золотым стандартом для решения обобщенных (A*x = lambda*B*x) и полиномиальных задач на собственные значения. В акустике салона автомобиля или концертного зала необходимо найти резонансные частоты воздуха в замкнутом объеме (решение уравнения Гельмгольца). Эти частоты находятся внутри спектра огромной матрицы конечных элементов. Задав параметр сдвига (target shift) в область, например, 400 Герц, алгоритм Якоби-Дэвидсона за считанные секунды выуживает из матрицы размером миллион на миллион те самые несколько векторов, которые вызовут резонанс. В физике плазмы метод используется для расчета магнитогидродинамической устойчивости токамаков (термоядерных реакторов), где матрицы сильно несимметричны, а собственные значения описывают опасные плазменные нестабильности.