Master Gaussian Elimination: Solving Linear Systems with Augmented Matrices

1 方程组(System of Equations)

线性方程组 (有这个未知量，所以也叫元一次方程组)

可以写成矩阵和列矢量相乘的形式

其中 是维度的矩阵，称为系数矩阵.

是 维列矢量.

是 维列矢量，称为常数列. 和 通常看做已知的，而 看做未知的，即方程组待求的解.

1.1 消元法

消元法是将方程组中的一方程的未知数用含有另一未知数的代数式表示，并将其代入到另一方程中，这就消去了一未知数，得到一解；或将方程组中的一方程倍乘某个常数加到另外一方程中去，也可达到消去一未知数的目的。消元法主要用于二元一次方程组的求解。

在方程组求解中：

1)两方程互换，解不变；

2)一方程乘以非零数k，解不变；

3)一方程乘以数 加上另一方程，解不变

1.2 方程组的解

方程式的解共有三种情况：

1、无解（出现了竖线左边没有未知数，右边是非零的情况）；

2、无穷组解（消元后不是完美的阶梯型，出现了很多全0行）；

3、唯一解

1.3 高斯消元法

高斯消元法，是线性代数中求解线性方程组的一种算法。它通常被理解为在相应的系数矩阵上执行的一系列操作。该方法还可用于求矩阵的秩，计算矩阵的行列式，以及计算可逆方阵的逆。该方法以卡尔·弗里德里希·高斯(1777-1855)的名字命名。

基本行操作有三种类型:

交换两行

将一行乘以一个非零数字

将一行的倍数添加到另一行

运用以上方法作，一个矩阵总是可以被转换成一个上三角矩阵，实际上是一个行阶梯形。一旦所有的主系数(每一行中最左边的非零项)都为1，并且包含主系数的每列在其他地方都为零，这个矩阵就称为行简化阶梯形。最终的形式是独特的;换句话说，它与所使用的行操作序列无关。

例如，在接下来的行运算序列中(每一步可能进行多个初等运算)，第三和第四个矩阵是行简化阶梯形矩阵，最终的矩阵是唯一的行简化阶梯形矩阵。

枚举每一列 1、找到当前这一列系数绝对值最大的一行（控制精度，有除法运算）；2、将该行与第一行进行交换；3、将改行第一个非零数变为1，后面的数同时做相应的改变；4、将下面所有行的这一列全部消为0；方程组的解共有三种情况：1、无解（出现了竖线左边没有未知数，右边是非零的情况）；2、无穷组解（消元后不是完美的阶梯型，出现了很多全0行）；3、唯一解（经过消元后成一个完美阶梯型）。

2 增广矩阵(Augmented Matrix)

对于方程组 写成矩阵形式为 增广矩阵为在系数矩阵基础上最后合并常数项矩阵形成的新矩阵：

3 简化阶梯型矩阵（Reduced Row Echelon Form）

3.1 定义

经过初等行变换, 可把矩阵化为行阶梯形矩阵, 其特点是: 可画出一条阶梯线, 线的下方全 为 0 ; 每个台阶只有一行, 台阶数即是非零行的行数, 阶梯线的坚线 (每段竖线的长度为一行)后面的第一个元素为非零元, 也就是非零行的第一个非零元.

任何矩阵，都可以通过矩阵的初等行变换，转换成行阶梯型矩阵。而行阶梯矩阵都可以继续通过初等行变换，转换成最简行阶梯矩阵。最简行阶梯矩阵，可以通过初等列变换，转换成标准型。

3.2 步骤

- 首先只做行变换。

- 固定一行，一般固定第一行，并且第一行的第一个元素最好为1。

- 固定好第一行后，用恰当的数乘以第一行，再加到其它行上去，并且把其它行的第一个元素全部化为0。

- 第一列完成化简，对第二行进行第一行时相同的操作，并且要保持第二行不变。

3.3 例子

考虑这个问题:已知点(1,3),(2, -2) ,(3, -5), and (4, 0)，如何找到一个经过这些点的三次多项式？

三次多项式的形式为

我们将点代入

增广矩阵是

解得最简阶梯形矩阵为

最后一列是解，即三次多项式的系数。所求三次多项式为

4 小结

本文主要介绍了方程组的高斯消元法及增广矩阵等概念。