Objectives: Topics
-
The Gram–Schmidt Process
-
The QR decomposition
Print preview
Section 6.4 Gram–Schmidt and QR Decomposition
Handout 6.4 Gram–Schmidt and QR Decomposition
Objectives: Goals
-
Apply Gram–Schmidt and QR decomposition to construct orthogonal or orthonormal bases.
-
Compute the QR factorization of a matrix.
Motivating Question
Identify an orthogonal basis for the subspace spanned by:
\begin{equation*}
\vec x_1=\begin{bmatrix}1\\1\\1\\1\end{bmatrix},\quad
\vec x_2=\begin{bmatrix}0\\1\\1\\1\end{bmatrix},\quad
\vec x_3=\begin{bmatrix}0\\0\\1\\1\end{bmatrix}.
\end{equation*}
Theorem 6.44 The Gram–Schmidt Process.
Given a basis \(\{\vec x_1,\dots,\vec x_p\}\) for a subspace \(W \subseteq \mathbb{R}^n\text{,}\) define:
\begin{align*}
\vec v_1 \amp =\vec x_1,\\
\vec v_2 \amp = \vec x_2 - \frac{\vec x_2\cdot\vec v_1}{\vec v_1\cdot\vec v_1}\vec v_1,\\
\vec v_3 \amp = \vec x_3 - \frac{\vec x_3\cdot\vec v_1}{\vec v_1\cdot\vec v_1}\vec v_1
- \frac{\vec x_3\cdot\vec v_2}{\vec v_2\cdot\vec v_2}\vec v_2,\\
\amp \vdots\\
\vec v_p \amp = \vec x_p - \frac{\vec x_p\cdot\vec v_1}{\vec v_1\cdot\vec v_1}\vec v_1 - \cdots - \frac{\vec x_p \cdot \vec v_{p-1}}{\vec v_{p-1} \cdot \vec v_{p-1}}\vec v_{p-1}.
\end{align*}
Then \(\{\vec v_1,\dots,\vec v_p\}\) is an orthogonal basis for \(W\text{.}\) Additionally,
\begin{equation*}
W_k = \Span\left\{\vec v_1, \dots, \vec v_k\right\} = \Span\left\{\vec x_1, \dots, \vec x_k\right\} \qquad \text{for $1 \leq k \leq p$}\text{.}
\end{equation*}
Thus, we see that each vector \(\vec v_k\) is formed by starting with \(\vec x_k\) and then removing the orthogonal projection of \(\vec x_k\) onto \(W_{k-1}\text{;}\) that is,
\begin{equation*}
\vec v_k = \vec x_k - \proj_{W_{k-1}}\vec x_k = \vec x_k - \proj_{\vec v_1}\vec x_k - \cdots - \proj_{\vec v_{k-1}}\vec x_k\text{.}
\end{equation*}
Vectors \(\vec x_1,\vec x_2,\vec x_3\) are used to produce orthogonal vectors \(\vec v_1,\vec v_2,\vec v_3\) via subtraction of projections.
Gram–Schmidt successively removes the components of each vector in the span of earlier ones.
Example 6.45.
Let \(W = \Span\left\{\begin{bmatrix} 3 \\ 0 \\ -1 \end{bmatrix}, \begin{bmatrix} 8 \\ 5 \\ -6 \end{bmatrix} \right\}\text{.}\) Find an orthogonal basis for \(W\text{.}\)
Solution.
Let \(\vec x_1 = \begin{bmatrix} 3 \\ 0 \\ -1 \end{bmatrix}\) and \(\vec x_2 = \begin{bmatrix} 8 \\ 5 \\ -6 \end{bmatrix}\text{.}\) Using Theorem 6.44, we have that
\begin{align*}
\vec v_1 \amp = \vec x_1 = \begin{bmatrix} 3 \\ 0 \\ -1 \end{bmatrix}
\end{align*}
and
\begin{align*}
\vec v_2 \amp = \vec x_2 - \proj_{\vec v_1}\vec x_2 \\
\amp = \begin{bmatrix} 8 \\ 5 \\ -6 \end{bmatrix} - \dfrac{8(3) + 5(0) -6(-1)}{3^2 + 0^2 + (-1)^2}\begin{bmatrix} 3 \\ 0 \\ -1 \end{bmatrix}\\
\amp = \begin{bmatrix}8 \\ 5 \\ -6 \end{bmatrix} - 3\begin{bmatrix} 3 \\ 0 \\ -1 \end{bmatrix}\\
\amp = \begin{bmatrix} -1 \\ 5 \\ -3 \end{bmatrix}
\end{align*}
Note that \(\vec v_1, \vec v_2 \in W\) and \(\vec v_1 \cdot \vec v_2 = 0\text{,}\) so \(\left\{\vec v_1, \vec v_2\right\}\) is an orthogonal basis for \(W\text{.}\)
Example 6.46.
The vectors below span a subspace \(W\subseteq\mathbb{R}^4\text{.}\) Construct an orthogonal basis for \(W\text{.}\)
\begin{equation*}
\vec x_1=\begin{bmatrix}1\\1\\1\\1\end{bmatrix},\quad
\vec x_2=\begin{bmatrix}0\\1\\1\\1\end{bmatrix},\quad
\vec x_3=\begin{bmatrix}0\\0\\1\\1\end{bmatrix}.
\end{equation*}
Solution.
First, note that
\begin{align*}
\vec v_1 \amp = \vec x_1 = \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix},
\end{align*}
Then, we have that
\begin{align*}
\vec v_2 \amp = \vec x_2 - \proj_{\vec v_1}\vec x_2\\
\amp = \begin{bmatrix} 0 \\ 1 \\ 1 \\ 1 \end{bmatrix} - \dfrac{0(1) + 1(1) + 1(1) + 1(1)}{1^2 + 1^2 + 1^2 + 1^2}\begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix}\\
\amp = \begin{bmatrix} \frac{-3}{4} \\ \frac{1}{4} \\ \frac{1}{4} \\ \frac{1}{4} \end{bmatrix}\\
\amp = \dfrac{1}{4}\begin{bmatrix}-3 \\ 1 \\ 1 \\ 1 \end{bmatrix}.
\end{align*}
Note that scaling \(\vec v_2\) will not change its orthogonality with \(\vec v_1\text{.}\) So, in order to make future projections easier, let’s scale the current \(\vec v_2\) by 4 to obtain
\begin{equation*}
\vec v_2' = 4\vec v_2 = \begin{bmatrix} -3 \\ 1 \\ 1 \\ 1 \end{bmatrix}\text{,}
\end{equation*}
which is still orthogonal to \(\vec v_1\text{.}\) Next, we have that
\begin{align*}
\vec v_3 \amp = \vec x_3 - \proj_{\vec v_1}\vec x_3 - \proj_{\vec v_2'}\vec x_3\\
\amp = \begin{bmatrix} 0 \\ 0 \\ 1 \\ 1 \end{bmatrix} - \dfrac{2}{4}\begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix} - \dfrac{0(-3) + 0(1) + 1(1) + 1(1)}{(-3)^2 + 1^2 + 1^2 + 1^2}\begin{bmatrix}-3 \\ 1 \\ 1 \\ 1 \end{bmatrix} \\
\amp = \begin{bmatrix} 0 \\ -\frac{2}{3} \\ \frac{1}{3} \\ \frac{1}{3} \end{bmatrix}\\
\amp = \dfrac{1}{3}\begin{bmatrix} 0 \\ -2 \\ 1 \\ 1 \end{bmatrix}
\end{align*}
Again, we can scale \(\vec v_3\) to obtain the a nicer vector \(\vec v_3'\) which is still orthogonal to \(\vec v_1\) and \(\vec v_2\text{:}\)
\begin{equation*}
\vec v_3' = 3\vec v_3 = \begin{bmatrix} 0 \\ -2 \\ 1 \\ 1 \end{bmatrix}\text{.}
\end{equation*}
Thus,
\begin{equation*}
\mathcal{B} = \left\{\vec v_1, \vec v_2', \vec v_3'\right\} = \left\{\begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix}, \begin{bmatrix} -3 \\ 1 \\ 1\\ 1 \end{bmatrix}, \begin{bmatrix} 0 \\ -2 \\ 1\\ 1 \end{bmatrix}\right\}
\end{equation*}
is an orthogonal basis for \(W\text{.}\) Note that there was nothing forcing us to start the process with \(\vec v_1 = \vec x_1\text{.}\) If instead we started with \(\vec v_1 = \vec x_3\) and then used \(\vec x_2\) followed by \(\vec x_1\text{,}\) we would have obtained the following orthogonal basis for \(W\)
\begin{equation*}
\mathcal{C} = \left\{\begin{bmatrix} 0 \\ 0 \\ 1 \\ 1 \end{bmatrix}, \begin{bmatrix} 0 \\ 1 \\ 0 \\ 0 \end{bmatrix}, \begin{bmatrix} 1 \\ 0 \\ 0 \\ 0 \end{bmatrix}\right\}\text{,}
\end{equation*}
which is a "nicer" orthogonal basis for \(W\text{,}\) especially if planning to use Theorem 6.23.
Theorem 6.47 QR Factorization.
If \(A\) is an \(m\times n\) matrix with linearly independent columns, then \(A\) has a QR factorization:
\begin{equation*}
A = QR,
\end{equation*}
where:
-
\(Q\) is \(m\times n\) whose columns are an orthonormal basis for \(\Col(A)\text{,}\)
-
\(R\) is \(n\times n\text{,}\) upper triangular, with positive entries on its diagonal, and the length of the \(j^\text{th}\) column of \(R\) is equal to the length of the \(j^\text{th}\) column of \(A\text{.}\)
Example 6.48.
Compute the QR decomposition of:
\begin{equation*}
A=\begin{bmatrix}
3 \amp -2\\
2 \amp 3\\
0 \amp 1
\end{bmatrix}.
\end{equation*}
Solution.
Note that the columns of \(A\) form an orthogonal basis for \(\Col(A)\) since. Therefore, we simply need to normalize them to get an orthonormal basis for \(\Col(A)\text{.}\) It follows that
\begin{equation*}
\left\{\dfrac{1}{\sqrt{13}}\begin{bmatrix} 3 \\ 2 \\ 0 \end{bmatrix}, \dfrac{1}{\sqrt{14}}\begin{bmatrix}-2 \\ 3 \\ 1 \end{bmatrix}\right\}
\end{equation*}
is an orthonormal basis for \(\Col(A)\text{.}\) We let these vectors be the columns of \(Q\text{,}\) so
\begin{equation*}
Q = \begin{bmatrix} \frac{3}{\sqrt{13}} \amp \frac{-2}{\sqrt{14}} \\ \frac{2}{\sqrt{13}} \amp \frac{3}{\sqrt{14}} \\ 0 \amp \frac{1}{\sqrt{14}} \end{bmatrix}\text{.}
\end{equation*}
To find \(R\text{,}\) we calculate \(R = Q^TA\text{.}\) Note that
\begin{align*}
R \amp = Q^TA\\
\amp = \begin{bmatrix} \frac{3}{\sqrt{13}} \amp \frac{2}{\sqrt{13}} \amp 0 \\ \frac{-2}{\sqrt{14}} \amp \frac{3}{\sqrt{14}} \amp \frac{1}{\sqrt{14}} \end{bmatrix} \begin{bmatrix} 3 \amp -2 \\ 2 \amp 3 \\ 0 \amp 1 \end{bmatrix}\\
\amp = \begin{bmatrix} \frac{9 + 4 + 0}{\sqrt{13}} \amp \frac{-6 + 6 + 0}{\sqrt{13}} \\ \frac{-6 + 6 + 0}{\sqrt{14}} \amp \frac{4 + 9 + 1}{\sqrt{14}} \end{bmatrix}\\
\amp = \begin{bmatrix} \frac{13}{\sqrt{13}} \amp 0 \\ 0 \amp \frac{14}{\sqrt{14}} \end{bmatrix}\\
\amp = \begin{bmatrix} \sqrt{13} \amp 0 \\ 0 \amp \sqrt{14} \end{bmatrix}.
\end{align*}
Note that \(R\) has all the desired properties: it is \(2 \times 2\text{,}\) upper triangular, has positive entries on the diagonal, and \(\|\vec a_1\| = \|\vec r_1\|\) and \(\|\vec a_2\| = \|\vec r_2\|\) where \(\vec a_i\) and \(\vec r_i\) are the columns of \(A\) and \(R\text{,}\) respectively.
Example 6.49.
Compute the QR decomposition of:
\begin{equation*}
A=\begin{bmatrix}
1 \amp 0 \amp 0 \\
1 \amp 1 \amp 0 \\
1 \amp 1 \amp 1 \\
1 \amp 1 \amp 1
\end{bmatrix}.
\end{equation*}
Solution.
Using \(\mathcal{B}\) from Example 6.46 and normalizing the vectors, we set
\begin{equation*}
Q = \begin{bmatrix} \frac{1}{2} \amp \frac{-3}{\sqrt{12}} \amp 0 \\ \frac{1}{2} \amp \frac{1}{\sqrt{12}} \amp \frac{-2}{\sqrt{6}} \\ \frac{1}{2} \amp \frac{1}{\sqrt{12}} \amp \frac{1}{\sqrt{6}} \\ \frac{1}{2} \amp \frac{1}{\sqrt{12}} \amp \frac{1}{\sqrt{6}} \end{bmatrix}\text{.}
\end{equation*}
It follows that
\begin{align*}
R \amp = Q^TA \\
\amp = \begin{bmatrix} \frac{1}{2} \amp \frac{1}{2} \amp \frac{1}{2} \amp \frac{1}{2} \\ \frac{-3}{\sqrt{12}} \amp \frac{1}{\sqrt{12}} \amp \frac{1}{\sqrt{12}} \amp \frac{1}{\sqrt{12}} \\ 0 \amp \frac{-2}{\sqrt{6}} \amp \frac{1}{\sqrt{6}} \amp \frac{1}{\sqrt{6}} \end{bmatrix} \begin{bmatrix} 1 \amp 0 \amp 0 \\ 1 \amp 1 \amp 0 \\ 1 \amp 1 \amp 1 \\ 1 \amp 1 \amp 1 \end{bmatrix}\\
\amp = \begin{bmatrix} 2 \amp \frac{3}{2} \amp 1 \\ 0 \amp \frac{3}{\sqrt{12}} \amp \frac{2}{\sqrt{12}} \\ 0 \amp 0 \amp \frac{2}{\sqrt{6}} \end{bmatrix}.
\end{align*}
Again, we can check that \(R\) has all the expected properties: it is \(3 \times 3\text{,}\) upper triangular, positive entries on the diagonal, and \(\|\vec a_1\| = \|\vec r_1\|, \|\vec a_2\| = \|\vec r_2\|,\) and \(\|\vec a_3 \| = \|\vec r_3 \|\text{.}\)
