Участник:Shostix/Алгоритм Ланцоша для точной арифметики (без переортогонализации): различия между версиями
Shostix (обсуждение | вклад) |
Shostix (обсуждение | вклад) |
||
Строка 1: | Строка 1: | ||
{{algorithm | {{algorithm | ||
− | | name | + | | name = Алгоритм Ланцоша для точной арифметики (без ортогонализации) |
| serial_complexity = <math>O(kn^2)</math> | | serial_complexity = <math>O(kn^2)</math> | ||
− | | input_data = <math>n*(n | + | | input_data = <math>n*(n-1)+2</math> |
− | | output_data | + | | output_data = <math>k*(n+1)</math> |
− | | pf_height | + | | pf_height = <math>O(k*log(n))</math> |
− | | pf_width | + | | pf_width = <math>O(n^2)</math> |
}} | }} | ||
Строка 24: | Строка 24: | ||
=== Математическое описание алгоритма === | === Математическое описание алгоритма === | ||
− | |||
− |
Версия 03:52, 19 января 2017
Алгоритм Ланцоша для точной арифметики (без ортогонализации) | |
Последовательный алгоритм | |
Последовательная сложность | [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 году. Он является оптимальным по точности вычислений, хоть и наиболее дорогостоящим алгоритмом из указанных.
Для наименее дорогостоящего в вычислениях алгоритма Ланцоша без ортогонализации будем подразумевать отсутствие влияния ошибок округления на вычислительный процесс.