向量和矩阵范数

向量范数的定义

称 $\mathbb{R}^n$ 上的一个函数 $\left\Vert\cdot\right\Vert$ 为范数，若满足：

非负性：$\left\Vert\mathbf{x}\right\Vert\ge0$, $\left\Vert\mathbf{x}\right\Vert=0$当且仅当$\mathbf{x}=\mathbf{0}$
齐次性：$\left\Vert\alpha\mathbf{x}\right\Vert=\left\vert \alpha \right\vert\left\Vert\mathbf{x}\right\Vert, \alpha\in\mathbb{R}$
三角不等式：$\left\Vert\mathbf{x}+\mathbf{y}\right\Vert\le\left\Vert\mathbf{x}\right\Vert+\left\Vert\mathbf{y}\right\Vert$

常见的向量范数有：

1-范数：$\left\Vert\mathbf{x}\right\Vert_{1}=\sum_{i=1}^{n}\left\vert x_{i} \right\vert$
2-范数：$\left\Vert\mathbf{x}\right\Vert_{2}=\left(\sum_{i=1}^{n}\left\vert x_{i} \right\vert^{2}\right)^{\frac 1{2}}$
$\infty$-范数：$\left\Vert\mathbf{x}\right\Vert_{\infty}=\max\limits_{1\le i\le n}\left\vert x_{i} \right\vert$

向量范数的性质

向量范数的等价性

对于 $\mathbb{R}^n$ 中的任意两种范数 $\left\Vert\mathbf{x}\right\Vert_{\alpha}$ 和 $\left\Vert\mathbf{x}\right\Vert_{\beta}$，都存在两个正数 $c_1,c_2$，使得对任意 $\mathbf{x}\in\mathbb{R}^n$ 都有：

\[ c_1\left\Vert\mathbf{x}\right\Vert_{\alpha}\le\left\Vert\mathbf{x}\right\Vert_{\beta}\le c_2\left\Vert\mathbf{x}\right\Vert_{\alpha} \]

Proof.

令 $f(\mathbf{x})=\left\Vert\mathbf{x}\right\Vert_{\beta}$，$\mathbf{S}=\{\mathbf{x}\in\mathbb{R}^n: \left\Vert\mathbf{x}\right\Vert_{\alpha}= 1\}$ 为一个有界闭集，则连续函数 $f(\mathbf{x})$ 在 $\mathbf{S}$ 上存在最小值 $c_1=\min\limits_{\mathbf{x}\in\mathbf{S}}f(\mathbf{x})$ 和最大值 $c_2=\max\limits_{\mathbf{x}\in\mathbf{S}}f(\mathbf{x})$。

对于 $\mathbf{x}\ne \mathbf{0}$ 有 $\frac{\mathbf{x}}{\left\Vert\mathbf{x}\right\Vert_{\alpha}}\in \mathbf{S}$，则有：

\[ c_1\le f\left(\frac{\mathbf{x}}{\left\Vert\mathbf{x}\right\Vert_{\alpha}}\right)=\frac{\left\Vert\mathbf{x}\right\Vert_{\beta}}{\left\Vert\mathbf{x}\right\Vert_{\alpha}}\le c_2 \]

即：

\[ c_1\left\Vert\mathbf{x}\right\Vert_{\alpha}\le\left\Vert\mathbf{x}\right\Vert_{\beta}\le c_2\left\Vert\mathbf{x}\right\Vert_{\alpha} \]

$\square$

对于常用的向量范数，有如下关系：

\[ \begin{aligned} \left\Vert\mathbf{x}\right\Vert_2\le\left\Vert\mathbf{x}\right\Vert_1\le\sqrt{n}\left\Vert\mathbf{x}\right\Vert_2 \\ \left\Vert\mathbf{x}\right\Vert_{\infty}\le\left\Vert\mathbf{x}\right\Vert_1\le n\left\Vert\mathbf{x}\right\Vert_{\infty} \\ \left\Vert\mathbf{x}\right\Vert_{\infty}\le\left\Vert\mathbf{x}\right\Vert_2\le\sqrt{n}\left\Vert\mathbf{x}\right\Vert_{\infty} \end{aligned} \]

向量序列的收敛性

