跳到主要内容

矩阵的初等变换与线性方程组

线性方程组里容易记住的是操作步骤,容易含糊的却是步骤之间的关系:

  • 为什么要把某些数消成 00?
  • 为什么只能对“行”做同样的变换?
  • 主元为 00 时,究竟是算法卡住了,还是方程真的无解?
  • 初等矩阵和 LULU 分解为什么会从消元中出现?

这一节从一个二元方程组出发,再完整解一个三元方程组。我们会先用熟悉的方程语言计算,等每一步的目的都清楚以后,再把同一过程翻译成矩阵语言。这样,矩阵不是额外增加的一套规则,而是对已有操作的简洁记录。

先看一个几乎小到不能再小的方程组:

2x−y=1x+y=5(1.1)\begin{aligned} 2x - y &= 1 \\ x + y &= 5 \end{aligned} \tag{1.1}

这个方程组不难:两式相加,yy 被消掉,得到 3x=63x=6;因此 x=2x=2,代回任一方程便有 y=3y=3。

这里最值得注意的不是答案,而是“消掉 yy”这个动作。原来有两个未知数,经过一次适当的组合,只剩一个未知数;问题因此变简单了。高斯消元所做的,正是把这个朴素动作整理成一套可以处理任意规模方程组的算法。

先不急着计算。面对这两个方程,我们可以怎样理解“解”?

1. 在计算之前,先看清“解”是什么​

1.1 行图像:同时满足所有方程​

第一种看法最朴素,叫做行图像(row picture)。

2x−y=12x-y=1 是平面上的一条直线,x+y=5x+y=5 是另一条直线。一个数对要成为方程组的解,就必须同时落在两条直线上,所以解正是两条直线的交点 (2,3)(2,3)。

这个图像也提醒我们,方程组不一定总有唯一解:

  • 两条直线相交:有唯一解;
  • 两条不同的平行线:无解;
  • 两条直线重合:有无穷多解。

三个未知数时,每个方程通常表示三维空间中的一个平面。三个平面可能交于一点,也可能没有公共点,还可能共享一条直线。几何图像很直观,但超过三维以后,我们已经无法直接把它画出来。

1.2 列图像:用已知向量拼出目标向量​

于是换一种看法。先把式 (1.1) 中 xx 的系数排在一起,再把 yy 的系数排在一起:

x[21]+y[−11]=[15](1.2)x\begin{bmatrix} 2 \\ 1 \end{bmatrix} + y\begin{bmatrix} -1 \\ 1 \end{bmatrix} = \begin{bmatrix} 1 \\ 5 \end{bmatrix} \tag{1.2}

等号左边有两个已知向量:

a1=[21],a2=[−11]a_1=\begin{bmatrix}2\\1\end{bmatrix}, \qquad a_2=\begin{bmatrix}-1\\1\end{bmatrix}

现在的问题变成:能不能选出两个数 x,yx,y,使 xa1+ya2x a_1+y a_2 恰好等于右边的目标向量 b=(1,5)Tb=(1,5)^T?

在本例中,取 x=2,y=3x=2,y=3,确实有

2[21]+3[−11]=[15]2\begin{bmatrix}2\\1\end{bmatrix} +3\begin{bmatrix}-1\\1\end{bmatrix} =\begin{bmatrix}1\\5\end{bmatrix}Image

这叫列图像(column picture)。这里的 x,yx,y 不再只是两个抽象未知数,而是两列向量在线性组合中的权重。

AxAx 的含义由此变得具体:把 AA 的各列按 xx 的分量做线性组合。行图像让我们看见方程的交点,列图像则把“求解”改写成“能否用这些列拼出 bb”。后一种看法会自然引出列空间、秩和线性相关等概念。

1.3 从两种图像到 Ax=bAx=b​

把系数收进矩阵里,式 (1.1) 可以写成:

A=[2−111],x=[xy],b=[15],Ax=b(1.3)A = \begin{bmatrix} 2 & -1 \\ 1 & 1 \end{bmatrix},\quad x = \begin{bmatrix} x \\ y \end{bmatrix},\quad b = \begin{bmatrix} 1 \\ 5 \end{bmatrix},\qquad Ax = b \tag{1.3}

AxAx 有两种完全等价的读法。

按行读:

Ax=[2x−yx+y]Ax= \begin{bmatrix} 2x-y\\ x+y \end{bmatrix}

