线性方程组初步

带有实系数$a,b,c,d,e,f$的线性方程$ax=b$，以及形如

$$
\begin{array}{c}
ax+by=e, \\
cx+dy=f \\
\end{array} \tag{1}
$$

方程组的求解问题在中学已经学习过了.我们现在的目的是学会解形如

$$
\begin{array}{c}
a_{11}x_1+a_{12}x_2+\cdots +a_{1n}x_n=b_1, \\
a_{21}x_1+a_{22}x_2+\cdots +a_{2n}x_n=b_2, \\
\cdots \cdots \cdots \cdots \\
a_{m1}x_1+a_{m2}x_2+\cdots +a_{mn}x_n=b_m, \\
\end{array} \tag{2}
$$

的一般线性代数方程组(或简称线性方程组).此处$m,n$是任意正整数.看起来，从方程$(1)$过渡到方程$(2)$时纯粹数量上的增长是一件具有本质意义的事情.形如$(2)$的线性方程组直接出现在几乎所有的数学分支中，而所谓线性方法，其最终产物往往是线性方程组的解，已经成为数学中发展最充分的部分.简略地说，形如$(2)$的线性方程组为$19$世纪创立积分方程的理论提供了原型，而后者在力学和物理学中有着特殊重要的作用.再如计算机处理的大量实际问题也要归结为线性方程组$(2)$.

名词

注意到方程组$(2)$的系数使用了非常简明方便的符号：系数$a_{ij}$表示在第$i$个方程中第$j$个未知数的系数(读作”$a-i-j$”，例如$a_{12}$读作”$a-1-2$”,而不是“$a-12$”).数字$b_i$叫作第$i$个方程的常数项.如果$b_i=0$，$i=1,2,\cdots ,m$，称方程组$(2)$为齐次的.对于任意的一组$b_i=0$，$i=1,\cdots ,m$，线性方程组

$$
\begin{array}{c}
a_{11}x_1+a_{12}x_2+\cdots +a_{1n}x_n=0, \\
a_{21}x_1+a_{22}x_2+\cdots +a_{2n}x_n=0, \\
\cdots \cdots \cdots \cdots \\
a_{m1}x_1+a_{m2}x_2+\cdots +a_{mn}x_n=0, \\
\end{array} \tag{2°}
$$

叫作与方程组$(2)$相对应的齐次方程组，或方程组$(2)$的诱导组，未知数的系数可以排成一个长方形的表

$$
\begin{pmatrix}
a_{11} & a_{12} & \cdots & a_{1n} \\
a_{21} & a_{22} & \cdots & a_{2n} \\
\cdots & \cdots & \cdots & \cdots \\
a_{m1} & a_{m2} & \cdots & a_{mn} \\
\end{pmatrix} \tag{3}
$$

叫作一个$m\times n$矩阵(如果$m=n$，则称为$n$阶方阵)，并可简记为$(a_{ij})$或用字母$A$表示.自然地$(a_{i1},a_{i2},\cdots ,a_{in})$叫作矩阵$(3)$的第$i$行，而第$j$列

$$
\begin{pmatrix}
a_{1j} \\
a_{2j} \\
\vdots \\
a_{mj} \\
\end{pmatrix}
$$

今后将表示成用方括号括起来的行$[a_{1j},a_{2j},\cdots ,a_{mj}]$以便节省地方.当矩阵是方阵时，我们还可以谈它的由元素$a_{11},a_{22},\cdots ,a_{nn}$组成的主对角线.除主对角线外，其他所有元素都等于零的方阵$(a_{ij})$，叫作对角矩阵，有时记作

$$\text{diag}(a_{11},a_{22},\cdots ,a_{nn}),$$

当$a_{11}=a_{22}=\cdots =a_{nn}=a$时，称之为纯量矩阵，记作$\text{diag}_n(a)$.矩阵$\text{diag}_n(1)$叫作单位矩阵，通常记作$E_n$，当矩阵的阶数确定时可简记作$E$.

与矩阵$(3)$同时，我们也考虑方程组$(2)$的增广矩阵$(a_{ij}\mid b_{i})$它是由矩阵$(3)$增添常数项的列$[b_1,b_2,\cdots ,b_m]$得到的；为清楚起见，用竖线将该列与其他列分开.

