Linear Algebra Done Left - Vanilla Matrix Analysis

关于为什么最近开了这个坑：

因为发现学校里教的线代毕竟是比较理论的东西，教的计算方法写成程序拿来实战百分之百是会被残酷的数据碾爆的。毕竟现实中的矩阵一多半是大而优雅或者小而丑陋或者大而丑陋，哪个都不是大一线代课上讲的一个小小的高斯消元就能解决的。要么时间爆炸，要么数值误差爆炸，至少有一个适合你。

另一方面，计算机图形学中，无论是物理模拟还是几何处理都不可避免地要与大规模的矩阵打交道，因此很有必要建立自己的数值线性代数库，学习矩阵计算的方法。

这是线性代数剩下的还需要学习的内容。 这个系列博客会用来记录数值线性代数中的一些理论与应用。

没错你已经发现了这不是讲线性代数的而是讲数值线性代数的

关于数值线代在网上并没有找到什么特别猛料的网课（也可能是我手段不足？），不过$\text{MIT}$的$\text{Strang}$老爷子新开的"数据分析中的矩阵方法"还是非常不错，就是太简单了，属于是讲给宝宝的矩阵计算入门特别适合下饭或者赶路。这一次我们参考数值线代的圣经 Matrix Computation 来学习。

$\text{2. 矩阵分析基础}$

很多东西在别的地方都有提过，无论是数学物理方法还是数值分析都有讲过向量范数，矩阵范数等等的概念，这些概念在此当然不会再全部扯一遍当然在那些地方我也不会再扯一遍。这里只是过一些简单的结论和话题。这一章的主要目的应当还是掌握必备的误差估计的知识。

$\text{2.1. First Things First}$

很多线性代数里老生常谈的东西这里也就不多加叙述了。但是有些东西，学院派的线性代数可能不怎么管它，在数值方法里却还是有点用处的。

$\text{Sherman-Morrison-Woodbury公式}$

对于可逆矩阵$A, B$来说，有$B^{-1}=A^{-1}-B^{-1}(B-A)A^{-1}$。验证起来还是很容易的。

没人会蠢到用这个东西去求逆，但是如果我们用$A+UV^T$代替这里的$B$，就可以得到 $\text{Sherman-Morrison-Woodbury}$公式:

$$(A+UV^T)^{-1}=A^{-1}-(A+UV^T)^{-1}UV^TA^{-1}=A^{-1}-A^{-1}(E+UV^TA^{-1})^{-1}UV^TA^{-1}$$

$$=A^{-1}-A^{-1}(U^{-1}+U^{-1}UV^TA^{-1})^{-1}V^TA^{-1}=A^{-1}-A^{-1}(U^{-1}+V^TA^{-1})^{-1}V^TA^{-1}$$

$$=A^{-1}-A^{-1}U(E_k+V^TA^{-1}U)^{-1}V^TA^{-1}$$

这里唯一要运用的就是矩阵乘积的逆的性质，并不难（但是我居然还想了一会儿，丢人）。

这个公式看起来更丑了，但是它好就好在$U,V$可以不是方阵，事实上$U,V\in \mathbb{R}^{n\times k}$就可以，而$k$可以是任意的（对于任意的$k$的情况可以由方阵情况推出）。特别的我们取$k=1$，这时$U,V$退化为向量$u, v$。取$\alpha=1+v^TA^{-1}u$就有

$$(A+uv^T)^{-1}=A^{-1}-\frac{1}{\alpha}A^{-1}uv^TA^{-1}$$

这个式子被称为$\text{Sherman-Morrison}$公式，很有用，在$\text{Strang}$老爷子的课里也讲过这个东西，可以用于对矩阵的低秩扰动的求逆，后者就更加有用了。

$\text{矩阵和向量范数}$

向量范数再稍微提一个性质也就是著名的赫尔德不等式：

$$|x^Ty|\le \parallel x \parallel_p\parallel y\parallel_q,\frac{1}{p}+\frac{1}{q}=1$$

首先说明一点，在有限维空间中，范数都是等价的，因此这里我们取各种乱七八糟的范数，数值效果可能有区别，不过至少收敛性上都是没啥问题的。但是在无穷维空间上就没那么幸运了，这些事情就需要留给犯寒泛函分析，这里当然就不提了。

$\text{Frobenius}$范数自不必多说，这里再简单回顾一下矩阵的算子范数。

