Участник:Shostix/Алгоритм Ланцоша для точной арифметики (без переортогонализации): различия между версиями
Shostix (обсуждение | вклад) |
Shostix (обсуждение | вклад) |
||
| Строка 1: | Строка 1: | ||
| + | {{algorithm | ||
| + | | name = Алгоритм Ланцоша для точной арифметики (без ортогонализации) | ||
| + | | serial_complexity = <math>O(kn^2)</math> | ||
| + | | input_data = <math>n*(n+1)/2</math> | ||
| + | | output_data = <math>k*(n+1)</math> | ||
| + | | pf_height = <math>O(k*log(n))</math> | ||
| + | | pf_width = <math>O(n^2)</math> | ||
| + | }} | ||
| + | |||
| + | '''Авторы''': | ||
| + | * [[Участник:Shostix|А.В. Шостик]]. | ||
| + | |||
==Свойства и структура алгоритма== | ==Свойства и структура алгоритма== | ||
=== Общее описание алгоритма === | === Общее описание алгоритма === | ||
| + | |||
| + | '''Алгоритм Ланцоша''' - один из итерационных методов вычисления собственных значений симметричных матриц. Используется для работы с матрицами столь большими, что классические численные методы нахождения собственных значений наприменимы из-за высокой вычислительной сложности. | ||
| + | |||
| + | Алгоритм был предложен в 1950 году венгерским физиком и математиком Корнелием Ланцошем. Основан на методе Ланцоша для построения крыловского подпространства и процедуре Рэлея-Ритца. | ||
| + | |||
| + | В данной статье будет рассмотрен простой метод Ланцоша (без ортогонализации). Он не является устойчивым к влиянию ошибок округления, в отличие от своих модификаций - алгоритма Ланцоша с выборочной ортогонализацией и полной ортогонализацией. На практике часто применяется алгоритм Ланцоша с полной ортогонализацией, предложенный в 1970 году. Он является оптимальным по точности вычислений, хоть и наиболее дорогостоящим алгоритмом из указанных. | ||
| + | |||
| + | Для наименее дорогостоящего в вычислениях алгоритма Ланцоша без ортогонализации будем подразумевать отсутствие влияния ошибок округления на вычислительный процесс. | ||
| + | |||
| + | === Математическое описание алгоритма === | ||
Версия 02:50, 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 году. Он является оптимальным по точности вычислений, хоть и наиболее дорогостоящим алгоритмом из указанных.
Для наименее дорогостоящего в вычислениях алгоритма Ланцоша без ортогонализации будем подразумевать отсутствие влияния ошибок округления на вычислительный процесс.
