线性方程组（一）：数值计算基本理论

1. 线性方程组问题

　　形如：$\sum\limits_{i=1}^n a_ix_i=b$ 的方程即线性方程；由关于一系列未知变量 $x_1, x_2, ...x_n$的同时成立的线性方程的集合构成线性方程组，即：$\sum\limits_{i=1}^n a_{ki}x_i=b_k, (k=1,2,...m)$ 即为一个由关于n个未知量的m个线性方程所构成的线性方程组。利用线性代数中矩阵和向量的一系列标记，可以将以上线性方程组写为：$$A_{m\times n}x_n=b_m,\quad或 Ax=b, \quad A = [a_{ij}] $$　　相当于 $m\times n$ 维矩阵A和 $n$ 维向量x的一次内积等于 $m$ 维向量b。其中A和b都是已知量，x为未知量，线性方程组问题就是求出可以使得方程成立的向量x。

　　线性方程组问题可以有很多种看法：可以看作是系数对于未知数的线性组合后形成一列新的数(b)；也可以看作是未知数对于系数矩阵的列向量进行线性组合，形成一个新的列向量(b)，因此如果要方程组有解，b一定要可以被系数矩阵A的列向量线性表出，换言之即 $b\in span(A)$ 。第二种看法对于理解第二部分解的存在唯一性是很有帮助的。

　　线性方程组问题及其数值解法在数值计算中有着基础而重要的地位。一方面，线性方程组本身就可以代表现实世界中的一大类模型，比如在小学初中课本上常常出现的给定预算规划购买方案等。另一方面，化曲为直的思想在数学的应用中常常表现为用线性在小范围内近似替代非线性，线性方程组问题能比较让人满意地通过数值方法解决可以说是讨论非线性方程（组）问题，当然也包括优化问题的基本前提；而对于数值计算中可能更为常用的一些问题，包括微（积）分方程边值问题（大气和水体的流动、岩石圈振动、静电场或电磁波传播等）等，这一系列问题的多种解决方法无一例外以回归到解线性方程组（很多时候是大型甚至超大型，这也意味着解线性方程组的数值方法在实践意义上必须足够高效迅速）问题告终。因此线性方程组的数值解法是重要的基础。

2. 解的性质：存在/唯一性

　　除了 $b\in span(A)$ 以外，线性代数知识还给出任意线性方程组解存在性的普遍判别法：记系数矩阵为 $A$ ，增广矩阵为 $\tilde{A}$ ，若 $rank(A)=rank(\tilde{A})$ 则线性方程组存在解。

　　对于线性方程组的系数矩阵 $A_{m\times n}$ ，若 $mn$ ，则为超定方程组，即“条件过剩”，即使 $A$ 已经列满秩，也总是存在一个空间，任意这一空间中的向量 $b$ 都能使得方程组无解。一般来讲在现实模型中，能够形成超定方程组的问题没有准确的解，但是可以通过最小二乘法或者其他优化方法获得残差最小的解。

　　当 $m=n$ 时，线性方程组的系数矩阵为方阵，在 $A$ 非奇异时，解有存在唯一性。所谓非奇异(Nonsingular)是指以下四个等价条件：$$A^{-1}存在\quad \Leftrightarrow \quad det(A)\neq 0 \quad \Leftrightarrow \quad rank(A)=n \quad \Leftrightarrow \quad Az\neq 0, \forall z\neq 0$$　　相反，任意违反一个条件（也就违反了所有四个条件）的矩阵均属奇异矩阵。

　　可以看出，当这四个等价条件满足时，由于 $A$ 的列向量已经构成了n维空间的一组基，$b\in span(A)$ 自动满足；类似地，因为矩阵的秩不能超过行/列维度，作为 $A$ 的扩充的增广矩阵 $rank(\tilde{A})=n$ 也自动满足，因此存在性无疑。另由于 $A$ 列向量线性无关，表出b的方法也唯一，因此方程组有唯一解。

3. 问题的性质：奇异性

　　奇异性的几何解释：线性方程组的每个方程均为n维空间中的一个平面（这里的平面指的是比空间维数少一维的集合，在二维空间中就是直线）。如果系数矩阵奇异，则行向量线性相关，那么也就是说存在一条行向量代表的平面，和其他行向量的一个线性组合所代表的平面，平行或者重合。线性方程组问题本身就是利用所有平面的交集来确定解的，若平面平行那么永无交集；若平面重合那么交集不唯一。

　　因此当系数矩阵奇异时，考虑到b的变化，方程组要么无解（平行），要么有无穷多组解（重合）。

　　奇异矩阵满足四个等价条件中的任意一条：$$A不可逆 \quad \Leftrightarrow \quad det(A)=0 \quad \Leftrightarrow \quad rank(A)