矩阵$A$的算子范数定义为$\parallel A\parallel=\max\limits_{\parallel x\parallel=1}\parallel Ax\parallel$，当然，这是和选取的向量范数有关的。

关于算子范数有一个挺不错的性质：

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

这对任意的矩阵$A,B$都成立，当然实际上考虑到矩阵范数作为函数，对于不同形状的矩阵是不同的，这个不等式比看起来的还是要更好，它甚至能揭示出三个完全不一样的函数的关系。

还有另外一种矩阵范数的定义，更宽泛：

$$\parallel A\parallel_{\alpha,\beta}=\max\limits_{\parallel x\parallel_\alpha = 1}\parallel Ax\parallel_\beta$$

$\text{矩阵的2-范数}$

$\text{Thm.}$ 存在单位向量$x$使得$A^TAz=\mu^2x$,$\mu = \parallel A\parallel_2$

这个定理的证明还是得依据定义来。。。假设存在这样的$z$就一定有$\parallel Az\parallel_2=\parallel A\parallel_2$

令$g(x)=\frac{\parallel Ax\parallel_2^2}{2\parallel x\parallel_2^2}$

$z$最小化$g(x)$于是就可以求梯度并且令其为$0$，最终能得到

$$A^TAz=(z^TA^TAz)z$$

比较一下就知道$\parallel Az\parallel_2=\mu$

这其实揭示了一个事情:$\parallel A\parallel_2^2$是$p(\lambda)=\det(A^TA-\lambda I)$的零点，也就是说
$\parallel A\parallel_2=\sqrt{\lambda_{\max}(A^TA)}$

$\text{逆矩阵的一些误差估计}$

$\text{Lemma.}$ 设$F\in \mathbb{R}^{n\times n},\parallel F\parallel_p < 1$，则$I-F$可逆，且有

$$\parallel (I-F)^{-1}\parallel_p \le \frac{1}{1-\parallel F\parallel}$$

可逆性的证明是经典的习题，因为我们能发现$I-F$是一个对角占优矩阵，对角占优矩阵是可逆的。不过这里还有另一个结论：

$$(I-F)^{-1}=\sum\limits_{k=0}^\infty F^k$$

这么写当然是OK的，因为$F$的范数小于$1$，这一定是收敛的。

两侧取范数，右边变成无穷等比数列求和，就得到了范数不等式。

这个引理表明了另一个事情：

$$\parallel (I-F)^{-1}-I\parallel_p \le \frac{\parallel F\parallel_p}{1-\parallel F \parallel_p}$$

考虑$\parallel F\parallel_p \sim O(\epsilon)$且$\epsilon \ll 1$，这意味着，如果我们对单位矩阵进行$O(\epsilon)$的扰动，其逆的变化也是$O(\epsilon)$的。

有了这个引理就能得到下面的定理:

$\text{Thm.}$ 若$A$可逆，且$r=\parallel A^{-1}E\parallel_p < 1$,那么$A+E$可逆且

$$(A+E)^{-1}-A^{-1}\le \frac{\parallel E\parallel_p\parallel A^{-1}\parallel_p^2}{1-r}$$

$\text{Proof.}$ 设$F=-EA^{-1}$，容易验证

$$(A+E)^{-1}-A^{-1}=-A^{-1}EA^{-1}(I+F)^{-1}$$

两侧取范数即可

$\text{The Eckhart-Young Theorem}$

这个定理的前置是$\text{SVD}$，$\text{SVD}$到处都有讲，本来应该说是个很重要的概念，但是因为实在是过于普遍所以这里就不多提了。

所幸网上已有很多资料，读者可以自行学习。这里至少应该给出个结论但是我连结论也不会给的。

这个定理在$\text{Strang}$老爷子的课里也专门讲过，但是$\text{Strang}$没有讲证明实际上他那个课都不怎么讲证明。这个定理是矩阵低秩近似的理论基础，还是相当重要的。

$\text{Thm.}$ 若$k < r = rk(A)$，令$A_k=\sum\limits_{i=1}^k\sigma_iu_iv_i^T$，则有

$$\min\limits_{rk(B)=k}\parallel A-B\parallel_2=\parallel A-A_k\parallel_2=\sigma_{k+1}$$

当然，这里$\sigma_{k+1}$说的是奇异值，并且$\sigma$是从大往小排列的。

