6.4 Gram–Schmidt and QR Decomposition

Print preview

Section 6.4 Gram–Schmidt and QR Decomposition

Handout 6.4 Gram–Schmidt and QR Decomposition

Objectives: Topics

The Gram–Schmidt Process

🔗
The 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*}

🔗

$Geometric view of Gram–Schmidt orthogonalization.$

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{.}$

🔗

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*}

🔗

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{.}$

🔗