Оглавление
- 1 Lanczos algorithm
- 1.1 История и развитие алгоритма
- 1.2 Описание алгоритма
- 1.3 Применение к собственной проблеме
- 1.4 Сравнение с другими методами
- 1.5 Householder и Lanczos
- 1.6 Derivation of the Lanczos algorithm
- 1.7 Gram–Schmidt process
- 1.8 Arnoldi iteration
- 1.9 Simultaneous approximation of extreme eigenvalues
- 1.10 Направления для улучшения
- 1.11 Параллельность и подпространства Крылова
- 1.12 Итеративное вычисление базиса
- 1.13 Конвергенция и динамика
- 1.14 Теория конвергенции Каниэля–Пейджа
- 1.15 Границы для θ1
- 1.16 Измерение m
- 1.17 Использование полиномов Чебышева
- 1.18 Скорость сходимости
- 1.19 Сравнение с степенным методом
- 1.20 Улучшение алгоритма Ланцоша
- 1.21 Численная стабильность
- 1.22 Практические реализации
- 1.23 Вариации алгоритма Ланцоша
- 1.24 Нулевое пространство над конечным полем
- 1.25 Приложения
- 1.26 Реализации
- 1.27 Полный текст статьи:
- 2 Алгоритм Ланцоша
Lanczos algorithm
-
История и развитие алгоритма
- Алгоритм Lanczos был разработан Корнелиусом Ланцошем для нахождения собственных значений и векторов эрмитовых матриц.
- В 1970 году Оялво и Ньюман улучшили метод, сделав его численно стабильным.
- В 1988 году Оялво опубликовал более подробную историю алгоритма и эффективный тест на ошибки.
-
Описание алгоритма
- Алгоритм не требует доступа к явной матрице, а использует функцию для вычисления произведения матрицы на вектор.
- Каждая итерация включает вычисление нового вектора и матрицы, которая является тридиагональной.
- Алгоритм использует Lanczos векторы для улучшения численной стабильности.
-
Применение к собственной проблеме
- Алгоритм преобразует собственную проблему для матрицы в собственную проблему для тридиагональной матрицы.
- Это позволяет использовать более эффективные методы для вычисления собственных значений и векторов.
- Алгоритм может быть использован для вычисления характеристического полинома и оценки его в точке.
-
Сравнение с другими методами
- Алгоритм Lanczos имеет преимущества для sparse матриц и может быть использован для нахождения нескольких собственных значений.
- Алгоритм Householder также используется для тридиагонализации, но имеет свои особенности.
- Lanczos и Householder имеют схожие требования к памяти и времени выполнения, но Lanczos использует исходную матрицу, а Householder модифицирует её.
-
Householder и Lanczos
- Householder численно стабилен, Lanczos нет
- Lanczos высокопараллелен, Householder менее параллелен
-
Derivation of the Lanczos algorithm
- Power method для нахождения собственных значений и векторов
- Критика метода: расточительность, использование одной переменной для всех векторов
-
Gram–Schmidt process
- Объединение power метода с Gram–Schmidt для получения ортогонального базиса
- Процедура для вычисления ортогональных векторов
-
Arnoldi iteration
- Процедура для вычисления коэффициентов Arnoldi
- Lanczos возникает как упрощение Arnoldi для Hermitian матриц
-
Simultaneous approximation of extreme eigenvalues
- Eigenvectors как стационарные точки Rayleigh quotient
- Локализация максимума и минимума Rayleigh quotient в подпространствах
- Выбор подпространств для оптимальной сходимости
-
Направления для улучшения
- Оптимальные направления для увеличения и уменьшения значений Rayleigh quotient
- Учет новых направлений: Axj и Ayj
- Линейная независимость векторов xj и yj
-
Параллельность и подпространства Крылова
- Нет необходимости увеличивать размер подпространств Крылова на каждом шаге.
- Подпространства Крылова позволяют избежать увеличения размера.
-
Итеративное вычисление базиса
- Удобно иметь ортонормированный базис для каждого подпространства Крылова.
- Итеративное вычисление базиса требует решения проблемы сходимости.
-
Конвергенция и динамика
- Анализ динамики алгоритма использует собственные значения и векторы.
- Начальный вектор v1 должен быть выбран так, чтобы избежать истощения собственных компонентов.
-
Теория конвергенции Каниэля–Пейджа
- После m итераций алгоритм Ланцоша выводит m-мерную симметричную матрицу T.
- Сходимость алгоритма Ланцоша часто быстрее, чем у степенного метода.
-
Границы для θ1
- λ1 является максимальным значением коэффициента Рэлея.
- θ1 является максимумом на m-мерном подпространстве Крылова.
-
Измерение m
- Подпространство Крылова можно выразить через многочлен p(A)v1.
- Многочлен p(A)v1 имеет действительные коэффициенты, но комплексные сопряженные.
-
Использование полиномов Чебышева
- Полиномы Чебышева позволяют получить строгую оценку ошибки.
- Полиномы Чебышева отображают все собственные значения, кроме λ1, в [-1, 1].
-
Скорость сходимости
- Скорость сходимости контролируется R, отношением первого собственного зазора к диаметру остальной части спектра.
- В случае степенного метода скорость сходимости зависит от ρ, отношения абсолютных значений собственных значений.
-
Сравнение с степенным методом
- В случае ρ≫1, R ≈ 1+4ρ, что аналогично степенному методу.
- В случае ρ≪1, R ≈ 1+2ρ, что хуже, чем степенной метод.
-
Улучшение алгоритма Ланцоша
- Алгоритм Ланцоша обеспечивает улучшение по сравнению с собственным зазором.
- В области ρ ≫ 1 алгоритм Ланцоша обеспечивает наименьшее улучшение по сравнению с силовым методом.
-
Численная стабильность
- Численная стабильность важна для оценки полезности реализации алгоритма на компьютере.
- В точной арифметике алгоритм Ланцоша строит ортонормированный базис, но на практике ортогональность теряется.
- Некоторые собственные значения могут быть ложными, что требует их удаления.
-
Практические реализации
- Предотвращение потери ортогональности.
- Восстановление ортогональности после создания базиса.
- Удаление ложных собственных значений после их определения.
-
Вариации алгоритма Ланцоша
- Блочные алгоритмы Ланцоша используют высокие узкие матрицы и маленькие квадратные матрицы.
- Перезапуск алгоритма после определенного количества итераций.
- Метод Ланцоша с неявным перезапуском реализован в ARPACK.
- Метод Ланцоша с толстым перезапуском реализован в TRLan.
-
Нулевое пространство над конечным полем
- Алгоритм Монтгомери для нахождения элементов нулевого пространства большой разреженной матрицы над GF(2).
- Часто называется блочным алгоритмом Ланцоша.
-
Приложения
- Алгоритмы Ланцоша эффективны для умножения на A, что важно для механизмов поиска текста и методов ранжирования.
- Используются в физике конденсированных сред и ядерной физике.
-
Реализации
- Библиотека NAG содержит подпрограммы для решения линейных систем и собственных задач.
- MATLAB и GNU Octave поставляются со встроенным ARPACK.
- Python пакет SciPy содержит scipy.sparse.linalg.eigsh.
- Библиотека GraphLab включает параллельную реализацию алгоритма Ланцоша для многоядерных процессоров.
- Библиотека PRIMME также реализует алгоритм, подобный алгоритму Ланцоша.