第二个等式相当容易验证的，重点是第一个。

首先很容易发现$A_k$的确是个秩为$k$的矩阵，我们要证明没有秩为$k$矩阵能比$A_k$更懂如何逼近逼近得更好，即要证明

$$\parallel A-B\parallel_2^2\ge \sigma_{k+1}^2$$

首先寻找矩阵$B$的零空间$\text{null}(B)$的一组正交基$\{x_1,x_2,...x_{n-k}\}$

运用维数公式，我们有

$$\text{dim}(\text{null}(B))+\text{dim}(<v_1,v_2,...,v_{k+1}>)-\text{dim}(\text{null}(B)\cap <v_1,v_2,...,v_{k+1}>)\le n$$

即

$$n-k+k+1-\text{dim}(\text{null}(B)\cap <v_1,v_2,...,v_{k+1}>)\le n$$

即有$\text{dim}(\text{null}(B)\cap <v_1,v_2,...,v_{k+1}>)\ge 1$

这说明$S=\text{null}(B)\cap <v_1,v_2,...,v_{k+1}> \neq \{0\}$，线性代数老师应该也提醒过这个地方绝对不能把$\{0\}$写成空集。

设$z$是$S$中的单位向量，于是有

$$Az=\sum\limits_{i=1}^{k+1}u_i\sigma_i v_i^Tz =\sum\limits_{i=1}^{k+1}\sigma_iu_i(z^Tv_i) =\sum\limits_{i=1}^{k+1}\sigma_i(v_i^Tz)u_i$$

$$\parallel Az-Bz\parallel_2^2=\parallel Az\parallel_2^2=\parallel \sum\limits_{i=1}^{k+1}\sigma_i(v_i^Tz)u_i\parallel_2^2$$

首先由于$u_i$是单位正交基，我们可以直接把范数和求和交换并且化简。于是

$$\parallel (A-B)z\parallel_2^2=\sum\limits_{i=1}^{k+1}\sigma_i^2(v_i^Tz)^2$$

其次，由于$z\in <v_1,v_2,...,v_{k+1}>$并且$\parallel z\parallel_2^2=1$，而且$v_1,v_2,...,v_{k+1}$都是单位正交基，有

$$\parallel z\parallel_2^2=\sum\limits_{i=1}^{k+1}(v_i^Tz)^2=1$$

所以说$\parallel (A-B)z\parallel_2^2=\sum\limits_{i=1}^{k+1}\sigma_i^2(v_i^Tz)^2$是$\sigma_1^2,\sigma_2^2,...\sigma_{k+1}^2$的凸组合，它肯定比最小的那一个即$\sigma_{k+1}^2$要大，由于对任意满足条件的$\parallel (A-B)z\parallel_2^2$都成立，我们取其上确界应当还是成立的，由于这个上确界一定不比$\parallel A-B\parallel_2^2$大（因为$z$取不到全空间）。就有

$$\parallel A-B\parallel_2^2\ge \sigma_{k+1}^2$$

$\text{2.2. 子空间度量}$

很多时候我们希望能够衡量两个子空间有多“接近”，或者说两个子空间有多少“重合”。这个时候考虑子空间的正交基就是非常好的，因为正交基拥有很好的运算性质。

$\text{2.2.1. 正交投影}$

其实要说吧，这个概念线代课上也讲过，不过这里还是重新提一下，至少给出一些重要结论，尤其是一些矩阵结论坦白说这一块儿我是没学好的最后还是滚去问了线代老师。

正交投影表示把一个向量投影到子空间上，所谓投影也就是说将向量分解为在子空间和其正交补空间中的两部分然后取前者。正交投影其作为算子肯定有其对应的方阵，依此定义:

如果$P\in \mathbb{R}^{n\times n}$满足$\text{ran}(P)=S$,且$P^2=P,P^T=P$称其为子空间$S$上的正交投影。

这里$\text{ran}$就是把矩阵作为线性映射的像空间，或者说矩阵的列空间。

$\text{ran}(P)$是列空间。本来投影算子的定义其实可以没有对称性的，但是这里有。这一点。。。挺迷的

一个重要的结论是，如果子空间$S$的一组单位正交基拼成的矩阵是$V=[v_1|v_2|...|v_k]$，那么$P$上的正交投影矩阵$P=VV^T$。

