高斯消元


简单的讲,高斯消元就是模拟小学生解多元一次方程组的过程。只不过这种方法更有规律可循,更适合计算机去解决。

对于方程组

$$
\begin{Bmatrix}
k_{11}x + k_{12}y + k_{13}z = d_1 \\
k_{21}x + k_{22}y + k_{23}z = d_2 \\
k_{31}x + k_{32}y + k_{33}z = d_3 \\
\end{Bmatrix}$$

我们把它保存为一个增广矩阵,这个矩阵的意思就是每个未知数在每个方程中的系数,添上一列为未知数与系数积的和。

$$
\begin{Bmatrix}
k_{11} & k_{12} & k_{13} & | & d_1 \\
k_{21} & k_{22} & k_{23} & | & d_2 \\
k_{31} & k_{32} & k_{33} & | & d_3 \\
\end{Bmatrix}
$$

然后通过以下几种简单的操作,将这个矩阵变换

1.将矩阵的某一行同时乘一个数

2.将矩阵的某一行同时减去另一行

3.交换两行的顺序(即交换方程组中两个方程的顺序)

通过这些操作,我们的目标是将矩阵变换为如下的形式(就简称三角矩阵吧)

$$
\begin{Bmatrix}
a_{11} & a_{12} & a_{13} & | & d_1 \\
0 & a_{22} & a_{23} & | & d_2 \\
0 & 0 & a_{33} & | & d_3 \\
\end{Bmatrix}
$$

这样,可知$z=\frac{d_3}{a_{33}}$

将$z$代入2式又知$y=\frac{d_2-a_{23}z}{a_{22}}$

将$y$,$z$带入1式又知$x=\frac{d_1-a_{13}z-a_{12}y}{a_{11}}$

这个过程也可以称为“回代”

然而,如何获得一个三角矩阵呢?

这其实就是我们常用的加减消元法,对于A式和B式,通过给A式乘一个数,使两式主元系数相同,再由B式减去A式即可。这样原矩阵可以变成:(用2,3式减去1式)

$$
\begin{Bmatrix}
x & x & x & | & x \\
0 & x & x & | & x \\
0 & x & x & | & x \\
\end{Bmatrix}
$$

进而变成(用3式减去2式)

$$
\begin{Bmatrix}
x & x & x & | & x \\
0 & x & x & | & x \\
0 & 0 & x & | & x \\
\end{Bmatrix}
$$

由此获得了一个三角矩阵。这个过程也称为“消元”。


总结一下,高斯消元的总体过程就是:

消元->回代(废话)

但是这也会遇到几个问题:1.由于不断的乘除操作,未知数系数的误差会逐渐增大,以至结果十分离谱。2.如果方程无解或有无数解,我们又该如何知道呢?

对于问题1,我们可以采用分子分母表示法计算,或用实数计算时采用“列主消元”,就是每次用主元(要消的元)最大的方程去减其余的方程。请自行百度。

对于问题2,我们分情况讨论

1.可以变换成为严格的三角矩阵:有唯一解

如果无法构造出严格的三角矩阵,那么至少可以构造出如下的阶梯矩阵。

$$
\begin{Bmatrix}
x & x & x & x & ... & x & | & x_1 \\
0 & x & x & x & ... & x & | & x_2 \\
0 & 0 & 0 & x & ... & x & | & x_3 \\
... & ... & ... & ... & ... & x & | & ... \\
0 & 0 & 0 & 0 & ... & x & | & x_{n-2} \\
0 & 0 & 0 & 0 & ... & 0 & | & x_{n-1} \\
0 & 0 & 0 & 0 & ... & 0 & | & x_{n} \\
\end{Bmatrix}
$$

2.这个矩阵中如果系数全部为0的几行中(即$x_{n-2},x_{n-1},x_{n}$所在这几行),存在$x_{i}$不为0,那么方程组无解。

3.如果$x_{i}$都为0,那么方程组有无数组解。

在这里给出一个没有解个数判断的,不完备的,模块化的,分数表示的,不知道对不对的,贼jb长的:高斯消元模板。