在空间 $\mathbb{R}^n$ 中，向量序列 $\{\mathbf{x}^{(k)}\}$ 收敛于向量 $\mathbf{x}^*$ 的充要条件是存在范数 $\left\Vert\cdot\right\Vert$ 使得：

\[ \lim_{k\to\infty}\left\Vert\mathbf{x}^{(k)}-\mathbf{x}^*\right\Vert=0 \]

压缩映射

设有非空集合 $\mathbf{D}\subset\mathbb{R}^n$，对于映射 $\mathbf{f}:\mathbf{D}\to\mathbf{D}$，若存在范数$\left\Vert\cdot\right\Vert$ 和常数 $q\in[0,1)$ 使得对任意 $\mathbf{x},\mathbf{y}\in\mathbf{D}$ 都有

\[ \left\Vert \mathbf{f}(\mathbf{x})-\mathbf{f}(\mathbf{y})\right\Vert\le q\left\Vert \mathbf{x}-\mathbf{y}\right\Vert \]

则称 $\mathbf{f}$ 为 $\mathbf{D}$ 上的压缩映射。

Banach压缩映射原理

设 $\mathbf{D}\subset\mathbb{R}^n$ 为闭集，映射 $\mathbf{f}$为 $\mathbf{D}$ 上的压缩映射，则 $\mathbf{f}$ 在 $\mathbf{D}$ 上有唯一不动点 $\mathbf{x}$，使得 $\mathbf{f}(\mathbf{x})=\mathbf{x}$。

Proof.

设 $\mathbf{x}^{(0)}\in\mathbf{D}$，构造序列$\{\mathbf{x}^{(k)}\}$ 如下：

\[ \mathbf{x}^{(k+1)}=\mathbf{f}(\mathbf{x}^{(k)}),\quad k=0,1,2,\ldots \]

则对任意 $k\ge0$，有

\[ \left\Vert\mathbf{x}^{(k+1)}-\mathbf{x}^{(k)}\right\Vert=\left\Vert\mathbf{f}(\mathbf{x}^{(k)})-\mathbf{f}(\mathbf{x}^{(k-1)})\right\Vert\le q\left\Vert\mathbf{x}^{(k)}-\mathbf{x}^{(k-1)}\right\Vert \]

由此可得

\[ \left\Vert\mathbf{x}^{(k+1)}-\mathbf{x}^{(k)}\right\Vert\le q^k\left\Vert\mathbf{x}^{(1)}-\mathbf{x}^{(0)}\right\Vert \]

对于 $m>n\ge0$，有

\[ \left\Vert\mathbf{x}^{(m)}-\mathbf{x}^{(n)}\right\Vert\le\sum_{k=n}^{m-1}\left\Vert\mathbf{x}^{(k+1)}-\mathbf{x}^{(k)}\right\Vert\le\sum_{k=n}^{m-1}q^k\left\Vert\mathbf{x}^{(1)}-\mathbf{x}^{(0)}\right\Vert=\frac{q^n-q^m}{1-q}\left\Vert\mathbf{x}^{(1)}-\mathbf{x}^{(0)}\right\Vert \]

由于 $q\in[0,1)$，当 $n\to\infty$ 时

\[ \lim_{n\to\infty}\left\Vert\mathbf{x}^{(m)}-\mathbf{x}^{(n)}\right\Vert=0 \]

即序列 $\{\mathbf{x}^{(k)}\}$ 为 Cauchy 序列，故在 $\mathbb{R}^n$ 中收敛，设其极限为 $\mathbf{x}^*\in\mathbf{D}$，则由映射的连续性可得

\[ \mathbf{x}^*=\lim_{k\to\infty}\mathbf{x}^{(k+1)}=\lim_{k\to\infty}\mathbf{f}(\mathbf{x}^{(k)})=\mathbf{f}(\lim_{k\to\infty}\mathbf{x}^{(k)})=\mathbf{f}(\mathbf{x}^*) \]

即 $\mathbf{x}^*$ 为 $\mathbf{f}$ 的不动点。设存在不动点 $\mathbf{x}_1,\mathbf{x}_2$，则有：

\[ \left\Vert\mathbf{x}_1-\mathbf{x}_2\right\Vert=\left\Vert\mathbf{f}(\mathbf{x}_1)-\mathbf{f}(\mathbf{x}_2)\right\Vert\le q\left\Vert\mathbf{x}_1-\mathbf{x}_2\right\Vert \]

