Введение

Разложение матрицы
В линейной алгебре, QR-разложение, также известное как QR-факторизация или QU-факторизация, — это разложение матрицы A в произведение A = QR ортогональной матрицы Q и верхнетреугольной матрицы R. QR-разложение часто используется для решения задачи линейных наименьших квадратов (LLS) и является основой для конкретного алгоритма вычисления собственных значений, QR-алгоритма.

Преимущества и недостатки

Использование преобразований Хаусхолдера является самым простым из численно устойчивых алгоритмов QR-разложения благодаря использованию отражений как механизма для создания нулей в матрице R. Однако алгоритм отражений Хаусхолдера требует больших затрат памяти и не поддается параллелизации, поскольку каждое отражение, создающее новый нулевой элемент, изменяет все элементы матриц Q и R.

Использование вращений Гивенса

QR-разложения также могут быть вычислены с помощью последовательности вращений Гивенса. Каждое вращение обнуляет элемент в поддиагонали матрицы, формируя матрицу R. Конкатенация всех вращений Гивенса формирует ортогональную матрицу Q. На практике вращения Гивенса не выполняются путем построения полной матрицы и выполнения матричного умножения. Вместо этого используется процедура вращения Гивенса, которая выполняет эквивалент разреженного матричного умножения Гивенса, без дополнительных затрат на обработку разреженных элементов. Процедура вращения Гивенса полезна в ситуациях, когда необходимо обнулить лишь относительно небольшое количество внедиагональных элементов, и она легче поддается параллелизации, чем преобразования Хаусхолдера.

Преимущества и недостатки

QR-разложение с использованием вращений Гивенса наиболее сложно реализовать, поскольку определение порядка строк, необходимого для полного использования алгоритма, не является тривиальной задачей. Однако, оно обладает существенным преимуществом: каждый новый нулевой элемент влияет только на строку, содержащую элемент, который нужно обнулить (i), и на строку выше (j). Это делает алгоритм вращений Гивенса более эффективным с точки зрения полосы пропускания и более пригодным для параллельных вычислений, чем метод отражений Хаусхолдера.

Использование для решения линейных инверсных задач

По сравнению с прямым вычислением обратной матрицы, обратные решения с использованием QR-разложения более численно устойчивы, что подтверждается их меньшими числами обусловленности. Для решения недоопределённой линейной задачи, где матрица имеет размеры и ранг , сначала найдите QR-факторизацию транспонированной матрицы : , где Q – ортогональная матрица (т.е. ), а R имеет специальную форму: Здесь – квадратная верхнетреугольная матрица, а нулевая матрица имеет размерность . После некоторых алгебраических преобразований можно показать, что решение обратной задачи может быть выражено как: , где можно найти либо методом Гаусса, либо вычислить непосредственно методом прямой подстановки. Последний метод обеспечивает более высокую числовую точность и требует меньше вычислений. Чтобы найти решение переопределённой задачи, минимизирующее норму <math>\left\ , сначала найдите QR-факторизацию матрицы : Решение может быть выражено как , где – матрица размера , содержащая первые столбцов полного ортонормального базиса , а – как и ранее. Аналогично недоопределённому случаю, обратная подстановка может быть использована для быстрого и точного нахождения этого , без явного вычисления обратной матрицы (и часто предоставляется численными библиотеками в виде "экономичного" QR-разложения).

Обобщения

Разложение Ивасавы обобщает QR-разложение на полупростые группы Ли.