03 向量范数与矩阵范数

1. 范数把代数对象变成度量对象

向量空间上的函数 $\parallel \cdot \parallel$ 是范数，当且仅当满足：

$$\parallel x\parallel \ge 0,\parallel x\parallel =0\iff x=0,$$$$\parallel \alpha x\parallel =|\alpha |\parallel x\parallel ,\parallel x+y\parallel \le \parallel x\parallel +\parallel y\parallel .$$

在有限维空间中，任意两个范数都等价：存在 $m,M>0$ 使

$$m\parallel x{\parallel }_a\le \parallel x{\parallel }_b\le M\parallel x{\parallel }_a.$$

“等价”指它们定义相同的收敛与连续性，不是数值相等。

2. ${\ell }_p$ 范数与对偶指数

对 $1\le p<\mathrm{\infty }$，

$$\parallel x{\parallel }_p={(\sum _{i=1}^n|x_i{|}^p)}^{1/p},\parallel x{\parallel }_{\mathrm{\infty }}=\underset{i}{max}|x_i|.$$

若 $p^{-1}+q^{-1}=1$，Hölder 不等式给出

$$|y^{\ast }x|\le \parallel x{\parallel }_p\parallel y{\parallel }_q.$$

Minkowski 不等式则保证三角不等式：

$$\parallel x+y{\parallel }_p\le \parallel x{\parallel }_p+\parallel y{\parallel }_p.$$

对固定 $x$，$p$ 越大，$\parallel x{\parallel }_p$ 越小；但不同维数下比较时要带上维数常数。

3. 相容范数与诱导范数

矩阵范数若满足

$$\parallel AB\parallel \le \parallel A\parallel \parallel B\parallel$$

称为次乘性的。由向量范数诱导的算子范数定义为

$$\parallel A\parallel =\underset{x\ne 0}{sup}\frac{\parallel Ax\parallel }{\parallel x\parallel }.$$

它就是线性映射的最大放大率，并自动满足

$$\parallel Ax\parallel \le \parallel A\parallel \parallel x\parallel ,\parallel I\parallel =1.$$

三个常用公式：

$$\parallel A{\parallel }_1=\underset{j}{max}\sum _i|a_{ij}|,$$$$\parallel A{\parallel }_{\mathrm{\infty }}=\underset{i}{max}\sum _j|a_{ij}|,$$$$\parallel A{\parallel }_2={\sigma }_{max}(A)=\sqrt{\rho (A^{\ast }A)}.$$

4. Frobenius 范数

$$\parallel A{\parallel }_F={(\sum _{i,j}|a_{ij}{|}^2)}^{1/2}=\sqrt{\mathrm{tr}(A^{\ast }A)}={(\sum _k{\sigma }_k(A{)}^2)}^{1/2}.$$

它不是由同维向量范数诱导的算子范数，但它计算简单、酉不变，并满足

$$\parallel AB{\parallel }_F\le \parallel A{\parallel }_2\parallel B{\parallel }_F,\parallel AB{\parallel }_F\le \parallel A{\parallel }_F\parallel B{\parallel }_2.$$

算子 2-范数只看最强方向，Frobenius 范数汇总所有方向的能量。

5. 谱半径、Neumann 级数与稳定性

谱半径为

$$\rho (A)=\underset{i}{max}|{\lambda }_i(A)|.$$

对任意相容矩阵范数，$\rho (A)\le \parallel A\parallel$。Gelfand 公式把长期幂行为与谱连接起来：

$$\rho (A)=\underset{k\to \mathrm{\infty }}{lim}\parallel A^k{\parallel }^{1/k}.$$

若 $\rho (A)<1$，则

$$\sum _{k=0}^{\mathrm{\infty }}{A}^k=(I-A{)}^{-1}.$$

注意：只知道某一个常见范数 $\parallel A\parallel >1$，不能推出级数发散；真正的充要条件由谱半径控制。

6. 到奇异矩阵的距离

若 $A$ 可逆，则在 2-范数下

$$\underset{A+E\text{ 奇异}}{min}\parallel E{\parallel }_2={\sigma }_{min}(A)=\frac{1}{\parallel A^{-1}{\parallel }_2}.$$

所以条件数

$${\kappa }_2(A)=\parallel A{\parallel }_2\parallel A^{-1}{\parallel }_2=\frac{{\sigma }_{max}(A)}{{\sigma }_{min}(A)}$$

衡量了矩阵离奇异性的相对程度。

7. 有限维范数为何等价

以任意范数 $\parallel \cdot \parallel$ 和欧氏范数比较。函数 $x\mapsto \parallel x\parallel$ 连续，而单位球面

$$S^{n-1}=\{x:\parallel x{\parallel }_2=1\}$$

在有限维空间中是紧集，所以该函数在球面上取得正的最小值 $m$ 和有限最大值 $M$。对 $x\ne 0$，把 $x$ 写成 $\parallel x{\parallel }_2(x/\parallel x{\parallel }_2)$，立即得到

$$m\parallel x{\parallel }_2\le \parallel x\parallel \le M\parallel x{\parallel }_2.$$

有限维假设用在“单位球面紧”这一步；无限维空间的单位球一般不紧，不同范数可能定义完全不同的收敛概念。

8. 诱导范数公式中的极值向量

对任意 $x$，

$$\parallel Ax{\parallel }_{\mathrm{\infty }}\le (\underset{i}{max}\sum _j|a_{ij}|)\parallel x{\parallel }_{\mathrm{\infty }}.$$

取达到最大行和的第 $i_0$ 行，并令 $x_j$ 取 $a_{i_{0}j}$ 的相位的共轭，使 $a_{i_{0}j}{x}_j=|a_{i_{0}j}|$，上界即可取到。这证明了行和公式。列和公式可由对偶关系

$$\parallel A{\parallel }_1=\parallel A^{\ast }{\parallel }_{\mathrm{\infty }}$$

得到。对 2-范数，最大值在 $A^{\ast }A$ 的最大特征值对应单位特征向量处取到，于是 $\parallel A{\parallel }_2={\sigma }_1(A)$。

9. 条件数把数据误差放大多少

设 $Ax=b$，扰动右端项得到 $A(x+\delta x)=b+\delta b$。则

$$\frac{\parallel \delta x\parallel }{\parallel x\parallel }\le \kappa (A)\frac{\parallel \delta b\parallel }{\parallel b\parallel }.$$

这个界可能达到。以

$$A=\left(\begin{array}{cc}1& 0\\ 0& \epsilon \end{array}\right),0<\epsilon \ll 1$$

为例，第二个方向上的右端项误差会被放大 $1/\epsilon$ 倍，而 ${\kappa }_2(A)=1/\epsilon$。条件数描述的是问题本身的敏感性；算法稳定性则描述程序额外引入多少误差，二者不能混为一谈。

10. 自检

• [ ] 能区分向量范数、诱导矩阵范数和一般矩阵范数。
• [ ] 能从行和/列和直接写出 $\parallel A{\parallel }_{\mathrm{\infty }}$ 与 $\parallel A{\parallel }_1$。
• [ ] 能解释 $\rho (A)<1$ 比 $\parallel A\parallel <1$ 更精确。
• [ ] 能用最小奇异值解释条件数。
• [ ] 知道有限维范数等价证明在哪一步使用了紧性。
• [ ] 能构造取到行和诱导范数的向量。

下一章：向量空间与线性映射。