Notes on Three QR Decomposition Methods

This article is also available in 简体中文, 繁體中文.

This article introduces three methods of QR decomposition of a matrix, namely Schmidt orthogonalization method, elementary transformation method and Givens transformation method. QR decomposition refers to decomposing a matrix into the product of an orthogonal matrix and an upper triangular matrix. This decomposition has many applications in numerical analysis and linear algebra. The article gives the principles, steps and examples of each method, as well as some properties and conclusions.

1. The Schmidt orthogonalization method is the most commonly used method. Its basic idea is to orthogonalize and unitize the column vectors of the matrix to obtain a column orthogonal matrix Q and a non-singular upper triangular matrix R. This method takes advantage of the equivalence and linear independence of orthogonal vector groups.
2. The primary transformation method is to use the third row and column elementary transformation of the matrix to convert matrix A into a symmetric positive definite matrix A^T A, and then perform corresponding row and column elementary transformations on A^T A at the same time to obtain a diagonal matrix D, where all diagonal elements are positive numbers. Then, D is used to construct a non-singular upper triangular matrix R and a column orthogonal matrix Q.
3. The Givens transformation method uses the Givens matrix, also known as the plane rotation matrix, to left multiply matrix A, so that some elements of A become zero, thereby obtaining an upper triangle matrix R. The Givens matrix is ​​an orthogonal matrix that only rotates on one of two axes without changing the elements on other axes. By multiplying all Givens matrices in reverse order, one column orthogonal matrix Q can be obtained.

1 Schmidt orthogonalization method

This method is to orthogonalize and unitize the column vectors of the matrix to obtain a column orthogonal matrix Q and a non-singular upper triangular matrix R. The specific steps are as follows:

1. Let $\alpha_1 = a_1$, where $a_1$ is the first column vector of matrix A.
2. Let $q_1 = \frac{\alpha_1}{|\alpha_1|}$, where $|\cdot|$ represents the modulus length of the vector.
3. For $i=2,3,\dots,n$, let $\alpha_i = a_i - \sum_{j=1}^{i-1}(q_j^T a_i)q_j$, where $a_i$ is the i-th column vector of matrix A, and $q_j$ is the jth unit orthogonal vector that has been found.
4. Let $q_i = \frac{\alpha_i}{|\alpha_i|}$.
5. Finally, we get $Q=[q_1,q_2,\dots,q_n]$ and $R=Q^T A$.

or

1. Take the first column vector $a1$ from matrix A and unitize it to obtain $q1$.

2. Take out the second column vector $a2$ from matrix A, subtract it from the projection with $q1$, and get a vector $b2$ orthogonal to $q1$, and then unitize it to get $q2$.(Note: The projection here refers to the projection of a vector on another vector, that is, the projection length of the vector on another vector multiplied by the unit vector of another vector.)

3. Repeat the above process until all column vectors are taken out and a set of orthogonal unit vectors $q1,q2,…,qn$ is obtained.

4. Use this set of vectors as column vectors of matrix $Q$, that is, $Q=[q1,q2,…,qn]$.

5. Calculate $R=Q^TA$, where $Q^T$ is the transpose matrix of $Q$. Since $Q$ is an orthogonal matrix, $Q^TQ=I$, $R=AQQ^TA$. Since the column vector of $Q$ is orthogonal, $R$ is an upper triangle matrix.

For example, for the matrix $$A=\begin{bmatrix}1 & -1 & 4 \\\ 1 & 4 & -2 \\ 1 & 4 & 2 \\ 1 & -1 & 0 \end{bmatrix}$$, we can follow the above steps to find $$Q=\begin{bmatrix}0.5 & -0.5 & 0.5 & -0.5 \\ 0.5 & 0.5 & -0.5 \\ 0.5 & 0.5 & -0.5 \\ 0.5 & -0.5 \\ 0.5 & -0.5 \\ 0.5 & -0.5 \\ 0.5 & -0.5 \\ 0.5 & -0.5 \\ 0.5 & -0.5 \end{bmatrix}$$ and $$R=\begin{bmatrix}2 & 3 & 2 \\ 0 & 5 & -2 \\\ 00 & 0 & \sqrt{10} \end{bmatrix}$$

