Уровень алгоритма

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

Материал из Алговики
Перейти к навигации Перейти к поиску


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


Авторы:

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

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

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

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

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

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

1.2 Математическое описание алгоритма

Исходные данные: