线性方程组、消元与 LU 分解

方程组研究的是共同满足条件的输入

关于未知量 $x_1,\ldots,x_n$ 的线性方程，具有形式

$$a_1x_1+\cdots+a_nx_n=b,$$

其中系数与右端都是已知数。未知量只以一次项出现，不互相相乘，也不出现在分母或非线性函数内部。例如 $2x-y=3$ 是线性方程，而 $xy=3$、$x^2+y=1$ 都不是。对于 $a=0$ 这样的特殊系数，某个未知量可以完全不出现在方程里。

线性方程组要求同一组未知量同时满足多个这样的等式。用矩阵写成 $A\mathbf x=\mathbf b$，有两种互补的读法：逐行看，每行是一条约束；按列看，是寻找系数，把矩阵的列组合成 $\mathbf b$。

例相交、重合与平行

在平面中，方程 $x+y=2$ 描述一条直线。再加 $x-y=0$，两条直线相交于 $(1,1)$，得到唯一解。

若第二条改成 $2x+2y=4$，它只是第一条的两倍，所有 $(t,2-t)$ 都满足系统。若改成 $2x+2y=5$，则两式矛盾，没有解。

所以，未知量与方程的数量只能提供初步线索。真正决定解的情况的是约束之间的独立性与右端是否相容。

消元的目标不是直接猜出所有未知量

消元先把约束整理成逐层可读的形式：有些变量能从别的变量确定，有些变量仍可自由选择，还有些系统会暴露矛盾。我们改变的是方程的表达方式，始终要求解集不变。

接下来先用守恒模型得到一套方程，再完整追踪这一过程。案例之后会把步骤抽成通用算法，并解释如何把消元记录成 LU 分解。

守恒提供了方程，为什么还不能确定车流

考虑四个路口 $A,B,C,D$，内部道路方向如下。每个 $x_i$ 表示同一时间单位内沿箭头方向通过的车辆数：

道路	方向
$x_1$	$D\to B$
$x_2$	$A\to B$
$x_3$	$C\to A$
$x_4$	$C\to D$
$x_5$	$B\to C$

假设统计期间路口没有车辆积累，流入等于流出。外部测量给出路口 $B$ 净流出 $45$，$C$ 净流入 $45$，$A$ 净流入 $10$，$D$ 净流出 $10$。这些外部收支和内部道路构成一个可以用守恒方程描述的网络[1][1] X. Yang, “ENG1005 Week 2: Traffic Flow, Personal Workshop Solutions,” 2024. Personal solutions to Monash ENG1005 workshop problems; source snapshot 77ebe58de2fea53d62533d6dd23caa16108ed109. Repository access may be restricted.. https://github.com/Eryc123Y/ENG1005-2024S2/blob/77ebe58de2fea53d62533d6dd23caa16108ed109/Source%20Code/W2.tex。

按 $B,C,A,D$ 的顺序写方程：

$$\begin{cases} x_1+x_2-x_5=45,\\ x_3+x_4-x_5=45,\\ -x_2+x_3=-10,\\ -x_1+x_4=10. \end{cases}$$

每个方程单独看都合理，但不能仅凭“四个方程”就声称有四条独立信息。

行变换为什么保持解集

用增广矩阵把系数与右端放在一起：

$$[A\mid\mathbf b]= \left[\begin{array}{rrrrr|r} 1&1&0&0&-1&45\\ 0&0&1&1&-1&45\\ 0&-1&1&0&0&-10\\ -1&0&0&1&0&10 \end{array}\right].$$

允许的初等行变换有三种：交换两行；把一行乘以非零数；把另一行的倍数加到当前行。每一步都有逆操作，所以变换前后满足的是同一组未知量。

把一行减去自身没有逆操作，会直接删掉一条约束，不能当作等价消元。例如，单个方程 $x=1$ 若被替换成 $0=0$，原来唯一的解就会变成任意实数。

先依次执行

$$R_4\leftarrow R_4+R_1,\qquad R_2\leftrightarrow R_3,\qquad R_2\leftarrow -R_2.$$

结果为

$$\left[\begin{array}{rrrrr|r} 1&1&0&0&-1&45\\ 0&1&-1&0&0&10\\ 0&0&1&1&-1&45\\ 0&1&0&1&-1&55 \end{array}\right].$$

接着做 $R_4\leftarrow R_4-R_2$，第四行变成与第三行相同的方程；再做 $R_4\leftarrow R_4-R_3$，才合法地得到零行：

$$\left[\begin{array}{rrrrr|r} 1&1&0&0&-1&45\\ 0&1&-1&0&0&10\\ 0&0&1&1&-1&45\\ 0&0&0&0&0&0 \end{array}\right].$$

这是行阶梯形：非零行的第一个非零元素叫主元，主元位置逐行向右移动，零行位于底部。若继续让主元为 $1$ 并消去主元上方的元素，就得到简化行阶梯形。

主元、自由变量与完整解集

继续消元可得

$$\left[\begin{array}{rrrrr|r} 1&0&0&-1&0&-10\\ 0&1&0&1&-1&55\\ 0&0&1&1&-1&45\\ 0&0&0&0&0&0 \end{array}\right].$$

前三列有主元，$x_4,x_5$ 可自由指定。令 $s=x_4,t=x_5$，则

$$\mathbf x= \begin{pmatrix}s-10\\55-s+t\\45-s+t\\s\\t\end{pmatrix} =\underbrace{\begin{pmatrix}-10\\55\\45\\0\\0\end{pmatrix}}_{\mathbf x_p} +s\underbrace{\begin{pmatrix}1\\-1\\-1\\1\\0\end{pmatrix}}_{\mathbf v_1} +t\underbrace{\begin{pmatrix}0\\1\\1\\0\\1\end{pmatrix}}_{\mathbf v_2}.$$

$\mathbf x_p$ 是一组代数特解，未必满足实际道路的非负要求。两个方向满足 $A\mathbf v_1=A\mathbf v_2=\mathbf0$：沿这些方向改变内部车流，不会改变外部守恒数据。

实际单向车流还要求所有分量非负，因此

$$s\ge10,\qquad t\ge0,\qquad s\le45+t.$$

例如 $s=20,t=0$ 给出 $(10,35,25,20,0)^{\mathsf T}$，是可行车流。线性方程给出一个平移后的平面，非负限制再从中选出可行区域。

秩怎样概括解的情况

矩阵的秩可以定义为列空间的维数，也等于行阶梯形中主元的数量。这里先用主元计数；向量空间与基会解释它与维数的联系。

对于 $m$ 个方程、$n$ 个未知量的实线性系统：

消元结果	解的情况
出现 $0=c$，其中 $c\ne0$	无解
没有矛盾行，且每个未知量所在列都有主元	唯一解
没有矛盾行，但有自由变量	无穷多解

相应地，有解等价于 $\operatorname{rank}(A)=\operatorname{rank}([A\mid\mathbf b])$；一致系统的自由变量数为 $n-\operatorname{rank}(A)$。本例秩为 $3$，因此有两个自由变量。

为什么恰好少一条独立方程？原系数行满足 $R_1-R_2+R_3+R_4=0$，右端也满足 $45-45-10+10=0$。把全部路口的守恒相加时，内部道路的流入和流出会抵消，只剩下整个区域的外部收支。矩阵与图会把这个现象写成关联矩阵的性质。

把消元写成一般步骤

设增广矩阵有 $m$ 行，系数部分有 $n$ 列。用 $r$ 表示下一个主元应该放入的行，开始时 $r=1$。依次查看系数列 $j=1,\ldots,n$：

1. 在第 $r$ 行及其下方，寻找第 $j$ 列的非零元素。若没有，这一列没有新的主元，继续下一列。
2. 若找到第 $p$ 行，就交换第 $p$ 行与第 $r$ 行。此时主元为 $a_{rj}\ne0$。
3. 对每个 $i>r$，用倍数 $a_{ij}/a_{rj}$ 消去主元下方的元素。整行操作必须包含右端。
4. 令 $r$ 增加一。若已没有待处理的行，就停止。

这得到行阶梯形。若需要简化行阶梯形，再从最后一个主元向上处理：把主元归一化成 $1$，并消去其上方的元素。求一个可逆三角系统的解时，后向代入通常已经足够，不必把矩阵彻底化成单位矩阵。

“找不到当前列的主元”不等于系统无解，只说明这个位置没有新约束。例如，一个零系数列对应完全不受任何方程限制的未知量。无解必须由增广矩阵中的矛盾行判断。

含参数的方程怎样分类

考虑

$$\begin{cases} x+y=2,\\ 2x+\lambda y=\mu. \end{cases}$$

第二式减去第一式的两倍，得到

$$(\lambda-2)y=\mu-4.$$

如果 $\lambda\ne2$，便有唯一解

$$y=\frac{\mu-4}{\lambda-2},\qquad x=2-y.$$

