QR decomposition

from Wikipedia, the free encyclopedia

The QR decomposition or QR factorization is a term from the mathematical sub-areas of linear algebra and numerics . It describes the decomposition of a matrix into the product

two other matrices, where is an orthogonal ( ) and unitary matrix ( ) and an upper triangular matrix . The QR decomposition is a special case of the Iwasawa decomposition .

Such a decomposition always exists and can be calculated using various algorithms . The most famous of these are

The latter is commonly used in linear algebra, but is numerically unstable in its standard form . However, the procedure can be expanded and numerically stabilized.


A matrix , has an (almost - see below) clearly reduced QR decomposition

as the product of a matrix which is orthogonal in the columns and an upper triangular matrix

This solution can be expanded to a complete QR decomposition


by adding further orthogonal columns to a square matrix, and adding zero lines at the bottom so that the product is a matrix:

The QR decomposition is unambiguous for and , if one specifies the signs of the diagonal elements of - usually one chooses all positive.


The QR decomposition plays an important role in many numerical mathematics methods , for example to determine an orthogonal or unitary basis or to deal with linear compensation problems. It is an integral part of the QR algorithm and the subspace iteration for calculating eigenvalues ​​of a matrix.

Solving regular or overdetermined systems of equations

To solve a linear system of equations with a matrix ,

To determine full rank, the following three steps must be carried out:
  1. Determine a QR decomposition of the matrix .
  2. Calculate , usually using the factorization of from step 1.
  3. Release by inserting backwards.

For this is an alternative to the LR decomposition , it has twice the effort of the LR decomposition, but is possibly more stable numerically.

In the case, there are more equations than variables in the system of equations and there is an over-determined system of equations . Here, by solving the equalization problem using the least squares method (see also regression analysis ), the following is determined:

Minimize .

In this case the Moore-Penrose pseudo inverse of and for the calculated least squares solution the relation applies , which generalizes the usual representation of the regular case .

Solution of underdetermined systems of equations

For the matrix has a nontrivial core . With the full rank of the solutions of the equation system therefore form an affine subspace . The solution with the smallest norm is in the orthogonal complement of the kernel and you get it with the help of a QR decomposition of :

  1. Determine a QR decomposition of the matrix .
  2. Solve by putting forward.
  3. Calculate .

Here, too, is the Moore-Penrose pseudo inverse of and the relationship applies to the calculated solution of the smallest norm .

Web links