condition number
浅谈条件数（condition number）
近日在看线代的书时，正好看到了奇异值（singular value）在计算条件数的应用，于是找了几份资料，似有所悟，在此现学现卖，分享与同道中人。
需要指出的是，条件数是个宽泛的概念，这里讨论的，用[1]的话说是“the condition number for inversion”。
向量的范数（the norm of a vector）
一个向量的norm是衡量向量大小的概念，有多种定义，材料[1]和[2]就采用了不同的范数，不过采用哪种范数，对于条件数没有影响。向量\(x\)的范数符号表示为\(||x||\)。例如[1]采用了Euclidean norm or 2- norm： \[ ||x||=(\sum_ix_i^2)^{1/2} \] 而[2]的定义为： \[ ||x||=\text{max}\{|x_1|,|x_2|,\cdots,|x_3|\} \]
矩阵的范数（the norm of a matrix）
一个矩阵的norm定义为其最大能拉伸（stretch)向量的能力： \[ M = ||A|| = \text{max}\frac{||Ax||}{||x||} \] 与此同时定义其最小拉伸向量的能力； \[ m = \text{min}\frac{||Ax||}{||x||} \] 可证： \[ m = \frac{1}{||A^{-1}||} \] 而条件数被定义为这两者的比值，即： \[ \kappa(A) = \frac{M}{m} = ||A||||A^{-1}|| \]
三条结论
条件数的应用主要体现在3个方面，我总结如下：
结论1
条件数越大，矩阵越接近不可逆。（例子来源[2])
结论2
条件数决定了当\(b\)变化时，\(x\)的变化的上界。（例子来源[1])
考虑一个线性系统： \[ Ax = b \] 当\(b\)变化时： \[ A(x+\Delta x)=b+\Delta b \] 因为： \[ ||b|| \leq M||x|| \quad ||\Delta b|| \geq m||\Delta x|| \] 得到： \[ \frac{||\Delta x||}{||x||} \leq \kappa(A) \frac{||\Delta b||}{||b||} \]
结论3
条件数决定了当矩阵\(A\)变化时，对其逆\(A^{-1}\)的影响。（见[1])
总结
资料[1]和[2]中有使用matlab计算条件数的例子，验证了上面的结论。如上是笔者的总结，然而尚且是半通不通，下键盘时甚为艰难，难免纰漏，见谅。
参考资料
[1] What is the Condition Number of a Matrix?
[3] Linear Algebra And Its Application 5th edition, David C.Lay etc.