LU、奇异值分解与伪逆

矩阵分解把矩阵拆成较简单的运算。LU 记录消元过程，适合反复求解方阵系统。奇异值分解（SVD）也适用于矩形矩阵和奇异矩阵：它把伸缩与旋转或反射分开，并指出丢失信息及逆运算不稳定的方向。

1 用 LU 表示消元

若高斯消元不需要交换行，可把消元乘数存入单位下三角矩阵 $L$，得到 $A=LU$，其中 $U$ 为上三角矩阵。例如

$$A=\begin{pmatrix}2&1\\4&5\end{pmatrix},\quad L=\begin{pmatrix}1&0\\2&1\end{pmatrix},\quad U=\begin{pmatrix}2&1\\0&3\end{pmatrix}.$$

求解 $Ax=b$ 时先解 $Ly=b$，再解 $Ux=y$。若 $b=(5,13)$，则 $y=(5,3)$，$x=(2,1)$。面对多个右端向量时可以重复使用这些因子。若主元为零，可能需要交换行；此时应写成 $PA=LU$，其中 $P$ 为置换矩阵。即使主元非零，太小的主元也可能使选主元对数值计算很重要。声称每个可逆矩阵都有不交换行的 LU 分解是不正确的。

实内积、诱导范数与所需不等式

实向量空间上的内积是取值于实数的映射 $\langle u,v\rangle$，它对称、对每个变量线性，并且正定：$v\ne0$ 时 $\langle v,v\rangle>0$。线性性给出 $\langle0,v\rangle=0$。定义 $\|v\|=\sqrt{\langle v,v\rangle}$，则范数恰在零向量处为零，且 $\|cv\|=|c|\|v\|$。$\mathbb R^m$ 上的标准例子是 $\langle u,v\rangle=\sum_{i=1}^mu_iv_i$。内积为零的向量称为正交；不同成员互相正交且每个成员范数为一的列表称为正交规范列表。

若 $v\ne0$，将 $t=\langle u,v\rangle/\|v\|^2$ 代入非负平方 $\|u-tv\|^2$，以双线性展开得 $\|u\|^2-\langle u,v\rangle^2/\|v\|^2\ge0$，故 $|\langle u,v\rangle|\le\|u\|\|v\|$。若 $v=0$，该不等式直接成立。对 $v\ne0$，等号意味着 $\|u-tv\|=0$，等价于 $u=tv$；零向量情形也取等。最后展开 $\|u+v\|^2$ 并对交叉项使用该界，得到 $\|u+v\|^2\le(\|u\|+\|v\|)^2$。待开方的两边非负，因此得到三角不等式。这确实定义了范数，任何非零向量的归一化都只除以正实数；这里不使用复双线性的约定。

不预设计数结论的有限基存在与扩充

设实向量空间 $V$ 已给定有限生成列表 $t_1,\ldots,t_N$。先证明任何线性无关列表 $u_1,\ldots,u_k$ 的长度不超过 $N$。插入 $j$ 个向量后，维持一个由 $u_1,\ldots,u_j$ 与 $N-j$ 个剩余旧向量组成的生成列表。将 $u_{j+1}$ 按此列表展开，至少一个剩余旧向量的系数非零；否则它在先前 $u_i$ 的张成空间中，与无关性矛盾。解出这个旧向量，再以 $u_{j+1}$ 取代它。新列表仍张成同一空间，而且保留全部先前插入向量。若 $k>N$，则 $N$ 步后前 $N$ 个向量已张成 $V$，与 $u_{N+1}$ 的无关性矛盾。此即所需上界，也包括 $N=0$。

每个子空间 $W$ 都有有限基。从空的无关列表开始；若当前张成空间尚不是 $W$，就在 $W$ 中取一个不在该张成空间内的向量。若新向量在某关系中的系数非零，就能由旧向量表示它，矛盾，故新列表仍无关。已证上界允许至多添加 $N$ 次，所以过程必停止于 $W$ 的无关生成列表。若 $W=\{0\}$，立即得到空基。改从 $W$ 内任意给定无关列表开始，同样证明该列表可扩充为 $W$ 的基；只需有界有限次选择。最后，若两组基的长度为 $p,q$，分别把它们用作上界证明中的有限生成列表，得到 $p\le q$ 与 $q\le p$。故基的长度有良定义，称为维数。这些论证补足秩–零度定理所用的基存在、扩充与维数事实。

