Difference between revisions of "QR decomposition of dense nonsingular matrices"
| [unchecked revision] | [unchecked revision] |
| Line 1: | Line 1: | ||
{{level-p}} | {{level-p}} | ||
| − | Finding the decomposition of a matrix A of the form <math>A = QR</math>, where <math>Q</math> is a unitary matrix and <math>R</math> is an upper triangular matrix <ref>В.В.Воеводин, Ю.А.Кузнецов. Матрицы и вычисления. М.: Наука, 1984.</ref> | + | Finding the decomposition of a matrix A of the form <math>A = QR</math>, where <math>Q</math> is a unitary matrix and <math>R</math> is an upper triangular matrix <ref>В.В.Воеводин, Ю.А.Кузнецов. Матрицы и вычисления. М.: Наука, 1984.</ref>, is an important stage in solving certain more complex problems. Существование такого разложения, в котором правая треугольная матрица ещё и не содержит нулей на диагонали, доказано<ref name="VOLA">Воеводин В.В. Вычислительные основы линейной алгебры. М.: Наука, 1977.</ref> для невырожденных матриц. Однако в ряде случаев <math>QR</math>-разложение (возможно, с нулями на диагонали <math>R</math>) нужно и в задачах без гарантии невырожденности. Поэтому для нахождения такого разложения разработано несколько классических методов, являющихся конструктивным доказательством существования разложения в общем случае, а также их варианты. |
== Методы нахождения QR-разложения плотных неособенных матриц == | == Методы нахождения QR-разложения плотных неособенных матриц == | ||
Revision as of 11:51, 5 March 2018
Finding the decomposition of a matrix A of the form [math]A = QR[/math], where [math]Q[/math] is a unitary matrix and [math]R[/math] is an upper triangular matrix [1], is an important stage in solving certain more complex problems. Существование такого разложения, в котором правая треугольная матрица ещё и не содержит нулей на диагонали, доказано[2] для невырожденных матриц. Однако в ряде случаев [math]QR[/math]-разложение (возможно, с нулями на диагонали [math]R[/math]) нужно и в задачах без гарантии невырожденности. Поэтому для нахождения такого разложения разработано несколько классических методов, являющихся конструктивным доказательством существования разложения в общем случае, а также их варианты.
Contents
1 Методы нахождения QR-разложения плотных неособенных матриц
Классические методы QR-разложения можно разделить на две группы: приведения матрицы унитарными преобразованиями к треугольному виду и приведения матрицы неунитарными преобразованиями к унитарному виду. К первой группе относятся методы Гивенса (вращений) и Хаусхолдера (отражений), ко второй — метод ортогонализации. Строго говоря, доказательство теоремы[2] о существовании даёт ещё один способ разложения — через разложение Холецкого матрицы [math]A^*A[/math] с последующей обратной подстановкой, но для вырожденных матриц он не работает, поэтому обычно не применяется.
1.1 Методы приведения унитарными преобразованиями к треугольному виду
1.1.1 Метод Гивенса
Классический метод Гивенса (вращений) основан на преобразованиях вращения (умножения на матрицы Гивенса) слева для приведения матрицы к правому треугольному виду [math]R[/math]. Имеет линейный по размеру задачи критический путь графа.
1.1.2 Метод Хаусхолдера
Классический метод Хаусхолдера (отражений) основан на преобразованиях отражения (Хаусхолдера) слева для приведения матрицы к правому треугольному виду [math]R[/math]. Устойчивый классический вариант имеет квадратичный по размеру задачи критический путь графа, применение сдваивания уменьшает его до [math]O (n log_{2} n)[/math]. Тем не менее, в библиотеках программ более популярен, чем метод Гивенса, из-за того, что легче опирается на базовые подпрограммы библиотеки BLAS.
1.2 Другие методы
1.2.1 Метод ортогонализации
Метод ортогонализации основан на процессе ортогонализации столбцов матрицы. Таким образом, правыми треугольными преобразованиями матрица приводится к унитарному виду [math]Q[/math]. Классический метод неустойчив, а переортогонализация делает этот метод более медленным.
1.2.2 Метод треугольного разложения матрицы Грама
Практически не применяющийся метод работает только в условиях гарантированной невырожденности исходной матрицы [math]A[/math]. Состоит из трёх частей: нахождение матрицы Грама [math]A^*A[/math] столбцов исходной матрицы, нахождение_симметричного_треугольного_разложения матрицы Грама [math]A^*A[/math] в виде [math]R^*R[/math], нахождение унитарной матрицы [math]Q=AR^{-1}[/math], например, с помощью модифицированной обратной подстановки.