这个玩意儿。。。很容易验证它确实满足上面的定义。但是这个结构我不是很能用线性映射去理解它。。。

在此特别感谢我的线性代数老师，拜托他解读了一下其中的线性映射理解，写得非常清晰。

有了这些东西，再结合$\text{SVD}$，我们就能够对子空间进行各种拆解。

考虑奇异值分解$A=U\Sigma V^T$，设$\text{rank}(A)=k$，将$U$写为$[U_k|\tilde{U_k}]$，其中$U_k=[u_1,u_2,...,u_k]$，用同样的方法将$V$写为$[V_k|\tilde{V_k}]$

于是我们就知道，$\text{ran}(A)=\text{ran}(U\Sigma V^T)=\text{ran}(\Sigma V^T)=\text{ran}(V\Sigma^T)=\text{ran}(V_k)$。第二个等号成立是因为$U$是满秩矩阵。

这说明$V_k$是$\text{ran}(A)$的一组单位正交基，由于由上面的结论我们就可以把各种正交投影矩阵写出来。

例如，假设做奇异值分解后$A=U\Sigma V^T$，设$\text{rank(A)}=k$，且$U=[\tilde{U_k}|\tilde{U_{n-k}}],V=[\tilde{V_k}|\tilde{V_{n-k}}]$，我们就能根据上面的结论写出$\text{null}(A),\text{ran}(A)$等等的正交投影矩阵。

$\text{2.2.2. 子空间的距离}$

其实距离好定义，就是两个子空间(维度相同)中点的距离的最小值。我们同样可以用矩阵来给出这个度量。

$\text{Thm.}$设$W=[W_1|W_2],Z=[Z_1|Z_2]$都是$n\times n$方阵，$W_1,Z_1\in \mathbb{R}^{n\times k}$，若$S_1=\text{ran}(W_1),S_2=\text{ran}(Z_1)$，则有

$$\text{dist}(S_1,S_2)=\parallel W^TZ_2\parallel_2=\parallel Z_1^TW_2\parallel_2$$

证明主要运用分块矩阵，关键是发现$\text{dist}(S_1,S_2)=\parallel W_1W_1^T-Z_1Z_1^T\parallel_2$

$\text{2.2.3. CS分解}$

一个简化版的结论是:

$\text{Thm.}$ 考虑矩阵

$$Q=\begin{bmatrix} Q_1\\Q_2\end{bmatrix}$$

且$Q_1\in \mathbb{R}^{m_1\times n},Q_2\in \mathbb{R}^{m_2\times n}$

如果$Q$的列向量正交，则存在正交矩阵$U_1,U_2,V$使得

$$\begin{bmatrix}U_1&0\\0&U_2\end{bmatrix}\begin{bmatrix}Q_1\\Q_2\end{bmatrix}V=\begin{bmatrix}C\\S\end{bmatrix}$$

其中$C,S$都是对角矩阵，且$C=\text{diag}(\cos(\theta_1), ... \cos(\theta_n)),S=C=\text{diag}(\sin(\theta_1), ... \sin(\theta_n))$

证明方法是首先对$Q_1$做$\text{SVD}$得到$U_1,V$，然后构造$U_2$，分离出$Q_2$的一个可以同时被$V$对角化的子空间。证明涉及到很多量化的性质。

一般性的结论是：

$\text{Thm.}$若$Q=\begin{bmatrix}Q_{11}&Q_{12}\\Q_{21}&Q_{22}\end{bmatrix}$是正交矩阵，就可以把它写成一个很丑的但是只含$C,S,I,0$块的矩阵。。。

如果去看看这个形式其实能发现两个子空间的正交基确实有一定联系但是不知道有啥用。。。

$\text{2.3. 线性系统的敏感性}$

实话说。。。上面那一节真挺无聊也不知道有啥用差点让我还没起步就弃坑了，但是这个话题就很有用了。

这一节我们的研究对象就只有一个$Ax=b,A\in \mathbb{R}^{n\times n},b\in \mathbb{R}^n$

$\text{2.3.1. 条件数}$

这其实是数值分析里讲过的话题。。。但是我很幸运地看完了那一章然后一点都不记得（

通过奇异值分解，我们可以写出来$A=\sum\limits_{i=1}^n\sigma_iu_iv_i^T$

于是解得$x=\sum\limits_{i=1}^n \frac{u_i^Tb}{\sigma_i}v_i$

