矩阵论7：标准正交基和 QR 分解

在现实世界中，我们可以轻松地确定唯一的垂直（正交）关系，然而在矩阵论的抽象之中，就连垂直（正交）关系也是相对的，定义不同的内积便有不同的垂直（正交）、不同的标准正交基，从其各自的标准正交基中观察自身都是自然的，垂直（正交）都是符合常理的，而对方则是不正常的。

正交

通过 Cauchy-Schwarz 不等式可以得到角度的定义，

$$\theta=\arccos\frac{(\bm\alpha,\bm\beta)}{\Vert\bm\alpha\Vert\Vert\bm\beta\Vert}$$

当 $(\bm\alpha,\bm\beta)=0$ 时，称为 $\bm\alpha$ 与 $\bm\beta$ 正交（垂直），表示为

$$\bm\alpha \perp \bm\beta$$

定理：正交 → 线性无关

Euclid 空间中 $k$ 个两两正交的非零向量 $\def\bm{\boldsymbol} \bm\alpha_1,…,\bm\alpha_k $ 线性无关

证明：设 $\lambda_1,…,\lambda_k\in\mathbb R$ ，且 $\lambda_1\bm\alpha_1+…+\lambda_k\bm\alpha_k=0 $ ，则有

$$(\sum_{i=1}^k\lambda_i\bm\alpha_i,\bm\alpha_j)=\sum_{i=1}^k\lambda_i(\bm\alpha_i,\bm\alpha_j)=0$$

由于 $i\neq j,(\bm\alpha_i,\bm\alpha_j)=0$ 且 $(\bm\alpha_j,\bm\alpha_j)>0$ ，所以 $\lambda_j=0$ 。由于 $j$ 的选择是任意的，得证。

从该定理我们可以轻松推得，$n$ 维 Euclid 空间中两两正交的非零向量组中所含向量的个数不超过 $n$ 。因此接下来我们的问题是： $n$ 维 Euclid 空间中是否存在 $n$ 个两两正交的非零向量构成的向量组？

Gram-Schmidt 正交化

设 $\bm\alpha_1,…,\bm\alpha_n $ 是 $n$ 维 Euclid 空间 $V$ 的一组基，则存在两两正交的非零向量 $\bm\beta_1,…,\bm\beta_n$ ，使得对于任意正整数 $k$ ， $\bm\beta_1,…,\bm\beta_k$ 是 $\bm\alpha_1,…,\bm\alpha_k$ 生产的子空间 $V_k$ 的一组基。

证明：使用数学归纳法，首先取 $\bm\beta_1=\bm\alpha_1$ ，对 $k=1$ 成立；

现在假设 $k=k-1$ 时成立，证明 $k=k$ 时也成立，设

$$\bm\beta_k=\bm\alpha_k-\lambda_{k-1}\bm\beta_{k-1}-...-\lambda_1\bm\beta_1$$

由于 $i\neq j,(\bm\beta_i,\bm\beta_j)=0$ ，所以

$$(\bm\beta_k,\bm\beta_j)=(\bm\alpha_k-\sum_{i=1}^{k-1}\lambda_{i-1},\bm\beta_j)=(\bm\alpha_k,\bm\beta_j)-\lambda_j(\bm\beta_j,\bm\beta_j)=0$$

得到

$$\lambda_j=\frac{(\bm\alpha_k,\bm\beta_j)}{(\bm\beta_j,\bm\beta_j)}$$

为了更加具象可以定义投影（projection）运算

$$\def\proj\{\text{proj}} \proj_{\bm\beta}\bm\alpha=\frac{(\bm\alpha,\bm\beta)}{(\bm\beta,\bm\beta)}\bm\beta=(\bm\alpha,\bm\beta^*)\bm\beta^*$$

计算具体如下

$$\begin{aligned} \bm\beta_1&=\bm\alpha_1,&\bm\beta_1^*&=\frac{\bm\beta_1}{\Vert\bm\beta_1\Vert}\\ \bm\beta_2&=\bm\alpha_2-\proj_{\bm\beta_1}\bm\alpha_2,&\bm\beta_2^*&=\frac{\bm\beta_2}{\Vert\bm\beta_2\Vert}\\ &\vdots &&\vdots \\ \bm\beta_n&=\bm\alpha_n-\sum_{i=1}^{n-1}\proj_{\bm\beta_i}\bm\alpha_n,&\bm\beta_n^*&=\frac{\bm\beta_n}{\Vert\bm\beta_n\Vert} \end{aligned}$$

这个求解方法即 Gram-Schmidt 正交化，最终得到的 $\bm\beta_1,…,\bm\beta_n$ 是 Euclid 空间 $V$ 的一组基，它称为 $V$ 的正交基。经过标准化后，则称为标准正交基。

数值稳定性

wikipedia-Gram-Schmidt 正交化数值稳定性分析

