Take the 2-minute tour ×
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.

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

share|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 zhao Sep 18 '12 at 12:16

1 Answer 1

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|improve this answer
    
QR algorithm is available for all square matrices,not just for symmetric matrices. –  y zhao 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

 
discard

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.