How to Calculate QR Decomposition Using the Gram-Schmidt Process Step-by-Step.

📚 Understanding QR Decomposition and the Gram-Schmidt Process

QR decomposition is a matrix factorization technique that decomposes a matrix $A$ into the product of an orthogonal matrix $Q$ and an upper triangular matrix $R$. The Gram-Schmidt process is a method for orthonormalizing a set of vectors, which is used to find the $Q$ matrix.

📜 History and Background

The Gram-Schmidt process was developed by Jørgen Pedersen Gram and Erhard Schmidt. It's a fundamental algorithm in linear algebra used to construct an orthonormal basis from a set of linearly independent vectors. QR decomposition, which utilizes Gram-Schmidt, has become crucial in various numerical algorithms, including solving linear least squares problems and eigenvalue computations.

🔑 Key Principles

• 📐 Orthogonalization: The Gram-Schmidt process takes a set of linearly independent vectors and produces a set of orthogonal vectors that span the same subspace.
• ✨ Normalization: The orthogonal vectors are then normalized to create orthonormal vectors (unit vectors that are orthogonal to each other).
• 📈 QR Decomposition: Applying Gram-Schmidt to the column vectors of matrix $A$ allows us to construct the orthogonal matrix $Q$, and subsequently, we find $R$ such that $A = QR$.

🪜 Step-by-Step Calculation with Example

Let's consider a matrix $A = \begin{bmatrix} 1 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \end{bmatrix}$. We will find its QR decomposition using the Gram-Schmidt process.

1. ➡️ Step 1: Apply Gram-Schmidt to the columns of $A$

   Let $a_1 = \begin{bmatrix} 1 \\ 1 \\ 0 \end{bmatrix}$, $a_2 = \begin{bmatrix} 1 \\ 0 \\ 1 \end{bmatrix}$, and $a_3 = \begin{bmatrix} 0 \\ 1 \\ 1 \end{bmatrix}$.

   • 🎯 $q_1$ Calculation:

     $u_1 = a_1 = \begin{bmatrix} 1 \\ 1 \\ 0 \end{bmatrix}$

     $\lVert u_1 \rVert = \sqrt{1^2 + 1^2 + 0^2} = \sqrt{2}$

     $q_1 = \frac{u_1}{\lVert u_1 \rVert} = \frac{1}{\sqrt{2}} \begin{bmatrix} 1 \\ 1 \\ 0 \end{bmatrix} = \begin{bmatrix} \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} \\ 0 \end{bmatrix}$

   • ➖ $q_2$ Calculation:

     $u_2 = a_2 - \text{proj}_{q_1}(a_2) = a_2 - (q_1^T a_2)q_1$

     $q_1^T a_2 = \begin{bmatrix} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} & 0 \end{bmatrix} \begin{bmatrix} 1 \\ 0 \\ 1 \end{bmatrix} = \frac{1}{\sqrt{2}}$

     $u_2 = \begin{bmatrix} 1 \\ 0 \\ 1 \end{bmatrix} - \frac{1}{\sqrt{2}} \begin{bmatrix} \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} \\ 0 \end{bmatrix} = \begin{bmatrix} \frac{1}{2} \\ -\frac{1}{2} \\ 1 \end{bmatrix}$

     $\lVert u_2 \rVert = \sqrt{(\frac{1}{2})^2 + (-\frac{1}{2})^2 + 1^2} = \sqrt{\frac{3}{2}}$

     $q_2 = \frac{u_2}{\lVert u_2 \rVert} = \sqrt{\frac{2}{3}} \begin{bmatrix} \frac{1}{2} \\ -\frac{1}{2} \\ 1 \end{bmatrix} = \begin{bmatrix} \frac{1}{\sqrt{6}} \\ -\frac{1}{\sqrt{6}} \\ \frac{\sqrt{2}}{\sqrt{3}} \end{bmatrix}$
   • ➗ $q_3$ Calculation:

     $u_3 = a_3 - \text{proj}_{q_1}(a_3) - \text{proj}_{q_2}(a_3) = a_3 - (q_1^T a_3)q_1 - (q_2^T a_3)q_2$

     $q_1^T a_3 = \begin{bmatrix} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} & 0 \end{bmatrix} \begin{bmatrix} 0 \\ 1 \\ 1 \end{bmatrix} = \frac{1}{\sqrt{2}}$

     $q_2^T a_3 = \begin{bmatrix} \frac{1}{\sqrt{6}} & -\frac{1}{\sqrt{6}} & \frac{\sqrt{2}}{\sqrt{3}} \end{bmatrix} \begin{bmatrix} 0 \\ 1 \\ 1 \end{bmatrix} = \frac{1}{\sqrt{6}}$

     $u_3 = \begin{bmatrix} 0 \\ 1 \\ 1 \end{bmatrix} - \frac{1}{\sqrt{2}} \begin{bmatrix} \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} \\ 0 \end{bmatrix} - \frac{1}{\sqrt{6}} \begin{bmatrix} \frac{1}{\sqrt{6}} \\ -\frac{1}{\sqrt{6}} \\ \frac{\sqrt{2}}{\sqrt{3}} \end{bmatrix} = \begin{bmatrix} -\frac{2}{3} \\ \frac{2}{3} \\ \frac{2}{3} \end{bmatrix}$

     $\lVert u_3 \rVert = \sqrt{(-\frac{2}{3})^2 + (\frac{2}{3})^2 + (\frac{2}{3})^2} = \frac{2}{\sqrt{3}}$

     $q_3 = \frac{u_3}{\lVert u_3 \rVert} = \frac{\sqrt{3}}{2} \begin{bmatrix} -\frac{2}{3} \\ \frac{2}{3} \\ \frac{2}{3} \end{bmatrix} = \begin{bmatrix} -\frac{1}{\sqrt{3}} \\ \frac{1}{\sqrt{3}} \\ \frac{1}{\sqrt{3}} \end{bmatrix}$

