线性代数(5)：QR分解

前言

前文我们讲解了投影矩阵和最小二乘法，本节我们深化正交基和正交矩阵的概念和性质，讨论QR分解以及将一组向量转化为标准正交向量组的方法：Gram-Schmidt正交化。

矩阵分解	QR分解
分解形式	$A=QR$ ($Q$代表标准正交矩阵，$R$代表非奇异上三角矩阵)
目的	(1)求解A的特征值； (2)求解A的逆； (3)求解线性最小二乘问题。

标准正交矩阵

标准正交向量（Orthonormal Vector）

我们用$q$表示单位向量，那么有$q_1,q_2,q_3,...,q_n$，若所有的向量$q$满足

$q_i^Tq_j = \begin{cases} 0 \quad i\not=j \\1 \quad i=j \end{cases}$

此时，我们称$q$为标准正交向量（Orthonormal Vector）。当$i=j$时，$q_i^Tq_j = 1$表示向量长度为单位长度。当$i\not= j$时，$q_i^Tq_j=0$表示不同的向量之间是正交的。

标准正交矩阵（Orthonormal Matrix）

将标准正交向量$q$放入矩阵$Q$中，得到$Q=\left[\begin{matrix}q_1& q_2& ...& q_n\end{matrix}\right]$，我们称这样的矩阵$Q$为标准正交矩阵（Orthonormal Matrices）。标准正交矩阵满足以下性质：

$Q^TQ = \left[\begin{matrix}q_1^T \\ q_2^T \\ ...\\ q_n^T\end{matrix}\right]\left[\begin{matrix}q_1& q_2& ...& q_n\end{matrix}\right] = \left[\begin{matrix}1 & 0 & \cdots & 0 \\ 0 & 1 & \cdots & \cdots \\ \vdots & \vdots &\ddots & \vdots \\ 0 & 0 & \cdots & 1 \end{matrix}\right] = I$

当矩阵$Q$恰好为方阵时，由于其正交性，可知矩阵$Q$是可逆的，而$Q^TQ = I$，所以 Q^T = Q^{-1}$，那么此时我们称$Q$为正交矩阵(Orthogonal Matrix)。

示例

