数值分析：矩阵求逆-奇异性、条件数

桃扇骨 2022-09-25 09:22 620阅读 0赞

http://[blog.csdn.net/pipisorry/article/details/52241141][blog.csdn.net_pipisorry_article_details_52241141]

本blog主要内容有：矩阵的奇异性、条件数与病态矩阵、矩阵求逆。

# 奇异矩阵和非奇异矩阵singular matrix&nonsingular matrix #

## 概念和定义    ##

若n阶矩阵A的行列式不为零，即 |A|≠0，则称A为非奇异矩阵或满秩矩阵，否则称A为奇异矩阵或降秩矩阵。

奇异矩阵是线性代数的概念，就是对应的行列式等于0的方阵。

## 奇异矩阵和非奇异矩阵的判断和性质 ##

### 奇异矩阵一定是方阵吗 ###

首先，看这个矩阵是不是方阵（即行数和列数相等的矩

阵。若行数和列数不相等，那就谈不上奇异矩阵和非奇异矩阵）。

不过限定在某个知识范围内是指方阵，例如线性代数当中只对方阵进行奇异矩阵的定义。正常来讲是不限定必须是方阵的，比如在奇异值分解当中，用作估计的时候会定义奇异值矩阵不满秩的矩阵为奇异阵，当然就不再限定是方阵。这种情况下矩阵不可求广义逆，即使求莫奈伪逆也要用特殊的方法，另外这种矩阵如果有物理意义的话，往往不满足正交核函数分解的条件。

一个矩阵A非奇异当且仅当：（等价的概念）  
A的所有特征值都不为零（lambda=0则|A|=0，只要矩阵A有一个特征值为零，一定是奇异矩阵。即零特征值反映矩阵的奇异性）  
或A的行列式不为零，即 |A|≠0（A 为可逆矩阵，也即A的行列式不为零）  
或A可逆  
或A的秩为n（非奇异矩阵 A满秩，Rank(A)=n；奇异矩阵 A的秩Rank(A)<n）  
或A的列向量线性无关

或矩阵方程AX=b有唯一非零解（如果A为奇异矩阵，则AX=b有无穷解或者无解）

或矩阵方程AX=0有且仅有零解（如果A为奇异矩阵，则AX=0有无穷解）  
一个非奇异矩阵可表示成若干个初等矩阵之积。  
一个矩阵非奇异当且仅当它代表的线性变换是个自同构。Note: 若A为非奇异矩阵，其顺序主子阵Ai（i=1,...,n-1）不一定均非奇异。  
如果n 阶方阵A奇异，则一定存在一个n\*1阶非零向量X使： X'AX=0；成立。  
\[更详细的描述ref：张贤达： 矩阵分析与应用 1.7逆矩阵与伪逆矩阵\]

### 注意事项 ###

计量经济学中，当样本容量太少或是当变量间存在完全相关性时会提示“near singular matrix”，意为“近奇异矩阵”。  
在信号处理中，当信号协方差矩阵不是奇异矩阵时，则信号不相关或者部分相关。

\[ [百度百科：奇异矩阵][Link 1]\]  
\[ [What is the difference between a discontinuity and a singularity? - Quora][What is the difference between a discontinuity and a singularity_ - Quora]\]  
[皮皮blog][blog]

优化有两大难题，一是：局部最小值，二是：ill-condition病态问题。前者俺就不说了，大家都懂吧，我们要找的是全局最小值，如果局部最小值太多，那我们的优化算法就很容易陷入局部最小而不能自拔，这很明显不是观众愿意看到的剧情。那下面我们来聊聊ill-condition。

# 条件数condition number与病态矩阵 #

## ill-condition对应的是well-condition，分别代表什么？ ##

假设我们有个方程组AX=b，我们需要求解X。如果A或者b稍微的改变，会使得X的解发生很大的改变，那么这个方程组系统就是ill-condition的，反之就是well-condition的。

举个例子

![SouthEast][]

