Алгоритм Ланцоша для арифметики с плавающей точкой с полной переортогонализацией

Основные авторы описания: С.А.Айвазян, В.Козлов (Часть 1), А.Ю.Чернявский (компоновка и редактирование), А.С.Антонов (предварительная проверка).

1 Свойства и структура алгоритма

1.1 Общее описание алгоритма

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

Алгоритм Ланцоша относится к методам аппроксимаций, которые применяют широко распространенную в математике процедуру Релея-Ритца к матричным вычислениям, посредством чего сводят исходную задачу к задаче гораздо меньшего размера, решив которую, получаем приближенные собственные значения и собственные векторы исходной задачи. Метод основан на применении процедуры Релея-Ритца к последовательности вложенных подпространств Крылова. Важной особенностью подпространства Крылова является трехдиагонольность ортогональной проекции на него исходной матрицы, что способствует тому, что процедура Релея-Ритца прорабатывает очень эффективно. Главными особенностями поведения алгоритмов метода Ланцоша являются потеря ортогональности векторов базиса и быстрая сходимость в области наибольших по значению собственных значений. Наиболее популярными средствами борьбы с потерей ортогональности векторов Ланцоша являются различные варианты переортогонализации: частичная, полная и выборочная.

Симметричность исходной матрицы позволяет хранить и вычислять чуть больше половины её элементов, что почти вдвое экономит как необходимые для вычислений объёмы памяти, так и количество операций. Также алгоритм позволяет использовать так называемый режим накопления, обусловленный тем, что значительную часть вычислений составляют вычисления скалярных произведений.

Преимущество алгоритма заключается в том, что он дает приближение за конечное число шагов. Метод Ланцоша выигрывает в конкуренции таким прямым методам, как метод прямых или обратных итераций, [math]QR[/math] и [math]QL[/math] преобразования, методы вращений (вращения Якоби), которые потеряли значение как самостоятельные методы поиска собственных значений матриц большого размера. Также нужно заметить, что метод Ланцоша практически всегда эффективнее других методов аппроксимаций.