范数

Math 范数

创建时间:2024-06-23 16:02

阅读:

范数

范数

范数¹是从实数或复向量空间到非负实数的函数,为向量空间中所有向量赋予非负的长度或大小.满足定义如下:

三角不等式,Triangle inequality: $p(x+y)\leq p(x)+p(y),\forall x,y\in X$
齐次性,Absolute homogeneity: $p(sx)=|s|p(x),\forall x\in X \forall, s \in \mathbb{R}$, 标量缩放
正定性,Positive definiteness: $p(x)\ge 0,\forall x\in X,\text{if }p(x)=0\text{ then }x=0$

p范数

$p>1,p\in \mathbb{R}$, 对于向量$\mathbf{x}=(x_1,\cdots,x_n)$, p范数定义如下

$|\mathbf{x}|_p:=\left(\sum_{i=1}^n|x_i|^p\right)^{1/p}$

$p=1$对应1-范数, $|\boldsymbol{x}|_1:=\sum_i^n|x_i|$.也叫曼哈顿距离, 与出租车在矩形街道网格（如纽约曼哈顿区）中从起点到终点必须行驶的距离有关
$p=2$对应2-范数, 也叫欧几里得范数, $|\boldsymbol{x}|_2:=\sqrt{x_1^2+\cdots+x_n^2}$
$p=\infty$对应$\infty$范数,$|\mathbf{x}|_\infty:=\max\left(\left|x_1\right|,\ldots,\left|x_n\right|\right)$. 简单理解就是幂的增长非常快,$p\to \infty$时最大的$|x_i|$起主导作用,其他项可忽略.得到最后的最大值的绝对值.

矩阵范数

和向量范数类似满足如下性质

正定$||A||\ge 0$, $||A||=0\Longleftrightarrow A=0_{m\times n}$
线性, $||\alpha A||=\alpha ||A||$
三角不等性, $||A+B||\le ||A||+||B||$
相容性, $||AB||\le ||A||||B||$

诱导范数

诱导范数衡量矩阵$A$对向量变换后得到新新向量,对应向量范数最大可能增长的倍数

$\begin{aligned} \|A\|_{\alpha,\beta}=\sup\left\{\frac{\|Ax\|_\beta}{\|x\|_\alpha}:x\in K^n\mathrm{~with~}x\neq0\right\} \end{aligned}$

p范数的诱导范数
$|A|_p=\sup_{x\neq0}\frac{|Ax|_p}{|x|_p}$

其中$sup$表示取上界

1-范数诱导矩阵范数, $||A||_1=\sup_{x\ne 0} \frac{||Ax||_1}{||x||_1} =\max_{1\leq j\leq n}\sum_{i=1}^m|a_{ij}|$.
证明如下
$||Ax||_1=||\sum^n_{i=1}x_ia_i||_1\le \sum^n_{i=1}||x_ia_i||_1=\sum^n_{i=1}|x_i|||a_i||_1\le \max_{1\le j\le n}(||a_j||_1)\cdot \sum^n_{i=1}|x_i|$
2-范数诱导矩阵范数, $|A|_2=\sqrt{\lambda_{\max}\left(A^TA\right)}=\sigma_{\max}(A)$, 即$A^TA$最大特征值得平方根或者$A$的最大奇异值,$||Ax||_2^2=x^TA^TAx=x^TQ\Lambda Q^Tx\le \lambda_{max}x^Tx$ 可证.如果是复数,则使用共轭转置
$\infty$-范数诱导矩阵范数, $|A|_\infty=\max_{1\leq i\leq m}\sum_{j=1}^n|a_{ij}|$. 证明如下
$||Ax||_{\infty}=\max_{i}|\sum^m_{j=1}a_{ij}x_j|\le \max_{i}\sum^m_{j=1}|a_{ij}x_j|\le \max_{i}\sum^m_{j=1}|a_{ij}||x_j|$
以及$\sum^m_{j=1}|a_{ij}||x_j|\le \max_i|x_i|\cdot \sum^m_{j=1}|a_{ij}|=|x|_1\cdot \sum^m_{j=1}|a_{ij}$

条件数

函数的条件数衡量函数的输出值在输入参数的微小变化下可以变化多少,例如与线性方程 $Ax = b$ 关联的条件数给出了近似解 $x$ 的不精确程度的界限(输入$b$,输出$x=A^{-1}b$)
观测值$b$有较小的偏差对应方程,$A(x+\delta x)=b+\delta b$,即$A\delta x=\delta b$,则有输出变化率相对输入变化率
$e=\frac{\frac{||\delta x||}{||x||} }{\frac{||\delta b||}{||b||} }=\frac{||\delta x||}{||\delta b||}\frac{||b||}{||x||}$
上界$e=\frac{||\delta x||}{||\delta b||}\frac{||b||}{||x||}=\frac{||A^{-1}\delta b||}{||\delta b||}\frac{||Ax||}{||x||}\le ||A^{-1}||||A||$,下界$e=\frac{||\delta x||}{||\delta b||}\frac{||b||}{||x||}=\frac{||\delta x||}{||A\delta x||}\frac{||b||}{||A^{-1}b||}\le \frac{1}{||A^{-1}||||A||}$

定义条件数

$\kappa(A)=\begin{Vmatrix}A\end{Vmatrix}\begin{Vmatrix}A^{-1}\end{Vmatrix}$

得到

$\begin{aligned}\frac{1}{\kappa(A)}\frac{\|\delta b\|}{\|b\|}\leq\frac{\|\delta x\|}{\|x\|}\leq\kappa(A)\frac{\|\delta b\|}{\|b\|}\end{aligned}$

当条件数为10时，观测值变化10%，会导致解变化范围[1%,100%]²
条件数依赖范数的选择,当选择2-范数时

$\kappa(A)=||A||_2||A^{-1}||_2=\frac{\sigma_{max}}{\sigma_{min}}$

其中$\sigma_{max}, \sigma_{min}$分别为$A$的最大最小奇异值

¹. https://en.wikipedia.org/wiki/Norm_(mathematics) ↩

². https://zhuanlan.zhihu.com/p/91393594 ↩

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以邮件至 yangbenbo@whu.edu.cn