2. 2️⃣ Step 2: Construct the matrix $Q$

   $Q = \begin{bmatrix} | & | & | \\ q_1 & q_2 & q_3 \\ | & | & | \end{bmatrix} = \begin{bmatrix} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{6}} & -\frac{1}{\sqrt{3}} \\ \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{6}} & \frac{1}{\sqrt{3}} \\ 0 & \frac{\sqrt{2}}{\sqrt{3}} & \frac{1}{\sqrt{3}} \end{bmatrix}$

3. 3️⃣ Step 3: Calculate the matrix $R$

   Since $A = QR$, we have $R = Q^T A$.

   $R = \begin{bmatrix} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} & 0 \\ \frac{1}{\sqrt{6}} & -\frac{1}{\sqrt{6}} & \frac{\sqrt{2}}{\sqrt{3}} \\ -\frac{1}{\sqrt{3}} & \frac{1}{\sqrt{3}} & \frac{1}{\sqrt{3}} \end{bmatrix} \begin{bmatrix} 1 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 1 \end{bmatrix} = \begin{bmatrix} \sqrt{2} & \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\ 0 & \frac{\sqrt{3}}{\sqrt{2}} & \frac{\sqrt{2}}{\sqrt{3}} \\ 0 & 0 & \frac{2}{\sqrt{3}} \end{bmatrix}$

🌍 Real-world Examples

• 📊 Data Analysis: QR decomposition is used in solving linear least squares problems, which arise frequently in statistical modeling and data fitting.
• 🤖 Computer Graphics: It helps in transformations and projections, ensuring objects are rendered correctly.
• 📡 Signal Processing: Used in adaptive filtering algorithms.

заключение Conclusion

The Gram-Schmidt process provides a systematic way to perform QR decomposition, transforming a matrix into an orthogonal and an upper triangular matrix. This technique is invaluable in various fields, offering robust solutions to complex computational problems.