可以发现，如果不幸的是某些$\sigma_i$极其小，那么在这些方向上对$A$或者$b$一点小扰动就会让解产生很大的偏移。

为了更加精细地衡量这个偏移，我们考虑一个微扰的线性系统

$$(A+\epsilon F)x(\epsilon) = b+\epsilon f,x(0)=x$$

假设$A$是可逆的，那么$x(\epsilon)$在原点至少一个小邻域内是可积的，而且$\epsilon$很小，我们可以在原点附近用泰勒展开来近似$x(\epsilon)$，但是要求$x(\epsilon)$的导数直接算并不是很直观，所以我们用隐函数求导会比较方便。

$$A\dot{x}(\epsilon)+Fx(\epsilon)+\epsilon F\dot{x}(\epsilon) = f$$

代入$\epsilon = 0$得$\dot{x}(\epsilon)=A^{-1}(f-Fx)$

现在再用泰勒展开

$$x(\epsilon)-x=A^{-1}(f-Fx)\epsilon+O(\epsilon^2)$$

为了估计误差，我们将其取范数并在两侧除以$\parallel x\parallel$，得到

$$\frac{\parallel x(\epsilon)-x\parallel}{\parallel x\parallel}\le \epsilon\parallel A^{-1}\parallel\{\frac{\parallel f\parallel}{\parallel x\parallel}+\parallel F\parallel\}+O(\epsilon^2)$$

对于方阵$A$，我们定义$A$的条件数为$\kappa(A)=\parallel A\parallel\parallel A^{-1}\parallel$

如果$A$不可逆，我们可以顺利成章地定义$\kappa(A)=+\infty$

由于$\parallel b\parallel\parallel A\parallel^{-1}\le \parallel x\parallel$，我们可以把上面的不等式里的$\parallel x\parallel$放缩掉，来把右边整理成和$A,b$的相对误差有关的不等式

$$\frac{\parallel x(\epsilon)-x\parallel}{\parallel x\parallel}\le \kappa(A)(\rho_A+\rho_b)+O(\epsilon^2)$$

其中$\rho_A=\epsilon \frac{\parallel F\parallel}{\parallel A\parallel},\rho_A=\epsilon \frac{\parallel f\parallel}{\parallel b\parallel}$

我们就发现，$x$的相对误差差不多是$A,b$的相对误差的$\kappa(A)$倍。于是$\kappa(A)$就衡量了$Ax=b$的敏感性。根据前面的范数定义可以写出2-范数下定义的条件数和矩阵奇异值的关系为

$$\kappa(A)=\frac{\sigma_{\max}}{\sigma_{\min}}$$

这上面的条件数都是在2-范数下定义的，实际上条件数的定义不依赖于范数，定义也有很多，这里不全列出。但是要记住我们是通过微分引入条件数的。

条件数是衡量矩阵的数值性质的非常好的量，很自然地会想到行列式是不是也是这么样一个量，但是事实上矩阵的行列式和线性系统的解的数值性质关系并不大。

最后，有了条件数，我们就可以用它来较精确地估计线性系统解的偏移量。

$\text{Lemma. }$设方程$Ax = b, (A+\Delta A)y=b+\Delta b$，且$\parallel \Delta A\parallel\le \epsilon\parallel A\parallel, \parallel \Delta b\parallel\le \epsilon\parallel b\parallel$，则有

$$\frac{\parallel y\parallel}{\parallel x\parallel}\le \frac{1+\epsilon\kappa(A)}{1-\epsilon\kappa(A)}$$

对微扰后的方程左乘$A^{-1}$然后运用条件数的定义和范数性质放缩可得。

$\text{Thm. }$ 如果引理中条件满足，那么

$$\frac{\parallel y - x\parallel}{\parallel x\parallel}\le \frac{2\epsilon \kappa(A)}{1-\epsilon\kappa(A)}$$

证明不难。这个界还行，但还可以更加精细化：

$$\frac{\parallel y-x\parallel_{\infty}}{\parallel x\parallel_{\infty}}\le\frac{2\epsilon}{1-\epsilon \kappa(A)}\parallel |A^{-1}||A|\parallel_{\infty}$$

其中$|A|$表示把|A|的元素全部取绝对值。$\parallel |A^{-1}||A|\parallel_{\infty}$被称为$\text{Skeel}$条件数。

