Матрицалық жіктеу: QR жіктеуінің әдістері мен қолданылуы

Matrix decomposition
In linear algebra, a QR decomposition, also known as a QR factorization or QU factorization, is a decomposition of a matrix A into a product A = QR of an orthonormal matrix Q and an upper triangular matrix R. QR decomposition is often used to solve the linear least squares (LLS) problem and is the basis for a particular eigenvalue algorithm, the QR algorithm.

The use of Householder transformations is inherently the most simple of the numerically stable QR decomposition algorithms due to the use of reflections as the mechanism for producing zeroes in the R matrix. However, the Householder reflection algorithm is bandwidth heavy and not parallelizable, as every reflection that produces a new zero element changes the entirety of both Q and R matrices.

QR decompositions can also be computed with a series of Givens rotations. Each rotation zeroes an element in the subdiagonal of the matrix, forming the R matrix. The concatenation of all the Givens rotations forms the orthogonal Q matrix. In practice, Givens rotations are not actually performed by building a whole matrix and doing a matrix multiplication. A Givens rotation procedure is used instead which does the equivalent of the sparse Givens matrix multiplication, without the extra work of handling the sparse elements. The Givens rotation procedure is useful in situations where only relatively few off diagonal elements need to be zeroed, and is more easily parallelized than Householder transformations.

The QR decomposition via Givens rotations is the most involved to implement, as the ordering of the rows required to fully exploit the algorithm is not trivial to determine. However, it has a significant advantage in that each new zero element affects only the row with the element to be zeroed (i) and a row above (j). This makes the Givens rotation algorithm more bandwidth efficient and parallelizable than the Householder reflection technique.

Compared to the direct matrix inverse, inverse solutions using QR decomposition are more numerically stable as evidenced by their reduced condition numbers. To solve the underdetermined linear problem where the matrix has dimensions and rank , first find the QR factorization of the transpose of : , where Q is an orthogonal matrix (i. e. ), and R has a special form: Here is a square right triangular matrix, and the zero matrix has dimension After some algebra, it can be shown that a solution to the inverse problem can be expressed as: where one may either find by Gaussian elimination or compute directly by forward substitution. The latter technique enjoys greater numerical accuracy and lower computations. To find a solution to the overdetermined problem which minimizes the norm <math>\left\ first find the QR factorization of : The solution can then be expressed as , where is an matrix containing the first columns of the full orthonormal basis and where is as before. Equivalent to the underdetermined case, back substitution can be used to quickly and accurately find this without explicitly inverting ( and are often provided by numerical libraries as an "economic" QR decomposition.)

Iwasawa decomposition generalizes QR decomposition to semi simple Lie groups.