还在用高斯消元法解线性方程组？
求解线性方程组是线性代数中最基本的一个问题。对于这个问题，本科课本中只教授了高斯消元法求解，我自己也从来没有专门去查查是否有其它解法。直到学习了广义逆矩阵后，才发现原来还有这么一个形式简洁优美的求解方法。
背景
逆矩阵的概念只对非奇异矩阵才有意义，但是在实际问题中，我们遇到的矩阵不一定是可逆方阵，因此我们希望能将逆矩阵的概念推广到非方阵、奇异矩阵上。具体的：
- 这个矩阵对于奇异矩阵甚至长方形矩阵都存在；
- 它具有通常逆矩阵的一些性质；
- 当矩阵非奇异时，它还原到通常的逆矩阵；
满足以上三个条件的矩阵称为广义逆矩阵 （以下都简称为广义逆）
广义逆的概念最初由E.H.Moore在1920年提出，但其后的三十年时间，该理论都没有得到重视。直到1955年，R.Penrose以更明确的形式给出了Moore的广义逆的定义后，广义逆的研究才进入了一个新时期。之后，广义逆在数理统计、系统理论、优化计算和控制论等领域中的广泛应用都大大推动了广义逆的理论与应用研究。
老师在课上评价道，好的理论不一定会马上得到认可，如果你真的觉得自己的理论是有价值的，那就坚持下去吧！
Penrose的广义逆定义
设矩阵$A\in C^{m×n}$，若矩阵$X\in C^{n×m}$满足如下四个方程：
\(AXA=A \tag {i}\) \(XAX=X \tag {ii}\) \((AX)^H=AX \tag {iii}\) \((XA)^H=XA \tag {iv}\) 的$\underline{某几个或全部}$，则称$X$为$A$的广义逆矩阵；满足全部四个方程的广义逆矩阵$X$被称为$A$的Moore-Penrose逆，记为$A^＋$
对于任意的$A\in C^{m×n}$，$A^＋$存在且唯一。这里不加证明。
上述四个方程看起来并不方便记忆，不过可以按照以下思路理解：
对于一个非奇异矩阵$A$，它的逆矩阵$X$应该满足：$AX=I$. 但对于奇异矩阵或长方形矩阵$A$来说，它的广义逆矩阵$X$也许并不一定能满足$AX=I$，但如果能使得$\underline{AX}A=A$，那么我们就认为$AX$起到了单位矩阵（$AX=I$）的效果。
其余的三个方程同理。
求一个矩阵的广义逆
目前我了解到的有两种方法，分别基于(1).奇异值分解；(2).满秩分解。
(1).基于奇异值分解
对A做奇异值分解：
\[A=UDV^H， \quad \begin{bmatrix}\sigma_1 & & & \\ & \ddots & & O \\ & & \sigma_r & \\ &O&&O\end{bmatrix}_{m×n}\]其中$\sigma_i >0(i=1,\cdots,r)$是A的奇异值，U和V分别是m阶和n阶酉矩阵。 取
\[X=V\begin{bmatrix}\sigma^{-1}_1 & & & \\ & \ddots & & O \\ & & \sigma^{-1}_r & \\ &O&&O\end{bmatrix}_{n×m}U^H\]可以验证$X$满足四个Penrose方程。可见，$A^＋$总是存在的。
(2).基于满秩分解
对A做满秩分解：
\[A_{m×n}=F^{m×r}_r×G^{r×n}_r\]令$F^＋=(F^HF)^{-1}F^H，G^＋=G^H(GG^H)^{-1}$
则
\[A^{＋}=G^{＋}F^{＋}\]广义逆矩阵与线性方程的求解
知道了广义逆后，我们现在来看如何用它求解线性方程组。
如果存在$x$使得非齐次线性方程组$Ax=b$成立，则称该方程组$\underline{相容}$，否则称为$\underline{不相容}或\underline{矛盾方程组}$。
我们关心以下四个问题：
- 相容的条件是什么？通解怎么求？
- 如果相容，其解可能有无穷多个，求$\underline{极小范数解}$（即$min||x||,\ s.t\ Ax=b$）
- 如果不相容，求矛盾方程组的$\underline{最小二乘解}$
- 最小二乘解不唯一，求其$\underline{极小范数最小二乘解}$
这里不加证明地给出下列定理。
线性方程组的相容性和通解
定理：设$A\in C^{m×n}，B\in C^{p×q}，D\in C^{m×q}$，则矩阵方程$AXB=D\Leftrightarrow AA^{1}DB^{1}B=D$，其中\(A^{(1)}\in A\{1\}，B^{(1)}\in B\{1\}\)。
通解为$X=A^{(1)}DB^{(1)}+Y-A^{(1)}AYBB^{(1)}$，其中$Y\in C^{n×p}$任意。
相容线性方程组的极小范数解与广义{1,4}-逆
定理：设方程组$Ax=b$相容，则\(x=A^{(1,4)}b\)是极小范数解，其中\(A^{(1,4)}\in A\{1,4\}\)。
矛盾方程组的最小二乘解与广义{1,3}-逆
定理：设\(A\in C^{m×n}，b\in C^{m}，A^{(1,3)}\in A\{1,3\}\)，则\(x\in A^{(1,3)}b\)是方程$Ax=b$的最小二乘解。
矛盾方程组的极小范数最小二乘解与广义逆矩阵$A^+$
定理：设$A\in C^{m×n}，b\in C^{m}$，则$x=A^+b$是方程组$Ax=b$的极小范数最小二乘解。
有了上述定理后，当我们求解线性方程组$Ax=b$时:
-
先求出$A$矩阵的广义逆矩阵$A^+$，具体的两种求解方法已在上文给出。
-
然后计算$AA^+b$是否等于$b$。
-
如果线性方程组相容的话，那么一定满足$AA^+b=b$，同时求出的$A^+$就是方程组的解；
-
反之，如果$AA^+b\neq b$，那么方程组无解，求出的$A^+$就是方程组的极小范数最小二乘解。
如果平时手算求解三、四阶的线性方程组的话，还是用高斯消元法比较简单。不过，当矩阵的规模非常大时，就不能指望高斯消元法了，好在还能求诸广义逆来求解。
结语
当我们的思绪再次回到1920年，谁也不知道广义逆这样抽象的理论有何用。
数学家们造好了形状各异、精巧十足的积木，人类的求知的天梯才得以一阶一阶地向上搭建。
有几块积木暂时没被用到，但可能会有那么一天，到了某一阶，人们突然发现，之前的那块看似没用的积木用在这里刚刚好啊。
参考文献：
[1].《矩阵论》, 程云鹏, 西北工业大学出版社, 1989
[2]. lecture note, 张世华