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

Алгоритм Ланцоша для точной арифметики (без ортогонализации)
Последовательный алгоритм
Последовательная сложность	$O(kn^2)$
Объём входных данных	$n*(n-1)+2$
Объём выходных данных	$k*(n+1)$
Параллельный алгоритм
Высота ярусно-параллельной формы	$O(k*log(n))$
Ширина ярусно-параллельной формы	$O(n^2)$

Авторы:

• А.В. Шостик.

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

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

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

Алгоритм был предложен в 1950 году венгерским физиком и математиком Корнелием Ланцошем. Основан на методе Ланцоша для построения крыловского подпространства и процедуре Рэлея-Ритца.

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

Для наименее дорогостоящего в вычислениях алгоритма Ланцоша без ортогонализации будем подразумевать отсутствие влияния ошибок округления на вычислительный процесс.