QR-разложения плотных неособенных матриц

Нахождение разложения матриц в виде [math]\displaystyle{ A = QR }[/math], где [math]\displaystyle{ Q }[/math] - унитарная, [math]\displaystyle{ R }[/math] — правая треугольная матрица., является важным этапом при решении некоторых более сложных задач. Существование такого разложения, в котором правая треугольная матрица ещё и не содержит нулей на диагонали, доказано для невырожденных матриц. Однако в ряде случаев [math]\displaystyle{ QR }[/math]-разложение (возможно, с нулями на диагонали [math]\displaystyle{ R }[/math]) нужно и в задачах без гарантии невырожденности. Поэтому для нахождения такого разложения разработано несколько классических методов, являющихся конструктивным доказательством существования разложения в общем случае, а также их варианты.

Методы нахождения QR-разложения плотных неособенных матриц

Классические методы QR-разложения можно разделить на две группы: приведения матрицы унитарными преобразованиями к треугольному виду и приведения матрицы неунитарными преобразованиями к унитарному виду. К первой группе относятся методы Гивенса (вращений) и Хаусхолдера (отражений), ко второй — метод ортогонализации. Строго говоря, доказательство теоремы о существовании даёт ещё один способ разложения — через разложение Холецкого матрицы [math]\displaystyle{ A^*A }[/math] с последующей обратной подстановкой, но для вырожденных матриц он не работает, поэтому обычно не применяется.

Методы приведения унитарными преобразованиями к треугольному виду

Метод Гивенса

Классический метод Гивенса (вращений) основан на преобразованиях вращения (умножения на матрицы Гивенса) слева для приведения матрицы к правому треугольному виду [math]\displaystyle{ R }[/math]. Имеет линейный по размеру задачи критический путь графа.

Метод Хаусхолдера

Классический метод Хаусхолдера (отражений) основан на преобразованиях отражения (Хаусхолдера) слева для приведения матрицы к правому треугольному виду [math]\displaystyle{ R }[/math]. Устойчивый классический вариант имеет квадратичный по размеру задачи критический путь графа, применение сдваивания уменьшает его до [math]\displaystyle{ O (n log_{2} n) }[/math]. Тем не менее, в библиотеках программ более популярен, чем метод Гивенса, из-за того, что легче опирается на базовые подпрограммы библиотеки BLAS.

Другие методы

Метод ортогонализации

Метод ортогонализации основан на процессе ортогонализации столбцов матрицы. Таким образом, правыми треугольными преобразованиями матрица приводится к унитарному виду [math]\displaystyle{ Q }[/math]. Классический метод неустойчив, а переортогонализация делает этот метод более медленным.

Метод треугольного разложения матрицы Грама

Практически не применяющийся метод работает только в условиях гарантированной невырожденности исходной матрицы [math]\displaystyle{ A }[/math]. Состоит из трёх частей: нахождение матрицы Грама [math]\displaystyle{ A^*A }[/math] столбцов исходной матрицы, нахождение_симметричного_треугольного_разложения матрицы Грама [math]\displaystyle{ A^*A }[/math] в виде [math]\displaystyle{ R^*R }[/math], нахождение унитарной матрицы [math]\displaystyle{ Q=AR^{-1} }[/math], например, с помощью модифицированной обратной подстановки.