MIT线性代数总结笔记——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

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

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

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

$B=e=b-p=b-\frac{A^Tb}{A^TA}A$
检验 $A\perp B$ ：

$A^TB = A^Tb- A^T\frac{A^Tb}{A^TA}A = A^Tb-\frac{A^Tb}{A^TA}Ab=0$
得到两个正交向量 $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$ 。

正交化：我们设两正交向量为 $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]$

单位化：设两单位正交向量为 $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]$
得到矩阵 $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]$