向量及矩阵范数

文章发布时间:

最后更新时间:

向量范数

定义： 设\(X\in \R^n\),若有非负实数\(||X||\)满足: - \(||X||\geq 0\),且\(||X||=0\Leftrightarrow X=0\)(非负性,强制性) - \(||\lambda X||=|\lambda|\cdot||X||\)(正齐次性) - \(||X+Y||\leq||X||+||Y||\)(三角不等式) 则称\(||X||\)为向量\(X\)的范数.

常用的几种范数 若\(X=(x_1,x_2,\cdots,x_n)^T\) - \[||X||_1=\sum_{i=1}^{n}|x_i|\] - \[||X||_{\infty}=\max_{1\leq i\leq n}|x_i|\] - \[||X||_2=\sqrt{\sum_{i=1}^{n}|x_i|^2},\quad ||X||^2_2=X^TX\]

定理:(范数的连续性定理) 向量范数\(||X||\)为关于\(X\)每个分量的一致连续函数.

证明: 只需证明\(\forall \epsilon>0, \exist\delta=\delta(\epsilon)\),当\(\Delta x_i\)满足\(|\Delta x_i|<\delta\)时,有\(|\,||X+\Delta X||-||X||\,|<\epsilon\) 事实上,由逆三角不等式有, \[|\,||X+\Delta X||-||X||\,|<||X+\Delta X-X||<||\Delta X||\] 另一方面, \[||\Delta X||=||(\Delta x_1,\Delta x_2,\cdots,\Delta x_n)^T||=||\Delta x_1e_1+\Delta x_2e_2+\cdots+\Delta x_ne_n||\] \[\leq||\Delta x_1e_1||+||\Delta x_2e_2||+\cdots+||\Delta x_ne_n|| <n\delta\] 其中, \[e_2=(0,1,\cdots,0)\] 以此类推

定理:(范数等价性定理) \(\R^n\)中任何范数都等价,即若有范数\(R_1(x)\)和\(R_2(x)\),则 \[\exist m,M>0,s.t. \quad m\leq \frac{R_1(x)}{R_2(x)}\leq M\]

证明: 记\(S=\{X|R_2(X)=1\}\),显然S为有界闭集,则连续函数\(R_1(X)\)在S上可以达到最大(小)值,记为, \[m=\min R_1(X), \quad M=\max R_1(X)\] 对 \[\forall X\neq 0\quad \frac{X}{R_2(X)}\in S\] 且 \[\frac{R_1(X)}{R_2(X)}=R_1(\frac{X}{R_2(X)})\] 故有, \[m<\frac{R_1(X)}{R_2(X)}=R_1(\frac{X}{R_2(X)})<M\]

定义: 若\(\{X^{(m)}\}_{m=1}^{\infty}\) 为\(\R^n\)上的向量序列,如果\(\exist \alpha\in\R^n,\quad s.t. \lim_{m\rightarrow\infty}||X^{(m)}-\alpha||=0\)则称,序列\(\{X^{(m)}\}_{m=1}^{\infty}\)收敛于\(\alpha\).

定理: 向量序列\(\{X^{(m)}\}_{m=1}^{\infty}\)收敛等价于每个分量收敛.即 \[\lim_{m\rightarrow\infty}||X^{(m)}-\alpha||= \Leftrightarrow \lim_{m\rightarrow\infty}||x_i^{(m)}-\alpha||=\alpha_i,\forall i\]

可用1范数证得.

矩阵范数和条件数

矩阵范数

定义: 若\(A\in \R^{m\times n}\)满足: - （非负性） - （正齐次性） - （三角不等式） - (矩阵范数相容性) \[||AB||\leq||A||||B||\]

定义: \[||A||=\sup_{X\in \R^{n},X\neq 0}\frac{||AX||}{||X||}=\sup_{X\in \R^n,||X||=1}||AX||\] 由定义显然可以推得,(证明是从定义显然得到的) \[||AX||\leq||A||||X||,X\in\R^{n}\] 即,矩阵向量范数相容. 另外,由这个定义也可以推得,矩阵范数的相容性 ,只要令\(X'=BX\),显然\(X'\)还是个向量.用矩阵向量范数的相容性,得 \[||AX'||\leq||A||||X'||\leq||A||\cdot||B||\cdot||X||,X'\in\R^{n+1}\] 即,得, \[\frac{||ABX||}{||X||}\leq||A||\cdot||B||\] 由\(X\)的任意性, \[\sup_{X\neq 0}{\frac{||ABX||}{||X||}}\leq||A||\cdot||B||\] 故, \[||AB||=\sup_{X\neq 0}{\frac{||ABX||}{||X||}}\leq||A||\cdot||B||\]

定理: 矩阵范数是关于\(n\times n\)个元素的一致连续函数.

定理: 矩阵范数都等价.(只要不是计算题,不必过分关心是什么范数)

常用的矩阵范数

  • 列和范数 \[||A||_1=\max_{1\leq j\leq n}\sum_{i=1}^{n}|a_{ij}|\]
  • 行和范数 \[||A||_{\infty}=\max_{1\leq i\leq n}\sum_{j=1}^{n}|a_{ij}|\]
  • 谱范数 \[||A||_2=\sqrt{\rho(A^*A)}\] 其中 \[A^*=A^T,\rho(A)=\max_{i}|\lambda_i(A)|\]
  • Frobenius范数 \[||A||_F=(\sum_{j=1}^{n}\sum_{i=1}^{n}|a_{ij}|^2)^{\frac{1}{2}}\]

定理:(列和范数) 设\(A=(a_{ij})_{n\times n}\),则 \[||A||_1=\max_{1\leq j\leq n}\sum_{i=1}^{n}|a_{ij}|\]

Proof: 根据矩阵范数定义 \[||A||_1=\sup_{X\in \R^{n},X\neq 0}\frac{||AX||_1}{||X||_1}\] 记\(Y=AX,y_i=\sum_{j=1}^{n}a_{ij}x_{j}\),于是 \[||AX||_1=||Y||_1=\sum_{i=1}^{n}|y_i|=\sum_{i=1}^{n}|\sum_{j=1}^{n}a_{ij}x_{j}|\] \[\leq \sum_{i=1}^{n}\sum_{j=1}^{n}|a_{ij}||x_{j}|=\sum_{j=1}^{n}\sum_{i=1}^{n}|a_{ij}||x_{j}|\] 记\(c_j=\sum_{i=1}^{n}|a_{ij}|\),于是, \[\sum_{j=1}^{n}\sum_{i=1}^{n}|a_{ij}||x_{j}|\leq ||C||_{\infty}||X||_1\] 其中, \[||C||_{\infty}=\max_{1\leq j\leq n}|c_j|=\max_{1\leq j\leq n}|\sum_{i=1}^{n}|a_{ij}||\] 即, \[\frac{||AX||_1}{||X||_1}\leq||C||_{\infty}\] 那么有, \[||A||_1=\sup_{X\neq 0}\frac{||AX||_1}{||X||_1}\leq||C||_{\infty}=\max_{1\leq j\leq n}|\sum_{i=1}^{n}|a_{ij}||\]

另一方面, 记,(第k列达到最大) \[||A||_1=\sum_{i=1}^{n}|a_{ik}|\] 取\(X=e_k=(0,)\)则, \[||A||_1=\sup{||AX||_1}\geq ||Ae_k||_1=\sum_{i=1}^{n}|a_{ik}|=\max_{1\leq j\leq n}\sum_{i=1}^{n}|a_{ij}|\] 命题得证.

定理:(行和范数) 设\(A=(a_{ij})_{n\times n}\),则 \[||A||_{\infty}=\max_{1\leq i\leq n}\sum_{j=1}^{n}|a_{ij}|\]

Proof: 由矩阵范数定义, \[||A||_{\infty}=\sup_{X\neq 0}\frac{||AX||_{\infty}}{||X||_{\infty}}\] 考虑\(||AX||_{\infty}\), 记\(Y=AX,y_i=\sum_{j=1}^{n}a_{ij}x_{j}\),于是 \[||AX||_{\infty}=||Y||_{\infty}=\max_{1\leq i \leq n}|y_i|=\max_{1\leq i \leq n}{|\sum_{j=1}^{n}a_{ij}x_{j}|}\leq \max_{0\leq i\leq n}\sum_{j=1}^{n}|a_{ij}||x_{j}|\] \[\leq\max_{0\leq i\leq n}||d||_1||x_{j}||_{\infty}\] 其中, \[||d||_{1}=\sum_{j=1}^{n}|d_j|=\sum_{j=1}^{n}|a_{ij}|\] 即有, \[||A||_{\infty}=\sup{\frac{||AX||_{\infty}}{||X||_{\infty}}}=\max_{1\leq i\leq n}\sum_{j=1}^{n}|a_{ij}|\]

另一方面， 若 \[\max_{1\leq i\leq n}\sum_{j=1}^{n}|a_{ij}|=\sum_{j=1}^{n}|a_{kj}|\] 取\(\xi=(\xi_1,\cdots,\xi_n)^T\),其中, \[\xi_j=\begin{cases} 1,\quad 若a_{kj}\geq 0\\ -1,\quad 若a_{kj}<0 \end{cases}\] 显然\(||\xi||_{\infty}=1\), 又由, \[||A||_{\infty}=\sup_{||X||_{\infty}=1}||AX||_{\infty}\geq ||A\xi||_{\infty}=\max_{1\leq i\leq n}\sum_{j=1}^{n}|a_{ij}\xi_j|\] (下面是关键部分) 注意:(1)\(a_{kj}\)与\(\xi_j\)同号;(2)\(\xi_j\)只影响\(a_{kj}\)的符号不影响绝对值 \[\max_{1\leq i\leq n}\sum_{j=1}^{n}|a_{ij}\xi_j|=\sum_{j=1}^{n}|a_{kj}\xi_j|=\sum_{j=1}^{n}|a_{kj}|=\max_{1\leq i\leq n}\sum_{j=1}^{n}|a_{ij}|\]

引理: 若\(A\in C^{n \times n}\),则 1. \(A^*A\)为半正定的Hermit矩阵 2. 若\(A\)为Hermit矩阵,即\(A^*=A\),则其特征根是实的 3. 若\(A\)为Hermit矩阵,则不同特征值的特征向量正交

Proof:

(1)由Hermit矩阵定义,有\((A^*A)^*=A^*(A^*)^*=A^*A\)

对\(\forall X\in C^n\),有 \[X^*(A^*A)X=X^*A^*AX=(AX)^*AX=(AX,AX)=||AX||_2^2\geq 0 \]

(2)记\(AV=\lambda V\),两边取共轭转置,得 \[V^*A^*=(AV)^*=(\lambda V)^*=\lambda^*V^*\] 上式两边右乘\(V\)得 \[V^*A^*V=\lambda^*V^*V\] 左边有 \[V^*A^*V=\lambda V^*V\] 于是可得, \[(\lambda-\lambda^*)V^*V=(\lambda-\lambda^*)||V||^2_2=0\] 故有, \(\lambda = \lambda^*=\bar{\lambda}\),即\(\lambda\)为实数.

(3)记\(AV=\lambda V,\quad AW=\mu W\)

对\(AW=\mu W\),左乘\(V^*\),有 \[V^*AW=V^*\mu W=\mu V^* W\] 等式左边, \[V^*AW=(A^*V)^*W=(AV)^*W=\lambda^*V^*W=\lambda V^*W\] 故有, \[(\lambda-\mu)V^*W=0\] 由于\(\lambda\neq\mu\),故有, \[V^*W=(V,W)=0\]

一个简单性质 \[(X,AY)=(A^*X,Y)\] Proof: \[(A^*X,Y)=(A^*X)^*Y=X^*AY=(X,AY)\]

下面证明2范数.

定理:(2范数 谱范数) 设\(A=(a_{ij})_{n\times n}\),则 \[||A||_2=\sqrt{\rho(A^*A)}\]

Proof: 记半正定的Hermit矩阵\(A^*A\)的实特征根为 \[\mu_1,\mu_2,\cdots,\mu_n\] \(A^*A\)有一组完备的单位正交的特征向量 \[\varphi_1,\varphi_2,\cdots,\varphi_n\] 则,对\(\forall X\in C^{n}\),\(X=\sum^{n}_{i=1}t_i\varphi_i\)

由 \[||A||_2=\sup_{||X||_2=1}{||AX||_2}\] 可取\(||X||_2=1\),则, \[1=||X||_2^2=(X,X)=(\sum^{n}_{i=1}t_i\varphi_i,\sum^{n}_{i=1}t_i\varphi_i)=\sum^{n}_{i=1}|t_i|^2||\varphi_i||_2^2=\sum^{n}_{i=1}|t_i|^2\] 由简单性质2, \[ \begin{split} ||X||_2=&\sqrt{(AX,AX)}=\sqrt{(A^*AX,X)}=\sqrt{(A^*A\sum^{n}_{i=1}t_i\varphi_i,\sum^{n}_{i=1}t_i\varphi_i)}\\=&\sqrt{(\sum^{n}_{i=1}t_iA^*A\varphi_i,\sum^{n}_{i=1}t_i\varphi_i)}=\sqrt{(\sum^{n}_{i=1}t_i\mu_i\varphi_i,\sum^{n}_{i=1}t_i\varphi_i)}\\ =&\sqrt{\sum^{n}_{i=1}\mu_i|t_i|^2}\leq\sqrt{\mu_{max}\sum^{n}_{i=1}|t_i|^2}=\sqrt{\mu_{max}} \end{split} \] 则, \[||A||_2=\sup_{||X||_2=1}||AX||_2\leq \sqrt{u_{max}}=\sqrt{\rho(A^*A)}\]

另一方面,取\(x=\varphi_n\),则\(||\varphi_n||_2=1\)(\(\varphi_n\)为\(\mu_{max}\)对应的特征向量) \[ \begin{split} ||A\varphi_n||_2=&\sqrt{(A\varphi_n,A\varphi_n)}=\sqrt{(A^*A\varphi_n,\varphi_n)}=\sqrt{(\mu_{max}\varphi_n,\varphi_n)}\\ =&\sqrt{u_{max}}=\sqrt{\rho(A^*A)} \end{split} \] 得, \[||A||_2=\sup_{||X||_2=1}||AX||_2\geq ||A\varphi_n||_2\geq \sqrt{u_{max}}=\sqrt{\rho(A^*A)}\]

推论: - \(\rho(A)\leq||A||\) - 若\(A\)是正规阵,即\(AA^*=A^*A\) ,则\(\rho(A)=||A||_2\)

Proof:

  1. 若\(A\varphi=\lambda\varphi\),则, \[||A||=\sup_{||X||\neq 0}\frac{||A\varphi||}{||X||}\geq \frac{||A\varphi||}{||\varphi||}=\frac{||\lambda\varphi||}{||\varphi||}=\frac{|\lambda|||\varphi||}{||\varphi||}=|\lambda|\] 由\(\lambda\)的任意性, \[ \max_{i}|\lambda|=\rho(A)\leq ||A|| \]
  2. 当\(A\)是正规阵时,可以进行酉对角化,即存在酉矩阵\(U^*U=UU^*=I\),使得, \[ U^{-1}AU=\Lambda \] \[ \begin{split} A^*A&=(U\Lambda U^{-1})^*U\Lambda U^{-1}\\ &=U^{**}\Lambda^* U^{*}U\Lambda U^{-1}\\ &=U\Lambda^*\Lambda U^{-1}\\&=U^{**}\begin{pmatrix} |\lambda_1|^2&&\\ &\ddots&\\ && |\lambda_n|^2\\ \end{pmatrix} U^{-1} \end{split} \] 于是\(\rho(A^*A)=\rho^2(A)\) \[||A||_2=\sqrt{\rho(A^*A)}=\sqrt{\rho^2(A)}=\rho(A)\]

矩阵的条件数与误差分析

定义: 若\(A\)非奇异,称 \(Cond(A)=||A||\cdot||A^{-1}||\) 为\(A\)的条件数.

条件数越大,误差放大的倍数就越大,矩阵的稳定性就越差,受到微小扰动对计算结果的影响就越大.

  • 若\(A\)的条件数较大,\(Cond(A)=O(n^2)\),称\(AX=b\)病态的.
  • \(1=||I||=||A^{-1}A||\leq ||A^{-1}||||A||=Cond(A)\)

引理: - 若\(||B||\leq 1\),则\(I+B\)非奇异,且 \[||(I+B^{-1}||\leq\frac{1}{1-||B||}\] - 若\(||A^{-1}||\cdot||\delta A||<1\),则\(A+\delta A\)可逆.

Proof: (1).用反证法.若\(I+B\)奇异,则有\(X\neq 0\)满足, \[(I+B)X=0\] 即, \[BX=-X\] 则\(B\)有一个特征值为\(-1\),那么 \[\rho(B)\geq 1\] 但是我们有, \[\rho(B)\leq ||B||<1\] 矛盾.故\(I+B\)非奇异. 记\(C=(I+B)^{-1}\),则, \[ \begin{split} 1&=||I||=||(I+B)C||\\ &=||C+BC||\geq ||C||-||BC||\\ &=||C||-||B||||C||=(1-||B||)||C|| \end{split} \] 于是就有, \[ ||C||=||(I+B)^{-1}||\leq\frac{1}{1-||B||} \]

(2)注意到, \[ A+\delta A=A(I+A^{-1}\delta A) \] 记\(B=A^{-1}\delta A\),且注意到, \[ ||B||\leq||A^{-1}||\cdot||\delta A||<1 \] 故\(I+B\)可逆,并且有, \[||(I+B)^{-1}||\leq\frac{1}{1-||B||}\leq \frac{1}{1-||A^{-1}||||\delta A||}\] 以下考虑\(A\rightarrow A+\delta A\),或\(b\rightarrow b+\delta b\)对 \[AX=b\] 解的影响,

  • \(A\rightarrow A+\delta A\), 而\(b\)精确. \[ (A+\delta A)(X+\delta X)=b \Rightarrow \delta A X+A\delta X+\delta A\delta X=0 \] \[ \Rightarrow (A+\delta A)\delta X=A(I+B)\delta X=-\delta A X \] \[ \Rightarrow \delta X =-A^{-1}(I+B)^{-1}(\delta A) X \] 于是, \[ ||\delta X||\leq||A^{-1}||\cdot||(I+B)^{-1}||\cdot||\delta A||||X|| \] \[ \begin{split} \Rightarrow \frac{ ||\delta X||}{ ||X||}\leq& ||A^{-1}||\cdot||(I+B)^{-1}||\cdot||\delta A||\\ \leq & \frac{ ||A^{-1}||||\delta A||}{1-||B||}\leq \frac{ ||A^{-1}||||\delta A||}{1-||A^{-1}||||\delta A||}\\ = & \frac{ ||A||||A^{-1}||\frac{||\delta A||}{||A||}}{1-||A||||A^{-1}||\frac{||\delta A||}{||A||}}\\ =&\frac{Cond(A)\frac{||\delta A||}{||A||}}{1-Cond(A)\frac{||\delta A||}{||A||}} \end{split} \] 一般有\(||\delta A||<<1\),此时不等式右边分母约等于1,于是,

    $$ Cond(A)

    $$

  • \(b\rightarrow b+\delta b\), 而\(A\)精确. \[A(X+\delta X)=b+\delta b\] 于是有, \[ A\delta X=\delta b \Rightarrow \delta X=A^{-1}\delta b \] 且, \[ ||\delta X||=||A^{-1}\delta b||\leq ||A^{-1}||||\delta b|| \] 另一方面, \[||b||=||AX||\leq ||A||||X||\] 则, \[||X||\geq\frac{||b||}{||A||}\] 故有, \[ \frac{||\delta X||}{||X||}\leq\frac{||A^{-1}||||\delta b||}{\frac{||b||}{||A||}}=Cond(A)\frac{||\delta b||}{||b||} \]

例题:行列式小,条件数不一定大

收敛矩阵（第三章铺垫）

定义: \(\{A^{(m)}\}_{m=1}^{\infty}\)为\(\R^{n\times m}\)上的矩阵序列,若, \[ \lim_{m\rightarrow \infty}||A^{(m)}-A||=0 \] 则称,\(\{A^{(m)}\}_{m=1}^{\infty}\)是收敛的,且\(A\)为序列的极限.

定理: 记\(A^{(m)}=(a_{ij}^{(m)})_{n\times n}\),则\(\{A^{(m)}\}_{m=1}^{\infty}\)收敛, 当且仅当, \[\lim_{m\rightarrow \infty}a_{ij}^{(m)}=a_{ij}\]

推论: 记\(A^{(m)}=(a_{ij}^{(m)})_{n\times n}\),则\(\{A^{(m)}\}_{m=1}^{\infty}\)收敛到零矩阵,则, \[\lim_{m\rightarrow \infty}a_{ij}^{(m)}=0\]

定义:(收敛矩阵) 记\(A^2=AA,A^3=A^2A,\cdots\),若\(A^k\)收敛到零矩阵,则称\(A\)为收敛矩阵.

定理: \(A\)为收敛矩阵\(\quad \Leftrightarrow\quad \rho(A)<1\)

证明: 由Jordan对角化,存在可逆矩阵\(S\),使得, \[ A=S^{-1} \begin{pmatrix} J_1&&\\ &\ddots&\\ && J_r\\ \end{pmatrix} S \] 其中,Jordan块为, \[ J_i= \begin{pmatrix} \lambda_i&1&&\\ &\ddots&\ddots&\\ &&\ddots&1\\ &&& \lambda_i\\ \end{pmatrix}_{l_i\times l_i} \quad \sum_{i=1}^{r}l_i=n \] 则, \[ A^k=S^{-1} \begin{pmatrix} J_1^k&&\\ &\ddots&\\ && J_r^k\\ \end{pmatrix} S \] 其中,!!!!!!!!!!! \[ J_i= \begin{pmatrix} \lambda_i&1&&\\ &\ddots&\ddots&\\ &&\ddots&1\\ &&& \lambda_i\\ \end{pmatrix}_{l_i\times l_i} \quad \sum_{i=1}^{r}l_i=n \]

  • 对角元: \(A^k\)收敛到零矩阵\(\Leftrightarrow|\lambda_i|<1\)
  • 非对角元(趋于0):由\(C_k^j=\frac{}{j!}\approx k^r\),非对角元, \[ \]

推论: 若\(||A||<1\),则\(A\)为收敛矩阵.(充分条件,上面的是充要)

这是因为,\(\rho(A)\leq ||A||\)

例题: 设\(A,B\in\R^{n\times n}\),试证,当\(A,B\)非奇异时, - \(Cond(A^{-1})=Cond(A)\) - \(Cond(\alpha A)=Cond(A),\alpha\in\R\) - \(Cond(AB)\leq Cond(A)Cond(B)\)

证明: 第一条显然.

第二条, \[Cond(\alpha A) =||\alpha A||||\alpha A^{-1}|| =|\alpha|||A||\frac{1}{|\alpha|}||A^{-1}|| =Cond(A),\alpha\in\R\] 第三条, \[ Cond(AB)=||AB||||B^{-1}A^{-1}||\leq ||A||||A^{-1}||||B||||B^{-1}||=Cond(A)Cond(B) \]

≡