如果用数字$x_i^0$代替未知数$x_i$时，方程组$(2)$中的每一个方程都变成了恒等式，则称$n$个数$x_1^0,x_2^0,\cdots ,x_n^0$的有序组为方程组$(2)$的一个解，而$x_i^0$称为解的第$i$个分量.这时也称有序组$x_1^0,x_2^0,\cdots ,x_n^0$满足$(2)$的每一个方程.没有任何解的方程组叫作不相容的.有解的方程组叫作相容的，如果只有唯一解，就叫作确定的.解的个数多于一个的方程组叫作不定的.一个给定的方程组是否相容，如果相容，它的所有的解是什么样的，这就是我们当前应该回答的问题.

再来看$\S 2$的第四个问题.我们给薄板内部的点以任意顺序从$1$到$416$编号(即图$3$所示的内点总数)，再添加$204$个边界点的号码，并将需要按照已知规则计算的温度$t_i$放到序号$i$的内点，编成$416$个相关的式子：

$$t_e=\dfrac{t_a+t_b+t_c+t_d}{4}.$$

比如说$a,b,c\leq 416,d>416$.这时，关系式可以写成线性方程的形式

$$-t_a-t_b-t_c+4t_e=t_d.$$

右边的$t_d=-273,-100,-50,0,50,100,300$(可能有其他的不同版本).这些方程构成了一个形如$(2)$的线性方程组，其中$n=m=416$.未知数$t_i$的系数等于$0$(在绝大多数情况下)，$-1$或$4$.这个方程组是否相容和确定呢？

我们得到了一个定性问题在数学上的准确的定量表达式.存在性和唯一性问题在由研究物理现象引出的许多数学分支中都是非常典型的问题.

线性方程组的等价

假设我们还有一个与方程组$(2)$未知数个数与方程个数相同的线性方程组

$$
\begin{array}{c}
a_{11}’x_1+a_{12}’x_2+\cdots +a_{1n}’x_n=b_1’, \\
a_{21}’x_1+a_{22}’x_2+\cdots +a_{2n}’x_n=b_2’, \\
\cdots \cdots \cdots \cdots \\
a_{m1}’x_1+a_{m2}’x_2+\cdots +a_{mn}’x_n=b_m’. \\
\end{array} \tag{2′}
$$

如果方程组$(2)$中除第$i,k$个之外的所有的方程保持不动，而第$i,k$个方程交换位置，则称$(2′)$是由$(2)$经过(Ⅰ)型初等变换得到的.如果$(2)$中除第$i$个之外的所有方程保持不变，而第$i$个方程变为

$$(a_{i1}+ca_{k1})x_1+\cdots +(a_{in}+ca_{kn})x_n=b_i+cb_k\tag{*}$$

(即$a_{ij}’=a_{ij}+ca_{kj},b_i’=b_i+cb_k$)，此外$c$是任意常数，则称方程组$(2)$是由$(2’)$经过(Ⅱ)型初等变换得到的.

如果两个线性方程组$(2)$和$(2’)$同时是不相容的，或者同时是相容的，且有相同的解，则称$(2)$和$(2’)$等价.两个等价的方程组$(a)$和$(b)$记作：$(a)\sim (b)$，我们注意到，$(a)\sim (a)$，$(a)\sim (b)$意味着$(b)\sim (a)$，而从$(a)\sim (b)$，$(b)\sim (c)$可推出$(a)\sim (c)$.

下述论断给出了等价性的一个充分条件.

定理$1$ 如果一个线性方程组是由另一个线性方程组经过有限多次初等变换得到的，则这两个方程组等价.

证明 只要证明当方程组$(2’)$由方程组$(2)$经一次初等变换得到，$(2)$与$(2’)$等价就可以了.

注意到方程$(2)$也是由方程$(2’)$经一次初等变换得到，因为这些变换是可逆的.事实上，在情况(Ⅰ)，再一次交换第$i,k$个方程的位置，我们就回到了原来的方程组；类似地，在情况(Ⅱ)，将第$k$个方程乘以$(-c)$加到$(2’)$中的第$i$个方程上去，我们就得到了$(2)$中的第$i$个方程.