如果 $\lambda=2,\mu=4$，第二式变成恒等式，$y$ 自由，解为 $(2-t,t)$。如果 $\lambda=2,\mu\ne4$，则出现 $0=\mu-4$，系统无解。

这里必须先分情况，再除以 $\lambda-2$。若一开始就直接相除，会漏掉全部多解与无解情形。

为什么一致的线性系统不会恰好有两个解

若 $\mathbf x_1\ne\mathbf x_2$ 都满足同一个系统，则对每个实数 $t$，

$$A\bigl(\mathbf x_1+t(\mathbf x_2-\mathbf x_1)\bigr) =\mathbf b+t(\mathbf b-\mathbf b)=\mathbf b.$$

随着 $t$ 改变，这些解互不相同。所以在实数范围内，解的数量只能是零、一个或无穷多个。这是线性结构的结论，不适用于一般非线性方程。

增加测量，必须增加独立的信息

只测量 $x_5=t$ 会固定一个参数，但 $s$ 仍可变化。若希望通过线性测量唯一确定一般车流，需要消除两个自由方向。

测量 $x_4$ 和 $x_5$ 就能做到。反之，同时测量 $x_1$ 与 $x_4$ 仍不足够，因为原系统已经要求 $x_4-x_1=10$；这两个读数只确定同一个参数 $s$。

更一般地，把新增测量写成 $M\mathbf x=\mathbf d$。代入参数解后，真正需要检验的是两列 $M\mathbf v_1,M\mathbf v_2$ 是否线性无关。测量数量够了，不等于信息足够。这里讨论的是线性等式对一般状态的辨识；特定边界上的非负限制可能进一步收缩可行集。

LU：把一次消元留给多个右端

交通流系统是矩形且秩亏的。为了展示可逆系统的普通 LU 分解，回到矩阵章的插值矩阵：

$$V=\begin{pmatrix}1&1&1\\4&2&1\\9&3&1\end{pmatrix},\qquad \mathbf y=\begin{pmatrix}6\\7\\5\end{pmatrix}.$$

依次做

$$R_2\leftarrow R_2-4R_1,\qquad R_3\leftarrow R_3-9R_1,\qquad R_3\leftarrow R_3-3R_2,$$

得到上三角矩阵

$$U=\begin{pmatrix}1&1&1\\0&-2&-3\\0&0&1\end{pmatrix}.$$

把消元倍数记录在下三角矩阵中：

$$L=\begin{pmatrix}1&0&0\\4&1&0\\9&3&1\end{pmatrix}.$$

于是 $V=LU$。可以直接按行检验：$LU$ 的第二行是 $4U_1+U_2$，第三行是 $9U_1+3U_2+U_3$，分别恢复原矩阵的第二、第三行。一般情形中，把初等消元矩阵连乘可写成 $EV=U$；在无需换行的标准消元下，逆操作的乘积构成 $L=E^{-1}$。

原方程因此拆成两个三角系统：

$$L\mathbf z=\mathbf y,\qquad U\mathbf c=\mathbf z.$$

前向代入给出

$$z_1=6,\qquad z_2=7-4z_1=-17,\qquad z_3=5-9z_1-3z_2=2.$$

后向代入则得到

$$\gamma=2,\qquad -2\beta-3\gamma=-17,\qquad \alpha+\beta+\gamma=6,$$

所以 $\alpha=-3/2,\beta=11/2,\gamma=2$。这正是插值所需的系数[2][2] X. Yang, “ENG1005 Week 3: Interpolation and Fitting, Personal Workshop Solutions,” 2024. Personal solutions to Monash ENG1005 workshop problems; source snapshot 77ebe58de2fea53d62533d6dd23caa16108ed109. Repository access may be restricted.. https://github.com/Eryc123Y/ENG1005-2024S2/blob/77ebe58de2fea53d62533d6dd23caa16108ed109/Source%20Code/W3.tex。

若换一组数据，例如 $\mathbf y=(1,4,9)^{\mathsf T}$，矩阵不变，便可复用同一组 $L,U$。此时 $\mathbf z=(1,0,0)^{\mathsf T}$，系数为 $(1,0,0)^{\mathsf T}$，对应 $p(t)=t^2$。稠密方阵的一次分解通常需要 $O(n^3)$ 次运算，之后每个右端的两次三角求解需要 $O(n^2)$ 次运算。

什么时候需要换行

可逆并不保证每个当前主元都非零。例如

$$H=\begin{pmatrix}0&1\\1&1\end{pmatrix}$$