正交规范基，以及保留指定向量的扩充

再设 $V$ 具有实正定内积。对无关列表 $v_1,\ldots,v_s$，逐次定义

$$w_j=v_j-\sum_{i<j}\langle v_j,q_i\rangle q_i,\qquad q_j=w_j/\|w_j\|.$$

归纳假设先前 $q_i$ 正交规范。对 $l<j$ 与 $q_l$ 取内积，得 $\langle w_j,q_l\rangle=\langle v_j,q_l\rangle-\langle v_j,q_l\rangle=0$。若 $w_j=0$，则 $v_j$ 在先前张成空间中，矛盾，因此可合法除以它的正范数。所列公式及其移项式说明前 $j$ 个新旧向量张成相同空间，归纳完成。用于一组基就得到正交规范基，子空间亦然。若要扩充一组指定的正交规范向量，先由已证定理将它扩充为普通基，再按此顺序进行上述构造。原先指定的向量没有分量被减去，范数又为一，所以全都精确保留。空列表与零子空间无需相除。这证明了 SVD 及投影存在性所用的正交规范扩充。

固定整数 $n\ge1$，在 $\mathbb R^n$ 上使用欧几里得范数。集合若包含在某个有限半径的球内，就称为有界；若补集是开集，就称为闭集；若它的每个由 $\mathbb R^n$ 中开集组成的覆盖都有有限子覆盖，就称为紧集。我们使用实数完备性，包括闭区间套性质。

有限维欧几里得空间的 Heine–Borel 定理

定理。 集合 $K\subseteq\mathbb R^n$ 紧致，当且仅当它闭且有界。空集具有这三种性质。

紧致推出有界。 开球 $B(0,m)$（整数 $m\ge1$）覆盖 $K$。取有限子覆盖后，$K$ 包含在其中最大的球内。

紧致推出闭。 设 $K\ne\varnothing$ 且 $y\notin K$。开球 $B(x,\|x-y\|/2)$（$x\in K$）覆盖 $K$。取中心为 $x_1,\ldots,x_r$ 的有限子覆盖，令 $\delta=\min_i\|x_i-y\|/2>0$。若 $z$ 在以 $x_i$ 为中心的所选球内，三角不等式给出 $\|z-y\|>\|x_i-y\|/2\ge\delta$。所以 $B(y,\delta)$ 不与 $K$ 相交，补集是开集。

闭且有界推出紧致。 设非空的 $K$ 闭且有界，把它包含在闭立方体 $Q_0=[-M,M]^n$ 内，其中 $M>0$。假设 $K$ 的某个开覆盖没有有限子覆盖。把每个坐标区间分成两个闭半区间，所得 $2^n$ 个闭子立方体覆盖 $Q_0$。至少一个子立方体与 $K$ 的交集不能由给定覆盖族有限覆盖；否则把有限多个有限子覆盖合并，就能覆盖 $K$。选取这样的子立方体并重复，得到闭立方体套 $Q_j$，其边长为 $2M/2^j$，且 $K\cap Q_j$ 不能被有限覆盖，因而非空。

对每个坐标使用闭区间套性质，得到公共坐标值；合起来得到 $p\in\bigcap_jQ_j$。$Q_j$ 中任意两点的距离不超过 $2M\sqrt n/2^j$，所以交集中只有 $p$。选取 $x_j\in K\cap Q_j$，则 $\|x_j-p\|\le2M\sqrt n/2^j\to0$。闭集包含这种极限：若 $p$ 在开补集中，$p$ 周围某个开球就会使最终的 $x_j$ 落在 $K$ 外，矛盾。因此 $p\in K$。

覆盖中有一个成员 $O$ 含 $p$，由开放性，存在 $\varepsilon>0$ 使 $B(p,\varepsilon)\subseteq O$。当 $j$ 足够大时，$Q_j$ 的每点到 $p$ 的距离都小于 $\varepsilon$，于是单个 $O$ 就覆盖 $K\cap Q_j$，与 $Q_j$ 的选取矛盾。因此每个开覆盖都有有限子覆盖。这里 $2^n$ 是有限数；若改成无限多个子块，这个论证就不再成立。

连续像与极值