由于计算机的舍入误差，Gram-Schmidt 正交化每次迭代都有可能会积累误差，使得 $\bm\beta_k^*$ 之间不是完全正交。

随着迭代式中 $\bm\beta_k^*$ 的增多，正交性的损失也愈加严重 ，尤其高纬度情况。因此（经典的）Gram-Schmidt 正交化在数值上是不稳定的。

Gram-Schmidt 正交化可以通过一个小的修改来稳定，这称为改进 Gram-Schmidt 正交化，在每次计算 $\bm\beta_k^*$ 后，都做如下操作，

$$\begin{aligned} \bm\alpha_i^*=\bm\alpha_i-(\bm\alpha_i,\bm\beta_k^*)\bm\beta_k^* ,i\in{k+1,...,n} \end{aligned}$$

即在之后的 $\bm\alpha$ 上减轻当前 $\bm\beta$ 上的分量。

标准正交基

由于引入了内积，Euclid 空间比线性空间具有更强的结构性，基的选择应当与这种结构相适应，通过正交引入的标准正交基正是 Euclid 空间所应当考虑的基，也是通常三维空间的笛卡尔坐标系的直接推广。

定理：标准正交基的优良性质

设 $\bm\xi_1,…,\bm\xi_n$ 是 $n$ 维 Euclid 空间的两组正交基，则对任意向量

$$\bm\alpha=x_1\bm\xi_1+...+x_n\bm\xi_n$$

有

$$x_i=(\bm\alpha,\bm\xi_i)$$

对任意两个向量

$$\bm\alpha=x_1\bm\xi_1+...+x_n\bm\xi_n\\ \bm\beta=y_1\bm\xi_1+...+y_n\bm\xi_n$$

有

$$(\bm\alpha,\bm\beta)=x_1y_1+...+x_ny_n$$

可见在标准正交基下，向量的坐标分量是该向量与相应基向量的内积，向量的内积是标准内积形式。由此我们可以得出一个结论，标准内积并非是一个特别的内积，而是内积在其对应的标准正交基下的形式，例如 上一节 中的例子。

对于 $\mathbb R^2$ ，定义内积运算如下：

$$(\bm\xi,\bm\eta)=\xi_1\eta_1-\xi_2\eta_1-\xi_1\eta_2+4\xi_2\eta_2$$

注意在不同的内积定义下，范数的定义也会发生改变

$$\Vert\bm\alpha\Vert=\sqrt{(\bm\alpha,\bm\alpha)}=\sqrt{\alpha_1^2-2\alpha_1\alpha_2+4\alpha_2^2}$$

设 $\bm\alpha_1=(1,0)^T,\bm\alpha_2=(0,1)^T$ ，显然

$$(\bm\alpha_1,\bm\alpha_2)=-1\neq 0$$

不是该内积运算的标准正交基，接下来通过 Gram-Schmidt 正交化，求得标准正交基

$$\begin{aligned} \bm\beta_1&=\bm\alpha_1=(1,0)^T,&\bm\beta_1^*&=\frac{\bm\beta_1}{\Vert\bm\beta_1\Vert}=(1,0)^T\\ \bm\beta_2&=(0,1)^T-(-1)\cdot(1,0)^T=(1,1), &\bm\beta_2^*&=\frac{\bm\beta_2}{\Vert\bm\beta_2\Vert}=\frac{\sqrt3}{3}(1,1)\\ \end{aligned}$$

两个基的过渡矩阵为

$$(\bm\beta_1^*,\bm\beta_2^*)=(\bm\alpha_1,\bm\alpha_2)P=(\bm\alpha_1,\bm\alpha_2) \begin{pmatrix} 1&\frac{\sqrt3}{3}\\ 0&\frac{\sqrt3}{3} \end{pmatrix}$$ $$\bm\alpha_1=1\cdot\bm\beta_1^*+0\cdot\bm\beta_2^*\\ \bm\alpha_2=-1\cdot\bm\beta_1^*+\sqrt3\cdot\bm\beta_2^*$$

可见

$$(\bm\alpha_1,\bm\alpha_2)=1\cdot(-1)+0\cdot\sqrt3=0$$

Gram 方阵在不同基下的变换

由于内积和 Gram 方阵有着一一对应的关系，Gram 在不同基下也随着内积形式而变化，有以下定理：

设 $\bm\alpha_1,…,\bm\alpha_n$ 与 $\bm\beta_1,…,\bm\beta_n$ 是 $n$ 维 Euclid 空间的两组基，内积 $(\bm\alpha,\bm\beta)$ 在两组基下的 Gram 方阵分别为 $G_1$ 和 $G_2$ ，而且

$$(\bm\beta_1,...,\bm\beta_n)=(\bm\alpha_1,...,\bm\alpha_n)P$$

则

$$G_2=P^TG_1P$$