现在我们来证明方程组$(2)$的任意解$(x_1^0,\cdots ,x_n^0)$也是$(2’)$的解.如果施行的初等变换是(Ⅰ)型的，方程自身没有改变(改变的仅仅是它们的次序).所以在变换前满足方程的数组$x_1^0,x_2^0\cdots ,x_n^0$在变换后仍满足方程.在(Ⅱ)型初等变换的情况下，除第$i$个之外的所有方程都没有改变，所以原来方程组的解$(x_1^0,x_2^0\cdots ,x_n^0)$满足这些方程.至于第$i$个方程，它变成了$(*)$的形式.因为我们的解满足$(2)$的第$i$个方程和第$k$个方程，所以

$$a_{i1}x_1^0+\cdots +a_{in}x_n^0=b_i,$$

$$a_{k1}x_1^0+\cdots +a_{kn}x_n^0=b_k.$$

用$c$乘第二个恒等式的两端，并加到第一个恒等式上，我们就得到了形如$(*)$的恒等式，此外$x_i=x_i^0$.

前面谈到的初等变换的可逆性可以用来证明，反过来，方程组$(2”)$的任意解也是$(2)$的解.

最后要说明的是，一个方程组的不相容性意味着另一个的不相容(通过反证法来证).

化为阶梯型

通过施行一系列的初等变换，可以将给定的方程组转化为较简单的形式.

首先指出，在系数$a_{i1}$当中至少有一个不等于$0$.否则谈未知数$x_1$就没有意义了.如果$a_{11}=0$，$a_{j1}\neq 0$，交换第$1$个方程与第$j$个方程的位置，(用(Ⅰ)型初等变换).现在第一个方程中第一个未知数的系数非$0$.将它记作$a_{11}’$.从第$i$个方程的两端($i=2,3,\cdots ,m$)减去新方程组中第一个方程的两端乘以系数$c_i$，使得减完后$x_1$的系数变为$0$(做$m-1$次(Ⅱ)型初等变换).显然为此必须取$c_i=\dfrac{a_{i1}}{a_{11}’}$.结果我们就得到了一个方程组，$x_1$只出现在该组的第一个方程中.这时也可能发生如下情况，即第二个未知数在标号$i>1$的所有方程中也不出现.设$x_k$出现在第一个方程以外的任意一个方程中脚标最小的未知数.我们得到方程组

$$
\begin{array}{ccccc}
a_{11}’x_1+ & & & \cdots & +a_{1n}’x_n=b_1’, \\
& a_{2k}’x_k+ & & \cdots & +a_{2n}’x_n=b_2’, \\
& & & \cdots \cdots \cdots & \\
& & a_{mk}’x_k+ & \cdots & +a_{mn}’x_n=b_m’, \\
& & & & k>1,a_{11}’ \neq 0 \\
\end{array}
$$

抛开第一个方程，对所有余下的方程运用上述推理.经过一系列初等变换，原方程组变成下述形式.

$$
\begin{array}{cccccc}
a_{11}’’x_1+ & & & & \cdots & +a_{1n}’’x_n=b_1’’, \\
& a_{2k}’’x_k+ & & & \cdots & +a_{2n}’’x_n=b_2’’, \\
& & a_{3l}’’x_l+ & & \cdots & +a_{3n}’’x_n=b_3’’, \\
& & & & \cdots \cdots \cdots & \\
& & & a_{ms}’’x_s+ & \cdots & +a_{mn}’’x_n=b_m’’, \\
& & & & s>l>k>1, & a_{11}’’ \neq 0 ,a_{2k}’’\neq 0 .\\
\end{array}
$$

因为第一个方程未被涉及，此处自然有$a_{1j}’’=a_{1j}’$，$b_1’’=b_1’$.只要还有可能，我们就运用这一过程.显然，如果在所得方程中头一个未知数(设脚标为$s$)及其后面直到脚标为$n$的所有未知数的系数都等于$0$，我们就不得不中止这一过程.这时，方程组$(2)$变为