左边的那个。第一行假设是我们的AX=b，第二行我们稍微改变下b，得到的x和没改变前的差别很大。第三行我们稍微改变下系数矩阵A，可以看到结果的变化也很大。换句话来说，这个系统的解对系数矩阵A或者b太敏感了。又因为一般我们的系数矩阵A和b是从实验数据里面估计得到的，所以它是存在误差的，如果我们的系统对这个误差是可以容忍的就还好，但系统对这个误差太敏感了，以至于我们的解的误差更大，那这个解就太不靠谱了。所以这个方程组系统就是ill-conditioned病态的，不正常不稳定有问题的。

右边那个就叫well-condition的系统了。

对于一个ill-condition的系统，输入稍微改变下，输出就发生很大的改变，这表明我们的系统不能实用。例如对于一个回归问题y=f(x)，我们是用训练样本x去训练模型f，使得y尽量输出我们期待的值，例如0。那假如我们遇到一个样本x’，这个样本和训练样本x差别很小，面对他，系统本应该输出和上面的y差不多的值的，例如0.00001，最后却给我输出了一个0.9999，这很明显不对呀。就好像，你很熟悉的一个人脸上长了个青春痘，你就不认识他了，那你大脑就太差劲了，哈哈。

奇异的本质原因在于矩阵有0特征值，x在对应特征向量的方向上运动不改变Ax的值。如果一个特征值比其它特征值在数量级上小很多，x在对应特征向量方向上很大的移动才能产生b微小的变化，这就解释了为什么这个矩阵为什么会有大的条件数，事实上，正规阵在二范数下的条件数就可以表示成 abs(最大特征值/最小特征值)。

## 病态的衡量标准：条件数condition number    ##

所以如果一个系统是ill-conditioned病态的，我们就会对它的结果产生怀疑。那到底要相信它多少呢？我们得找个标准来衡量吧，因为有些系统的病没那么重，它的结果还是可以相信的。终于回来了，上面的condition number就是拿来衡量ill-condition系统的可信度的。

### condition number的定义 ###

条件数是线性方程组Ax=b的解对b中的误差或不确定度的敏感性的度量。数学定义为矩阵A的条件数等于A的范数与A的逆的范数的乘积，即cond(A)=‖A‖·‖A的逆‖，对应矩阵的3种范数，相应地可以定义3种条件数。

condition number衡量的是输入发生微小变化的时候，输出会发生多大的变化。也就是系统对微小变化的敏感度。

从线性代数的分析可知，矩阵的条件数总是大于1，正交矩阵的条件数等于1，奇异矩阵的条件数为无穷大，而病态矩阵的条件数则为比较大的数据（远大于1）。也就是说奇异矩阵一定是病态的！

如果方阵A是非奇异的，那么A的conditionnumber定义为：

![SouthEast 1][]

也就是矩阵A的norm乘以它的逆的norm。所以具体的值是多少，就要看你选择的norm是什么了。

如果方阵A是奇异的，那么A的condition number就是正无穷大了。

实际上，每一个可逆方阵都存在一个condition number。但如果要计算它，我们需要先知道这个方阵的norm（范数）和Machine Epsilon（机器的精度）。

当然，这个定义依赖于范数的选取。

*  若 ∥ ⋅ ∥ \{\\displaystyle \\|\\cdot \\|\} ![\\|\\cdot \\|][cdot] 是  l 2 \{\\displaystyle l\_\{2\}\} ![l\_2][l_2] 矩阵范数则

κ ( A ) = σ m a x ( A ) σ m i n ( A ) \{\\displaystyle \\kappa (A)=\{\\frac \{\\sigma \_\{max\}(A)\}\{\\sigma \_\{min\}(A)\}\}\}  ![\\kappa(A) = \\frac\{\\sigma\_\{max\}(A)\}\{\\sigma\_\{min\}(A)\}][kappa_A_ _ _frac_sigma_max_A_sigma_min_A] 其中  σ m a x ( A ) \{\\displaystyle \\sigma \_\{max\}(A)\}  ![\\sigma\_\{max\}(A)][sigma_max_A]和  σ m i n ( A ) \{\\displaystyle \\sigma \_\{min\}(A)\}  ![\\sigma\_\{min\}(A)][sigma_min_A]分别是  A \{\\displaystyle A\}  ![A][]的极大和极小 奇异值。因此

*  若 A \{\\displaystyle A\} ![A][]是正规矩阵则

κ ( A ) = | λ m a x ( A ) λ m i n ( A ) | \{\\displaystyle \\kappa (A)=\\left|\{\\frac \{\\lambda \_\{max\}(A)\}\{\\lambda \_\{min\}(A)\}\}\\right|\}  ![\\kappa(A) = \\left|\\frac\{\\lambda\_\{max\}(A)\}\{\\lambda\_\{min\}(A)\}\\right|][kappa_A_ _ _left_frac_lambda_max_A_lambda_min_A_right] (  λ m a x ( A ) ,   λ m i n ( A ) \{\\displaystyle \\lambda \_\{max\}(A),\\ \\lambda \_\{min\}(A)\}  ![\\lambda\_\{max\}(A),\\ \\lambda\_\{min\}(A)][lambda_max_A_ _lambda_min_A]分别是  A \{\\displaystyle A\}  ![A][]的极大和极小（根据模数） 特征值）

*  若 A \{\\displaystyle A\} ![A][]是酉矩阵则

κ ( A ) = 1 \{\\displaystyle \\kappa (A)=1\}  ![\\kappa(A) = 1][kappa_A_ _ 1]

*  若  ∥ ⋅ ∥ \{\\displaystyle \\|\\cdot \\|\} ![\\|\\cdot \\|][cdot]是 l ∞ \{\\displaystyle l\_\{\\infty \}\} ![l\_\{\\infty\}][l_infty] 矩阵范数而 A \{\\displaystyle A\} ![A][]是下三角矩阵，非奇异（也即 a i i ≠ 0 ∀ i \{\\displaystyle a\_\{ii\}\\neq 0\\;\\forall i\} ![a\_\{ii\} \\ne 0 \\; \\forall i][a_ii_ _ne 0 _ _forall i]）则： κ ( A ) ≥ max i ( | a i i | ) min i ( | a i i | ) \{\\displaystyle \\kappa (A)\\geq \{\\frac \{\\max \_\{i\}(|a\_\{ii\}|)\}\{\\min \_\{i\}(|a\_\{ii\}|)\}\}\} ![\\kappa(A) \\geq \\frac\{\\max\_i(|a\_\{ii\}|)\}\{\\min\_i(|a\_\{ii\}|)\}][kappa_A_ _geq _frac_max_i_a_ii_min_i_a_ii]

### 其它意义下的条件数 ###

[奇异值分解][Link 2]，多项式求根，[特征值][Link 3]和其它许多问题的条件数也可以有定义。

通常，如果一个数值问题是适定的，它可以表达为一个函数 f \{\\displaystyle f\} ![f][]映射它的数据（一个实数的 m \{\\displaystyle m\} ![m][]元组 x \{\\displaystyle x\} ![x][]）到它的解（一个实数的 n \{\\displaystyle n\} ![n][]元组 y \{\\displaystyle y\} ![y][]）。

它的条件数则定义为解中的[相对误差][Link 4]的半径和数据中的相对误差的比的最大值，取遍整个问题的定义域：

max \{ | f ( x ) − f ( x ∗ ) f ( x ) | / | x − x ∗ x | : | x − x ∗ | < ϵ \} \{\\displaystyle \\max \\left\\\{\\left|\{\\frac \{f(x)-f(x^\{\*\})\}\{f(x)\}\}\\right|\\left/\\left|\{\\frac \{x-x^\{\*\}\}\{x\}\}\\right|\\right.:|x-x^\{\*\}|<\\epsilon \\right\\\}\}  ![\\max \\left\\\{ \\left| \\frac\{f(x) - f(x^\*)\}\{f(x)\} \\right| \\left/ \\left| \\frac\{x - x^\*\}\{x\} \\right| \\right. : |x - x^\*| < \\epsilon \\right\\\}][max _left_ _left_ _frac_f_x_ - f_x_f_x_ _right_ _left_ _left_ _frac_x - x_x_ _right_ _right. _ _x - x_ _ _epsilon _right]

其中 ϵ \{\\displaystyle \\epsilon \} ![\\epsilon][epsilon]是问题中的数据的偏差的某个合理的小数值。

如果 f \{\\displaystyle f\} ![f][]也是可微的，这可以近似的表示为

| f ′ ( x ) f ( x ) | . | x | \{\\displaystyle \\left|\{\\frac \{f'(x)\}\{f(x)\}\}\\right|.\\left|x\\right|\}  ![\\left| \\frac\{ f'(x) \}\{ f(x) \} \\right|. \\left| x \\right|][left_ _frac_ f_x_ _ f_x_ _ _right_. _left_ x _right].

### 为什么要范数？ ###

范数就相当于衡量一个矩阵的大小，我们知道矩阵是没有大小的，但上面不是要衡量一个矩阵A或者向量b变化的时候，我们的解x变化的大小吗？所以肯定得要有一个东西来度量矩阵和向量的大小吧？它就是范数，表示矩阵大小或者向量长度。对于AX=b，我们可以有以下的结论：

![SouthEast 2][]

也就是我们的解x的相对变化和A或者b的相对变化是有像上面那样的关系的，其中k(A)的值就相当于倍率，相当于x变化的界。

一句话总结：condition number是一个矩阵（或者它所描述的线性系统）的稳定性或者敏感度的度量，如果一个矩阵的condition number在1附近，那么它就是well-conditioned的，如果远大于1，那么它就是ill-conditioned的，如果一个系统是ill-conditioned的，它的输出结果就不要太相信了。

\[[wikipedia: 条件数][wikipedia_]\]

[皮皮blog][blog]

# 矩阵求逆 #

非奇异正方矩阵A的逆矩阵A-1

m\*n(m!=n)的长方形满列秩矩阵的左伪逆矩阵(A^HA)^-1A^H， 满行秩矩阵的右伪逆矩阵A^H(AA^H)^-1

秩亏缺矩阵的逆矩阵：Moore-Penrose逆矩阵

\[张贤达： 矩阵分析与应用 1.7逆矩阵与伪逆矩阵\]

## 奇异矩阵/病态矩阵的求逆    ##

L2范数有助于处理条件数 condition number不好的情况下矩阵求逆很困难的问题。

如将下面的奇异矩阵XTX改造一下再求逆：

![SouthEast 3][]  ![SouthEast 4][]

\[[最优化方法：范数和规则化 ][Link 5]\]

还有SVD分解的方法？Moore-Penrose逆矩阵？

[皮皮blog][blog]

from: [http://blog.csdn.net/pipisorry/article/details/52241141][blog.csdn.net_pipisorry_article_details_52241141]

ref: \[张贤达： 矩阵分析与应用\]

[blog.csdn.net_pipisorry_article_details_52241141]: http://blog.csdn.net/pipisorry/article/details/52241141
[Link 1]: http://baike.baidu.com/link?url=JDg9Iz0agsmhqm0pufHzRIH4FiwM-oeWnljwhdAOIcvQiJWOHTnxSi635jnYb9qIM6_X557-Bp0Ykdo5fanNTa
[What is the difference between a discontinuity and a singularity_ - Quora]: https://www.quora.com/What-is-the-difference-between-a-discontinuity-and-a-singularity
[blog]: http://blog.csdn.net/pipisorry
[SouthEast]: /images/20220718/f55c5fa16ee8409ab20ea3c27a5fe1b8.png
[SouthEast 1]: /images/20220718/0468a6e1173942379a886a7a4846a36d.png
[cdot]: https://wikimedia.org/api/rest_v1/media/math/render/svg/113f0d8fe6108fc1c5e9802f7c3f634f5480b3d1
[l_2]: https://wikimedia.org/api/rest_v1/media/math/render/svg/84708bbc21c20c9834e0e57746dbbc437414c350
[kappa_A_ _ _frac_sigma_max_A_sigma_min_A]: https://wikimedia.org/api/rest_v1/media/math/render/svg/1698c5ac6cd99b2dad8bd80feb7c114f4bc37d94
[sigma_max_A]: https://wikimedia.org/api/rest_v1/media/math/render/svg/4f3b9c564ebb3bb68de41e0b19d2cec9abb9d290
[sigma_min_A]: https://wikimedia.org/api/rest_v1/media/math/render/svg/2899c75100a78126e9a39555ea6c40c97decf80d
[A]: https://wikimedia.org/api/rest_v1/media/math/render/svg/7daff47fa58cdfd29dc333def748ff5fa4c923e3
[kappa_A_ _ _left_frac_lambda_max_A_lambda_min_A_right]: https://wikimedia.org/api/rest_v1/media/math/render/svg/eb6e4026bccdc8e6059a9c46fbbf3fd54e74b5e4
[lambda_max_A_ _lambda_min_A]: https://wikimedia.org/api/rest_v1/media/math/render/svg/e94d08e8a4a6e6bdd1fa7a10185672f5440b6bc5
[kappa_A_ _ 1]: https://wikimedia.org/api/rest_v1/media/math/render/svg/65771097679e42ce4d1587c3cf306d032c1120f7
[l_infty]: https://wikimedia.org/api/rest_v1/media/math/render/svg/7fefbd2f82b7d8b19dec6b7db510fd72c9689e52
[a_ii_ _ne 0 _ _forall i]: https://wikimedia.org/api/rest_v1/media/math/render/svg/c9d33489733ddd303906d95388f3f6a715d7d491
[kappa_A_ _geq _frac_max_i_a_ii_min_i_a_ii]: https://wikimedia.org/api/rest_v1/media/math/render/svg/1a875842386a271e6aaa142f869fdcb4e467e9d3
[Link 2]: https://zh.wikipedia.org/wiki/%E5%A5%87%E5%BC%82%E5%80%BC%E5%88%86%E8%A7%A3
[Link 3]: https://zh.wikipedia.org/wiki/%E7%89%B9%E5%BE%81%E5%80%BC
[f]: https://wikimedia.org/api/rest_v1/media/math/render/svg/132e57acb643253e7810ee9702d9581f159a1c61
[m]: https://wikimedia.org/api/rest_v1/media/math/render/svg/0a07d98bb302f3856cbabc47b2b9016692e3f7bc
[x]: https://wikimedia.org/api/rest_v1/media/math/render/svg/87f9e315fd7e2ba406057a97300593c4802b53e4
[n]: https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b
[y]: https://wikimedia.org/api/rest_v1/media/math/render/svg/b8a6208ec717213d4317e666f1ae872e00620a0d
[Link 4]: https://zh.wikipedia.org/wiki/%E9%80%BC%E8%BF%91%E8%AF%AF%E5%B7%AE
[max _left_ _left_ _frac_f_x_ - f_x_f_x_ _right_ _left_ _left_ _frac_x - x_x_ _right_ _right. _ _x - x_ _ _epsilon _right]: https://wikimedia.org/api/rest_v1/media/math/render/svg/dfe7cd64f4f5efec58b4c345ee0948d8c3e2eef9
[epsilon]: https://wikimedia.org/api/rest_v1/media/math/render/svg/c3837cad72483d97bcdde49c85d3b7b859fb3fd2
[left_ _frac_ f_x_ _ f_x_ _ _right_. _left_ x _right]: https://wikimedia.org/api/rest_v1/media/math/render/svg/18db18f4c368c0d6350c4b4f56fe72971d0edf36
[SouthEast 2]: /images/20220718/97dd88038ffc468ca58436cdd5fbcdfc.png
[wikipedia_]: https://zh.wikipedia.org/wiki/%E6%9D%A1%E4%BB%B6%E6%95%B0
[SouthEast 3]: https://img-blog.csdn.net/20140504122601437?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvem91eHkwOQ==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[SouthEast 4]: /images/20220718/246e09c028e24865bb27c602955252be.png
[Link 5]: http://blog.csdn.net/pipisorry/article/details/52108040