# 向量和矩阵范数

我们采用范数作为向量或矩阵间距离的衡量。

# 向量范数

向量范数 (norm) 是一个 $\mathbb{R}^n \to \mathbb{R}$ 的映射 $\|\cdot\|$, 满足以下的性质：

1. 非负性: $\|\boldsymbol{x}\| \geq 0$;
2. 正定性: $\|\boldsymbol{x}\| = 0$ 当且仅当$\boldsymbol{x} = \boldsymbol{0}$;
3. 齐次性: $\|\alpha \boldsymbol{x}\| = |\alpha|\|\boldsymbol{x}\|$，其中$\alpha \in \mathbb{R}$ 且$\boldsymbol{x} \in \mathbb{R}^n$;
4. 三角不等式: $\|\boldsymbol{x} + \boldsymbol{y}\| \leq \|\boldsymbol{x}\| + \|\boldsymbol{y}\|$，其中$\boldsymbol{x}, \boldsymbol{y} \in \mathbb{R}^n$.
5. Cauchy-Bunyakovsky-Schwarz 不等式: $\boldsymbol{x}'\boldsymbol{y} \leq \|\boldsymbol{x}\|_2\cdot\|\boldsymbol{y}\|_2$，其中$\boldsymbol{x}, \boldsymbol{y} \in \mathbb{R}^n$.

在向量范数中，最常见的定义为 $l_p$ 范数。对于向量 $\boldsymbol{x} = (x_1,x_2,\dots,x_n)'$, 其 $l_p$ 范数定义为

$$\|\boldsymbol{x}\|_p:=\left(\sum_{i=1}^nx_i^p\right)^{\frac{1}{p}}$$

于是在极限意义下，有 $\|\boldsymbol{x}\|_0 = \#(i|x_i \neq 0)$ 表示 $\boldsymbol{x}$ 中非零项的数目，$\|\boldsymbol{x}\|_\infty = \max_{i=1}^n|x_i|$ 表示 $\boldsymbol{x}$ 中最大项的值。

# 向量距离

两个向量 $\boldsymbol{x}, \boldsymbol{y}$ 的距离定义为 $\|\boldsymbol{x-y}\|$. 定义距离时，最常用的范数为 $l_2$ 范数即欧氏距离，又称为欧几里得范数 (Euclidean norm).

# 矩阵范数

# 定义

矩阵范数是一个 $\mathbb{R}^{n \times n} \to \mathbb{R}$ 的映射。对所有的 $A \in \mathbb{R}^{n \times n}$ 及 $\alpha \in \mathbb{R}$, 满足：

1. 非负性: $\|A\| \geq 0$;
2. 正定性: $\|A\| = 0$ 当且仅当 $A = O$;
3. 齐次性: $\|\alpha A\| = |\alpha|\|A\|$, 其中 $\alpha \in \mathbb{R}$ 且 $A \in \mathbb{R}^{n \times n}$;
4. 三角不等式: $\|\boldsymbol{x} + \boldsymbol{y}\| \leq \|\boldsymbol{x}\| + \|\boldsymbol{y}\|$, 其中 $\boldsymbol{x}, \boldsymbol{y} \in \mathbb{R}^n$.
5. $\|AB\| \leq \|A\|\cdot\|B\|$ (可以采用 Hölder 不等式证明).

# 自然范数

向量范数可以自然诱导出矩阵范数。

对于 $\mathbb{R}^n$ 上的向量范数 $\|\cdot\|$, 其诱导出的

$$\|A\| = \max_{\|\boldsymbol{x}\| = 1}\|A\boldsymbol{x}\|$$

必定为矩阵范数，称为矩阵 $A$ 在向量范数 $\|\cdot\|$ 诱导下的自然矩阵范数 (natural matrix norm).

一般地，有

$$\|A\boldsymbol{x}\| \leq \|A\| \cdot \|\boldsymbol{x}\|, \quad \forall \boldsymbol{x} \in \mathbb{R}^n$$

# 特征值和特征向量

# 谱半径

# 概念

矩阵 $A$ 的谱半径 (spectral radius) 定义为

$$\rho(A) \coloneqq \max|\lambda|, \quad \text{where }\lambda\text{ is an eigenvalue of }A.$$

# 性质

性质 1 $\|A\|_2 = \sqrt{\rho(A^\dag A)}$, 其中 $A^\dag$ 是 $A$ 的复共轭转置。

性质 2 对任意自然范数 $\|\cdot\|$, 有 $\rho(A) = \|A\|$.

# Geršgorin 圆盘定理

设 $A = (a_{ij})_{n\times n} \in \mathbb{C}^{n \times n}$, $R_i$ 是复平面上以 $a_{ii}$ 为中心的圆盘，其半径为 $\sum_{j=1,j\neq i}^n|a_{ij}|$, 即

$$R_i = \left\{\boldsymbol{z} \in \mathbb{C}\left||\boldsymbol{z} - a_{ii}| \leq \sum_{\substack{j=1 \\ j \neq i}}^n|a_{ij}|\right.\right\}$$

则 $A$ 的全体特征值位于上述圆盘组成的并集 $R = \bigcup_{i=1}^nR_i$ 中。且若任意 $k$ 个圆盘组成的并集与其余 $n-k$ 个圆盘不相交，则这 $k$ 个圆盘组成的并集中必定包括 $k$ 个特征值。

证明

基于 Geršgorin 圆盘定理可以立即得到一个推论：

推论 1 对角占优的实对称矩阵是半正定的。

# 矩阵特征值的近似求解

矩阵特征值求解的近似方法包括幂法、对称幂法和反幂法等。

# 幂法

幂法 (power method) 是用来求解矩阵最大特征值的方法。

# Ref

• sola - 数值分析学习笔记（六）
• 三半俊秀 - 特征值分析 - 盖氏圆盘定理
• 吃饭吧唧吧唧嘴 - Perron-Frobenius 定理
• Wikipedia - Diagonally dominant matrix
• Wikipedia - Laplacian matrix