关于条件数的两个简单不等式的证明

条件数的产生是为了度量一个线性方程组解对误差的敏感程度.我们知道在计算机做数值计算的时候,是没有我们的极限思想的,比如求导,计算机就是利用差分来近似.但说白了极限的存在也是为了刻画收敛性的有无,只要这个解具有收敛性,那么我们就可以经过一定的步数达到这个真解的收敛半径内,这样得到的解计算机近似为真解.由此可知,这样的解满足它与真解的距离足够小,也就是$\Vert x - x'\Vert < \varepsilon$∥x−x′∥<ε.
其中$x$x表示数值解,$x'$x′表示真解,$\varepsilon$ε表示一个较小的数.
但是在实际去解一个线性方程组问题$Ax = b$Ax=b的时候,可能会出现给A一个很小的扰动,或者给b一个很小的扰动,不妨看第二种,即$\Delta b$Δb,那这个时候$Ax^{*} = b + \Delta b$Ax∗=b+Δb,其中$x^{*}$x∗满足$x^{*} = x + \Delta x$x∗=x+Δx,我们不妨就写作$A(x+\Delta x) = b + \Delta b \qquad (1)$A(x+Δx)=b+Δb(1).我们希望我们得到的解是稳定的,也就是说给b一个很小的扰动,得到的解距离之前的解也在一个可控范围内,用数学上收敛的定义来说,就是存在一个常数C,使得$\frac{\Vert \Delta x\Vert}{\Vert x\Vert} \leqslant C\frac{\Vert\Delta b\Vert}{\Vert b\Vert}\qquad (2)$∥x∥∥Δx∥​⩽C∥b∥∥Δb∥​(2),我们称作解的误差被常数项的误差所控制,一般来说,我们希望这个C在1附近,如果是这样,我们称这个方程组是适定的,如果这个C远大于1,我们称这个方程式病态的,病态的方程去求它的解是没有意义的,因为给常数项或者系数项一个很小的扰动,解的变化非常大,超出了控制.
继续回到公式(1),因为Ax = b,所以$A\Delta x = \Delta b$AΔx=Δb,所以$\Delta x = A^{-1}b$Δx=A−1b,由范数的不等式关系,很容易得到$\Vert \Delta x \Vert\leqslant \Vert A^{-1}\Vert \Vert\Delta b\Vert\qquad (3)$∥Δx∥⩽∥A−1∥∥Δb∥(3)和$\Vert b\Vert \leqslant \Vert A\Vert \Vert x\Vert\qquad (4)$∥b∥⩽∥A∥∥x∥(4),由上面两式得,$\frac{\Vert \Delta x\Vert}{\Vert A\Vert \Vert x\Vert} \leqslant \frac{\Vert A^{-1}\Vert\Delta b\Vert}{\Vert b\Vert}$∥A∥∥x∥∥Δx∥​⩽∥b∥∥A−1∥Δb∥​.经过简单的移项操作,既可以得到$\frac{\Vert \Delta x\Vert}{ \Vert x\Vert} \leqslant \frac{\Vert A\Vert\Vert A^{-1}\Vert\Delta b\Vert}{\Vert b\Vert}\qquad (5)$∥x∥∥Δx∥​⩽∥b∥∥A∥∥A−1∥Δb∥​(5),令$cond(A) = \Vert A\Vert\Vert A^{-1}\Vert$cond(A)=∥A∥∥A−1∥,这就是我们所说的条件数了.
结合(2),我们可以知道A的条件数就是(2)中的C,所以说cond(A)可以用来刻画解对扰动的敏感程度.
除了对b做扰动,还可以对A做扰动,即令$(A+\Delta A)(x + \Delta x) = b$(A+ΔA)(x+Δx)=b,根据一个定理(Von-Neumann),

如果矩阵$A\in R^{m\times n}$A∈Rm×n非奇异,则对于任何$E \in R^{n\times n}$E∈Rn×n,如果$\Vert A^{-1}E\Vert\leqslant 1$∥A−1E∥⩽1,A+E非奇异,并且有估计式$\Vert(A+E)^{-1}\Vert \leqslant \frac{\Vert A^{-1}\Vert}{1-\Vert A^{-1}E\Vert}$∥(A+E)−1∥⩽1−∥A−1E∥∥A−1∥​.

当$\Vert A^{-1} \Delta A\Vert\leqslant 1$∥A−1ΔA∥⩽1时,$A+\Delta A$A+ΔA非奇异,并且$\Vert(A+\Delta A)^{-1}\Vert\leqslant\frac{\Vert A^{-1}\Vert}{1-\Vert A^{-1}\Delta A\Vert}\qquad (7)$∥(A+ΔA)−1∥⩽1−∥A−1ΔA∥∥A−1∥​(7)
因为$x + \Delta x = (A + \Delta A)^{-1} b$x+Δx=(A+ΔA)−1b,且$\begin{aligned}\Delta x &= ((A + \Delta A)^{-1} - A^{-1})b\\ &= -A^{-1}((A+\Delta A)-A)(A+\Delta A)^{-1}b\\ & = -A^{-1}\Delta A(x+\Delta x) \end{aligned}$Δx​=((A+ΔA)−1−A−1)b=−A−1((A+ΔA)−A)(A+ΔA)−1b=−A−1ΔA(x+Δx)​
从而$\Vert \Delta x\Vert\leqslant\Vert A^{-1}\Vert\Vert\Delta A\Vert\Vert(x+\Delta x)\Vert$∥Δx∥⩽∥A−1∥∥ΔA∥∥(x+Δx)∥,也就是
$\frac{\Vert \Delta x\Vert}{\Vert x+\Delta x\Vert}\leqslant Cond(A)\frac{\Vert\Delta A\Vert}{\Vert A\Vert}\qquad (8)$∥x+Δx∥∥Δx∥​⩽Cond(A)∥A∥∥ΔA∥​(8)
由(7)式,得
$\begin{aligned}\frac{ \Vert \Delta x\Vert}{\Vert x\Vert} &\leqslant \Vert \Delta A\Vert *\Vert(A+\Delta A)^{-1}\Vert\\ &\leqslant\frac{\Vert A^{-1}\Vert}{1-\Vert A^{-1}\Delta A\Vert} * \frac{\Delta Ax\Vert}{\Vert x\Vert}\\ &\leqslant Cond(A)\frac{\Vert\Delta A\Vert /\Vert x\Vert }{1-Cond(A)*\Vert\Delta A\Vert / \Vert A\Vert} \end{aligned}\\ (9)$∥x∥∥Δx∥​​⩽∥ΔA∥∗∥(A+ΔA)−1∥⩽1−∥A−1ΔA∥∥A−1∥​∗∥x∥ΔAx∥​⩽Cond(A)1−Cond(A)∗∥ΔA∥/∥A∥∥ΔA∥/∥x∥​​(9)
(5)式和(9)式同时说明了方程组的解对于误差的敏感程度取决于其条件数,这和一般以为系数矩阵的行列式的大小决定其解对误差的敏感程度的印象是不一样的.