Note: Step 1-3 is the Gram-Schmidt process, the specific process is as follows:
Given a set of linearly independent vectors ${v_1, …, v_k}$, the Gram–Schmidt process can produce a set of standard orthogonal vectors ${u_1, …, u_k}$, so that
$$u_1 = \frac{v_1}{|v_1|}$$
$$u_i = \frac{v_i - \sum_{j=1}^{i-1} \langle v_i, u_j \rangle u_j}{|v_i - \sum_{j=1}^{i-1} \langle v_i, u_j \rangle u_j|}, \quad i = 2, …, k$$
where $\langle \cdot, \cdot \rangle$ represents the inner product, and $|\cdot|$ represents the norm (length) of the vector.

This process can be regarded as an orthogonalization process for a given vector group, turning the original vector group into an orthogonal vector group. The geometric meaning of this process is to take out a vector from the original group of vectors, then subtract it from the projection with all previous vectors, obtain a vector orthogonal to all previous vectors, and then unitize it to obtain a unit orthogonal vector. Repeat this process until all vectors are taken out and a set of orthogonal unit vectors are obtained.

2 Elementary Transformation Method

This method uses the third row and column elementary transformation of the matrix to convert matrix A into a symmetric positive definite matrix $A^T A$, and then performs the corresponding row and column elementary transformation of $A^T A$ at the same time to obtain a diagonal matrix D, where all the diagonal elements are positive numbers. Then, D is used to construct a non-singular upper triangular matrix R and a column orthogonal matrix Q. The specific steps are as follows:

1. For $i=1,2,\dots,n-1$, let $p_{ii}=a_{ii}$, where $a_{ii}$ is the i-th column element of matrix A.
2. For $j=i+1,i+2,\dots,n$, let $p_{ij}=a_{ij}-\frac{a_{ii}}{p_{ii}}a_{ji}$, where $a_{ij}$ and $a_{ji}$ are the i-th column j and j-th column i-th elements of matrix A.
3. For $k=i+1,i+2,\dots,n$, let $p_{kk}=a_{kk}-\sum_{j=i+1}^{k-1}\frac{p_{kj}^2}{p_{jj}}$.
4. For $k=i+2,i+3,\dots,n$ and $j=i+1,i+2,\dots,k-1$, let $p_{kj}=a_{kj}-\sum_{s=i+1}^{j-1}\frac{p_{ks}}{p_{ss}}p_{sj}$.
5. Finally, we get $P=[p_{ij}]$ and $D=P^T P$.
6. For $i=1,2,\dots,n$, let $r_{ii}=\sqrt{d_{ii}}$, where $d_{ii}$ is the i-th column element of matrix D.
7. For $i=1,2,\dots,n-1$ and $j=i+1,i+2,\dots,n$, let $r_{ij}=\frac{p_{ij}}{r_{ii}}$.
8. Finally, we get $R=[r_{ij}]$ and $Q=A R^{-1}$.

or

1. Transpose the matrix $A$ by $A$ to obtain a symmetric positive definite matrix $B=A^TA$.
2. Perform the third row and column elementary transformation on $B$, so that $B$ becomes a diagonal matrix $D$, and record the elementary matrices $P_i$ and $Q_i$ used for each transformation.
3. Open the square root of $D$ to obtain a non-singular upper triangle matrix $R$.
4. Multiply all $P_i$ and $Q_i$ to obtain an orthogonal matrix $Q$.

For example, for the matrix $$A=\begin{bmatrix}3 & -6 \\ 4 & -8 \end{bmatrix}$$, we can follow the above steps to find $$P=\begin{bmatrix}3 & -6 \\ 4 & -4 \end{bmatrix}$$,$$D=\begin{bmatrix}25 & -50 \\ -50 &100 \end{bmatrix}$$,$R=\begin{bmatrix}5 & -10 \\ 0 &10 \end{bmatrix}$$ and $$Q=\begin{bmatrix}-0.6 & -0.8 \\ -0.8 &0.6\end{bmatrix}$$

3 Givenns transformation method

This method uses the Givens matrix, also known as the plane rotation matrix, to left multiply matrix A, so that some elements of A become zero, thereby obtaining an upper triangle matrix R. The Givens matrix is ​​an orthogonal matrix that only rotates on one of two axes without changing the elements on other axes. By multiplying all Givens matrices in reverse order, one column orthogonal matrix Q can be obtained. The specific steps are as follows:

1. Starting from the first column of matrix A, each column is transformed in sequence, so that except for the elements on the diagonal line, all other elements of each column become zero, and an upper triangle matrix R is obtained.
2. Record the Givens matrix $G_i$ used for each transformation, and multiply them in reverse order to obtain an orthogonal matrix Q.