2.2 The Idea of Elimination - 消元的概念

本节阐述一种系统的求解线性方程组的方式——消元

消元的目标是要得到上三角方程组

Before elimination:
$\begin{aligned} x-2y &=1 \\ 3x+2y &=11 \end{aligned}$x−2y3x+2y​=1=11​

• 第二行式子减去第一行式子的三倍，这里的三倍称为Multiplier

After elimination:
$\begin{aligned} x-2y &=1 \\ 8y &=8 \end{aligned}$x−2y8y​=1=8​

从第二行往上，就能够通过回代（back substitution） 的方法依次求出y和x的值，解和原方程相同

Multiplier的值通过第一行的主元（pivot） 来确定，主元就是每行的第一个非零未知量的系数

• Multiplier = (entry to eliminate) divided by (pivot)

在完成消元之后，主元都位于三角方程组的对角线上

Breakdown of Elimination - 消元失败

---

通常消元都能够使我们得到主元的值进而得到解

上部分消元之后的结果为
$\begin{aligned} x-2y &=1 \\ 8y &=8 \end{aligned}$x−2y8y​=1=8​

但消元也存在不可行的情况，例如假设第一个式子不变，第二个式子如下所示

• Permanent failure with no solution
  $\mathbf{0}y=8$0y=8

  这个式子使得第二个主元不存在，表现在行图像上就是平行的两条线，列图像上就是共线的两个向量

• Failure with infinitely many solutions
  $\mathbf{0}y=\mathbf{0}$0y=0

  这个式子使得第二个主元不存在，表现在行图像上就是重合的两条线。列图像上就是共线的两个向量

• Temporary failure (zero in pivot). A row exchange produces two pivots

  例如如下线性方程组
  $\begin{aligned} 0x+2y &=4 \\ 3x-2y &=5 \end{aligned}$0x+2y3x−2y​=4=5​

  主元的位置为0，可以通过换行的方式来使得消元可以继续

在上述的距离中，称前两个没有第二个主元的例子是奇异的，第三个例子是非奇异的

• 奇异的方程组没有解或者有无穷多个解
• 非奇异的方程组，有完整的主元，且只有一个解

Three Equations in Three Unknowns - 三个未知数

---

含有三个未知数的三个方程更容易帮助我们理解消元的含义
$\begin{aligned} 2x+4y-2z &=2 \\ 4x+9y-3z &=8\\ -2x-3y+7z &=10 \end{aligned}$2x+4y−2z4x+9y−3z−2x−3y+7z​=2=8=10​

通过消元我们将原来的$\mathbf{Ax=b}$Ax=b转变为一个上三角的$\mathbf{Ux=c}$Ux=c
$\begin{aligned} \mathbf{2}x+4y-2z &=2 \\ \mathbf{1}y+1z &=4\\ \mathbf{4}z &=8 \end{aligned}$2x+4y−2z1y+1z4z​=2=4=8​

可以解得$z=2,y=2,x=-1$z=2,y=2,x=−1，用列的视角来表示
$A \boldsymbol{x}=\left(\begin{array}{l} {-1} \end{array}\right)\left[\begin{array}{r} {2} \\ {4} \\ {-2} \end{array}\right]+2\left[\begin{array}{r} {4} \\ {9} \\ {-3} \end{array}\right]+2\left[\begin{array}{r} {-2} \\ {-3} \\ {7} \end{array}\right] \text { equals }\left[\begin{array}{r} {2} \\ {8} \\ {10} \end{array}\right]=b$Ax=(−1​)⎣⎡​24−2​⎦⎤​+2⎣⎡​49−3​⎦⎤​+2⎣⎡​−2−37​⎦⎤​ equals ⎣⎡​2810​⎦⎤​=b

Elimination from A to U - 从 A 到 U 的消元

---

对于更多未知数的情况，消元的方式也是相同的

1. 通过第一个式子使得第一个主元下的数字全是0
2. 通过新产生的第二个式子使得第二个主元下的数字全是0
3. 一直到第n列，重复操作直至找到所有主元，得到上三角矩阵U

---

总结：本节主要讲了高斯消元法的步骤，以及消元失败的三种情况