Участник:M.grigoriev/Алгоритм Ланцоша для точной арифметики (без переортогонализации)

Алгоритм Ланцоша без переортогонализации

Основные авторы описания: Григорьев М.А.

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

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

Алгоритм Ланцоша был опубликовн физиком и математиком Корнелием Ланцошем в 1950 году. Этот метод является частным случаем алгоритма Арнольда в случае, если исходная матрица $A$ - симметрична, и был представлен как итерационный метод вычисления собственных значений симметричной матрицы. Этот метод позволяет за $k$ итераций вычислять $k$ приближений собственных значений и собственных векторов исходной матрицы. Хотя алгоритм и был эффективным в вычислительном смысле, но он на некоторое время был предан забвению из-за численной неустойчивости. Только в 1970 Ojalvo и Newman модифицировали алгоритм для использования в арифметике с плавающей точкой. Новый метод получил название алгоритма Ланцоша с полной переортогонализацией.

Алгоритм соединяет в себя метод Ланцоша построения крыловского подпространства с процедурой Релея-Ритца. Из ортонормированных векторов Ланцоша строится матрица $Q_k = [q_1, q_2, \dots, q_k]$ размерности $n \times k$ и в качестве приближенных собственных значений принимаются числа Ритца, т.е. собственные значения симметричной трехдиагональной матрицы $T_k = Q^T_k A Q$ размерности $k \times k$.