由于 $q\in[0,1)$，上式只在 $\mathbf{x}_1=\mathbf{x}_2$ 时成立，故不动点唯一。 $\square$

矩阵范数的定义

称 $\mathbb{R}^{n\times n}$ 上的一个函数 $\left\Vert\cdot\right\Vert$ 为范数，若满足：

非负性：$\left\Vert\mathbf{A}\right\Vert\ge0$, $\left\Vert\mathbf{A}\right\Vert=0$ 当且仅当 $\mathbf{A}=\mathbf{0}$。
齐次性：$\left\Vert\alpha\mathbf{A}\right\Vert=\left\vert \alpha \right\vert\left\Vert\mathbf{A}\right\Vert, \alpha\in\mathbb{R}$。
三角不等式：$\left\Vert\mathbf{A}+\mathbf{B}\right\Vert\le\left\Vert\mathbf{A}\right\Vert+\left\Vert\mathbf{B}\right\Vert$。
矩阵乘法不等式：$\left\Vert\mathbf{A}\mathbf{B}\right\Vert\le\left\Vert\mathbf{A}\right\Vert\cdot\left\Vert\mathbf{B}\right\Vert$。

常见的矩阵范数有：

列范数：$\left\Vert\mathbf{A}\right\Vert_{1}=\max\limits_{1\le j\le n}\sum_{i=1}^{n}\left\vert a_{ij} \right\vert$
行范数：$\left\Vert\mathbf{A}\right\Vert_{\infty}=\max\limits_{1\le i\le n}\sum_{j=1}^{n}\left\vert a_{ij} \right\vert$
谱范数：$\left\Vert\mathbf{A}\right\Vert_{2}=\sqrt{\lambda_{\max}(\mathbf{A}^T\mathbf{A})}$
F-范数：$\left\Vert\mathbf{A}\right\Vert_{F}=\sqrt{\sum_{i=1}^{n}\sum_{j=1}^{n}\left\vert a_{ij} \right\vert^2}$

矩阵范数的性质

算子范数

称向量范数导出的矩阵范数为算子范数，定义如下：

\[ \left\Vert\mathbf{A}\right\Vert=\max_{\mathbf{x}\ne \mathbf{0}}\frac{\left\Vert\mathbf{A}\mathbf{x}\right\Vert}{\left\Vert\mathbf{x}\right\Vert}=\max_{\left\Vert\mathbf{x}\right\Vert=1}\left\Vert\mathbf{A}\mathbf{x}\right\Vert \]

由定义可知算子范数是矩阵范数，且与向量范数相容：

\[ \left\Vert\mathbf{A}\mathbf{x}\right\Vert\le\left\Vert\mathbf{A}\right\Vert\cdot\left\Vert\mathbf{x}\right\Vert \]

矩阵范数的等价性

对于 $\mathbb{R}^{n\times n}$ 中的任意两种范数 $\left\Vert\mathbf{A}\right\Vert_{\alpha}$ 和 $\left\Vert\mathbf{A}\right\Vert_{\beta}$，都存在两个正数$c_1,c_2$，使得对任意 $\mathbf{A}\in\mathbb{R}^{n\times n}$ 都有

\[ c_1\left\Vert\mathbf{A}\right\Vert_{\alpha}\le\left\Vert\mathbf{A}\right\Vert_{\beta}\le c_2\left\Vert\mathbf{A}\right\Vert_{\alpha} \]

对于常用的矩阵范数，有如下关系：

$\frac 1n\left\Vert\mathbf{A}\right\Vert_{\infty}\le\left\Vert\mathbf{A}\right\Vert_{1}\le n\left\Vert\mathbf{A}\right\Vert_{\infty}$

Proof.

对于任意$a_{ij}\in\mathbf{A}$，有

\[ \left\vert a_{ij} \right\vert\le\left\Vert\mathbf{A}\right\Vert_{\infty} \]

则有

\[ \sum_{i=1}^{n}\left\vert a_{ij} \right\vert\le n\left\Vert\mathbf{A}\right\Vert_{\infty} \]

取最大值可得

