9.md

Orthogonalization (Gram-Schmidt), QR decomposition

TOC

• Orthogonalization (Gram-Schmidt), QR decomposition
  • TOC
  • Explanation
    • Orthogonalization (Gram-Schmidt)
    • QR Decomposition
  • Solution

Explanation

Certainly! Let's go through both topics one by one.

Orthogonalization (Gram-Schmidt)

Orthogonalization is the process of finding a set of orthogonal vectors that span a particular vector space. The Gram-Schmidt process is a method for orthogonalizing a set of vectors in an inner product space, most commonly the Euclidean space $\mathbb{R}^n$.

The idea is to take a set of linearly independent vectors and construct a new set of vectors that are mutually orthogonal (perpendicular to each other) and that span the same subspace as the original set.

Here's how the Gram-Schmidt process works step-by-step:

1. Start with a set of linearly independent vectors ${v_1, v_2, ..., v_n}$.
2. The first vector of the orthogonal set is just the first vector of the original set: $u_1 = v_1$.
3. For each subsequent vector $v_k$, subtract the projection of $v_k$ onto each of the previous $u$ vectors to make it orthogonal to those vectors: $$ u_k = v_k - \sum_{j=1}^{k-1} \text{proj}{u_j}(v_k) $$ where the projection of $v_k$ onto $u_j$ is given by: $$ \text{proj}{u_j}(v_k) = \frac{\langle v_k, u_j \rangle}{\langle u_j, u_j \rangle}u_j $$ Here, $\langle \cdot, \cdot \rangle$ denotes the inner product.
4. Normalize each $u_k$ to get an orthonormal set if desired.

QR Decomposition

QR decomposition is a matrix factorization technique that breaks a matrix down into a product of two matrices: $Q$ (an orthogonal matrix) and $R$ (an upper triangular matrix). This is very useful in solving linear systems, eigenvalue problems, and many other areas of linear algebra.

Here's a brief overview:

• Given a matrix $A$, we want to find matrices $Q$ and $R$ such that $A = QR$.
• $Q$ is an orthogonal matrix, meaning its columns are orthonormal vectors ($Q^T Q = I$, where $I$ is the identity matrix).
• $R$ is an upper triangular matrix, meaning all the elements below the main diagonal are zero.

The QR decomposition can be computed using the Gram-Schmidt process, as the columns of $Q$ can be obtained by applying the process to the columns of $A$. The elements of $R$ are then given by the inner products of the original columns of $A$ and the orthonormal vectors (columns of $Q$).

The QR decomposition is used in numerical methods, particularly in the QR algorithm for finding eigenvalues, in linear regression (via the least squares method), and in solving linear systems when $A$ is not square or is ill-conditioned for inversion.

Solution

9. Apply the Gram-Schmidt process to: $$ x_1=\begin{bmatrix}0\0\2\0\end{bmatrix}, x_2=\begin{bmatrix}-1\0\1\0\end{bmatrix}, x_3=\begin{bmatrix}2\1\0\0\end{bmatrix}, x_4=\begin{bmatrix}1\0\0\-1\end{bmatrix} $$ and write the result in form $A=QR$. (12 pts.)

Certainly! To apply the Gram-Schmidt process to the vectors $x_1, x_2, x_3, x_4$, we will follow the steps outlined earlier:

1. Set $u_1 = x_1$.
2. For $k = 2, 3, 4$, compute $$ u_k = x_k - \sum_{j=1}^{k-1} \text{proj}{u_j}(x_k) $$ where $$ \text{proj}{u_j}(x_k) = \frac{\langle x_k, u_j \rangle}{\langle u_j, u_j \rangle}u_j $$

After computing the orthogonal vectors $u_1, u_2, u_3, u_4$, we will form the matrix $Q$ with these vectors as its columns. Since we want $Q$ to be an orthogonal matrix, we will also normalize each $u_k$ to have a unit length.

The matrix $R$ will be an upper triangular matrix where the entries above the diagonal are the inner products of $x_k$ with the normalized $u_j$. The entries on the diagonal of $R$ will be the norms of the $u_k$ vectors before normalization.

Let's start by computing the orthogonal vectors using the Gram-Schmidt process.

The orthogonal vectors obtained from the Gram-Schmidt process are:

$$ u_1 = \begin{bmatrix}0\0\2\0\end{bmatrix}, \quad u_2 = \begin{bmatrix}-1\0\0\0\end{bmatrix}, \quad u_3 = \begin{bmatrix}0\1\0\0\end{bmatrix}, \quad u_4 = \begin{bmatrix}0\0\0\-1\end{bmatrix} $$

After normalization, these become the columns of the orthogonal matrix $Q$:

$$ Q = \begin{bmatrix} 0 & -1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & -1 \end{bmatrix} $$

The corresponding upper triangular matrix $R$ is:

$$ R = \begin{bmatrix} 2 & 1 & 0 & 0 \\ 0 & 1 & -2 & -1 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} $$

Hence, the QR decomposition of the matrix $A$ whose columns are the original vectors $x_1, x_2, x_3, x_4$ is:

$$ A = QR = \begin{bmatrix} 0 & -1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & -1 \end{bmatrix} \begin{bmatrix} 2 & 1 & 0 & 0 \\ 0 & 1 & -2 & -1 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} $$