Science Fair Project Encyclopedia

Science Fair Project Encyclopedia Contents Page

QR decomposition

In linear algebra, the QR decomposition of a matrix $A$ is a factorization expressing $A$ as

A = Q R

where $Q$ is an orthogonal matrix ( $Q Q T = I$ ), and $R$ is an upper triangular matrix.

The QR decomposition is often used to solve the linear least squares problem. The QR decomposition is also the basis for a particular eigenvalue algorithm, the QR algorithm.

There are several methods for actually computing the QR decomposition, such as by means of Givens rotations, Householder transformations, or the Gram-Schmidt decomposition. Each has a number of advantages and disadvantages. (The matrices Q and R are not uniquely determined, so different methods may produce different decompositions.)

Contents

1 Computing QR by means of Gram-Schmidt

1.1 Example

2 Computing QR by means of Householder reflections

2.1 Example

Computing QR by means of Gram-Schmidt

Recall the Gram-Schmidt method, with the vectors to be considered in the process as columns of the matrix $A=(\mathbf{a}_1| \cdots|\mathbf{a}_n)$ . Then

$\mathbf{u}_1 = \mathbf{a}_1, \qquad\mathbf{e}_1 = {\mathbf{u}_1 \over ||\mathbf{u}_1||}$

$\mathbf{u}_2 = \mathbf{a}_2-\mathrm{proj}_{\mathbf{e}_1}\,\mathbf{a}_2, \qquad\mathbf{e}_2 = {\mathbf{u}_2 \over ||\mathbf{u}_2||}$

$\mathbf{u}_3 = \mathbf{a}_3-\mathrm{proj}_{\mathbf{e}_1}\,\mathbf{a}_3-\mathrm{proj}_{\mathbf{e}_2}\,\mathbf{a}_3, \qquad\mathbf{e}_3 = {\mathbf{u}_3 \over ||\mathbf{u}_3||}$

$\vdots$

$\mathbf{u}_k = \mathbf{a}_k-\sum_{j=1}^{k-1}\mathrm{proj}_{\mathbf{e}_j}\,\mathbf{a}_k,\qquad\mathbf{e}_k = {\mathbf{u}_k\over||\mathbf{u}_k||}$

Naturally then, we rearrange the equations so the a_is are the subject, to get the following

$\mathbf{a}_1 = \mathbf{e}_1||\mathbf{u}_1||$

$\mathbf{a}_2 = \mathrm{proj}_{\mathbf{e}_1}\,\mathbf{a}_2+\mathbf{e}_2||\mathbf{u}_2||$

$\mathbf{a}_3 = \mathrm{proj}_{\mathbf{e}_1}\,\mathbf{a}_3+\mathrm{proj}_{\mathbf{e}_2}\,\mathbf{a}_3+\mathbf{e}_3||\mathbf{u}_3||$

$\vdots$

$\mathbf{a}_k = \sum_{j=1}^{k-1}\mathrm{proj}_{\mathbf{e}_j}\,\mathbf{a}_k+\mathbf{e}_k||\mathbf{u}_k||$

Each of these projections of the vectors $\mathbf{a}_i$ onto one of these $e j$ are merely the inner product of the two, since the vectors are normed.

Now these equations can be written in matrix form, viz.,

$\left(\mathbf{e}_1\left|\ldots\right|\mathbf{e}_n\right) \begin{pmatrix} ||\mathbf{u}_1|| & \langle\mathbf{e}_1,\mathbf{a}_2\rangle & \langle\mathbf{e}_1,\mathbf{a}_3\rangle & \ldots \\ 0 & ||\mathbf{u}_2|| & \langle\mathbf{e}_2,\mathbf{a}_3\rangle & \ldots \\ 0 & 0 & ||\mathbf{u}_3|| & \ldots \\ \vdots & \vdots & \vdots & \ddots \end{pmatrix}$

But the product of each row and column of the matrices above give us a respective column of A that we started with, and together, they give us the matrix A, so we have factorized A into an orthogonal matrix Q (the matrix of e_ks), via Gram Schmidt, and the obvious upper triangular matrix as a remainder R.

