Оглавление
QR-алгоритм
-
Основы QR-алгоритма
- QR-алгоритм используется для вычисления собственных значений и собственных векторов симметричных матриц.
- Алгоритм основан на последовательном преобразовании матрицы в верхнюю гессенберговскую форму и последующем QR-разложении.
- QR-алгоритм является итеративным методом, который стремится к фиксированной точке, где матрица становится диагональной.
-
Стратегия итераций
- Итерации алгоритма направлены на приближение к фиксированной точке, которая может быть стабильной или нестабильной.
- Нестабильная точка может быть стабилизирована с помощью сдвига или дефляции матрицы.
-
Сравнение с поиском собственных векторов
- Нахождение собственных векторов возможно только для матриц с известными собственными значениями.
- Приближение к собственным значениям может быть затруднено, если полуоси эллипса становятся слишком маленькими.
-
Ускорение и дефляция
- Ускорение достигается путем смещения матрицы к более растянутому состоянию, что ускоряет сходимость.
- Дефляция матрицы выполняется, когда одна из поддиагональных записей становится достаточно малой.
-
Неявная версия алгоритма
- В современной вычислительной практике используется неявная версия алгоритма, которая упрощает использование множественных сдвигов.
-
История и развитие
- Алгоритм LR предшествовал QR-алгоритму и использовался для нахождения собственных значений.
- QR-алгоритм был разработан в начале 1950-х годов и является более стабильным, чем LR.
-
Другие варианты и рекомендации
- Существуют различные варианты QR-алгоритма, включая алгоритм Голуба-Кахана-Рейнша и алгоритм для бесконечных измерений.
- В статье приведены ссылки на дополнительные ресурсы и материалы для изучения QR-алгоритма.
Полный текст статьи: