线性方程组求解与矩阵求逆

1. 线性方程组
在大地测量数据处理方面，线性方程组的求解无疑是最重要的问题之一。线性方程组的通用形式可写为\( AX=B \)，系数矩阵A的维数为 \( (M，N) \)，\( M \)为观测方程的个数（等于观测值的个数，1个观测值一个方程），\(N\)为需要求解的系数个数，因此向量\( X \) 的长度为\( N \)，观测值向量\( B \)的长度为\( M \)。根据\(M\)和\( N \)的大小观测，可以将线性方程组分为三类：

• \( M > N \), 超定方程组（也称矛盾方程组），此时通常求方程的LS解；
• \( M = N \)，适定方程组，有唯一解；
• \( M < N \)，欠定方程组，有无数组解，但通常求其最小范数解。

接下来主要讨论超定方程组和适定方程组的情况。

对于超定方程组，根据LS准则，可得到法方程：\( A^TAX=A^TB \)，令\( C=A^TA，D=A^TB \)，则\( C \)的维数为\((N，N)\)，D的维数为\((N，1)\)，此时法方程的求解与适定方程组一致。下面的讨论以适定方程组为例。

2. 线性方程组的求解与求逆的关系

线性方程组\( AX=B \)的求解在数学上表示为\( X=A^{-1} \times B \)，但是在实际数值计算过程中，并不是一定要去计算\( A^{-1} \)，如常用的消去法，三角分解前推回代法等。

矩阵求逆等价于求解方程组\( AX=I \)，理论上与求解线性方程组一致。

在数值计算过程中，我们必须考虑计算的速度以及对内存的耗用情况，此时求逆和线性方程组的求解是两个不同的概念。

在求解线性方程组之前，必须明确你所需要的结果。如果只要最后结果\( X \)，则尽量不要去求逆；

如果系数阵\( A \)的求逆无法避免，尽量选择快速的求逆算法。当然，对于小矩阵，就不用考虑两者的差别了。

用matlab函数表示以上情况：

\( X=A\B \) (基于LU分解，前推回代直接求解参数向量\( X \))；

\( X=A^{-1} \cdot B \) （基于求逆求解参数向量\( X \) ）；

通常第一种方法速度快，占用内存少，但无法给出\( A^{-1} \)的信息。

3. 线性方程组的常用数值解法

通常把线性方程组的数值解法分为直接法和间接法。所谓直接法，就是经有限次运算即可求得方程组的精确解的方法；迭代法将求解的方程组转化为一个无限序列，其极限就是方程组的解。直接法一般来说用于求解系数矩阵阶数不是太高的问题，工作量较小，精度较高，但程序较复杂；迭代法主要用于一些高阶问题，一般程序较为简单，但工作量有时较大，耗用内存较多。

1> 直接法

 a. 克莱姆法则

\( x_i=\frac{det(A_i)}{detA} \)

算法复杂度：\( (n+1) \times [(n-1) \times n! + n!] \)

运算量非常大，理论上可行，实际计算中很少用；

三角形方程组的求解简单快速，所以通常将系数阵A转化为三角阵再进行运算。不同的分解形式对应不同的分解方法。求解下三角阵L的过程，称为前推\( (X_1-X_2---X_n) \);求解上三角阵U的过程，称为回代\( (X_n---X_2-X_1)\)。前推和回代的计算量一样，为\( \frac{n^2}{2} \)次乘法和加减法以及n次除法。

b. 高斯消去法

利用消去法，将方程组变换为上三角形方程组；整个消去过程需完成\( O(\frac{1}{3}n^3) \)次乘法和加法运算； 回代过程需\( \frac{n^2}{2} \)次乘法和加减法以及n次除法，故用消去法求解n阶方程组的计算量约为\( O(\frac{2}{3}n^3+2n^2) \)；

从高斯消去法进一步完善，产生了列主元和全主元消去法，这两种方法在消去过程中的计算量进一步增加，但方法上更严谨。

每一步消去过程对应系数阵A左乘了一个初等变换矩阵，这一系列初等变换矩阵的乘积对应一个下三角矩阵L，故高斯消去法理论上等价与LU分解法。

c. LU分解法

将系数阵A直接分解成两个三角阵的乘积，根据矩阵运算的规则计算每个三角阵的元素。分解后\( AX=B \)的计算转化为两个三角形方程组的求解：

\( LY=B \) （前推，计算出Y）

\( UX=Y \) （回代，计算出X）

算法复杂度为 \( O(\frac{2}{3}n^3+2n^2) \)，所以直接分解法与消去法的计算工作量基本上是相同的。

求解逆阵的算法复杂度为\( O(2n^3) \)，是求解线性方程组的3倍。

d. 正交分解法

将矩阵A分解为一个正交阵和一个上三角阵的乘积，\( A=QR \)。根据分解方法，通常有Householder方法（镜像映射法）和Schmidt正交化方法。

运算复杂度为：\( O(\frac{4}{3}n^3+2n^2) \)，与上面两种方法相比，运算量多一倍。

该方法在求解超定方程组时，较为优越，原因如下：
 \( A^TAX=A^TB \)  with \( A=QR \), then \( R^TQ^TQRX=R^TQ^TB \) and finally, \( RX=Q^TB \)，因此，QR分解大大减少了计算量。

e. 对称正定矩阵的平方根法和\( LDL^T\)分解法
对称正定矩阵是特殊矩阵，可以用平方根法和\( LDL^T\)分解法（通常也叫做Cholesky decomposition），其运算量和存储量较普通消去法和LU分解法均节省一半，为\( O(\frac{1}{3}n^3+2n^2) \)。
平方根分解：\( A=LL^T \)
\( LDL^T\)分解：\( L \) 为单位下三角阵

2> 迭代法
对于阶数不高的线性方程组，直接法有效，但对于阶数很高的矩阵，有时需要迭代法来解决。迭代的规则不同，迭代法也就不同。通常分为：线性迭代和非线性迭代；一阶迭代和P阶迭代；定常迭代和非定常迭代。具体，可参考教科书，如“数值计算方法（冯康）”。
共轭梯度法：非线性迭代法，适用于对称正定阵，不需选取任何迭代参数，使用方便。
此外，对于高阶方程组的处理通常还采用分块矩阵处理方法。节省内存需要量，但增加了计算量，需要更多的计算时间（由于内外存交换数据需要时间）。

4. 矩阵求逆
除了必须要求矩阵的逆，否则尽量不采用求逆阵的方法来求解线性方程组。
求逆阵的算法复杂度为\( O(2n^3) \)，大约是同等方法求线性方程组\( O(\frac{2}{3}n^3) \)的3倍。
矩阵乘积的算法复杂度和矩阵求逆是等价的。
矩阵求逆当前最快方法的复杂度为\( O(n^{2.37}) \)
高斯消去法，LU分解法，SVD等，复杂度都为\( O(n^3) \)，差别在于前面的系数。

特殊矩阵的处理通常会有特殊的方法，能大大减少运算量和存储量。