$$
\begin{array}{cccccc}
\overline{a}_{11}x_1+ & & & & \cdots & +\overline{a}_{1n}x_n=\overline{b}_1, \\
& \overline{a}_{2k}x_k+ & & & \cdots & +\overline{a}_{2n}x_n=\overline{b}_2, \\
& & \overline{a}_{3l}x_l+ & & \cdots & +\overline{a}_{3n}x_n=\overline{b}_3, \\
& & & & \cdots \cdots \cdots & \\
& & & \overline{a}_{rs}x_s+ & \cdots & +\overline{a}_{rn}x_n=b_r, \\
& & & & & 0=\overline{b}_{r+1},\\
& & & & & \cdots \cdots \cdots \\
& & & & & 0=\overline{b}_m,\\
\end{array} \tag{4}
$$

此处$\overline{a}_{11}\overline{a}_{2k}\overline{a}_{3l}\cdots \overline{a}_{rs}\neq 0$，$ 1 < k < l < \cdots < s$.如果$r=m$，则方程组$(4)$中形如$0=\overline{b}_i $的方程不会出现.方程组$(4)$叫作阶梯形的.

这一术语不是唯一通用的，方程组$(4)$有时被称为梯形的或拟三角形的，它们都没有本质上的区别.

定理$2$ 任意线性方程组都等价于五个阶梯形方程组.

证明可直接由上述推导得到.

有时不把初等变换用于线性方程组，而用于它的增广矩阵$(a_{ij}\mid b_i)$.与定理$2$的证明相同，我们有

定理$2’$ 任意矩阵可以用初等变换化成阶梯形.

对阶梯形线性方程组的研究

根据定理$1$和定理$2$，相容性和确定性问题只要对阶梯形方程组$(4)$进行研究就可以了.

我们从相容性问题入手.如果方程组$(4)$包含一个形如$0=\overline{b}_t $的方程，且$\overline{b}_t\neq 0 $，则方程组显然是不相容的，因为当未知数取任何值时，等式$0=\overline{b}_t $都不能成立.我们来证明，如果方程组$(4)$不包含这种方程，则方程组是相容的.

于是当$t > r$时，令$\overline{b}_t= 0 $，我们称第$1$，第$2$，$\cdots ，$第$r$个方程开头的未知数$x_1,x_k,x_l,\cdots ,x_s$为主未知数，其余的未知数(如果它们存在的话)，为自由变量.根据定义，主未知数共有$r$个.

取定自由变量的任意一组值，并代入方程组$(4)$.则关于$x_s$的第$r$个方程形如$ax_s=b$，其中$a=\overline{a}_{rs}\neq 0$方程有唯一解.将得到的解$x_s =x_s^0$代入前$r-1$个方程，并在方程组$(4)$中按照自下而上的顺序求解，我们看到，主未知数的值由自由变量的任意一组给定的值唯一确定.

这就证明了

定理$3$ 一个线性方程组具有相容性的充分必要条件是，将它转化为阶梯形方程组后，不包含形如$0=\overline{b}_t $的方程，且$\overline{b}_t\neq 0 $的方程.如果这一条件成立，自由变量可以取做任意值；而主未知数(在自由变量的任意一组定值之下)由方程组唯一确定.

现在我们来搞清楚，一个方程组在相容性条件成立的情况下，何时是确定的.如果方程组$(4)$有自由变量，则方程组显然是不确定的：我们可以给自由变量以任意值，并通过它们来表示主未知数(定理$3$).如果自由变量不存在，即所有的未知数都是主未知数，则根据定理$(3)$，主未知数的值由方程组唯一确定，所以方程组是确定的.

注意到没有自由变量等价于条件$r=n$.

我们证明了下述论断.

定理$4$ 一个相容的线性方程组$(2)$是确定的，当且仅当由它得到的阶梯形方程组$(4)$满足条件$r=n$.$\square$

当$m=n$，则线性方程组转化为阶梯形时也可以写成如下(三角形式)：