定理。 若 $K\subseteq\mathbb R^n$ 紧致，且 $F:K\to\mathbb R^m$ 相对于 $K$ 连续，则 $F(K)$ 紧致。特别地，非空紧集 $K$ 上的连续函数 $f:K\to\mathbb R$ 有界，并达到最大值和最小值。

证明。 $F(K)$ 的开覆盖 $(O_i)$ 的原像是相对开集 $F^{-1}(O_i)=K\cap U_i$，其中 $U_i$ 在 $\mathbb R^n$ 中开。这些 $U_i$ 覆盖 $K$，所以有限多个足够。对应的 $O_i$ 覆盖 $F(K)$，证明了像的紧致性。对标量函数 $f$，由已证明定理的一维情形，其像非空、闭且有界。令 $a=\sup f(K)$。对每个 $j\ge1$，由上确界定义，可取 $y_j\in f(K)$ 使 $a-1/j<y_j\le a$。于是 $y_j\to a$，闭性使 $a$ 属于像，所以最大值可达。对 $-f$ 使用同一论证即得最小值。该结论证明存在性，而不提供极大点的计算公式。

不暗用求导法则的“极大点产生特征向量”步骤

设 $S=S^T$ 为实矩阵，$\|u\|_2=1$，且 $u^TSu$ 是二次型在单位球面上的最大值。对 $w\perp u$，记 $a=u^TSu$、$b=w^TSu$、$c=w^TSw$、$d=\|w\|_2^2$。谱定理证明中的归一化曲线对应二次型值为

$$G(t)=\frac{a+2bt+ct^2}{1+dt^2},\qquad \frac{G(t)-G(0)}t=\frac{2b+t(c-ad)}{1+dt^2}\quad(t\ne0).$$

最后的差商在 $t\to0$ 时趋于 $2b$。极大性使它在 $t>0$ 时非正、$t<0$ 时非负，所以共同的双侧极限为零，故 $w^TSu=b=0$。这里使用明确的有理差商，不暗中调用多元梯度或链式法则。已证明的正交规范扩充将 $u^\perp$ 与少一维的实坐标空间对应起来；在此坐标中，其不变限制的矩阵对称，因为 $x^TSy=(Sx)^Ty$。这就说明维数归纳的合法性，也包括最后的零维正交补。

2 实对称矩阵谱定理

定理。 对 $n\ge1$，每个实对称矩阵 $S\in\mathbb R^{n\times n}$ 都有正交规范特征向量基，且特征值均为实数。

证明。 当 $n=1$ 时，矩阵是实标量，标准单位向量构成正交规范特征向量基。设 $n\ge2$。连续函数 $v^TSv$ 在紧的单位球面上取得最大值。设 $u$ 是达到最大值的单位向量。对任意 $w\perp u$，令 $\gamma(t)=(u+tw)/\|u+tw\|$。因为 $\|u+tw\|^2=1+t^2\|w\|^2>0$，分母对每个实数 $t$ 均非零。函数 $\gamma(t)^TS\gamma(t)$ 在 $t=0$ 取得最大值，求导得 $2w^TSu=0$。取 $w=Su-(u^TSu)u$，则 $w\perp u$ 且 $w^TSu=\|w\|^2=0$，所以 $Su=(u^TSu)u$。因此 $u$ 是特征向量，其特征值 $u^TSu$ 为实数。由于 $u^TSw=(Su)^Tw=0$ 对 $w\perp u$ 成立，其正交补是不变子空间。把 $S$ 限制在该正交补上仍得到对称算子，对维数归纳即可。$\square$

对于 $S=A^TA$，因为 $v^TSv=\|Av\|^2\ge0$，所有特征值均非负。

3 奇异值分解

取 $A^TA$ 的一组正交规范特征向量基 $v_i$，使正特征值排在前面。将这些特征值写成 $\sigma_i^2$，其中 $\sigma_i>0$，$1\le i\le r$。令 $u_i=Av_i/\sigma_i$，则

$$u_i^Tu_j=\frac{v_i^TA^TAv_j}{\sigma_i\sigma_j}=\delta_{ij}.$$

将这些向量扩充成 $\mathbb R^m$ 的正交规范基。特征值为零的特征向量满足 $Av_i=0$，因此

$$A=U\Sigma V^T,$$

其中 $U,V$ 是正交矩阵，$\Sigma$ 是矩形对角矩阵，其正对角元满足 $\sigma_1\ge\cdots\ge\sigma_r$。这些数称为奇异值。它们不一定是 $A$ 的特征值；它甚至可能不是方阵。

公式显示 $Av_i=\sigma_i u_i$：先用 $V^T$ 旋转坐标，沿各个有效坐标伸缩，再用 $U$ 旋转。矩阵的秩为 $r$，核由其余 $v_i$ 张成。

4 伪逆与最小范数

定义 $A^+=V\Sigma^+U^T$，把每个正奇异值换成其倒数，并转置矩形形状。于是

$$x_*=A^+b=\sum_{i=1}^r\frac{u_i^Tb}{\sigma_i}v_i.$$

定理。 $x_*$ 使 $\|Ax-b\|$ 最小；在所有使残差最小的向量中，它的欧氏范数最小，且唯一。

证明。 写成 $x=\sum z_iv_i$ 和 $b=\sum c_iu_i$。由正交性，残差平方为 $\sum_{i\le r}(\sigma_iz_i-c_i)^2+\sum_{i>r}c_i^2$。取得最小值要求有效坐标满足 $z_i=c_i/\sigma_i$。核方向的坐标不影响残差，却对 $\|x\|^2$ 贡献 $\sum_{i>r}z_i^2$，该项唯一的最小值在这些坐标全为零时取得。$\square$

对 $A=\begin{pmatrix}1&1\\0&0\end{pmatrix}$，一个正奇异值为 $\sqrt2$，相应向量为 $v_1=(1,1)/\sqrt2$ 和 $u_1=(1,0)$。若 $b=(4,3)$，则 $x_*=(2,2)$，预测向量为 $(4,0)$，残差为 $(0,3)$。所有最小化向量均满足 $x_1+x_2=4$，但 $(2,2)$ 的范数最小。

小奇异值会放大逆运算系数中的误差：扰动 $\varepsilon u_i$ 使 $A^+b$ 改变 $(\varepsilon/\sigma_i)v_i$。截断或正则化会改变问题，必须明确说明，不能称为精确求逆。

5 分级练习

E1 基础。 求 $A=\begin{pmatrix}1&2\\3&8\end{pmatrix}$ 的 LU 分解，并解 $Ax=(5,17)^T$。

E2 奇异值分解。 给出 $D=\begin{pmatrix}3&0\\0&0\\0&0\end{pmatrix}$ 的奇异值及一个伪逆。

E3 最小范数。 对行矩阵 $A=(1\;2)$ 和目标 $b=5$，求范数最小的精确解并证明其最小性。

E4 选主元。 给出一个可逆 $2\times2$ 矩阵，使其在不交换行的情况下不能写成 $A=LU$，其中 $L$ 是单位下三角矩阵，$U$ 是上三角矩阵。

6 完整解答

S1. $L=\begin{pmatrix}1&0\\3&1\end{pmatrix}$，$U=\begin{pmatrix}1&2\\0&2\end{pmatrix}$。前代得 $y=(5,2)$，回代得 $x=(3,1)$。

S2. 正奇异值是 3，另一个奇异值是 0。$D^+=\begin{pmatrix}1/3&0&0\\0&0&0\end{pmatrix}$。它把第一个观测坐标除以 3，并将未确定的定义域坐标设为零。

S3. $A^+=\binom12/5$，所以 $x_*=(1,2)$。每个精确解都形如 $(1,2)+t(-2,1)$。这两个向量正交，因此范数平方为 $5+5t^2$，在零处唯一地取得最小值。

S4. 取 $A=\begin{pmatrix}0&1\\1&0\end{pmatrix}$。若 $L=\begin{pmatrix}1&0\\\ell&1\end{pmatrix}$ 且 $U=\begin{pmatrix}u&v\\0&w\end{pmatrix}$，则左上角元素迫使 $u=0$，从而左下角元素 $\ell u=0$，与 $a_{21}=1$ 矛盾。交换行可解决这个主元障碍。

总结

LU 封装消元，SVD 封装几何，即使矩阵是矩形或奇异的也适用。伪逆选出唯一的最小范数最小二乘解。使用分解时应始终注意其假设、秩的信息和数值影响。