可逆，却无法直接用左上角作为除数。先交换两行，用置换矩阵 $P$ 记录，得到 $PH=LU$。求解时右端也必须同步换行：

$$L\mathbf z=P\mathbf b,\qquad U\mathbf x=\mathbf z.$$

浮点计算还要考虑很小的主元造成的误差放大。部分选主元会在当前列尚未处理的行中选择绝对值最大的元素。这里建立分解的代数含义；条件数与误差分析留给数值线性代数。

完整的换行求解例子

求解

$$\begin{pmatrix}0&2\\1&3\end{pmatrix} \begin{pmatrix}x\\y\end{pmatrix} =\begin{pmatrix}4\\7\end{pmatrix}.$$

第一列的当前主元为零，交换两行：

$$P=\begin{pmatrix}0&1\\1&0\end{pmatrix},\qquad PA=\begin{pmatrix}1&3\\0&2\end{pmatrix}.$$

这里 $L=I_2$，$U=PA$。右端同步变为 $P\mathbf b=(7,4)^{\mathsf T}$，所以后向代入得到 $2y=4$、$x+3y=7$，即 $(x,y)=(1,2)$。

若只交换系数矩阵的行，却仍使用右端 $(4,7)^{\mathsf T}$，求出的就是另一套方程。因此，置换矩阵记录的是完整方程的重排。

三角求解的通式

若 $L$ 是对角线全为 $1$ 的下三角矩阵，则前向代入为

$$z_i=b_i-\sum_{j=1}^{i-1}l_{ij}z_j,\qquad i=1,\ldots,n.$$

右侧只出现已经算过的量。若 $U$ 的对角元素都非零，后向代入为

$$x_i=\frac{z_i-\sum_{j=i+1}^n u_{ij}x_j}{u_{ii}},\qquad i=n,n-1,\ldots,1.$$

这里使用的是 $A=LU$；若分解为 $PA=LU$，第一步的 $b_i$ 要替换成 $P\mathbf b$ 的相应分量。

对无换行的方阵消元，要求每一阶段都能得到非零主元，才能按这种形式继续分解和求解。对已经得到的 $U$，若对角元素全非零，三角系统对每个右端都有唯一解，因此 $L,U$ 以及 $A$ 都可逆。

练习

练习检查新增测量

交通流中已知 $x_2=30,x_5=5$。求其余流量，并检查非负性。

解答

$t=5$，由 $55-s+t=30$ 得 $s=30$，所以 $\mathbf x=(20,30,20,30,5)^{\mathsf T}$，全部非负。

练习矛盾来自哪里

如果只把原系统第一行右端改为 $46$，其他三行不变，系统是否仍有解？

解答

没有。系数行仍满足 $R_1-R_2+R_3+R_4=0$，右端却变成 $46-45-10+10=1$，所以会得到 $0=1$。这代表外部流量不再满足整体守恒。

练习先分类，再相除

对 $x+y=1$、$2x+ay=b$，分别给出唯一解、无解和无穷多解的条件。

解答

消元得 $(a-2)y=b-2$。若 $a\ne2$，唯一解为 $y=(b-2)/(a-2),x=1-y$；若 $a=2,b=2$，有无穷多解；若 $a=2,b\ne2$，无解。

练习复用三角分解

使用正文的插值矩阵 $V=LU$，求右端为 $(2,3,4)^{\mathsf T}$ 时的系数。

解答

前向代入得 $\mathbf z=(2,-5,1)^{\mathsf T}$。后向代入得 $(\alpha,\beta,\gamma)=(0,1,1)$，即多项式 $p(t)=t+1$。代回三个采样点即可复核。

参考文献

1. [1] X. Yang, “ENG1005 Week 2: Traffic Flow, Personal Workshop Solutions,” 2024. Personal solutions to Monash ENG1005 workshop problems; source snapshot 77ebe58de2fea53d62533d6dd23caa16108ed109. Repository access may be restricted.. https://github.com/Eryc123Y/ENG1005-2024S2/blob/77ebe58de2fea53d62533d6dd23caa16108ed109/Source%20Code/W2.tex ↩
2. [2] X. Yang, “ENG1005 Week 3: Interpolation and Fitting, Personal Workshop Solutions,” 2024. Personal solutions to Monash ENG1005 workshop problems; source snapshot 77ebe58de2fea53d62533d6dd23caa16108ed109. Repository access may be restricted.. https://github.com/Eryc123Y/ENG1005-2024S2/blob/77ebe58de2fea53d62533d6dd23caa16108ed109/Source%20Code/W3.tex ↩