$$
\begin{array}{cccc}
\overline{a}_{11}x_1+ & \overline{a}_{12}x_2+ & \cdots & +\overline{a}_{1n}x_n=\overline{b}_1, \\
& \overline{a}_{22}x_2+ & \cdots & +\overline{a}_{2n}x_n=\overline{b}_2, \\
& & & \cdots \cdots \cdots\\
& & & \overline{a}_{nn}x_n=\overline{b}_n,\\
\end{array} \tag{5}
$$

如果我们不在意对任意$i$，是否有$\overline{a}_{ii}\neq 0$.事实上，记法$(5)$仅仅表明，方程组中的第$k$个方程不包含未知数$x_i$，其中$i < k$，而阶梯形方程组显然满足这一条件.

设$(a_{ij})$是一个矩阵，如果当$i> j$时，元素$a_{ij}=0$，则称矩阵为上三角矩阵.类似地可定义下三角矩阵.

从定理$3$和公式$(4)$引出

推论$1$ 线性方程组$(2)$当$m=n$时是相容且确定的，当且仅当将它化为阶梯形后，所得的线性方程组$(5)$满足条件$\overline{a}_{11}\overline{a}_{22}\cdots \overline{a}_{nn}\neq 0$.$\square$

注意到一个事实，即这一条件不信赖于方程组中方程的右半部分.所以当$m=n$时，方程组$(2)$是相容且确定的，当且仅当与之对应的齐次方程组$(2°)$是相容且确定的.但是一个齐次方程组永远相容：它至少有一个零解

$$x_1^0=0,\cdots ,x_n^0=0.$$

条件$\overline{a}_{11}\overline{a}_{22}\cdots \overline{a}_{nn}\neq 0$意味着，齐次方程组仅有零解.我们得到了推论$1$的另一种形式，它与方程组的阶梯形无关.

推论$1’$ 线性方程组$(2)$在$m=n$的情况下是相容的且确定的，当且仅当与之对应的齐次线性方程组$(2°)$只有零解. $square$

$n> m$的情况值得特别的关注.

推论$2$ 当$n > m$时，相容的方程组$(2)$是不定的.特别地，齐次方程组当$n > m$时永远有非零解.

证明 事实上，因为方程组$(4)$的方程个数不会多于方程组$(2)$(去掉左右两边恒等于零的方程)，在任何情况下都有$r \leq m$.所以不等式$n > m$意味着$n > r$，根据定理$4$方程组$(2)$是不定的.最后要指出，齐次方程组的不定性，等价于非零解的存在性.

我们得到的结果反映在下表中.

$$
\begin{array}{|c|c|c|c|c|}
\hline
线性方程组的类型 & 一般 & 齐次 & n > m非齐次 & n > m齐次 \\
\hline
解的个数 & 0、1、\infty & 1、\infty & 0、\infty & \infty \\
\hline
\end{array}
$$

评注和例子

上述解线性方程组的方法叫作高斯法或逐次消元法.当$n$不大时这种方法是非常方便的，并且适用于计算机实现.可是由于种种原因，其他的一些解法，例如迭代法往往更切实际.当系数给定时，寻找具有确定精确度的解就属于这种情况.但是在理论研究中，最重要的问题是得到线性方程组相容性或确定性条件的表述，并寻求用系数和常数项表示解的一般公式，而不必将方程组化为阶梯形.推论$1’$就在某种程度上符合这一点.

例$1$ 重新回到$\S 2$的薄板受热问题.正如本节第一段所示，引起我们兴趣的这一问题变成了一个非常具体的线性问题（为确定起见，将其记作$\text{HP}$）的求解问题，该方程组含有非常多的未知数$t_i$.按照推论$1’$中陈述的判别法，我们来研究对应于$\text{HP}$的齐次线性方程组($\text{HHP}$).换言之，薄板所有的边界点的温度现在取零.设$e$是一个内顶点的脚标，该点的温度有极大值$\mid t_e \mid $.这时条件

$$t_e =\dfrac{t_a +t_b +t_c +t_d }{4}$$

意味着$\mid t_e \mid =\mid t_a \mid =\mid t_b \mid =\mid t_c \mid =\mid t_d \mid = $.在没有达到温度为$0$的边界点之前，我们沿着点阵中由一个内点给出的四个方向中的任意五个方向移动一步，就会看到所有的点均取值$\mid t_i \mid =\mid t_e \mid $.这就意味着$\mid t_e \mid =0$，所以对任意的脚标$i$，$t_i =0$.因而方程组$\text{HHP}$仅有零解，故$\text{HP}$是一个相容的且确定的线性方程组.这样最初提到的薄板受热问题本身也就解决了.