即方阵 $G_1$ 和 $G_2$ 是合同的。

该定理可以通过拆散矩阵再化为矩阵形式，轻松证明。

回到上一个例子，该内积在原本的基 $\bm\alpha_1,\bm\alpha_2$ 下的 Gram 方阵为，

$$G_1=\begin{pmatrix} 1&-1\\-1&4 \end{pmatrix} \\ G_2=P^TG_1P=\begin{pmatrix} 1&0\\0&1 \end{pmatrix}$$

即在内积对映的标准正交基下，内积的计算形式是标准内积，其 Gram 方阵也是单位阵。

定理：标准正交基间的转换

设 $\bm\xi_1,…,\bm\xi_n$ 与 $\bm\eta_1,…,\bm\eta_n$ 是 $n$ 维 Euclid 空间的两组正交基，则两者之间的过渡矩阵 $P$ 是正交方阵，即

$$PP^T=P^TP=I$$

证明：记

$$P=(p_{ij})_{n\times n}$$

则

$$\bm\eta_j=\sum_{i=1}^np_{ij}\bm\xi_i$$ $$\begin{aligned} (\bm\eta_i,\bm\eta_j)&=(\sum_{k=1}^np_{ki}\bm\xi_k,\sum_{l=1}^np_{lj}\bm\xi_l)\\ &=\sum_{k=1}^n\sum_{l=1}^np_{ki}p_{lj}(\bm\xi_k,\bm\xi_l) \\ &=\sum_{k=1}^np_{ki}p_{kj} \\ &=\begin{cases} 1,\text{if }i=j\\ 0,\text{if }i\neq j \end{cases} \end{aligned}$$

化为矩阵形式，即 $P^TP=I$ 。

这个定理将给出同一个 Euclid 空间中两组标准正交基的联系。

类似的证明方法可以证明：一组标准正交基通过一个正交矩阵变换得到的依然是一组标准正交基。

由此表明：$n$ 维 Euclid 空间 $V$ 中所有标准正交基集合和所有 $n$ 阶实正交方阵集合之间一一对应。

矩阵的 QR 分解

任何实方阵都可以做 QR 分解：

$$A=QR$$

其中 $Q$ 是正交阵，$R$ 是上三角矩阵。

证明可以直接从 Gram-Schmidt 正交化中汲取线索，

$$\begin{aligned} \bm\alpha_1&=\bm\beta_1=\Vert\bm\beta_1\Vert\bm\beta_1^*, &\bm\beta_1^*&=\frac{\bm\beta_1}{\Vert\bm\beta_1\Vert}\\ \bm\alpha_2&=\Vert\bm\beta_2\Vert\bm\beta_2^*+(\bm\alpha_2,\bm\beta_1^*)\bm\beta_1^*, &\bm\beta_2^*&=\frac{\bm\beta_2}{\Vert\bm\beta_2\Vert}\\ &\vdots &&\vdots \\ \bm\alpha_n&=\Vert\bm\beta_n\Vert\bm\beta_n^*-\sum_{i=1}^{n-1}(\bm\alpha_n,\bm\beta_i^*)\bm\beta_i^*, &\bm\beta_n^*&=\frac{\bm\beta_n}{\Vert\bm\beta_n\Vert} \end{aligned}$$

转化为矩阵形式即

$$(\bm\alpha_1,...,\bm\alpha_n) = (\bm\beta_1^*,...,\bm\beta_n^*) \begin{pmatrix} \Vert \bm\beta_1 \Vert & (\bm\alpha_2,\bm\beta_1^*) & \cdots & (\bm\alpha_n,\bm\beta_1^*) \\ 0 & \Vert \bm\beta_2 \Vert & \cdots & (\bm\alpha_n,\bm\beta_2^*) \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & \Vert \bm\beta_n \Vert \end{pmatrix}$$

这个过程也适用非方阵和列不满秩矩阵：

1. 非方阵：

   $$A_{m\times n}=Q_{m\times n}R_{n\times n}$$

2. 列不满秩矩阵：$\bm\beta_i$ 会等于 0， $R$ 末尾将有全零行。

应用——最小二乘问题

$$\min_x\Vert Ax-b\Vert^2 \\ \Rightarrow x=(A^TA)^{-1}A^Tb$$

通常对于 $A_{m\times n}$ ，$m\gg n$ 并且 $A$ 列满秩。

对 $A$ 进行 QR 分解，即 $A=QR$ ，则

$$\begin{aligned} (A^TA)x&=A^Tb \\ (QR)^T(QR)x&=(QR)^Tb\\ R^TQ^TQRx&=R^TQ^Tb\\ Rx&=Q^Tx\\ \Rightarrow x&=R^{-1}Q^Tx \end{aligned}$$

其中 $R$ 为上三角矩阵，求逆相对容易很多，规避了直接对 $(ATA)^{−1}$ 求逆复杂度高的问题。