\[ \left\Vert\mathbf{A}\right\Vert_{1}=\max_{1\le j\le n}\sum_{i=1}^{n}\left\vert a_{ij} \right\vert\le n\left\Vert\mathbf{A}\right\Vert_{\infty} \]

同理可得

$$ \left\Vert\mathbf{A}\right\Vert_{\infty}=\max_{1\le i\le n}\sum_{j=1}^{n}\left\vert a_{ij} \right\vert\le n\left\Vert\mathbf{A}\right\Vert_{1} $$ $\square$

$\frac{1}{\sqrt{n}}\left\Vert\mathbf{A}\right\Vert_{\infty}\le\left\Vert\mathbf{A}\right\Vert_{2}\le\sqrt{n}\left\Vert\mathbf{A}\right\Vert_{\infty}$

Proof.

先证明 $\left\Vert\mathbf{x}\right\Vert_{\infty}\le\left\Vert\mathbf{x}\right\Vert_{2}\le\sqrt{n}\left\Vert\mathbf{x}\right\Vert_{\infty}$：

对于任意 $x_i\in\mathbf{x}$，有 $\left\vert x_i \right\vert\le\left\Vert\mathbf{x}\right\Vert_{2}$，取最大值可得 $\left\Vert\mathbf{x}\right\Vert_{\infty}\le\left\Vert\mathbf{x}\right\Vert_{2}$。

对于任意 $x_i\in\mathbf{x}$，有 $\left\vert x_i \right\vert\le\left\Vert\mathbf{x}\right\Vert_{\infty}$，则有 $\left\vert x_i \right\vert^2\le\left\Vert\mathbf{x}\right\Vert_{\infty}^2$，对所有 $i$ 求和可得 $\left\Vert\mathbf{x}\right\Vert_{2}^2\le n\left\Vert\mathbf{x}\right\Vert_{\infty}^2$，即 $\left\Vert\mathbf{x}\right\Vert_{2}\le\sqrt{n}\left\Vert\mathbf{x}\right\Vert_{\infty}$。

由算子范数定义可得

\[ \left\Vert\mathbf{A}\right\Vert_{2}=\max_{\mathbf{x}\ne \mathbf{0}}\frac{\left\Vert\mathbf{A}\mathbf{x}\right\Vert_{2}}{\left\Vert\mathbf{x}\right\Vert_{2}}, \; \left\Vert\mathbf{A}\right\Vert_{\infty}=\max_{\mathbf{x}\ne \mathbf{0}}\frac{\left\Vert\mathbf{A}\mathbf{x}\right\Vert_\infty}{\left\Vert\mathbf{x}\right\Vert_{\infty}} \]

对于任意 $\mathbf{x}\ne \mathbf{0}$，有

\[ \frac{\left\Vert\mathbf{A}\mathbf{x}\right\Vert_2}{\left\Vert\mathbf{x}\right\Vert_2}\le\frac{\sqrt{n}\left\Vert\mathbf{A}\mathbf{x}\right\Vert_\infty}{\left\Vert\mathbf{x}\right\Vert_2}\le\frac{\sqrt{n}\left\Vert\mathbf{A}\mathbf{x}\right\Vert_\infty}{\left\Vert\mathbf{x}\right\Vert_\infty}\le\sqrt{n}\left\Vert\mathbf{A}\right\Vert_{\infty} \]

取最大值可得

\[ \left\Vert\mathbf{A}\right\Vert_{2}\le\sqrt{n}\left\Vert\mathbf{A}\right\Vert_{\infty} \]

对于任意 $\mathbf{x}\ne \mathbf{0}$，有

\[ \frac{\left\Vert\mathbf{A}\mathbf{x}\right\Vert_\infty}{\left\Vert\mathbf{x}\right\Vert_\infty}\le\frac{\left\Vert\mathbf{A}\mathbf{x}\right\Vert_2}{\left\Vert\mathbf{x}\right\Vert_\infty}\le\sqrt{n}\frac{\left\Vert\mathbf{A}\mathbf{x}\right\Vert_2}{\left\Vert\mathbf{x}\right\Vert_2}\le\sqrt{n}\left\Vert\mathbf{A}\right\Vert_{2} \]

取最大值可得

\[ \left\Vert\mathbf{A}\right\Vert_{\infty}\le\sqrt{n}\left\Vert\mathbf{A}\right\Vert_{2} \]

$\square$