例$2$ 给出线性方程组

$$
\begin{array}{ccccc}
x_1 & & & & =1,\\
& x_2 & & & =1,\\
& -x_1-x_2+x_3 & & & =0, \\
& & \cdots \cdots \cdots & & \\
& & -x_{n-2} & -x_{n-1}+x_n & =0,\\
\end{array}
$$

这显然是一个相容的且确定的方程组，它已经尤为阶梯形(三角形)了.只不过求解时不是自下而上，而是自上而下.按照定义，它的解是前$n$个斐波那契数$f_1,f_2,\cdots ,f_n$.这些数与植物中的叶序数(叶子在茎上的排列)有关.与其孤立地求解$n=1000$或做任意给定的$n$.不如得到对第$n$个斐波那契数的一般表达式(解析公式).你可能会反对说，我们有足够的耐心，就可以根据这些数的归纳定义给出$f_{1000}$.但这不是解决数学问题的根本办法.我们将在第二章和第三章中给出$f_n$的两个表达式，尽管这个具体问题可以用更直接的办法来解.

注记$1$ 有时不必化阶梯形就可以更方便地求出线性方程组的解.特别是当线性方程组的矩阵包含很多零时.此时简短的实际解法取代了冗长的解释.

注记$2$ 当我们用高斯法解$n$元$n$个方程的线性方程组时经过多少步必要的算术$\Gamma _n$可以求解？这不是一个等闲的问题，因为在通常情况下，当我们对大数$n$使用计算机时，应当对求解问题所需的机时进行预先估计.

因为两数相乘要比相加工作量大，所以建议只计算做乘法的次数，自然也包括除法，以后简称运算.不失一般性，可以假定线性方程组有唯一解，即所有的未知数都是主未知数.暂且忽略方程的右边.为了从第$i$个方程($i >1$)消去未知数$x_1$需准备好数$l_i=\dfrac{a_{i1}}{a_{11}}$(做一次除法)，还要算出$n-1$个乘积$l_ia_{ij}$，$j=2,3,\cdots ,n$，即共需要$n$次运算.按照我们的约定，忽略从第$i$个方程减去第一个方程的$l_i$倍的过程.因为$i=2,3,\cdots ,n$，那么为了消去$x_1$，需要$n(n-1)$次运算.第二步，我们对得到的$n-1$阶方程组需要$(n-1)(n-2)$次运算，第三步相应地为$(n-2)(n-3)$等等.为了将方程组的左边化为如同公式$(5)$的三角形式，总运算次数为和式

$$\Gamma (n)=n(n-1)+(n-1)(n-2)+\cdots +1(1-1).$$

不难验证(自己证明或者参看$\S 7$)，

$$\Gamma (n)=\dfrac{n^3-n}{3}.$$

找到解的分量$x_n^0,x_{n-1}^0,\cdots ,x_1^0$(按方程组$(5)$自下而上运作)，共需要

$$1+2+3+\cdots +n=\dfrac{n(n+1)}{2}$$

次运算，当$n$较大时，并不引起运算次数总和的本质影响.于是，高斯算法相当准确的运算次数是$\Gamma (n)=\dfrac{n^3}{3}$.

$1969$年，施特拉辛研究出一种方法，(详见$[BAⅡ]$)，仅需

$$S_n=C\cdot n^{\log_27 }\approx C\cdot n^{2.81}$$

次运算，当$n$非常大时，可以节省大量运算，诚然，做到这一点是由于增加了加法运算的次数.但$S_n$中常数$C$特别大，而实现它的程序在逻辑上又很复杂，因而这里所谈的节省仍停留在理论上的计划.

我们所了解的两种方法是典型的数学算法，适用于大量问题的解决.稍后我们会看到算法的其他例子.它们的作用在我们这个全盘计算机化的时代是非常巨大的.这时重要的不但是算法本身，还有对计算复杂性的估计.