Conditional Number of Matrix

In This post, I will comb the inference of the conditional number of Matrix

WHAT

不得不说，咱们语言文化的博大精深。所谓“千里之堤，溃于蚁穴”，则正是条件数的表示，旨在对某件事物进行轻微的扰动，那么其会产生巨大的影响。

Defenition

所以对于方程组 $Ax=b$， 如果我们给$A$一个轻微的扰动，其解x变化仍在我们可接受的范围之内的话，那么就说这个矩阵是良好的矩阵(Well Done!)，否则，它就是一个病态的矩阵。

针对上述定义，我们引出两个问题

1. 什么是轻微的扰动？

2. 如何评测一个矩阵是否是病态的？

所谓轻微的扰动，并不是指整个矩阵中所有元素变化量的大小，而是说变化元素的个数。通常，我们用

$$e_i·\alpha {e_j}^T$$

来表示仅在$(i, j)$位置的元素为$\alpha$，其余位置为$0$的矩阵。而轻微扰动，即在$A$的基础之上 append 一些$(1)$的元素。

下面进行条件数的推导。

Inference of the Conditional Number

Neumann Series

在这里只能说诺伊曼牛逼, If $\lim_{n \to \infty} A^n=0$, 那么$I-A$就是非奇异的，并且

$$(I-A)^{-1} = I+A+A^2+···=\sum_{k=0}^{\infty}A^k$$

这个直接相乘即可验证出来了，诺伊曼给了我们一个估算$(I-A)^{-1}$的级数，太棒了。

Perturbation Term

现在我们假设给予$A$矩阵一些轻微的扰动$B$， 即$A+B$，现在来考虑$Ax=b$的解$x$，与$(A+B)\widetilde{x}=b$的解$\widetilde{x}$的gap。因为$A$可逆，且$B$是轻微扰动，所以说$A+B$是可逆的，所以

$$\left\{\begin{matrix} x=A^{-1}b\\ \widetilde{x}=(A+B)^{-1}b \end{matrix}\right.$$

从而，我们仅要看$A^{-1}$与$(A+B)^{-1}$的差异即可。下面由诺伊曼级数进行导出。

假设$\lim_{n \to \infty}(A^{-1}B)^n=0$，(这个其实很好满足嘛，直觉上只要$A^{-1}$不要太大就好，因为$B$是轻微扰动项，所以说$B^n$本身很小很小的，这样说不太严谨，但是intuitive)。

$$(A+B)^{-1} = (A(I-[-A^{-1}B]))^{-1} = (I-[-A^{-1}B])^{-1}A^{-1}=(\sum_{k=0}^{\infty}[-A^{-1}B]^k)A^{-1}$$

为了方便起见，我们仅考虑其一阶估计

$$(A+B)^{-1} \approx A^{-1}-A^{-1}BA^{-1}$$

可见，右边儿的第二项就是扰动项：$A^{-1}BA^{-1}$。

扰动项 => 条件数

首先我们先得到$x- \widetilde{x}$的上界

$$x- \widetilde{x} = A^{-1}b-(A+B)^{-1}b \approx A^{-1}Bx$$

这肯定是上界嘛，因为只估算到了一阶。那么，只要这个上界足够小，那么其误差就可能大。

$$\left \| x-\widetilde{x} \right \| \leq \left \|A^{-1} \right \| \left \| B \right \| \left \| x \right \|$$

由于解本身有大有小，所以我们不能直接用其差值进行误差的估量，进而采用

$$\frac{\left \| x-\widetilde{x} \right \|}{\left \|x \right \|} \leq \left \| A^{-1} \right \| \left \|B \right \| = \kappa\{ \frac{\left \|B \right \|} {\left \|A \right \|}\}$$

其中，由于B是扰动，所以 $\frac{\left |B \right |} {\left |A \right |}$本身很小，所以其上界如果很大，那么肯定是$\kappa$出了问题。

$$\kappa = \left \|A \right \|·\left \| A^{-1} \right \|$$

我们称$\kappa$为矩阵$A$的条件数。如果$\kappa$很小，那么其差值上界定然小，如果$\kappa$很大，那么其差值上界就很大，从而其真实的差值就可能大，就是病态矩阵。（注意定然和可能）。

至于这个“小”还是“大”，因为已经经过模的规范化了，所以不同矩阵之间也可以比较。

条件数为多少时才是凉态的？

这里其实可以做一个实验，编写代码画图，构造一些指定条件数的矩阵出来，观察其轻微扰动之后的差值。给出网友的结论：（第一步骤实验！）

首先奇异和病态没有必然的联系，良态、病态、条件数都要针对求解的问题而言，比如说矩阵求逆的性态和矩阵求特征值的性态就完全是两码事 　在2-范数扰动的意义下，矩阵求逆或者解线性方程组的时候奇异矩阵可以认为是最病态（无限病态）的矩阵，因为它有零奇异值（注意，这个问题的性态体现在奇异值而不是特征值） 　至于什么样的矩阵算病态，没有绝对的标准，因为大和小是相对的概念 　通常病态与否也与实际计算的机器精度有关，比如IEEE单精度下K=10^4算比较病态了，但在IEEE双精度下就算比较良态