矩阵的每一行产生一个方程。按列读:

Ax=x[21]+y[−11]Ax= x\begin{bmatrix}2\\1\end{bmatrix} +y\begin{bmatrix}-1\\1\end{bmatrix}

矩阵的每一列参与一次线性组合。求解 Ax=bAx=b,既是在找所有方程的公共解,也是在找一组权重,把 AA 的列组合成 bb。

2. 为什么要消元​

如果直接盯着三个未知数同时变化,求解会很乱。更舒服的做法是逐层减少未知数:

  1. 先让第一个方程保留 x,y,zx,y,z,后面的方程都不再含 xx;
  2. 再让第二个方程保留 y,zy,z,第三个方程不再含 yy;
  3. 这样第三个方程只含 zz,可以立刻求出;随后依次求 yy 和 xx。

这就是消元(elimination)。它不是为了让矩阵看起来整齐,而是为了制造一个“最后一行只有一个未知数”的方程组。

来看一个三元例子:

{x+2y+z=23x+8y+z=124y+z=2A=[121381041],b=[2122](2.1)\begin{cases} x + 2y + z = 2 \\ 3x + 8y + z = 12 \\ 4y + z = 2 \end{cases} \qquad A = \begin{bmatrix} 1 & 2 & 1 \\ 3 & 8 & 1 \\ 0 & 4 & 1 \end{bmatrix},\quad b = \begin{bmatrix} 2 \\ 12 \\ 2 \end{bmatrix} \tag{2.1}

2.1 第一步:消去第二、三行中的 xx​

第一行先留着不动。我们盯住第一行 xx 的系数 11,用它去消掉后面各行的 xx。这个起带头作用的数叫第一个主元(pivot)。

第二行中 xx 的系数是 33。为了让它变成 00,需要用第二行减去 33 倍第一行:

(3x+8y+z)−3(x+2y+z)=12−3⋅2(3x+8y+z)-3(x+2y+z)=12-3\cdot2

整理后得到

2y−2z=62y-2z=6

这里的 33 叫做消元乘数(multiplier)。一般地,

ℓij=aij/ajj(2.2)\ell_{ij}=a_{ij}/a_{jj} \tag{2.2}

其中 ajja_{jj} 是第 jj 个主元,aija_{ij} 是它下方准备消掉的系数。本例中 ℓ21=3/1=3\ell_{21}=3/1=3。

第三行本来就是 4y+z=24y+z=2,不含 xx,所以不需要变化。完成第一列消元后,方程组成为

{x+2y+z=22y−2z=64y+z=2(2.3)\begin{cases} x+2y+z=2\\ 2y-2z=6\\ 4y+z=2 \end{cases} \tag{2.3}

只看系数矩阵,就是:

[12102−2041](2.4)\begin{bmatrix} 1 & 2 & 1 \\ 0 & 2 & -2 \\ 0 & 4 & 1 \end{bmatrix} \tag{2.4}

第一列现在是 (1,0,0)T(1,0,0)^T。这表示:第一行仍然含 xx,而第二、三行已经与 xx 无关。于是剩下两行构成一个只关于 y,zy,z 的二元方程组。

2.2 第二步:消去第三行中的 yy​

第二行中 yy 的系数 22 成为第二个主元。第三行中 yy 的系数是 44,所以新的乘数是 4/2=24/2=2。用第三行减去 22 倍第二行:

(4y+z)−2(2y−2z)=2−2⋅6(4y+z)-2(2y-2z)=2-2\cdot6

左边的 yy 正好抵消,得到

5z=−105z=-10

整个方程组现在变成

{x+2y+z=22y−2z=65z=−10(2.5)\begin{cases} x+2y+z=2\\ 2y-2z=6\\ 5z=-10 \end{cases} \tag{2.5}

对应的系数矩阵为

U=[12102−2005](2.6)U = \begin{bmatrix} 1 & 2 & 1 \\ 0 & 2 & -2 \\ 0 & 0 & 5 \end{bmatrix} \tag{2.6}

UU 表示 upper triangular,即上三角矩阵。所谓上三角,是指主对角线下方全为 00。这种形状之所以好,不是因为整齐,而是因为它对应一组从下往上越来越容易解的方程。

三个主元就是消元过程中依次承担带头作用的 1,2,51,2,5。它们都不为 00,所以第三行能确定 zz,第二行继而确定 yy,第一行最后确定 xx。

2.3 为什么右端也必须一起变换​

刚才每次变换的对象都是一个完整方程,并非只有等号左边。若第二行减去 33 倍第一行,右边也必须做 12−3⋅212-3\cdot2;否则等号就不再成立。

因此手算时最好使用增广矩阵,把系数和右端放在一起:

[1212381120412]⟶[121202−260412]⟶[121202−26005−10](2.7)\left[ \begin{array}{ccc|c} 1&2&1&2\\ 3&8&1&12\\ 0&4&1&2 \end{array} \right] \longrightarrow \left[ \begin{array}{ccc|c} 1&2&1&2\\ 0&2&-2&6\\ 0&4&1&2 \end{array} \right] \longrightarrow \left[ \begin{array}{ccc|c} 1&2&1&2\\ 0&2&-2&6\\ 0&0&5&-10 \end{array} \right] \tag{2.7}

竖线只是帮助阅读,不参与计算。最后得到的方程是 Ux=cUx=c,其中

c=[26−10](2.8)c=\begin{bmatrix}2\\6\\-10\end{bmatrix} \tag{2.8}

2.4 回代:沿着消元的反方向求解​

现在从最后一行往上解,这叫回代(back substitution):

5z=−10⇒z=−22y−2z=6⇒y=1x+2y+z=2⇒x=2(2.9)\begin{aligned} 5z &= -10 &&\Rightarrow\quad z=-2 \\ 2y - 2z &= 6 &&\Rightarrow\quad y=1 \\ x + 2y + z &= 2 &&\Rightarrow\quad x=2 \end{aligned} \tag{2.9}

所以解向量为

[xyz]=[21−2]\begin{bmatrix}x\\y\\z\end{bmatrix} = \begin{bmatrix}2\\1\\-2\end{bmatrix}

不妨停下来检查一次:

2+2(1)−2=2,3(2)+8(1)−2=12,4(1)−2=2.\begin{aligned} 2+2(1)-2&=2,\\ 3(2)+8(1)-2&=12,\\ 4(1)-2&=2. \end{aligned}

三个原方程都成立。至此,消元的计算过程已经完整走完。

接下来要回答一个比“怎么算”更重要的问题:这些行变换为什么不会改变方程组的解?

3. 为什么行变换不改变解​

先从方程本身看。若一个数值组合 (x,y,z)(x,y,z) 同时满足第一、二个方程,那么它当然也满足“第二个方程减去三倍第一个方程”。反过来,如果它满足第一个方程,也满足变换后的第二个方程,那么把三倍第一个方程加回去,就能恢复原来的第二个方程。

所以“第二行减去三倍第一行”是可逆的。新旧方程组只是写法不同,解集相同。

还可以把这个操作写成矩阵乘法。这样做不是为了增加符号,而是为了把多步行变换组合起来,并最终看出 LULU 分解从何而来。

3.1 怎样构造消元矩阵​

单位矩阵左乘任何矩阵都不改变它:

IA=AIA=A

如果在 II 上先做“第二行减去 33 倍第一行”,便得到

E21=[100−310001](3.1)E_{21} = \begin{bmatrix} 1 & 0 & 0 \\ -3 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} \tag{3.1}

为什么它左乘 AA 后恰好改变第二行?观察乘积的三行:

  • E21E_{21} 第一行是 (1,0,0)(1,0,0),所以取出 AA 的第一行;
  • 第二行是 (−3,1,0)(-3,1,0),所以得到 −3A-3A 的第一行加 AA 的第二行;
  • 第三行是 (0,0,1)(0,0,1),所以取出 AA 的第三行。

因此

E21A=[12102−2041](3.2)E_{21}A = \begin{bmatrix} 1 & 2 & 1 \\ 0 & 2 & -2 \\ 0 & 4 & 1 \end{bmatrix} \tag{3.2}

下标 2121 提醒我们:变化发生在第 2 行,用到第 1 行。类似地,“第三行减 22 倍第二行”对应

E32=[1000100−21](3.3)E_{32} = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & -2 & 1 \end{bmatrix} \tag{3.3}

两步依次作用,就有

E32(E21A)=U(3.4)E_{32}(E_{21}A) = U \tag{3.4}

乘法可以结合,括号挪一下也一样:

(E32E21)A=U(3.5)(E_{32}E_{21})A = U \tag{3.5}

这表明多步消元也能合成一次矩阵乘法。算出两个消元矩阵的乘积:

E32E21=[100−3106−21](3.6)E_{32}E_{21} = \begin{bmatrix} 1 & 0 & 0 \\ -3 & 1 & 0 \\ 6 & -2 & 1 \end{bmatrix} \tag{3.6}

注意顺序:E21E_{21} 先接触 AA,所以先做;E32E_{32} 后作用。矩阵从右向左作用,因此先做的矩阵写在更靠右的位置。

3.2 三种初等行变换​

在单位矩阵上做一次行变换得到的矩阵,叫做初等矩阵。允许使用的基本行变换有三种:

  1. 一行加上另一行的若干倍;
  2. 交换两行;
  3. 一行乘一个非零常数。

它们都可逆:减去的可以加回去,交换的两行可以再交换一次,乘上的非零常数可以用其倒数除回去。因此这些操作都不会改变方程组解集的本质。

为什么是左乘?

矩阵乘法中,EAEA 的每一行是 AA 各行的线性组合,所以左乘改变行;AEAE 的每一列是 AA 各列的线性组合,所以右乘改变列。一个方程对应系数矩阵的一行,因此对方程做变换时必须左乘。

3.3 用逆矩阵恢复消元前的方程​

刚才是“第二行减去 33 倍第一行”,反过来就是“第二行加上 33 倍第一行”:

E21−1=[100310001](3.7)E_{21}^{-1} = \begin{bmatrix} 1 & 0 & 0 \\ 3 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} \tag{3.7}

确实有 E21−1E21=IE_{21}^{-1}E_{21}=I。如果

EAx=EbEAx=Eb

那么在两边左乘 E−1E^{-1},就恢复为 Ax=bAx=b。新旧方程组能够互相恢复,所以解完全相同。这就是消元可信的代数原因。

4. 主元为 00 时发生了什么​

计算乘数时要除以主元,所以主元不能为 00。但“主元位置出现 00”和“方程组无解”不是一回事,需要分两种情况看。

4.1 下面还有非零数:交换两行继续​

例如

[0123]\begin{bmatrix} 0&1\\ 2&3 \end{bmatrix}

左上角是 00,但下面还有 22。交换两行,就可以让 22 成为第一个主元。交换方程的先后顺序显然不会改变解,因此这只是算法暂时卡住,并不代表矩阵不可逆。

对换第 1、2 行可以写成左乘置换矩阵

P=[010100001](4.1)P = \begin{bmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix} \tag{4.1}

更一般地,数值计算即使遇到一个很小但非零的主元,也常把绝对值更大的数换上来,以免除法放大舍入误差。这叫选主元(pivoting)。

4.2 下面也全为 00:这一列没有主元​

如果主元位置是 00,下方也全是 00,行交换就无能为力了。这一列无法产生主元,说明某个未知数不能被方程独立确定。

对 n×nn\times n 方阵,可以记住下面这个判据:

A 可逆  ⟺  消元能找出 n 个非零主元(4.2)A\text{ 可逆} \;\Longleftrightarrow\; \text{消元能找出 }n\text{ 个非零主元} \tag{4.2}

但“矩阵不可逆”仍不能直接告诉我们是无解还是无穷多解,还要看增广矩阵的右端。例如消元后出现

[12\vline300\vline1]\begin{bmatrix} 1&2&\vline&3\\ 0&0&\vline&1 \end{bmatrix}

第二行表示 0=10=1,矛盾,所以无解。若出现

[12\vline300\vline0]\begin{bmatrix} 1&2&\vline&3\\ 0&0&\vline&0 \end{bmatrix}

第二行只是 0=00=0,没有提供新约束,因此会留下自由变量,产生无穷多解。

所以应当分清三件事:

  • 主元位置为 00、下方非零:交换行,继续消元;
  • 某列找不到主元:矩阵不可逆;
  • 不可逆系统究竟无解还是无穷多解:继续查看右端是否产生矛盾行。

5. 从消元自然得到 A=LUA=LU​

消元把 AA 变成了 UU。如果只关心一次求解,到这里已经足够;但如果希望保存整个消元过程,就需要把用过的乘数记录下来。

本例只用了两个非零乘数:

ℓ21=3,ℓ32=2\ell_{21}=3,\qquad \ell_{32}=2

ℓ21=3\ell_{21}=3 表示用第 1 行消第 2 行,ℓ32=2\ell_{32}=2 表示用第 2 行消第 3 行。把它们放到单位下三角矩阵的对应位置:

L=[100310021],U=[12102−2005](5.1)L = \begin{bmatrix} 1 & 0 & 0 \\ 3 & 1 & 0 \\ 0 & 2 & 1 \end{bmatrix},\qquad U = \begin{bmatrix} 1 & 2 & 1 \\ 0 & 2 & -2 \\ 0 & 0 & 5 \end{bmatrix} \tag{5.1}

第三行第一列原本就是 00,所以 ℓ31=0\ell_{31}=0。直接相乘可验证

A=LU(5.2)A = LU \tag{5.2}

5.1 为什么乘数恰好组成 LL​

前面的两步消元是

E32E21A=UE_{32}E_{21}A=U

要把 UU 恢复成 AA,依次撤销两步操作:

A=E21−1E32−1UA=E_{21}^{-1}E_{32}^{-1}U

而

E21−1E32−1=[100310021]=LE_{21}^{-1}E_{32}^{-1} = \begin{bmatrix} 1&0&0\\ 3&1&0\\ 0&2&1 \end{bmatrix} =L

因此 A=LUA=LU。UU 是消元后的结果,LL 则保存消元时用过的乘数。两者合起来,完整记录了原矩阵。

这里有一个使用条件:上面这种直接把乘数填进 LL 的写法,假设消元过程中没有交换行。若发生行交换,需要先用置换矩阵 PP 记录排列:

PA=LU(5.3)PA = LU \tag{5.3}

5.2 为什么要保存为 LULU​

将 Ax=bAx=b 中的 AA 换成 LULU:

LUx=bLUx=b

可以引入中间向量 c=Uxc=Ux,把一个问题拆成两个三角方程组:

{Lc=b,Ux=c.\begin{cases} Lc=b,\\ Ux=c. \end{cases}

先从上往下解 Lc=bLc=b,称为前代;再从下往上解 Ux=cUx=c,称为回代。

当 AA 固定而 bb 经常变化时,LULU 只需计算一次。以后每来一个新的 bb,只做两次三角求解,不必重新消元。这是 LULU 分解在实际计算中的主要价值。

6. 消元、可逆与逆矩阵​

如果方阵 AA 有 nn 个非零主元,它就可逆。从 A=LUA=LU 立刻有

A−1=U−1L−1(6.1)A^{-1} = U^{-1}L^{-1} \tag{6.1}

因为乘积求逆时顺序要倒过来:

(LU)−1=U−1L−1(LU)^{-1}=U^{-1}L^{-1}

有行交换、即 PA=LUPA=LU 时,则

A−1=U−1L−1PA^{-1}=U^{-1}L^{-1}P

求逆的一种做法,是对增广矩阵 [A∣I][A\mid I] 继续做 Gauss–Jordan 消元:

[A∣I]⟶[I∣A−1][A\mid I]\longrightarrow[I\mid A^{-1}]

右边的 II 有 nn 列,所以这件事本质上是在同时求解

Ax=e1,Ax=e2,…,Ax=enAx=e_1,\quad Ax=e_2,\quad\ldots,\quad Ax=e_n

所得解恰好组成 A−1A^{-1} 的各列。

因此没有必要把行列式当成求解方程组的起点。消元先给出主元和解;行列式随后概括这些主元的信息;特征值解决的则是另一类问题。就当前问题而言,判断可逆只需看能否找到 nn 个主元。


回头看整个过程:

  1. Ax=bAx=b 既可以看作若干方程的公共解,也可以看作列向量的线性组合;
  2. 消元逐列制造 00,把一般方程组化成容易回代的上三角方程组;
  3. 每一步行变换都可逆,所以变换前后解集相同;
  4. 初等矩阵把行变换写成矩阵乘法;
  5. UU 保存消元结果,LL 保存消元乘数,因此得到 A=LUA=LU;
  6. 主元是否齐全,决定方阵是否可逆。

这几部分不是彼此孤立的概念。它们描述的是同一件事的不同层面:方程语言告诉我们在消什么,矩阵语言告诉我们变换如何组合,LULU 分解则把整个消元过程保存下来。

Reference​

[1] Strang, Gilbert. Introduction to Linear Algebra. Wellesley-Cambridge Press.

[2] MIT OpenCourseWare. 18.06 Linear Algebra(Lecture 1–4).

[3] MIT OCW 18.06SC. Elimination with Matrices.