QR decomposition

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 ${\displaystyle A}$

${\displaystyle A=Q\cdot R}$

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 . ${\displaystyle Q}$ ${\displaystyle Q^{T}Q=I}$ ${\displaystyle Q^{\ast }Q=I}$ ${\displaystyle R}$

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

• Household Transformations
• Givens rotations
• Gram-Schmidt's orthogonalization method .

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.

definition

A matrix , has an (almost - see below) clearly reduced QR decomposition ${\displaystyle A\in \mathbb {R} ^{m\times n}}$ ${\displaystyle m\geq n}$

${\displaystyle A={\hat {Q}}\cdot {\hat {R}}}$

as the product of a matrix which is orthogonal in the columns and an upper triangular matrix ${\displaystyle {\hat {Q}}\in \mathbb {R} ^{m\times n}}$ ${\displaystyle {\hat {R}}\in \mathbb {R} ^{n\times n}.}$

This solution can be expanded to a complete QR decomposition

${\displaystyle A=Q\cdot R}$,

by adding further orthogonal columns to a square matrix, and adding zero lines at the bottom so that the product is a matrix: ${\displaystyle {\hat {Q}}}$ ${\displaystyle {\tilde {Q}}}$ ${\displaystyle m\times m}$ ${\displaystyle {\hat {R}}}$ ${\displaystyle m\times n}$

${\displaystyle Q\cdot R={\begin{pmatrix}{\hat {Q}}&{\tilde {Q}}\end{pmatrix}}\cdot {\begin{pmatrix}{\hat {R}}\\0\end{pmatrix}}={\hat {Q}}\cdot {\hat {R}}.}$

The QR decomposition is unambiguous for and , if one specifies the signs of the diagonal elements of - usually one chooses all positive. ${\displaystyle m\geq n}$ ${\displaystyle \operatorname {Rang} (A)=n}$ ${\displaystyle R,{\hat {R}}}$

application

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 , ${\displaystyle x\in \mathbb {R} ^{n}}$ ${\displaystyle A\in \mathbb {R} ^{m\times n},\ m\geq n}$

${\displaystyle Ax=b}$ To determine full rank, the following three steps must be carried out:

1. Determine a QR decomposition of the matrix . ${\displaystyle A}$
2. Calculate , usually using the factorization of from step 1. ${\displaystyle z=Q^{T}b\in \mathbb {R} ^{n}}$ ${\displaystyle Q}$
3. Release by inserting backwards. ${\displaystyle Rx=z}$

For this is an alternative to the LR decomposition , it has twice the effort of the LR decomposition, but is possibly more stable numerically. ${\displaystyle m=n}$

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: ${\displaystyle m>n}$ ${\displaystyle x}$

Minimize . ${\displaystyle \|Ax-b\|^{2}=\sum _{j=1}^{m}\left(\sum _{k=1}^{n}a_{jk}x_{k}-b_{j}\right)^{2}}$

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 . ${\displaystyle A^{+}=R^{+}Q^{T}}$ ${\displaystyle A}$ ${\displaystyle x}$ ${\displaystyle x=A^{+}b}$ ${\displaystyle x=A^{-1}b}$ ${\displaystyle m=n}$

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 : ${\displaystyle m<n}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle Ax=b}$ ${\displaystyle A^{T}}$

1. Determine a QR decomposition of the matrix . ${\displaystyle A^{T}=QR}$
2. Solve by putting forward. ${\displaystyle R^{T}z=b\in \mathbb {R} ^{m}}$
3. Calculate . ${\displaystyle x=Qz\in \mathbb {R} ^{n}}$

Here, too, is the Moore-Penrose pseudo inverse of and the relationship applies to the calculated solution of the smallest norm . ${\displaystyle A^{+}=Q(R^{T})^{+}}$ ${\displaystyle A}$ ${\displaystyle x=A^{+}b}$

Web links

• QR decomposition calculator : Calculates the QR decomposition of a matrix using household transformation
• LP: QR decomposition for linear equalization problems , Georg-August-Universität Göttingen
• taramath online tool for calculating the QR decomposition of real matrices.