Skip to main content
Contents Dark Mode Prev Up Next \(\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\dimens}{\operatorname{dim}}
\DeclareMathOperator{\row}{\operatorname{row}}
\DeclareMathOperator{\col}{\operatorname{col}}
\newcommand{\im}{\operatorname{im}}
\newcommand{\nulls}{\operatorname{null}}
\newcommand{\minor}{\operatorname{minor}}
\newcommand{\spans}{\operatorname{span}}
\newcommand{\nullity}{\operatorname{nullity}}
\newcommand{\kers}{\operatorname{ker}}
\newcommand{\proj}{\operatorname{proj}}
\newcommand{\diag}{\operatorname{diag}}
\newcommand{\Tr}{\operatorname{Tr}}
\newcommand{\rank}{\operatorname{rank}}
\newcommand{\lt}{<}
\newcommand{\gt}{>}
\newcommand{\amp}{&}
\definecolor{fillinmathshade}{gray}{0.9}
\newcommand{\fillinmath}[1]{\mathchoice{\colorbox{fillinmathshade}{$\displaystyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\textstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptscriptstyle\phantom{\,#1\,}$}}}
\)
Section 4.4 \(QR\) factorization and least squares
Subsection QR factorization
Recall that a list of vectors is orthonormal when the vectors have length
\(1\) and are pairwise orthogonal. Also recall the notion of an upper triangular matrix from
Definition 2.5.22 .
Definition 4.4.1 .
Let
\(A\) be an
\(m \times n\) matrix with independent columns. A
QR factorization of
\(A\) is an
\(m \times n\) matrix
\(Q\text{,}\) with orthonormal columns, and an invertible upper triangular
\(n \times n\) matrix
\(R\text{,}\) with positive entries on its diagonal, so that
\(A = QR\text{.}\)
QR for least squares.
Normal equations are conceptually important, but \(QR\) is often a better computational method. If \(A=QR\) with \(Q\) having orthonormal columns, then
\begin{equation*}
\|A\mathbf{x}-\mathbf{b}\|=\|QR\mathbf{x}-\mathbf{b}\|.
\end{equation*}
Orthogonality reduces the least-squares problem to
\begin{equation*}
R\hat{\mathbf{x}}=Q^T\mathbf{b},
\end{equation*}
which is triangular and easier to solve accurately.
Activity 4.4.1 . Reading QR least-squares code.
The following code uses
\(QR\) to solve the same least-squares problem from the Unit 2 target activity.
A = np.array([
[1.0, 0.0],
[0.0, 1.0],
[1.0, 1.0],
])
b = np.array([1.0, 2.0, 4.0])
Q, R = np.linalg.qr(A)
x_qr = np.linalg.solve(R, Q.T @ b)
x_lstsq = np.linalg.lstsq(A, b, rcond=None)[0]
Q.T @ Q, x_qr, x_lstsq
What should
Q.T @ Q be close to?
Why does the code solve a system with
R instead of a system with
A?
Why should
x_qr and
x_lstsq agree?
Does this mean
\(A\mathbf{x}=\mathbf{b}\) has an exact solution?
Solution .
The matrix \(Q\) has orthonormal columns, so Q.T @ Q should be close to the identity matrix. The \(QR\) factorization rewrites the least-squares problem using \(A=QR\text{,}\) which leads to the triangular system
\begin{equation*}
R\hat{\mathbf{x}}=Q^T\mathbf{b}.
\end{equation*}
The vectors x_qr and x_lstsq should agree because they compute the same least-squares solution. This does not mean \(A\mathbf{x}=\mathbf{b}\) has an exact solution; it means the fitted vector \(A\hat{\mathbf{x}}\) is the closest reachable output.
Activity 4.4.2 .
Let
\begin{equation*}
Q = \begin{bmatrix} \frac{1}{\sqrt{3}} \amp \frac{1}{\sqrt{6}} \\ \frac{1}{\sqrt{3}} \amp -\frac{2}{\sqrt{6}} \\ \frac{1}{\sqrt{3}} \amp \frac{1}{\sqrt{6}} \end{bmatrix}\text{.}
\end{equation*}
Check that the columns are orthonormal and compute \(Q^TQ\text{.}\)
Solution .
Column 1:
\(\|\mathbf{q}_1\|^2 = \left(\frac{1}{\sqrt{3}}\right)^2 + \left(\frac{1}{\sqrt{3}}\right)^2 + \left(\frac{1}{\sqrt{3}}\right)^2 = \frac{1}{3} + \frac{1}{3} + \frac{1}{3} = 1\)
Column 2:
\(\|\mathbf{q}_2\|^2 = \left(\frac{1}{\sqrt{6}}\right)^2 + \left(-\frac{2}{\sqrt{6}}\right)^2 + \left(\frac{1}{\sqrt{6}}\right)^2 = 1\)
Orthogonality:
\begin{align*}
\mathbf{q}_1 \cdot \mathbf{q}_2 \amp = \frac{1}{\sqrt{3}} \cdot \frac{1}{\sqrt{6}} + \frac{1}{\sqrt{3}} \cdot \left(-\frac{2}{\sqrt{6}}\right) + \frac{1}{\sqrt{3}} \cdot \frac{1}{\sqrt{6}}\\
\amp = \frac{1}{\sqrt{18}} - \frac{2}{\sqrt{18}} + \frac{1}{\sqrt{18}} = 0
\end{align*}
Compute \(Q^TQ\text{:}\)
\begin{align*}
Q^TQ \amp = \begin{bmatrix}
\frac{1}{\sqrt{3}} \amp \frac{1}{\sqrt{3}} \amp \frac{1}{\sqrt{3}} \\
\frac{1}{\sqrt{6}} \amp -\frac{2}{\sqrt{6}} \amp \frac{1}{\sqrt{6}}
\end{bmatrix}
\begin{bmatrix}
\frac{1}{\sqrt{3}} \amp \frac{1}{\sqrt{6}} \\
\frac{1}{\sqrt{3}} \amp -\frac{2}{\sqrt{6}} \\
\frac{1}{\sqrt{3}} \amp \frac{1}{\sqrt{6}}
\end{bmatrix}\\
\amp = \begin{bmatrix}
\frac{1}{3} + \frac{1}{3} + \frac{1}{3} \amp \frac{1}{\sqrt{18}} - \frac{2}{\sqrt{18}} + \frac{1}{\sqrt{18}} \\
\frac{1}{\sqrt{18}} - \frac{2}{\sqrt{18}} + \frac{1}{\sqrt{18}} \amp \frac{1}{6} + \frac{4}{6} + \frac{1}{6}
\end{bmatrix}\\
\amp = \begin{bmatrix}
1 \amp 0 \\
0 \amp 1
\end{bmatrix} = I_2
\end{align*}
Activity 4.4.3 .
Solve the linear system \(R\mathbf{x} = \mathbf{b}\) where
\begin{equation*}
R = \begin{bmatrix} 4 \amp 2 \amp 7 \\ 0 \amp 3 \amp 5 \\ 0 \amp 0 \amp 2 \end{bmatrix} \quad\text{and}\quad \mathbf{b} = \begin{bmatrix} 30 \\ 21 \\ 6 \end{bmatrix}
\end{equation*}
Solution .
For an upper triangular matrix like \(R\text{,}\) we can solve the system using back-substitution. Starting with the last equation:
\begin{align*}
2x_3 \amp = 6\\
x_3 \amp = 3
\end{align*}
Now substitute this value into the second equation:
\begin{align*}
3x_2 + 5x_3 \amp = 21\\
3x_2 + 5(3) \amp = 21\\
3x_2 + 15 \amp = 21\\
3x_2 \amp = 6\\
x_2 \amp = 2
\end{align*}
Finally, substitute both known values into the first equation:
\begin{align*}
4x_1 + 2x_2 + 7x_3 \amp = 30\\
4x_1 + 2(2) + 7(3) \amp = 30\\
4x_1 + 4 + 21 \amp = 30\\
4x_1 \amp = 5\\
x_1 \amp = 1.25
\end{align*}
The solution is
\(\mathbf{x} = (1.25, 2, 3)\text{.}\)
The QR factorization is a matrix version of the
Gram-Schmidt orthogonalization process , which has many applications in many numerical algorithms.
Theorem 4.4.3 .
Every
\(m \times n\) matrix
\(A\) with linearly independent columns has a QR factorization
\(A = QR\text{.}\)
Why is this true?.
Let \(A = [\mathbf{c}_1 \mathbf{c}_2 \cdots \mathbf{c}_n]\) be the matrix with columns \(\mathbf{c}_1, \mathbf{c}_2, \ldots, \mathbf{c}_n\text{.}\) Apply Gram-Schmidt process to obtain orthogonal vectors \(\mathbf{f}_1, \mathbf{f}_2, \ldots, \mathbf{f}_n\) where: \(\mathbf{f}_1 = \mathbf{c}_1\) and
\begin{equation*}
\mathbf{f}_k = \mathbf{c}_k - \frac{\mathbf{c}_k \cdot \mathbf{f}_1}{\|\mathbf{f}_1\|^2}\mathbf{f}_1 - \frac{\mathbf{c}_k \cdot \mathbf{f}_2}{\|\mathbf{f}_2\|^2}\mathbf{f}_2 - \cdots - \frac{\mathbf{c}_k \cdot \mathbf{f}_{k-1}}{\|\mathbf{f}_{k-1}\|^2}\mathbf{f}_{k-1}
\end{equation*}
for \(k = 2, 3, \ldots, n\text{.}\)
Let
\(\mathbf{q}_k = \frac{\mathbf{f}_k}{\|\mathbf{f}_k\|}\) for each
\(k\text{.}\) Then
\(\mathbf{q}_1, \mathbf{q}_2, \ldots, \mathbf{q}_n\) are orthonormal vectors.
We can rewrite each column \(\mathbf{c}_k\) as a linear combination of the \(\mathbf{q}_i\text{:}\) \(\mathbf{c}_1 = \|\mathbf{f}_1\|\mathbf{q}_1\text{,}\)
\begin{align*}
\mathbf{c}_2 \amp = (\mathbf{c}_2 \cdot \mathbf{q}_1)\mathbf{q}_1 + \|\mathbf{f}_2\|\mathbf{q}_2\\
\mathbf{c}_3 \amp = (\mathbf{c}_3 \cdot \mathbf{q}_1)\mathbf{q}_1 + (\mathbf{c}_3 \cdot \mathbf{q}_2)\mathbf{q}_2 + \|\mathbf{f}_3\|\mathbf{q}_3
\end{align*}
and so on. This gives us the matrix factorization:
\begin{align*}
A \amp = [\mathbf{c}_1 \mathbf{c}_2 \cdots \mathbf{c}_n]\\
\amp = [\mathbf{q}_1 \mathbf{q}_2 \cdots \mathbf{q}_n]
\begin{bmatrix}
\|\mathbf{f}_1\| \amp \mathbf{c}_2 \cdot \mathbf{q}_1 \amp \mathbf{c}_3 \cdot \mathbf{q}_1 \amp \cdots \amp \mathbf{c}_n \cdot \mathbf{q}_1\\
0 \amp \|\mathbf{f}_2\| \amp \mathbf{c}_3 \cdot \mathbf{q}_2 \amp \cdots \amp \mathbf{c}_n \cdot \mathbf{q}_2\\
0 \amp 0 \amp \|\mathbf{f}_3\| \amp \cdots \amp \mathbf{c}_n \cdot \mathbf{q}_3\\
\vdots \amp \vdots \amp \vdots \amp \ddots \amp \vdots\\
0 \amp 0 \amp 0 \amp \cdots \amp \|\mathbf{f}_n\|
\end{bmatrix}
\end{align*}
So
\(A = QR\) where
\(Q = [\mathbf{q}_1 \mathbf{q}_2 \cdots \mathbf{q}_n]\) has orthonormal columns and
\(R\) is upper triangular with positive diagonal entries.
Activity 4.4.4 .
Consider the matrix
\begin{equation*}
A = \begin{bmatrix} 3 \amp 1 \\ 4 \amp 2 \end{bmatrix}\text{.}
\end{equation*}
Find its QR factorization.
Solution .
The columns of
\(A\) are
\(\mathbf{c}_1 = \begin{bmatrix} 3 \\ 4 \end{bmatrix}\) and
\(\mathbf{c}_2 = \begin{bmatrix} 1 \\ 2 \end{bmatrix}\text{.}\)
Set
\(\mathbf{f}_1 = \mathbf{c}_1 = \begin{bmatrix} 3 \\ 4 \end{bmatrix}\text{.}\) Then
\(\|\mathbf{f}_1\| = \sqrt{3^2 + 4^2} = 5\text{.}\)
Compute
\(\mathbf{q}_1 = \frac{\mathbf{f}_1}{\|\mathbf{f}_1\|} = \frac{1}{5}\begin{bmatrix} 3 \\ 4 \end{bmatrix} = \begin{bmatrix} \frac{3}{5} \\ \frac{4}{5} \end{bmatrix}\text{.}\)
Compute
\(\mathbf{f}_2 = \mathbf{c}_2 - \frac{\mathbf{c}_2 \cdot \mathbf{f}_1}{\|\mathbf{f}_1\|^2}\mathbf{f}_1\text{:}\)
\(\mathbf{c}_2 \cdot \mathbf{f}_1 = 1 \cdot 3 + 2 \cdot 4 = 11\)
\(\mathbf{f}_2 = \begin{bmatrix} 1 \\ 2 \end{bmatrix} - \frac{11}{25}\begin{bmatrix} 3 \\ 4 \end{bmatrix} = \begin{bmatrix} 1 - \frac{33}{25} \\ 2 - \frac{44}{25} \end{bmatrix} = \begin{bmatrix} \frac{25-33}{25} \\ \frac{50-44}{25} \end{bmatrix} = \begin{bmatrix} -\frac{8}{25} \\ \frac{6}{25} \end{bmatrix}\)
Compute
\(\|\mathbf{f}_2\| = \sqrt{(-\frac{8}{25})^2 + (\frac{6}{25})^2} = \sqrt{\frac{64+36}{625}} = \sqrt{\frac{100}{625}} = \frac{10}{25} = \frac{2}{5}\text{.}\)
Compute
\(\mathbf{q}_2 = \frac{\mathbf{f}_2}{\|\mathbf{f}_2\|} = \frac{1}{\frac{2}{5}}\begin{bmatrix} -\frac{8}{25} \\ \frac{6}{25} \end{bmatrix} = \frac{5}{2}\begin{bmatrix} -\frac{8}{25} \\ \frac{6}{25} \end{bmatrix} = \begin{bmatrix} -\frac{4}{5} \\ \frac{3}{5} \end{bmatrix}\text{.}\)
Calculate the entries of \(R\text{:}\)
\begin{align*}
r_{11} \amp = \|\mathbf{f}_1\| = 5\\
r_{12} \amp = \mathbf{c}_2 \cdot \mathbf{q}_1 = 1 \cdot \frac{3}{5} + 2 \cdot \frac{4}{5} = \frac{3+8}{5} = \frac{11}{5}\\
r_{22} \amp = \|\mathbf{f}_2\| = \frac{2}{5}
\end{align*}
Therefore, \(A = QR\) where:
\begin{equation*}
Q = \begin{bmatrix} \frac{3}{5} \amp -\frac{4}{5} \\ \frac{4}{5} \amp \frac{3}{5} \end{bmatrix} \quad
R = \begin{bmatrix} 5 \amp \frac{11}{5} \\ 0 \amp \frac{2}{5} \end{bmatrix}
\end{equation*}
Activity 4.4.5 .
Find the QR factorization of the matrix
\begin{equation*}
A = \begin{bmatrix} 6 \amp 2 \\ 0 \amp 3 \end{bmatrix}\text{.}
\end{equation*}
Solution .
The columns of
\(A\) are
\(\mathbf{c}_1 = \begin{bmatrix} 6 \\ 0 \end{bmatrix}\) and
\(\mathbf{c}_2 = \begin{bmatrix} 2 \\ 3 \end{bmatrix}\text{.}\)
\(\mathbf{f}_1 = \mathbf{c}_1 = \begin{bmatrix} 6 \\ 0 \end{bmatrix}\text{,}\) \(\|\mathbf{f}_1\| = 6\)
\(\mathbf{q}_1 = \frac{\mathbf{f}_1}{\|\mathbf{f}_1\|} = \begin{bmatrix} 1 \\ 0 \end{bmatrix}\)
\(\mathbf{c}_2 \cdot \mathbf{q}_1 = 2 \cdot 1 + 3 \cdot 0 = 2\)
\(\mathbf{f}_2 = \mathbf{c}_2 - (\mathbf{c}_2 \cdot \mathbf{q}_1)\mathbf{q}_1 = \begin{bmatrix} 2 \\ 3 \end{bmatrix} - 2\begin{bmatrix} 1 \\ 0 \end{bmatrix} = \begin{bmatrix} 0 \\ 3 \end{bmatrix}\)
\(\mathbf{q}_2 = \frac{\mathbf{f}_2}{\|\mathbf{f}_2\|} = \begin{bmatrix} 0 \\ 1 \end{bmatrix}\)
Therefore, \(A = QR\) where:
\begin{equation*}
Q = \begin{bmatrix} 1 \amp 0 \\ 0 \amp 1 \end{bmatrix} \quad
R = \begin{bmatrix} 6 \amp 2 \\ 0 \amp 3 \end{bmatrix}
\end{equation*}
Theorem 4.4.4 .
Every square, invertible matrix
\(A\) can be written as
\(A = QR\text{,}\) where
\(Q\) is an orthogonal matrix, and
\(R\) is an upper triangular matrix with positive diagonal entries.