$(1) \quad Q = \left[\begin{matrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1\end{matrix}\right]$

此时$Q^T = Q^{-1} = \left[\begin{matrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0\end{matrix}\right]$，易得$Q^TQ = I$

$(2) \quad Q = \left[\begin{matrix} cos\theta & -sin\theta \\ sin\theta & cos\theta \end{matrix}\right]$

此时列向量长度为$1$，列向量相互正交

$(3) \quad Q = \frac{1}{\sqrt{2}}\left[\begin{matrix} 1 & -1 \\ 1 & -1 \end{matrix}\right]$

此时列向量长度为$1$，列向量相互正交

$(4) \quad Q = \frac{1}{2}\left[\begin{matrix} 1 & 1 & 1 & 1 \\ 1 & -1 & 1 & -1 \\ 1& 1 & -1 & -1 \\ 1 & -1 & -1 & 1\end{matrix}\right]$

$(5) \quad Q = \frac{1}{3}\left[\begin{matrix} 1 & -2 & 2 \\ 2 & -1 & -2 \\ 2 & 2 & 1\end{matrix}\right]$

用途

上一篇文章我们知道投影矩阵$P=A(A^TA)^{-1}A^T$，当矩阵$A$为标准正交矩阵$Q$时，有

$P = Q(Q^TQ)^{-1}Q^T = QQ^T$

当$Q$是方阵时，$QQ^T=I$，那么其投影矩阵$P=I$。

验证：

$P^T = P: \quad (Q^TQ)^T = (Q^T)^TQ^T = QQ^T$

$P^2 = P: \quad (QQ^T)^2 = QQ^TQQ^T = Q(Q^TQ)Q^T = QQ^T$

将Q带入到最小二乘法公式（$A^TA\hat{x} = A^Tb$）中，得到：

$Q^TQ\hat{x} = Q^Tb => \hat{x} = Q^Tb$

分解开即为

$\hat{x_i} = q_i^Tb$

Gram-Schmidt正交化

两个向量的单位正交化

已知两个线性无关的向量$a,b$无法满足标准的正交（如图1所示），现在我们想通过Gram-Schmidt方法进行单位化和正交化，将其转化为标准的单位正交基$q_1,q_2$。

图1：无法满足标准正交的两个向量a,b

1. 设正交向量为$A, B$，接着我们以向量$a$为其中的正交向量$A$，则需求出正交向量$B$。
2. 若要求出正交向量$B$，其实就是将$b$投影到$a$上，再求$b$到$a$的距离，也就是误差向量$e$，也就是用向量$b$去减$b$在向量$a$上的分量，如图2所示

图2：向量b与向量a的误差向量e

3. 根据上一节关于向量投影的知识可知：

   $B=e=b-p=b-\frac{A^Tb}{A^TA}A$

4. 检验$A\perp B$：

   $A^TB = A^Tb- A^T\frac{A^Tb}{A^TA}A = A^Tb-\frac{A^Tb}{A^TA}Ab=0$

5. 得到两个正交向量$q_1,q_2$：

   $q_1 = \frac{A}{||A||}, \quad q_2 = \frac{B}{||B||}$

三个向量的单位正交化

如果有三个向量要做单位正交化，那第三个向量需要垂直于前两个向量，我们设三个向量分别为$a,b,c$，三个相互正交的向量为$A,B,C$，三个相互正交的单位向量为$q_1,q_2,q_3$，并令$A=a$，那么根据上一小节的内容，可以推出：

$B=b-\frac{A^Tb}{A^TA}A \\ C=c-p=c-p_a-p_b = c-\frac{A^Tc}{A^TA}A-\frac{B^Tc}{B^TB}B$

示例

设有线性无关的非正交向量$a,b$，其中$a = \left[\begin{matrix} 1 \\ 1 \\ 1 \end{matrix}\right],b = \left[\begin{matrix} 1 \\ 0 \\ 2 \end{matrix}\right]$，求两向量的标准正交矩阵$Q$。

1. 正交化：我们设两正交向量为$A,B$，其中

$A = a = \left[\begin{matrix} 1 \\ 1 \\ 1 \end{matrix}\right]\\ B=b-p_a = b-\frac{A^Tb}{A^TA}A = \left[\begin{matrix} 1 \\ 0 \\ 2 \end{matrix}\right] - \frac{\left[\begin{matrix} 1 & 1 & 1 \end{matrix}\right]\left[\begin{matrix} 1 \\ 1 \\ 2 \end{matrix}\right]}{\left[\begin{matrix} 1 & 1 & 1 \end{matrix}\right]\left[\begin{matrix} 1 \\ 1 \\ 1 \end{matrix}\right]}\left[\begin{matrix} 1 \\ 1 \\ 1 \end{matrix}\right]= \left[\begin{matrix} 1 \\ 0 \\ 2 \end{matrix}\right] -\left[\begin{matrix} 1 \\ 1 \\ 1 \end{matrix}\right] = \left[\begin{matrix} 0 \\ -1 \\ 1 \end{matrix}\right]$

2. 单位化：设两单位正交向量为$q_1,q_2$，则

$q_1 = \frac{1}{\sqrt3}\left[\begin{matrix} 1 \\ 1 \\ 1 \end{matrix}\right] \\ q_2 = \frac{1}{\sqrt2}\left[\begin{matrix} 0 \\ -1 \\ 1 \end{matrix}\right]$

3. 得到矩阵$Q$：

$Q = \left[\begin{matrix} \frac{1}{\sqrt3} & 0 \\ \frac{1}{\sqrt3} & -\frac{1}{\sqrt2} \\ \frac{1}{\sqrt3} & \frac{1}{\sqrt2} \end{matrix}\right]$

QR分解

我们继续上文所述的示例，我们设原来的矩阵为$A= \left[\begin{matrix} 1 & 1 \\ 1 & 0 \\ 1 & 2 \end{matrix}\right]$，然后来对比一下矩阵$A$和$Q$：

$A= \left[\begin{matrix} 1 & 1 \\ 1 & 0 \\ 1 & 2 \end{matrix}\right] \quad Q = \left[\begin{matrix} \frac{1}{\sqrt3} & 0 \\ \frac{1}{\sqrt3} & -\frac{1}{\sqrt2} \\ \frac{1}{\sqrt3} & \frac{1}{\sqrt2} \end{matrix}\right]$

会发现，$A$和$Q$的列空间是相同的，当然这是因为我们只是将原来的基标准正交化了。那么和LU分解表达了高斯消元法类似，上述示例中使用Gram-Schmidt正交化方法的过程也可以用矩阵的形式来表达，即$A=QR$，其中$Q$为标准正交矩阵，$R$为非奇异上三角矩阵。具体地，设矩阵$A$有列$a,b$，即$A = \left[\begin{matrix} a & b \end{matrix}\right]$，那么我们可以直接写出矩阵$Q$和矩阵$R$，即

$A = \left[\begin{matrix} a & b \end{matrix}\right] = QR = \left[\begin{matrix} q_1 & q_2 \end{matrix}\right]\left[\begin{matrix} a^T q_1 & b^T q_1 \\a^Tq_2 & b^T q_2\end{matrix}\right]$

由于我们令$a$为两正交向量中的一个，因此$a\perp b$，所以$a^Tq_2 =0$，因此矩阵$R$是一个上三角矩阵，就有

$A = \left[\begin{matrix} a & b \end{matrix}\right] = QR = \left[\begin{matrix} q_1 & q_2 \end{matrix}\right]\left[\begin{matrix} a^T q_1 & b^T q_1 \\0 & b^T q_2\end{matrix}\right]$