Problem level

Difference between revisions of "QR decomposition of dense nonsingular matrices"

From Algowiki
Jump to navigation Jump to search
[unchecked revision][quality revision]
 
(11 intermediate revisions by one other user not shown)
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>., is an important stage in solving certain more complex problems. Существование такого разложения, в котором правая треугольная матрица ещё и не содержит нулей на диагонали, доказано<ref name="VOLA">Воеводин В.В. Вычислительные основы линейной алгебры. М.: Наука, 1977.</ref> для невырожденных матриц. Однако в ряде случаев <math>QR</math>-разложение (возможно, с нулями на диагонали <math>R</math>) нужно и в задачах без гарантии невырожденности. Поэтому для нахождения такого разложения разработано несколько классических методов, являющихся конструктивным доказательством существования разложения в общем случае, а также их варианты.  
+
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>Voevodin V.V., Kuznetsov Yu.A. Matrices and computations, Moscow: Nauka, 1984.</ref>, is an important stage in solving certain more complex problems. Usually, the existence of this decomposition is proved for nonsingular matrices (see <ref name="VOLA">Voevodin V.V. Computational foundations of linear algebra Moscow: Nauka, 1977.</ref>), 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.  
  
== Методы нахождения QR-разложения плотных неособенных матриц ==
+
== Methods for finding the QR decomposition of a dense square matrix ==
  
Классические методы QR-разложения можно разделить на две группы: приведения матрицы унитарными преобразованиями к треугольному виду и приведения матрицы неунитарными преобразованиями к унитарному виду. К первой группе относятся методы Гивенса (вращений) и Хаусхолдера (отражений), ко второй — метод ортогонализации. Строго говоря, доказательство теоремы<ref name="VOLA" /> о существовании даёт ещё один способ разложения — через разложение Холецкого матрицы <math>A^*A</math> с последующей обратной подстановкой, но для вырожденных матриц он не работает, поэтому обычно не применяется.  
+
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 ====
  
Классический [[Метод Гивенса (вращений) QR-разложения матрицы|метод Гивенса (вращений)]] основан на преобразованиях вращения (умножения на матрицы Гивенса) слева для приведения матрицы к правому треугольному виду <math>R</math>. Имеет линейный по размеру задачи критический путь графа.
+
The classical [[Метод Гивенса (вращений) QR-разложения матрицы|Givens (rotations) method]] uses left multiplications by Givens (rotation) matrices for transforming A into the upper triangular matrix <math>R</math>. The critical path of the graph of this method is linear with respect to the size of the problem.
  
==== Метод Хаусхолдера ====
+
==== Householder method ====
  
Классический [[Метод Хаусхолдера (отражений) QR-разложения матрицы|метод Хаусхолдера (отражений)]] основан на преобразованиях отражения (Хаусхолдера) слева для приведения матрицы к правому треугольному виду <math>R</math>. Устойчивый классический вариант имеет квадратичный по размеру задачи критический путь графа, применение сдваивания уменьшает его до <math>O (n log_{2} n)</math>. Тем не менее, в библиотеках программ более популярен, чем метод Гивенса, из-за того, что легче опирается на базовые подпрограммы библиотеки BLAS.
+
The classical [[Метод Хаусхолдера (отражений) QR-разложения матрицы|Householder (reflections) method]] uses left multiplications by Householder (reflection) matrices for transforming A into the upper triangular matrix <math>R</math>. The critical path of the graph for the stable classical variant is quadratic with respect to the size of the problem, while the use of doubling reduces its size to <math>O (n log_{2} n)</math>. Nevertheless, in program libraries, this method is more popular than Givens' method. The reason is that the former is better suited for using the basic subroutines of the BLAS library.
  
=== Другие методы ===
+
=== Other methods ===
  
==== Метод ортогонализации ====
+
==== Orthogonalization method ====
  
[[Метод ортогонализации]] основан на процессе ортогонализации столбцов матрицы. Таким образом, правыми треугольными преобразованиями матрица приводится к унитарному виду <math>Q</math>. Классический метод неустойчив, а переортогонализация делает этот метод более медленным.
+
The [[orthogonalization method]] implements the orthogonalization process for the columns of A. That is, by using upper triangular elementary matrices, A is transformed into a unitary matrix <math>Q</math>. The classical process is unstable, while the reorthogonalization slows down the process.  
  
==== Метод треугольного разложения матрицы Грама ====
+
==== Triangular decomposition of a Gram matrix ====
  
Практически не применяющийся [[Метод треугольного разложения матрицы Грама|метод]] работает только в условиях гарантированной невырожденности исходной матрицы <math>A</math>. Состоит из трёх частей: нахождение матрицы Грама <math>A^*A</math> столбцов исходной матрицы, [[Метод_Холецкого_(нахождение_симметричного_треугольного_разложения)|нахождение_симметричного_треугольного_разложения]] матрицы Грама <math>A^*A</math> в виде <math>R^*R</math>, нахождение унитарной матрицы <math>Q=AR^{-1}</math>, например, с помощью модифицированной обратной подстановки.
+
This [[Метод треугольного разложения матрицы Грама|method]] is practically not used and works only if the non-singularity of the original matrix <math>A</math> is guaranteed. The method consists of three parts: 1. Construction of the Gram matrix <math>A^*A</math> for the columns of the original matrix. 2. Finding the [[Метод_Холецкого_(нахождение_симметричного_треугольного_разложения)|Cholesky decomposition]] <math>R^*R</math> of the Gram matrix <math>A^*A</math>. 3. Calculation of the unitary matrix <math>Q=AR^{-1}</math> by using, for instance, the modified back substitution.
  
== Литература ==
+
== References ==
 
<references />
 
<references />
  

Latest revision as of 16:14, 16 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.

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 upper 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 Householder method

The classical Householder (reflections) method uses left multiplications by Householder (reflection) matrices for transforming A into the upper triangular matrix [math]R[/math]. The critical path of the graph for the stable classical variant is quadratic with respect to the size of the problem, while the use of doubling reduces its size to [math]O (n log_{2} n)[/math]. Nevertheless, in program libraries, this method is more popular than Givens' method. The reason is that the former is better suited for using the basic subroutines of the BLAS library.

1.2 Other methods

1.2.1 Orthogonalization method

The orthogonalization method implements the orthogonalization process for the columns of A. That is, by using upper triangular elementary matrices, A is transformed into a unitary matrix [math]Q[/math]. The classical process is unstable, while the reorthogonalization slows down the process.

1.2.2 Triangular decomposition of a Gram matrix

This method is practically not used and works only if the non-singularity of the original matrix [math]A[/math] is guaranteed. The method consists of three parts: 1. Construction of the Gram matrix [math]A^*A[/math] for the columns of the original matrix. 2. Finding the Cholesky decomposition [math]R^*R[/math] of the Gram matrix [math]A^*A[/math]. 3. Calculation of the unitary matrix [math]Q=AR^{-1}[/math] by using, for instance, the modified back substitution.

2 References

  1. Voevodin V.V., Kuznetsov Yu.A. Matrices and computations, Moscow: Nauka, 1984.
  2. 2.0 2.1 Voevodin V.V. Computational foundations of linear algebra Moscow: Nauka, 1977.