题解：P2455 [SDOI2006] 线性方程组
LoongPig
·
·
题解
高斯-约旦消元法
基本操作：
对于一个有 m 个一次方程，n 个变量的线性方程组可以表示为一个增广矩阵。
举个栗子：
3x_1+7x_2-5x_3=47\\
x_1+4x_2+x_3=58\\
8x_1-3x_2+9x_3=88
\end{cases}\Rightarrow\left [
\begin{array}{c|c}
\begin{matrix}
3&7&-5\\
1&4&1\\
8&-3&9
\end{matrix}&
\begin{matrix}
47\\
58\\
88
\end{matrix}
\end{array}
\right ]
增广矩阵的 3 种变换，称为初等变换：
- 交换某两行的位置。
- 用一个非 0 的常数 k 乘某个方程。
- 把某一行乘 k 然后加到另一行上。
应该不用举栗子了吧。
解的情况
线性方程组的解有 3 种情况：
- 有唯一解：
3x_1+7x_2-5x_3=47\\
x_1+4x_2+x_3=58\\
8x_1-3x_2+9x_3=88
\end{cases}\Rightarrow\left [
\begin{array}{c|c}
\begin{matrix}
3&7&-5\\
1&4&1\\
8&-3&9
\end{matrix}&
\begin{matrix}
47\\
58\\
88
\end{matrix}
\end{array}
\right ]
首先把左边的方程组写成右边的增广矩阵，然后反复使用初等变换，得：
\begin{array}{c|c}
\begin{matrix}
3&7&-5\\
1&4&1\\
8&-3&9
\end{matrix}&
\begin{matrix}
47\\
58\\
88
\end{matrix}
\end{array}
\right ]\Rightarrow\left [
\begin{array}{c|c}
\begin{matrix}
3&7&-5\\
1&4&1\\
0&35&-1
\end{matrix}&
\begin{matrix}
47\\
58\\
376
\end{matrix}
\end{array}
\right ]\Rightarrow\left [
\begin{array}{c|c}
\begin{matrix}
3&7&-5\\
0&5&8\\
0&35&-1
\end{matrix}&
\begin{matrix}
47\\
127\\
376
\end{matrix}
\end{array}
\right ]\Rightarrow\left [
\begin{array}{c|c}
\begin{matrix}
3&7&-5\\
0&5&8\\
0&0&57
\end{matrix}&
\begin{matrix}
47\\
127\\
513
\end{matrix}
\end{array}
\right ]\Rightarrow\left [
\begin{array}{c|c}
\begin{matrix}
3&7&-5\\
0&5&8\\
0&0&1
\end{matrix}&
\begin{matrix}
47\\
127\\
9
\end{matrix}
\end{array}
\right ]\left [
\begin{array}{c|c}
\begin{matrix}
3&7&-5\\
0&5&0\\
0&0&1
\end{matrix}&
\begin{matrix}
47\\
55\\
9
\end{matrix}
\end{array}
\right ]\left [
\begin{array}{c|c}
\begin{matrix}
3&7&-5\\
0&1&0\\
0&0&1
\end{matrix}&
\begin{matrix}
47\\
11\\
9
\end{matrix}
\end{array}
\right ]\Rightarrow\left [
\begin{array}{c|c}
\begin{matrix}
1&0&0\\
0&1&0\\
0&0&1
\end{matrix}&
\begin{matrix}
5\\
11\\
9
\end{matrix}
\end{array}
\right ]
最后解得 x_1=5，x_2=11，x_3=9。这是唯一解，称最后得矩阵为简化梯形矩阵，特征是左半部分是一个单位矩阵。
- 有无穷多解：
3x_1+7x_2-5x_3=47\\
x_1+4x_2+x_3=58\\
2x_1+3x_2-6x_3=-11
\end{cases}\Rightarrow
\left [
\begin{array}{c|c}
\begin{matrix}
3&7&-5\\
1&4&1\\
2&3&-6
\end{matrix}&
\begin{matrix}
47\\
58\\
-11
\end{matrix}
\end{array}
\right ]\Rightarrow
\left [
\begin{array}{c|c}
\begin{matrix}
3&7&-5\\
0&5&8\\
0&0&0
\end{matrix}&
\begin{matrix}
47\\
127\\
0
\end{matrix}
\end{array}
\right ]
最后的矩阵出现了一个全都是 0 的行，说明这一行无效。3 个未知数，却只有两个方程，所以有无穷多个解。
- 无解：
3x_1+7x_2-5x_3=47\\
x_1+4x_2+x_3=58\\
2x_1+3x_2-6x_3=5
\end{cases}\Rightarrow
\left [
\begin{array}{c|c}
\begin{matrix}
3&7&-5\\
1&4&1\\
2&3&-6
\end{matrix}&
\begin{matrix}
47\\
58\\
5
\end{matrix}
\end{array}
\right ]\Rightarrow
\left [
\begin{array}{c|c}
\begin{matrix}
3&7&-5\\
0&5&8\\
0&0&0
\end{matrix}&
\begin{matrix}
47\\
127\\
16
\end{matrix}
\end{array}
\right ]
最后的矩阵出现了 0x_1+0x_2+0x_3=16 的矛盾方程，说明该方程组无解。
具体实现方法
- 从第一行开始，选择一个非 0 的系数（一般选择绝对值最大的系数，避免转换其他系数时产生过大的数值）所在的行，把这一行与第 1 行交换。此时 x_1 是主元；
- 把 x_1 的系数转换为 1；
- 利用主元 x_1 的系数，把其他行的这一列的主元消去；
- 重复上述步骤，直到该增广矩阵变为简化梯形矩阵。