Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Why do we need QR factorization? Is this used in any particular field?

share|cite|improve this question
QR-decompostion based algorithm developed in 1950s is an efficient algorithm for computing the eigenvalues and eigenvectors of a matrix.A wiki link is provided here. – y zh Sep 18 '12 at 12:16
up vote 3 down vote accepted

$\def\R{\mathbb R}\def\norm#1{\left\|#1\right\|}\def\Mat{\mathrm{Mat}}$ QR-factorisation can, for example, be used to solve linear least squares approximation problems as follows: Given $n \le m$, $A \in \Mat_{m,n}(\R)$ with full rank $n$, $b \in \R^m$ \[ \mathrm{find}\ x \in \R^n : \norm{Ax - b}_2 = \min \] Computing the QR-factorisation of $A$, we write $A = QR$ with $Q \in O(m)$, $R \in \Mat_{m,n}(\R)$ upper triangular. Now, as the $2$-norm is invariant under multiplication with orthogonal matrices, \[ \norm{Ax- b}_2 = \norm{Q^{-1}Ax - Q^{-1}b}_2 = \norm{Rx - Q^{-1}b}_2 \] As $m \ge n$, $R$ is of the form $R = \begin{pmatrix} R' \\ 0\end{pmatrix}$ with $R' \in \Mat_n(\R)$ upper triangular. Writing $Q^{-1}b = \begin{pmatrix} y_1 \\ y_2\end{pmatrix}, x = \begin{pmatrix} x_1\\ x_2\end{pmatrix} \in \R^n \times \R^{m-n}$, we have \[ \norm{Ax - b}_2 = \sqrt{\norm{Rx_1 - y_1}^2 + \norm{y_2}^2} \] as $\mathop{\mathrm{rank}} R' = \mathop{\mathrm{rank}} A = n$, $R'$ is invertible and hence we need $x = R'^{-1}y_1$ for minimisation.

Another thing, QR factorisation can be useful for is numerical approximation of eigenvectors and -values of a symmetric matrix $A$. Let $A_0 = A$, $A_{k+1} = R_kQ_k$ with $A_k = Q_kR_k$ the QR-decomposition of $A$. One can show that $Q_k \to Q$ and $R_k \to \Lambda$ where $\Lambda$ contains the eigenvalues of $A$ along its diagonal and $Q$ the eigenvectors in its columns.

share|cite|improve this answer
QR algorithm is available for all square matrices,not just for symmetric matrices. – y zh Sep 18 '12 at 13:41
@yzhao You are right, but IIRC, it needn't converge for a general $A$, so I restricted the above to symmetric $A$s? – martini Sep 18 '12 at 13:43

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.