【数论】高斯消元

高斯消元

给出 \(n\) 组方程，每组方程形如 \(\sum\limits_{i=1}^n a_ix_i = b_i\)，要求求出 \(x_1, x_2 \cdots x_n\) 或告知无解。

我们把这些方程转化为矩阵 \(\begin{vmatrix} & a_{1,1} & a_{1,2} & a_{1,3} & \cdots & a_{1, n} & b_1 \\ & a_{2,1} & a_{1,2} & a_{1,3}& \cdots & a_{2, n} & b_2 \\ & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \\ & a_{n,1} & a_{n,2} & a_{n,3} & \cdots & a_{n, n} & b_n \\ \end{vmatrix}\)

我们希望最后的矩阵形如 \(\begin{vmatrix} & 1 & 0 & 0 & 0 & \cdots & 0 & c_1 \\ & 0 & 1 & 0 & 0 & \cdots & 0 & c_2 \\ & 0 & 0 & 1 & 0 & \cdots & 0 & c_3 \\ & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \\ & 0 & 0 & 0 & \cdots & 1 & 0 & c_{n-1} \\ & 0 & 0 & 0 & \cdots & 0 & 1 & c_n \\ \end{vmatrix}\)

对于第 \(i\) 行就能求出 \(x_i = c_i\)，即可求出解。

1. 我们从上往下做，先将当前系数绝对值最大的移到当前这一行，减小误差。
2. 让当前系数化为 \(1\)，即让当前行的每一个数都除以当前系数。
3. 再用当前第 \(i\) 行的第 \(i\) 个系数（即为 \(1\)）消去 $j \ (j \not= i) $ 的第 \(i\) 个系数，把它消为 \(0\)。

重复做以上的操作，直到做到第 \(n\) 行，此时最后的矩阵形如上述。

最后说一下如何判无解和无限解：

1. 无解：当前行系数全为 \(0\)，但值不为 \(0\)。

2. 无限解：当前行系数全为 \(0\)，且值为 \(0\)。

【数论】高斯消元

原文：https://www.cnblogs.com/chzhc-/p/14405827.html