高斯消元法与矩阵的初等行运算

矩阵

系数矩阵和增广矩阵

将方程中未知数的系数形成的阵列称为方程组的系数矩阵，在系数矩阵的右端添加一列方程组的右端项，形成的矩阵称为方程组的增广矩阵。

矩阵的初等行运算

交换两行。
以非零实数乘以某行。
将某行替换为它与其他行的倍数之和。

严格三角形方程组

若方程组中，对于 $k =1,2, \cdots,n$ ，第 $k$ 个方程的前 $k-1$ 个变量的系数为 $0$ ，且 $x_k$ 的系数不为 $0$ ，则称这样的方程组为严格三角形方程组。

求解严格三角形方程组可以采用回代的方法，逐步求出 $x_n$ ， $x_{n-1}$ ，……， $x_1$ 。

思考：严格三角形方程组是否具有唯一解？

我们采用数学归纳法。

基础： $x_n$ 的系数不为 $0$ ，可以解出 $x_n$ 。
归纳：假设我们已经解出了 $x_{k+1} ,\cdots ,x_n$ ，第 $k$ 个方程必然能够化成 $mx_{k}=t$ 的形式，因为 $m$ 不等于 $0$ （严格三角形方程组的定义），可以得出 $x_k=\frac{t}{m}$ 。

思考：通过矩阵的初等行运算是否能够将任意增广矩阵化为严格三角形方程组？

答案是否定的，我们消元只能将增广矩阵化为“阶梯型”的方程组，也就是说不满足严格三角形方程组 $x_k$ 的系数不为 $0$ 的条件。

如果一个矩阵满足：

每一非零行中的第一个非零元为 1。
第 $k$ 行的元不全为 0 时，第 $k+1$ 行的首变量之前 0 的个数多于第 $k$ 行首变量之前 0 的个数。
所有元素均为 0 的行必在不全为 0 的行后。

则称这样的矩阵为行阶梯型矩阵。

这样的方程组可能无解，或者有无穷多组解，举两个简单的例子：

0x_1+x_2=2\\ 0x_1+x_2=1

无解。

0x_1+x_2=1\\ 0x_1+x_2=1

无穷多组解。

高斯消元就是通过矩阵的初等行运算，将线性方程组的增广矩阵化为行阶梯型。

高斯消元法

思考：既然矩阵的初等行运算只能将线性方程组的增广矩阵化为行阶梯型，那么如何判断是否有唯一解、无穷解、是否无解？

当且仅当可以化为严格三角形方程组时，方程组有唯一解。

若方程组不为严格三角形，则必然存在所有系数均为 0 的行。

若存在类似于：

[0,0,\cdots,0|0]

的行，说明缺少了限制条件，方程组可能无解或者有无穷解。

若存在类似于：

[0,0,\cdots,0|m],m\not=0

的行，说明方程组无解。

思考：如果不需要判断是否有无穷解，无解，遇到这种情况程序自动退出，该如何编写？

只需要判断是否满足严格三角形的条件。

namespace Gauss{
	double c[MAXN][MAXN];
	void gauss(int n){
		for (int i=1;i<=n;++i){
			for (int j=i+1;j<=n;++j){
				if (c[i][i]==0) puts("No Solution"),exit(0);//不满足严格三角形
				double rate=c[j][i]/c[i][i];
				for (int k=i;k<=n+1;++k) c[j][k]-=c[i][k]*rate;
			}
		}
		for (int i=n;i>=1;--i){
			for (int j=i+1;j<=n;++j){
				c[i][n+1]-=c[j][n+1]*c[i][j];
			}
			if (c[i][i]==0) puts("No Solution"),exit(0);//不满足严格三角形，可能位于末尾而在前面没有判定到
			c[i][n+1]/=c[i][i];
		}
	}
}
using namespace Gauss;

思考：如何减小误差？

int id=i;
for (int j=i+1;j<=n;++j){
	if (fabs(c[j][i])>fabs(c[id][i])) id=j;
}
if (id!=i) for (int j=i;j<=n+1;++j) swap(c[i][j],c[id][j]);

选取当前主元的系数绝对值最大的行即可。

高斯消元法的其他应用

基尔霍夫定律

任一节点上流出电流的量等于流入电流的量。
任一回路上电压的代数和等于各元件压降的代数和。

计算电阻的压降可以用欧姆定律：

E=iR

计算电池的压降可以用：

E=iR-\varepsilon

我们可以设未知数为每条导线上的电流 $i_j$ ，每个节点的电势 $\varphi_k$ 。其中 $j=1,2,\cdots,m$ ， $k=1,2,\cdots,n$ 。

对于每个节点，有 $\sum i=0$ ，对于每条边， $\varphi_u=\varphi_v+E$ ，列出 $n+m$ 个方程，即可求解。

配平化学方程式

利用好原子守恒即可。

计算概率和期望时使用马尔科夫方法

老生常谈了。

关于高斯消元和动态规划

我们推方程式经常会得出不同数之间的关系，将这些关系简单地看成一个图，如：

dp_{i,j,k}=dp_{i+1,j-1,k}+dp_{i,j+1,k-1}

看做 $dp_{i+1,j-1,k},dp_{i,j+1,k-1}$ 向 $dp_{i,j,k}$ 连一条边，称为 $dp_{i+1,j-1,k},dp_{i,j+1,k-1}$ 向 $dp_{i,j,k}$ 转移。

如果形成的图是一个 DAG，则我们采用传统动态规划或者记忆化搜索。

如果形成的图带环（如果是自环，可以转化为上面一种情况，详见下），我们可以采用高斯消元或者多次迭代。

例

https://zhuanlan.zhihu.com/p/500216185

令 $dp_{i,j,k}$ 表示 $i$ 个三蛋糕， $j$ 个二蛋糕， $k$ 个一蛋糕，到达这个状态的期望。

则：

dp_{i,j,k}=1+dp_{i,j,k}\frac{n-i-j-k}{n}+dp_{i-1,j+1,k}\frac{i}{n}+dp_{i,j-1,k+1} \frac{j}{n}+dp_{i,j,k-1} \frac{k}{n}

（这是向下 dp 的形式）

注意到这里存在一个自环，则我们可以把 $dp_{i,j,k}$ 解出来，破除自环，形成一个 DAG。

为什么是 DAG 呢？因为只可能从蛋糕个数少的转移到蛋糕个数多的，同样蛋糕个数之间无法相互转移。这样就保证了无环。

但是，这个转移的结构还是不太明晰，这样我们就可以采用记忆化搜索。

关于实现的细节，细心的读者会注意到，如果 $i=0,j=0,k=0$ ，则需要麻烦的分类讨论。

我们这里直接在函数那里加特判即可，不需要讨论，如 if i<0 return 0。