高斯消元

现在不搞oi了，搞点数学的东西

近日被一学奥数的同学水了一把，于是补了一下高斯消元的知识

如下：

历史

该方法以数学家高斯命名，但最早出现于中国古籍《九章算术》，成书于约公元前150年。

例子

高斯消元法可用来找出下列方程组的解或其解的限制：

$2x + y - z = 8 \quad (L_1)$

$-3x - y + 2z = -11 \quad (L_2)$

$-2x + y + 2z = -3 \quad (L_3)$

这个算法的原理是：

首先，要将 $L 1$ 以下的等式中的 $x$ 消除，然后再将 $L 2$ 以下的等式中的 $y$ 消除。这样可使整毎方程组变成一个三角形似的格式。之后再将已得出的答案一个个地代入已被简化的等式中的未知数中，就可求出其余的答案了。

在刚才的例子中，我们将 $\begin{matrix}\frac{3}{2}\end{matrix} L_1$ 和 $L 2$ 相加，就可以将 $L 2$ 中的 $x$ 消除了。然后再将 $L 1$ 和 $L 3$ 相加，就可以将 $L 3$ 中的 $x$ 消除。

我们可以这样写：

$L_2 + \frac{3}{2}L_1 \rightarrow L_2$

$L_3 + L_1 \rightarrow L_3$

结果就是：

$2x + y - z = 8 \,$

$\frac{1}{2}y + \frac{1}{2}z = 1 \,$

$2y + z = 5 \,$

现在将 $- 4 L 2$ 和 $L 3$ 相加，就可将 $L 3$ 中的 $y$ 消除：

$L_3 + -4L_2 \rightarrow L_3$

其结果是：

$2x + y - z = 8 \,$

$\frac{1}{2}y + \frac{1}{2}z = 1 \,$

$-z = 1 \,$

这样就完成了整个算法的初步，一个三角形的格式出现了。

第二步，就是由尾至头地将已知的答案代入其他等式中的未之数。第一个答案就是：

$z = -1 \quad (L_3)$

然后就可以将 $z$ 代入 $L 2$ 中，立即就可得出第二个答案：

$y = 3 \quad (L_2)$

之后，将 $z$ 和 $y$ 代入 $L 1$ 之中，最后一个答案就出来了：

$x = 2 \quad (L_1)$

就是这样，这个方程组就被高斯消元法解决了。

这种算法可以用来解决所有线性方程组。即使一个方程组不能被化为一个三角形的格式，高斯消元法仍可找出它的解。例如在第一步化简后， $L 2$ 及 $L 3$ 中没有出现任何 $y$ ，没有三角形的格式，照着高斯消元法而产生的格式仍是一个行梯阵式。这情况之下，这个方程组会有超过一个解，当中会有至少一个变量作为答案。每当变量被锁定，就会出现一个解。

通常人或电脑在应用高斯消元法的时候，不会直接写出方程组的等式来消去未知数，反而会使用矩阵来计算。以下就是使用矩阵来计算的例子：

$\begin{pmatrix} 2 & 1 & -1 & 8 \\ -3 & -1 & 2 & -11 \\ -2 & 1 & 2 & -3 \end{pmatrix}$

跟着以上的方法来运算，这个矩阵可以转变为以下的样子：

$\begin{pmatrix} 2 & 1 & -1 & 8 \\ 0 & \frac{1}{2} & \frac{1}{2} & 1 \\ 0 & 0 & -1 & 1 \end{pmatrix}$

这矩阵叫做“行梯阵式”。

最后，可以利用同样的算法产生以下的矩阵，便可把所得出的解或其限制简明地表示出来：

$\begin{pmatrix} 1 & 0 & 0 & 2 \\ 0 & 1 & 0 & 3 \\ 0 & 0 & 1 & -1 \end{pmatrix}$

最后这矩阵叫做“简化行梯阵式”，亦是高斯－约当消元法指定的步骤。

其他应用

找出逆矩阵

高斯消元法可以用来找出一个可逆矩阵的逆矩阵。设 $A$ 为一个 $n \times n$ 的矩阵，其逆矩阵可被两个分块矩阵表示出来。将一个 $n \times n$ 单位矩阵放在 $A$ 的右手边，形成一个 $n \times 2n$ 的分块矩阵 $B = [A, I]$ 。经过高斯消元法的计算程序后，矩阵 $B$ 的左手边会变成一个单位矩阵 $I$ ，而逆矩阵 $A - 1$ 会出现在 $B$ 的右手边。

假如高斯消元法不能将 $A$ 化为三角形的格式，那就代表 $A$ 是一个不可逆的矩阵。

应用上，高斯消元法极少被用来求出逆矩阵。高斯消元法通常只为线性方程组求解。^[2]

计出秩的基本算法

高斯消元法可应用在任何 $m \times n$ 的矩阵 $A$ 。在不可减去某数的情况下，我们都只有跳到下一行。以一个 $6 \times 9$ 的矩阵作例，它可以变化为一个行梯阵式：

$\begin{pmatrix} 1 & * & 0 & 0 & * & * & 0 & * & 0 \\ 0 & 0 & 1 & 0 & * & * & 0 & * & 0 \\ 0 & 0 & 0 & 1 & * & * & 0 & * & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & * & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{pmatrix}$

而矩阵中的 *' 是一些数字。这个梯阵式的矩阵 $T$ 会有一些关于 $A$ 的资讯：

$A$ 的秩是5，因为 $T$ 有5行非0的行；
$A$ 的列的向量空间，可从 $A$ 的第1、3、4、7和9列中得知，其数值在矩阵 $T$ 之中；
矩阵中的 *' 表示了 $A$ 的列可怎样写为列中的数的组合。

分析

高斯消元法的算法复杂度是O(n³)；这就是说，如果系数矩阵的是n × n，那么高斯消元法所需要的计算量大约与n³成比例。

高斯消元法可以用在电脑中来解决数千条等式及未知数。不过，如果有过百万条等式时，这个算法会十分费时。一些极大的方程组通常会用叠代法来解决。亦有一些方法特地用来解决一些有特别排列的系数的方程组。

高斯消元法可用在任何域中。

高斯消元法对于一些矩阵来说是稳定的。对于普遍的矩阵来说，高斯消元法在应用上通常也是稳定的，不过亦有例外。^[3]

伪代码

高斯消元法的其中一种伪代码：

i := 1
j := 1
while (i ≤ m and j ≤ n) do
  Find pivot in column j, starting in row i:
  maxi := i
  for k := i+1 to m do
    if abs(A[k,j]) > abs(A[maxi,j]) then
      maxi := k
    end if
  end for
  if A[maxi,j] ≠ 0 then
    swap rows i and maxi, but do not change the value of i
    Now A[i,j] will contain the old value of A[maxi,j].
    divide each entry in row i by A[i,j]
    Now A[i,j] will have the value 1.
    for u := i+1 to m do
      subtract A[u,j] * row i from row u
      Now A[u,j] will be 0, since A[u,j] - A[i,j] * A[u,j] = A[u,j] - 1 * A[u,j] = 0.
    end for
    i := i + 1
  end if
  j := j + 1
end while

这个算法和之前谈及的有点儿不同，它由绝对值最大的部分开始做起，这样可以改善算法上的稳定性。将经过调换后的第一列作为起点，这算法由左至右地计算。每作出以下两个步骤，才跳到下一列：

定出每列的最后一个非0的数，将每行的数字除以该数，使到每行的第一个数成为1；
将每行的数字减去第一行的第一个数的某个倍数。

所有步骤完成后，这个矩阵会变成一个行梯阵式，再用代入法就可解决这个方程组。