Alternatively, $\begin{matrix} R \end{matrix}$ can be calculated as follows:

Recall that $\begin{matrix}Q\end{matrix} = \left(\mathbf{e}_1\left|\ldots\right|\mathbf{e}_n\right).$ Then, we have

$\begin{matrix} R = Q^{T}A = \end{matrix} \begin{pmatrix} \langle\mathbf{e}_1,\mathbf{a}_1\rangle & \langle\mathbf{e}_1,\mathbf{a}_2\rangle & \langle\mathbf{e}_1,\mathbf{a}_3\rangle & \ldots \\ 0 & \langle\mathbf{e}_2,\mathbf{a}_2\rangle & \langle\mathbf{e}_2,\mathbf{a}_3\rangle & \ldots \\ 0 & 0 & \langle\mathbf{e}_3,\mathbf{a}_3\rangle & \ldots \\ \vdots & \vdots & \vdots & \ddots \end{pmatrix}.$

Note that $\langle\mathbf{e}_j,\mathbf{a}_j\rangle = ||\mathbf{u}_j||,$ $\langle\mathbf{e}_j,\mathbf{a}_k\rangle = 0 \mathrm{~~for~~} j > k,$ and $Q Q T = I$ , so $Q T = Q - 1$ .

Example

Consider the decomposition of

$A = \begin{pmatrix} 12 & -51 & 4 \\ 6 & 167 & -68 \\ -4 & 24 & -41 \end{pmatrix} .$

Recall the orthogonal matrix $Q$ such that

$\begin{matrix} Q\,Q^{T} = I. \end{matrix}$

Then, we can calculate $Q$ by means of Gram-Schmidt as follows:

$U = \begin{pmatrix} \mathbf u_1 & \mathbf u_2 & \mathbf u_3 \end{pmatrix} = \begin{pmatrix} 12 & -51 & 4 \\ 6 & 167 & -68 \\ -4 & 24 & -41 \end{pmatrix};$

$Q = \begin{pmatrix} \frac{\mathbf u_1}{||\mathbf u_1||} & \frac{\mathbf u_2}{||\mathbf u_2||} & \frac{\mathbf u_3}{||\mathbf u_3||} \end{pmatrix} = \begin{pmatrix} 6/7 & -69/175 & -58/175 \\ 3/7 & 158/175 & 6/175 \\ -2/7 & 6/35 & -33/35 \end{pmatrix};$

Thus, we have

$\begin{matrix} A = Q\,Q^{T}A = Q R; \end{matrix}$

$\begin{matrix} R = Q^{T}A = \end{matrix} \begin{pmatrix} 14 & 21 & -14 \\ 0 & 175 & -70 \\ 0 & 0 & 35 \end{pmatrix}.$

Considering numerical errors of finite precision operation in MATLAB, we have that

$\begin{matrix} Q = \end{matrix} \begin{pmatrix} 0.857142857142857 & -0.394285714285714 & -0.331428571428571 \\ 0.428571428571429 & 0.902857142857143 & 0.034285714285714 \\ -0.285714285714286 & 0.171428571428571 & -0.942857142857143 \end{pmatrix};$

$\begin{matrix} R = \end{matrix} \begin{pmatrix} 14 & 21 & -14 \\ 1.11022302462516 \times 10^{-016} & 175 & -70 \\ -1.77635683940025 \times 10^{-015} & -5.32907051820075 \times 10^{-014} & 35 \end{pmatrix}.$

Computing QR by means of Householder reflections

A Householder reflection (or Householder transformation) is a transformation that takes a vector and reflects it about some plane. We can use this property to calculate the QR factorization of a matrix.

Q can be used to reflect a vector in such a way that all coordinates but one disappear. Let x be an arbitrary m-dimensional column vector of length |α| (for numerical reasons α should get the same sign as the first coordinate of x).

Then, where e₁ is the vector (1,0,...,0)^T, and || || the euclidean norm, set

