Участник: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</math> | + | | input_data = <math>n*(n+1)/2</math> |
| − | | output_data = <math>k*(n+1)</math> | + | | output_data = <math>k*(n+1)</math> |
| − | | pf_height = <math>O(k*log(n))</math> | + | | pf_height = <math>O(k*log(n))</math> |
| − | | pf_width = <math>O(n^2)</math> | + | | pf_width = <math>O(n^2)</math> |
}} | }} | ||
| Строка 24: | Строка 24: | ||
=== Математическое описание алгоритма === | === Математическое описание алгоритма === | ||
| + | |||
| + | ''Исходные данные'': | ||
Версия 03:48, 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 году. Он является оптимальным по точности вычислений, хоть и наиболее дорогостоящим алгоритмом из указанных.
Для наименее дорогостоящего в вычислениях алгоритма Ланцоша без ортогонализации будем подразумевать отсутствие влияния ошибок округления на вычислительный процесс.
1.2 Математическое описание алгоритма
Исходные данные:
