Difference between revisions of "QR decomposition of dense nonsingular matrices"
| [unchecked revision] | [unchecked revision] |
| Line 7: | Line 7: | ||
The classical methods for the QR decomposition can be divided into two groups, namely, methods for the unitary reduction to triangular form and methods for the non-unitary transformation to a unitary matrix. The first group includes the Givens (rotations) and Householder (reflections) methods, while the second group includes the orthogonalization method. Strictly speaking, the proof of the existence theorem (see <ref name="VOLA" />) yields another method for the decomposition via the Cholesky factorization of <math>A^*A</math> and the subsequent calculation of the unitary factor. However, this method does not work for singular matrices; consequently, it is rarely used. | The classical methods for the QR decomposition can be divided into two groups, namely, methods for the unitary reduction to triangular form and methods for the non-unitary transformation to a unitary matrix. The first group includes the Givens (rotations) and Householder (reflections) methods, while the second group includes the orthogonalization method. Strictly speaking, the proof of the existence theorem (see <ref name="VOLA" />) yields another method for the decomposition via the Cholesky factorization of <math>A^*A</math> and the subsequent calculation of the unitary factor. However, this method does not work for singular matrices; consequently, it is rarely used. | ||
| − | === | + | === Unitary reduction to triangular form === |
| − | ==== | + | ==== Givens method ==== |
| − | + | The classical [[Метод Гивенса (вращений) QR-разложения матрицы|Givens (rotations) method]] uses left multiplications by Givens (rotation) matrices for transforming A into the right triangular matrix <math>R</math>. The critical path of the graph of this method is linear with respect to the size of the problem. | |
==== Метод Хаусхолдера ==== | ==== Метод Хаусхолдера ==== | ||
Revision as of 13: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. Usually, the existence of this decomposition is proved for nonsingular matrices (see [2]), in which case all the diagonal entries of the triangular factor are nonzero. However, often, the QR decomposition is also needed in problems where the non-singularity of A is not guaranteed and [math]R[/math] may have some zero diagonal entries. There are several classical methods for finding the QR decomposition. They, and their variants, yield constructive proofs of the existence of this decomposition in the general case.
Contents
1 Methods for finding the QR decomposition of a dense square matrix
The classical methods for the QR decomposition can be divided into two groups, namely, methods for the unitary reduction to triangular form and methods for the non-unitary transformation to a unitary matrix. The first group includes the Givens (rotations) and Householder (reflections) methods, while the second group includes the orthogonalization method. Strictly speaking, the proof of the existence theorem (see [2]) yields another method for the decomposition via the Cholesky factorization of [math]A^*A[/math] and the subsequent calculation of the unitary factor. However, this method does not work for singular matrices; consequently, it is rarely used.
1.1 Unitary reduction to triangular form
1.1.1 Givens method
The classical Givens (rotations) method uses left multiplications by Givens (rotation) matrices for transforming A into the right triangular matrix [math]R[/math]. The critical path of the graph of this method is linear with respect to the size of the problem.
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], например, с помощью модифицированной обратной подстановки.
