Definition 6.3.1.
The QR factorization of a matrix \(A\) is given by
\begin{equation*}
A = QR
\end{equation*}
where \(Q\) is an orthogonal matrix and \(R\) is an upper triangular matrix.
Section 6.3 QR Factorization
The QR factorization of a matrix is a decomposition of a matrix into the product of an orthogonal matrix and an upper triangular matrix. This factorization is useful in solving systems of linear equations, computing eigenvalues, and in numerical linear algebra.
Subsection 6.3.1 QR Factorization Algorithm
The QR-factorization can be performed using the Gram-Schmidt orthogonalization seen in Subsection 4.4.4. We will first show this with an example and then explain why this works.
Example 6.3.2.
Perform Gram-Schmidt Orthogonalization to find an orthonormal set of vectors of the columns of
\begin{equation*}
A = \begin{bmatrix} -9 \amp 4 \amp 7 \\ -18 \amp 15 \amp -28 \\ 6 \amp 2 \amp 49 \\ \end{bmatrix}
\end{equation*}
and then use the resulting matrix \(Q\) to find \(R\) using
\begin{equation*}
R = Q^{\intercal} A
\end{equation*}
Solution.
Let \(\boldsymbol{a}_j\) be the columns of \(A\) and we will call the resulting orthogonal vectors as \(\boldsymbol{q}_j\text{.}\)
\begin{equation*}
\boldsymbol{q}_1 = \frac{\boldsymbol{a}_1}{||\boldsymbol{a}_1||} = \frac{1}{\sqrt{9^2+18^2+6^2}} \begin{bmatrix} -9 \\ -18 \\ 6 \end{bmatrix} = \begin{bmatrix} -3/7 \\ -6/7 \\ 2/7 \end{bmatrix}
\end{equation*}
For the second vector,
\begin{equation*}
\begin{aligned} \boldsymbol{u}_2 \amp = \boldsymbol{a}_2 - \langle \boldsymbol{q}_1, \boldsymbol{a}_2 \rangle \boldsymbol{q}_1\\ \amp = \begin{bmatrix} 4 \\ 15 \\ 2 \end{bmatrix} - (-14) \begin{bmatrix} -3/7 \\ -6/7 \\ 2/7 \end{bmatrix} = \begin{bmatrix} 4 \\ 15 \\ 2 \end{bmatrix} + \begin{bmatrix} -6 \\ -12 \\ 4 \end{bmatrix} = \begin{bmatrix} -2 \\ 3 \\ 6 \end{bmatrix} \end{aligned}
\end{equation*}
and then this vectors is normalized with
\begin{equation*}
\boldsymbol{q}_2 = \frac{1}{||\boldsymbol{u}_2||} \boldsymbol{u_2} = \frac{1}{\sqrt{2^2+3^2+6^2}} \begin{bmatrix} -2 \\ 3 \\ 6 \end{bmatrix} = \frac{1}{7} \begin{bmatrix} -2 \\ 3 \\ 6 \end{bmatrix} = \begin{bmatrix} -2/7 \\ 3/7 \\ 6/7 \end{bmatrix}
\end{equation*}
Lastly, the third column of \(Q\) can be found with
\begin{equation*}
\begin{aligned} \boldsymbol{u}_3 \amp = \boldsymbol{a}_3 - \langle \boldsymbol{q}_2, \boldsymbol{a}_3 \rangle \boldsymbol{q}_2 - \langle \boldsymbol{q}_1, \boldsymbol{a}_3 \rangle \boldsymbol{q}_1 \\ \amp = \begin{bmatrix} 7 \\ -28 \\ 49 \end{bmatrix} - 28 \begin{bmatrix} -2/7 \\ 3/7 \\ 6/7 \end{bmatrix} - 35 \begin{bmatrix} -3/7 \\ -6/7 \\ 2/7 \end{bmatrix} \\ \amp = \begin{bmatrix} 7 \\ -28 \\ 49 \end{bmatrix} + \begin{bmatrix} 8 \\ -12 \\ -24 \end{bmatrix} + \begin{bmatrix} 15 \\ 30 \\ -10 \end{bmatrix} = \begin{bmatrix} 30 \\ -10 \\ 15 \end{bmatrix} \end{aligned}
\end{equation*}
and lastly, we normalize this vector as
\begin{equation*}
\boldsymbol{q3} = \frac{1}{||\boldsymbol{u}_2||} \boldsymbol{u_2} = \frac{1}{\sqrt{30^2+10^2+15^2}} \begin{bmatrix} 30 \\ -10 \\ 15 \end{bmatrix} = \frac{1}{35} \begin{bmatrix} 30 \\ -10 \\ 15 \end{bmatrix} = \begin{bmatrix} 6/7 \\ -2/7 \\ 3/7 \end{bmatrix}
\end{equation*}
and thus the matrix \(Q\) is the matrix with these three vectors or
\begin{equation*}
Q = \begin{bmatrix} -3/7 \amp -2/7 \amp 6/7 \\ -6/7 \amp 3/7 \amp -2/7 \\ 2/7 \amp 6/7 \amp 3/7 \end{bmatrix}
\end{equation*}
Lastly, we find \(R\) with
\begin{equation*}
\begin{aligned} R \amp = Q^{\intercal} A \\ \amp = \begin{bmatrix} -3/7 \amp -6/7 \amp 2/7 \\ -2/7 \amp 3/7 \amp 6/7 \\ 6/7 \amp -2/7 \amp 3/7 \end{bmatrix} \begin{bmatrix} -9 \amp 4 \amp 7 \\ -18 \amp 15 \amp -28 \\ 6 \amp 2 \amp 49 \end{bmatrix} \\ \amp = \begin{bmatrix} 21 \amp -14 \amp 35 \\ 0 \amp 7 \amp 28 \\ 0 \amp 0 \amp 35 \\ \end{bmatrix}
\end{aligned}
\end{equation*}
A natural question to ask is why does this work? Why does the Gram-Schmidt process give us the QR factorization? The answer is that the Gram-Schmidt process gives us an orthonormal basis for the column space of \(A\) and thus the matrix \(Q\) is an orthogonal matrix. Then, the matrix \(R\) is the change of basis matrix from the standard basis to the orthonormal basis given by the columns of \(Q\text{.}\)
Examining the result of \(R = Q^{\intercal}A \text{,}\) the matrix \(Q^{\intercal}\) projects the columns of \(A\) onto \(Q\text{.}\) Because \(Q\) is constructed as the
Subsection 6.3.2 Solving Linear Systems with QR factoring.
We can solving linear systems with the QR factorization and is often done if the original matrix is difficult to solve (Section where this is explained??). Let’s look the example in Subsection 6.1.4.
-
Write \(A = QR\)
-
Solve \(R\boldsymbol{x} = Q^{\intercal}\boldsymbol{b}\text{.}\) Note that \(R\) is upper triangular and thus this can be solved with back substitution.
Example 6.3.3.
Solve the linear system \(A\boldsymbol{x}= \boldsymbol{b}\) using the \(QR\)-decomposition where
\begin{equation*}
A = \begin{bmatrix}
3 \amp -2 \amp 1 \\ 6 \amp 0 \amp 4 \\ -6 \amp -8 \amp -7
\end{bmatrix} \qquad \boldsymbol{b} = \begin{bmatrix}
14 \\ 22 \\ -9
\end{bmatrix}
\end{equation*}
Solution.
First, we need to find the factorization. We can follow the same steps using Gram-Schmidt Orthogonalization as in Example 6.3.2, however, generally the resulting elements of \(Q\) are not rational, so we will resort to software to do this. Using Matlab or Julia, the result in
\begin{equation*}
\begin{aligned}
Q \amp = \begin{bmatrix}
-0.333333 \amp -0.522976 \amp 0.784465 \\
-0.666667 \amp -0.457604 \amp -0.588348 \\
0.666667 \amp -0.719092 \amp -0.196116 \\
\end{bmatrix} \\
R \amp = \begin{bmatrix}
-9.0 \amp -4.66667 \amp -7.66667 \\
0.0 \amp 6.79869 \amp 2.68025 \\
0.0 \amp 0.0 \amp -0.196116 \\
\end{bmatrix}
\end{aligned}
\end{equation*}
and this just shows the first 5 or so digits of the two matrices.
The next step is to find \(Q^{\intercal} \boldsymbol{b}\) or
\begin{equation*}
Q^{\intercal} \boldsymbol{b}
= \begin{bmatrix}
-25.33333333333333 \\
-10.917131522692245 \\
-0.19611613513818504 \\
\end{bmatrix}
\end{equation*}
And lastly, we solve \(R\boldsymbol{x} = Q^{\intercal} \boldsymbol{b}\text{.}\) This is done with back-substitution. The result of this is:
\begin{equation*}
\boldsymbol{x} = \begin{bmatrix}
2.999999999999997 \\
-2.000000000000001 \\
1.0000000000000033 \\
\end{bmatrix}
\end{equation*}
which is close to the answer found in Subsection 6.1.4, the difference being that here we used floating-point numbers which have round off errors.