$\text{2.4. 有限精度的计算}$

这个很重要，因为计算机里用的浮点数都是精度有限的。

$\text{IEEE}$标准这种人尽皆知的东西就无需多言了。

$\text{2.4.1. 舍入误差}$

在$\text{IEEE}$标准里，用一定位数的二进制位编码指数，这个位数决定了表示的最低精度，更高的精度就必须舍入，通常采用的是舍入到最近浮点数，也就是所谓的“四舍六入五成双”。

用$\text{round(x)}$表示$x$舍入后的结果，容易发现，如果我们使用$e$位编码指数，那么就有

$$\frac{|\text{round}(x)-x|}{|x|}\le 2^{-e-1}$$

如果考虑到这个层次的细节，那也太过于底层了。计算机按照$\text{IEEE}$标准实现的浮点运算还是值得相信的，为了方便这个层面上的表示，用$\text{fl}(x)$表示$x$作为一个浮点数的存储或者计算。

于是我们就知道$\text{fl}(x)=x(1+\delta),|\delta|<2^{-e-1}$

$2^{-e-1}$在书中被记作$u$，对单精度浮点来说差不多是$10^{-7}$，对双精度浮点来说差不多是$10^{-16}$，可以发现如果把这两种浮点数用的编码位带进去，的确是差不多的数量级。

$\text{2.4.2. 浮点数注意事项}$

计算顺序很重要

这是计算机内容，神书csapp强调过这个事情，无需多言。

逼近精度小不一定是真的小

例如，如果我们用一阶差分算$\sin x$的数值导数，取步长$h=\sqrt{u}$能得到近似最小的误差。

更细节地说一下这个事情，我们如果试图用一阶差分也就是
$d=\frac{\sin(x+h)-\sin x}{h}$来近似计算导数。假设$\sin$的计算没有误差，那么由数值分析知识（其实就是一个泰勒展开），我们有$|d - \cos x|\sim O(h) $

事实上，正弦函数的数值计算本身也有误差，这是我们无法改变的，我们除以$h$的操作把这个误差放大了$\frac{1}{h}$倍，这意味着$h$绝非取得越小越好，因此实际上我们取$h=\sqrt{u}$才能近似地最小化此误差。

$\text{2.4.3. 应用：存储矩阵}$

很容易就能知道，如果把一个矩阵$A$存在计算机里，会有

$$|\text{fl}(A)-A|\le u|A|$$

$$\parallel \text{fl}(A)-A\parallel_1 \le u\parallel A\parallel_1$$

这边很多结论就不细说了，基本上都是一个放缩就能放出来的事情。大部分结论这里会跳过，后面需要用到的时候直接给出结果，不给出证明。

但是有个结论还是在这里提一嘴。

$\text{Lemma. }$ 如果$(1+\alpha)=\prod\limits_{k=1}^n (1+\alpha_k)$且$|\alpha_k|\le u$且$nu\le 0.01$，那么$|\alpha|\le 1.01nu$

这个结果还是比较恐怖的，它表明如果两个向量的夹角比较接近垂直的话，向量点积的相对误差可能会很大。

$\text{2.4.4. 前向和后向误差分析}$

舍入误差拿来计算相对误差时，既可以是和实际计算结果作比，也可以是和输入数据作比。前者就是前向误差分析，后者就是后向误差分析。

原书在这里还分析了一下$\text{Strassen}$矩阵乘法，略去。

$\text{2.4.5. 分析理想的解方程组}$

我们重新回到数值线性代数的一个重要课题（也是下一个课题）：解方程组$Ax=b$.

假设我们解出来的解是$\hat{x}$，那么它满足

$$(A+E)\hat{x} = b+e$$

这里的$E$不是单位矩阵，而是误差矩阵。有$\parallel E\parallel_{\infty}\le u\parallel A\parallel_{\infty},\parallel e\parallel_{\infty}\le u\parallel b\parallel_{\infty}$ 并且$\text{fl}(b)=b+e,\text{fl}(A)=A+E$

假设$u\kappa_{\infty}(A)\le \frac{1}{2}$，那么利用前面在矩阵条件数那里得到的结果，我们就知道

$$\frac{\parallel x-\hat{x}\parallel_{\infty}}{\parallel x\parallel_{\infty}}\le 4u\kappa_{\infty}(A)$$

$\text{Fin.}$