《矩陣QR分解的三種方法》學習筆記

本文同時提供以下語言的翻譯： 簡體中文， English。

本文介紹了矩陣的QR分解的三種方法，分別是Schmidt正交化方法，初等變換方法和Givens變換方法。QR分解是指將一個矩陣分解爲一個正交矩陣和一個上三角矩陣的乘積，這種分解在數值分析和線性代數中有很多應用。文章給出了每種方法的原理，步驟和例子，以及一些性質和結論。

1. Schmidt正交化方法是最常用的方法，它的基本思想是將矩陣的列向量進行正交化和單位化，得到一個列正交矩陣Q和一個非奇異上三角矩陣R。這種方法利用了正交向量組的等價性和線性無關性。
2. 初等變換方法是利用矩陣的第三種行和列初等變換，將矩陣A轉化爲對稱正定矩陣A^T A，然後對A^T A同時進行相應的行和列初等變換，得到一個對角矩陣D，其中對角元素全爲正數。再利用D構造一個非奇異上三角矩陣R和一個列正交矩陣Q。
3. Givens變換方法是利用Givens矩陣，也稱爲平面旋轉矩陣，對矩陣A進行左乘，使得A的某些元素變爲零，從而得到一個上三角矩陣R。Givens矩陣是一個正交矩陣，它只在某兩個座標軸上進行旋轉，不改變其他座標軸上的元素。通過逆序地將所有Givens矩陣相乘，可以得到一個列正交矩陣Q。

1 Schmidt正交化方法

這種方法是將矩陣的列向量進行正交化和單位化，得到一個列正交矩陣Q和一個非奇異上三角矩陣R。具體步驟如下：

1. 令$\alpha_1 = a_1$，其中$a_1$是矩陣A的第一列向量。
2. 令$q_1 = \frac{\alpha_1}{|\alpha_1|}$，其中$|\cdot|$表示向量的模長。
3. 對於$i=2,3,\dots,n$，令$\alpha_i = a_i - \sum_{j=1}^{i-1}(q_j^T a_i)q_j$，其中$a_i$是矩陣A的第i列向量，$q_j$是已經求出的第j個單位正交向量。
4. 令$q_i = \frac{\alpha_i}{|\alpha_i|}$。
5. 最後得到$Q=[q_1,q_2,\dots,q_n]$和$R=Q^T A$。

或

1. 從矩陣A中取出第一列向量$a1$，將其單位化，得到$q1$。

2. 從矩陣A中取出第二列向量$a2$，將其減去與$q1$的投影，得到一個與$q1$正交的向量$b2$，然後將其單位化，得到$q2$。(注意：這裏的投影是指向量在另一個向量上的投影，即向量在另一個向量上的投影長度乘以另一個向量的單位向量。)

3. 重複上述過程，直到取出所有的列向量，得到一組正交單位向量$q1,q2,…,qn$。

4. 將這組向量作爲矩陣$Q$的列向量，即$Q=[q1,q2,…,qn]$。

5. 計算$R=Q^TA$，其中$Q^T$是$Q$的轉置矩陣。由於$Q$是正交矩陣，$Q^TQ=I$，所以$R=AQQ^TA$。由於$Q$的列向量是正交的，$R$是一個上三角矩陣。

例如，對於矩陣$$A=\begin{bmatrix}1 & -1 & 4 \\ 1 & 4 & -2 \\ 1 & 4 & 2 \\ 1 & -1 & 0 \end{bmatrix}$$，我們可以按照上述步驟求出$$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 \end{bmatrix}$$和$$R=\begin{bmatrix}2 & 3 & 2 \\ 0 & 5 & -2 \\ 0 & 0 & \sqrt{10} \end{bmatrix}$$

