QR-алгоритм

• Основы QR-алгоритма

  • QR-алгоритм используется для вычисления собственных значений и собственных векторов симметричных матриц. 
  • Алгоритм основан на последовательном преобразовании матрицы в верхнюю гессенберговскую форму и последующем QR-разложении. 
  • QR-алгоритм является итеративным методом, который стремится к фиксированной точке, где матрица становится диагональной. 

• Стратегия итераций

  • Итерации алгоритма направлены на приближение к фиксированной точке, которая может быть стабильной или нестабильной. 
  • Нестабильная точка может быть стабилизирована с помощью сдвига или дефляции матрицы. 

• Сравнение с поиском собственных векторов

  • Нахождение собственных векторов возможно только для матриц с известными собственными значениями. 
  • Приближение к собственным значениям может быть затруднено, если полуоси эллипса становятся слишком маленькими. 

• Ускорение и дефляция

  • Ускорение достигается путем смещения матрицы к более растянутому состоянию, что ускоряет сходимость. 
  • Дефляция матрицы выполняется, когда одна из поддиагональных записей становится достаточно малой. 

• Неявная версия алгоритма

  • В современной вычислительной практике используется неявная версия алгоритма, которая упрощает использование множественных сдвигов. 

• История и развитие

  • Алгоритм LR предшествовал QR-алгоритму и использовался для нахождения собственных значений. 
  • QR-алгоритм был разработан в начале 1950-х годов и является более стабильным, чем LR. 

• Другие варианты и рекомендации

  • Существуют различные варианты QR-алгоритма, включая алгоритм Голуба-Кахана-Рейнша и алгоритм для бесконечных измерений. 
  • В статье приведены ссылки на дополнительные ресурсы и материалы для изучения QR-алгоритма.