$\mathbf{u} = \mathbf{x} - \alpha\mathbf{e}_1,$

$\mathbf{v} = {\mathbf{u}\over||\mathbf{u}||},$

$Q = I - 2 \mathbf{v}\mathbf{v}^T.$ .

$Q$ is a Householder matrix and

$Qx = (\alpha\ , 0, \cdots, 0)^T$ .

This can be used to gradually transform an m-by-n matrix A to upper triangular form. First, we multiply A with the Householder matrix Q₁ we obtain when we choose the first matrix column for x. This results in a matrix QA with zeros in the left column (except for the first line).

$Q_1A = \begin{bmatrix} \alpha_1&\star&\dots&\star\\ 0 & & & \\ \vdots & & A' & \\ 0 & & & \end{bmatrix}$

This can be repeated for A' resulting in a Housholder matrix Q'₂. Note that Q'₂ is smaller than Q₁. Since we want it really to operate on Q₁A instead of A' we need to expand it to the upper left, filling in a 1, or in general:

$Q_k = \begin{pmatrix} I_{k-1} & 0\\ 0 & Q_k'\end{pmatrix}$

After $t$ iterations of this process, $t = m i n (m - 1, n)$ ,

$R = Q_t \cdots Q_2Q_1A$

is a upper triangular matrix. So, with

$Q = Q_1Q_2 \cdots Q_t$

$A = Q R$ is a QR decomposition of $A$ .

This method has greater numerical stability than using the Gram-Schmidt method above. .

Example

Let us calculate the decomposition of

$A = \begin{pmatrix} 12 & -51 & 4 \\ 6 & 167 & -68 \\ -4 & 24 & -41 \end{pmatrix}$

We need to find a reflection that takes the vector $a 1 = (12,6, - 4) T$ to $\| \;\mathrm{a}\| \;\mathrm{e}_1 = (14, 0, 0)^T$ .

Now, $u = ( - 2,6, - 4) T$ and $v = 14^{-{1 \over 2}}(-1, 3, -2)^T$ , and then

$Q_1 = I - {2 \over 14} \begin{pmatrix} -1 \\ 3 \\ -2 \end{pmatrix}\begin{pmatrix} -1 & 3 & -2 \end{pmatrix}$

$= I - {1 \over 7}\begin{pmatrix} 1 & -3 & 2 \\ -3 & 9 & -6 \\ 2 & -6 & 4 \end{pmatrix} =\begin{pmatrix} 6/7 & 3/7 & -2/7 \\ 3/7 &-2/7 & 6/7 \\ -2/7 & 6/7 & 3/7 \\ \end{pmatrix}$

Observe now:

$Q_1A = \begin{pmatrix} 14 & 21 & -14 \\ 0 & -49 & -14 \\ 0 & 168 & -77 \end{pmatrix}$

So we already have almost a triangular matrix. We only need to zero the (3, 2) entry.

Take the (1, 1) minor, and then apply the process again to

$A' = M_{11} = \begin{pmatrix} -49 & -14 \\ 168 & -77 \end{pmatrix}$

By the same method as above, we obtain the matrix of the Householder transformation to be,

$Q_2 = \begin{pmatrix} 1 & 0 & 0 \\ 0 & -7/25 & 24/25 \\ 0 & 24/25 & 7/25 \end{pmatrix}$

after performing a direct sum with 1 to make sure the next step in the process works properly.

Now, we find

$Q=Q_1Q_2=\begin{pmatrix} 6/7 & -69/175 & 58/175 \\ 3/7 & 158/175 & -6/175 \\ -2/7 & 6/35 & 33/35 \end{pmatrix}$

$R=Q^\top A=\begin{pmatrix} 14 & 21 & -14 \\ 0 & 175 & -70 \\ 0 & 0 & -35 \end{pmatrix}$

The matrix Q is orthogonal and R is upper triangular, so A = QR is the required QR-decomposition.

Categories: Matrix theory

Science Fair Project Encyclopedia Contents Page

03-10-2013 05:06:04
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details

All Science Fair Projects