注: 步驟1-3位爲Gram–Schmidt過程,具體過程如下:
給定一組線性無關的向量${v_1, …, v_k}$，Gram–Schmidt過程可以產生一組標準正交的向量${u_1, …, u_k}$，使得
$$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$$
其中$\langle \cdot, \cdot \rangle$表示內積，$|\cdot|$表示向量的範數（長度）。

這個過程可以看作是對給定向量組的一種正交化處理，將原來的向量組變成一組正交的向量組。這個過程的幾何意義是，從原來的向量組中，依次取出一個向量，然後將其減去與前面所有向量的投影，得到一個與前面所有向量都正交的向量，然後將其單位化，得到一個單位正交向量。重複這個過程，直到取出所有的向量，得到一組正交單位向量。

2 初等變換方法

這種方法是利用矩陣的第三種行和列初等變換，將矩陣A轉化爲對稱正定矩陣$A^T A$，然後對$A^T A$同時進行相應的行和列初等變換，得到一個對角矩陣D，其中對角元素全爲正數。再利用D構造一個非奇異上三角矩陣R和一個列正交矩陣Q。具體步驟如下：

1. 對於$i=1,2,\dots,n-1$，令$p_{ii}=a_{ii}$，其中$a_{ii}$是矩陣A的第i行第i列元素。
2. 對於$j=i+1,i+2,\dots,n$，令$p_{ij}=a_{ij}-\frac{a_{ii}}{p_{ii}}a_{ji}$，其中$a_{ij}$和$a_{ji}$是矩陣A的第i行第j列和第j行第i列元素。
3. 對於$k=i+1,i+2,\dots,n$，令$p_{kk}=a_{kk}-\sum_{j=i+1}^{k-1}\frac{p_{kj}^2}{p_{jj}}$。
4. 對於$k=i+2,i+3,\dots,n$和$j=i+1,i+2,\dots,k-1$，令$p_{kj}=a_{kj}-\sum_{s=i+1}^{j-1}\frac{p_{ks}}{p_{ss}}p_{sj}$。
5. 最後得到$P=[p_{ij}]$和$D=P^T P$。
6. 對於$i=1,2,\dots,n$，令$r_{ii}=\sqrt{d_{ii}}$，其中$d_{ii}$是矩陣D的第i行第i列元素。
7. 對於$i=1,2,\dots,n-1$和$j=i+1,i+2,\dots,n$，令$r_{ij}=\frac{p_{ij}}{r_{ii}}$。
8. 最後得到$R=[r_{ij}]$和$Q=A R^{-1}$。

或

1. 將矩陣$A$轉置乘以$A$，得到一個對稱正定矩陣$B=A^TA$。
2. 對$B$進行第三種行和列初等變換，使得$B$變成一個對角矩陣$D$，並記錄每次變換所用的初等矩陣$P_i$和$Q_i$。
3. 對$D$開平方根，得到一個非奇異上三角矩陣$R$。
4. 將所有的$P_i$和$Q_i$相乘，得到一個正交矩陣$Q$。

例如，對於矩陣$$A=\begin{bmatrix}3 & -6 \\ 4 & -8 \end{bmatrix}$$，我們可以按照上述步驟求出$$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}$$和$$Q=\begin{bmatrix}-0.6 & -0.8 \\ -0.8 &0.6 \end{bmatrix}$$

3 Givens變換方法

這種方法是利用Givens矩陣，也稱爲平面旋轉矩陣，對矩陣A進行左乘，使得A的某些元素變爲零，從而得到一個上三角矩陣R。Givens矩陣是一個正交矩陣，它只在某兩個座標軸上進行旋轉，不改變其他座標軸上的元素。通過逆序地將所有Givens矩陣相乘，可以得到一個列正交矩陣Q。具體步驟如下：

1. 從矩陣A的第一列開始，依次對每一列進行Givens變換，使得每一列除了對角線上的元素外，其他元素都變爲零，得到一個上三角矩陣R。
2. 記錄每次變換所用的Givens矩陣$G_i$，並將它們逆序相乘，得到一個正交矩陣Q。