最后更新: 2026-06-15 06:27 查看: 11 次纠错评论(0) 课件开VIP

高斯消元法

## 线性方程组的数值解法

线性方程组尤其是大规模线性方程组的求解是科学与工程计算的基础核心问题之一。本章我们主要研究求解线性方程组

$$
\left\{\begin{array}{c}
a_{11} x_1+a_{12} x_2+\cdots+a_{1 n} x_n=b_1, \\
a_{21} x_1+a_{22} x_2+\cdots+a_{2 n} x_n=b_2, \\
\cdots \cdots \\
a_{n 1} x_1+a_{n 2} x_2+\cdots+a_{n n} x_n=b_n .
\end{array}\right.
$$

上述线性方程组可以写为如下矩阵形式：

$$
\left(\begin{array}{ccc}
a_{11} & \cdots & a_{1 n} \\
\vdots & & \vdots \\
a_{n 1} & \cdots & a_{n n}
\end{array}\right)\left(\begin{array}{c}
x_1 \\
\vdots \\
x_n
\end{array}\right)=\left(\begin{array}{c}
b_1 \\
\vdots \\
b_n
\end{array}\right) .
$$

我们可以将上述线性方程组简洁地表示为

$$
A x=b,
$$

其中

$$
A=\left(\begin{array}{ccc}
a_{11} & \cdots & a_{1 n} \\
\vdots & & \vdots \\
a_{n 1} & \cdots & a_{n n}
\end{array}\right), \quad x=\left(\begin{array}{c}
x_1 \\
\vdots \\
x_n
\end{array}\right), \quad b=\left(\begin{array}{c}
b_1 \\
\vdots \\
b_n
\end{array}\right) .
$$

## 3.1 高斯消元法

在求解线性方程组之前我们先研究线性方程组解的存在性和唯一性等基本问题．如下定理回答了线性方程组解的存在性和唯一性。

定理 3.1 记增广矩阵 $(A \mid b)$ 为

$$
\left(\begin{array}{cccc}
a_{11} & \cdots & a_{1 n} & b_1 \\
\vdots & & \vdots & \vdots \\
a_{n 1} & \cdots & a_{n n} & b_n
\end{array}\right),
$$

如果 $\operatorname{rank}(A)=\operatorname{rank}(A \mid b)$ ，则线性方程组有解。如果 $\operatorname{rank}(A)=\operatorname{rank}(A \mid b)=n$ ，则线性方程组有唯一解；如果 $\operatorname{rank}(A)=\operatorname{rank}(A \mid b)<n$ ，则线性方程组有无穷多解。

在讨论一般线性方程组求解之前，我们先看两类特殊线性方程组的求解．第一类是上三角线性方程组 $U x=b$ 。以如下 $3 \times 3$ 线性方程组为例，

$$
\left\{\begin{aligned}
u_{11} x_1+u_{12} x_2+u_{13} x_3 & =b_1, \\
u_{22} x_2+u_{23} x_3 & =b_2, \\
u_{33} x_3 & =b_3 .
\end{aligned}\right.
$$

从最后一个方程开始，从后往前每次求解一个方程，则上三角线性方程组解为

$$
\left\{\begin{array}{l}
x_3=b_3 / u_{33}, \\
x_2=\left(b_2-u_{23} x_3\right) / u_{22}, \\
x_1=\left(b_1-u_{13} x_3-u_{12} x_2\right) / u_{11} .
\end{array}\right.
$$

第二类是下三角线性方程组 $L x=b$ 。 以如下 $3 \times 3$ 线性方程组为例，

$$
\begin{cases}l_{11} x_1 & =b_1, \\ l_{21} x_1+l_{22} x_2 & =b_2, \\ l_{31} x_1+l_{32} x_2+l_{33} x_3 & =b_3 .\end{cases}
$$

从第一个方程开始，从前往后每次求解一个方程，则下三角方程组解为

$$
\left\{\begin{array}{l}
x_1=b_1 / l_{11} \\
x_2=\left(b_2-l_{21} x_1\right) / l_{22}, \\
x_3=\left(b_3-l_{31} x_1-l_{32} x_2\right) / l_{33} .
\end{array}\right.
$$
上述两类特殊线性方程组相对于一般线性方程组容易求解．高斯（Gauss）消元法的核心思想是通过不改变方程组解的初等变换（交换两个方程的位置、非零数 $k$ 乘某一个方程和一个方程的 $k$ 倍加到另一个方程）将一般线性方程组转化为等价且相对容易求解的上三角方程组求解。下面我们通过一个例子说明如何通过初等变换将一般线性方程组转化为上三角线性方程组求解。

例 3.1 高斯消元法求解如下线性方程组：

$$
\left\{\begin{aligned}
8 x_1-6 x_2+2 x_3 & =28 \\
-4 x_1+11 x_2-7 x_3 & =-40 \\
4 x_1-7 x_2+6 x_3 & =33
\end{aligned}\right.
$$

解 进行第一轮消元（第一行 0.5 倍和 -0.5 倍分别加到第2行和第3行）得

$$
\left\{\begin{aligned}
8 x_1-6 x_2+2 x_3 & =28, \\
8 x_2-6 x_3 & =-26, \\
-4 x_2+5 x_3 & =19,
\end{aligned}\right.
$$

其中 8 称为主元，-0.5 和 0.5 称为乘子。
第一轮消元过程可以用矩阵语言精确表述为

$$
F_1 A x=\left(\begin{array}{ccc}
1 & 0 & 0 \\
0.5 & 1 & 0 \\
-0.5 & 0 & 1
\end{array}\right)\left(\begin{array}{ccc}
8 & -6 & 2 \\
-4 & 11 & -7 \\
4 & -7 & 6
\end{array}\right)\left(\begin{array}{c}
x_1 \\
x_2 \\
x_3
\end{array}\right)=\left(\begin{array}{ccc}
1 & 0 & 0 \\
0.5 & 1 & 0 \\
-0.5 & 0 & 1
\end{array}\right)\left(\begin{array}{c}
28 \\
-40 \\
33
\end{array}\right)=F_1 b,
$$

其中 $F_1$ 称为弗罗贝尼乌斯（Frobenius）矩阵。
记 $A^{(1)}=F_1 A$ 和 $b^{(1)}=F_1 b$ ，我们有

$$
A^{(1)} x=\left(\begin{array}{ccc}
8 & -6 & 2 \\
0 & 8 & -6 \\
0 & -4 & 5
\end{array}\right)\left(\begin{array}{l}
x_1 \\
x_2 \\
x_3
\end{array}\right)=\left(\begin{array}{c}
28 \\
-26 \\
19
\end{array}\right)=b^{(1)} .
$$

进行第二轮消元（即第二行的 0.5 倍加到第 3 行）得

$$
\left\{\begin{aligned}
8 x_1-6 x_2+2 x_3 & =28, \\
8 x_2-6 x_3 & =-26, \\
2 x_3 & =6,
\end{aligned}\right.
$$

其中 8 是主元，-0.5 是乘子．由于初等变换不改变线性方程组的解，求解上述上三角线性方程组得到原线性方程组的解 $x=(2,-1,3)^{\mathrm{T}}$ ．

第二轮消元过程可以用矩阵语言精确表述为

$$
F_2 A^{(1)} x=\left(\begin{array}{ccc}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0.5 & 1
\end{array}\right)\left(\begin{array}{ccc}
8 & -6 & 2 \\
0 & 8 & -6 \\
0 & -4 & 5
\end{array}\right)\left(\begin{array}{c}
x_1 \\
x_2 \\
x_3
\end{array}\right)=\left(\begin{array}{ccc}
8 & -6 & 2 \\
0 & 8 & -6 \\
0 & 0 & 2
\end{array}\right)\left(\begin{array}{c}
x_1 \\
x_2 \\
x_3
\end{array}\right)=F_2 b^{(1)}
$$

记 $A^{(2)}=F_2 A^{(1)}$ 和 $b^{(2)}=F_2 b^{(1)}$ ，我们有

$$
A^{(2)} x=\left(\begin{array}{ccc}
8 & -6 & 2 \\
0 & 8 & -6 \\
0 & 0 & 2
\end{array}\right)\left(\begin{array}{l}
x_1 \\
x_2 \\
x_3
\end{array}\right)=\left(\begin{array}{c}
28 \\
-26 \\
6
\end{array}\right)=b^{(2)} .
$$

我们将整个消元过程整理如下：

$$
F_2 F_1 A=\left(\begin{array}{ccc}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & 0.5 & 1
\end{array}\right)\left(\begin{array}{ccc}
1 & 0 & 0 \\
0.5 & 1 & 0 \\
-0.5 & 0 & 1
\end{array}\right)\left(\begin{array}{ccc}
8 & -6 & 2 \\
-4 & 11 & -7 \\
4 & -7 & 6
\end{array}\right)=\left(\begin{array}{ccc}
8 & -6 & 2 \\
0 & 8 & -6 \\
0 & 0 & 2
\end{array}\right)=A^{(2)} \triangleq U .
$$

上式两边同时乘 $F_1^{-1} F_2^{-1}$ 得

$$
A=\left(\begin{array}{ccc}
8 & -6 & 2 \\
-4 & 11 & -7 \\
4 & -7 & 6
\end{array}\right)=\left(\begin{array}{ccc}
1 & 0 & 0 \\
-0.5 & 1 & 0 \\
0.5 & 0 & 1
\end{array}\right)\left(\begin{array}{ccc}
1 & 0 & 0 \\
0 & 1 & 0 \\
0 & -0.5 & 1
\end{array}\right)\left(\begin{array}{ccc}
8 & -6 & 2 \\
0 & 8 & -6 \\
0 & 0 & 2
\end{array}\right)=F_1^{-1} F_2^{-1} U .
$$

记 $L=F_1^{-1} F_2^{-1}$ ，我们有如下 $L U$ 分解：

$$
A=\left(\begin{array}{ccc}
8 & -6 & 2 \\
-4 & 11 & -7 \\
4 & -7 & 6
\end{array}\right)=\left(\begin{array}{ccc}
1 & 0 & 0 \\
-0.5 & 1 & 0 \\
0.5 & -0.5 & 1
\end{array}\right)\left(\begin{array}{ccc}
8 & -6 & 2 \\
0 & 8 & -6 \\
0 & 0 & 2
\end{array}\right)=L U .
$$

我们用矩阵语言将高斯消元法精确表述后，发现高斯消元法求解线性方程组本质上是计算相应系数矩阵的 $L U$ 分解．事实上，用矩阵语言精确表述算法能够帮助我们深刻理解算法的本质．

下面讨论求解一般线性方程组的高斯消元法．

假设 $a_{11}^{(0)} \neq 0$ ，进行第一轮消元

$$
\left\{\begin{array}{c}
a_{11}^{(0)} x_1+a_{12}^{(0)} x_2+\cdots+a_{1 n}^{(0)} x_n=b_1^{(0)}, \\
a_{22}^{(1)} x_2+\cdots+a_{2 n}^{(1)} x_n=b_2^{(1)}, \\
\cdots \cdots \\
a_{n 2}^{(1)} x_2+\cdots+a_{n n}^{(1)} x_n=b_n^{(1)},
\end{array}\right.
$$

其中 $a_{i j}^{(1)}=a_{i j}^{(0)}-\left(a_{i 1}^{(0)} / a_{11}^{(0)}\right) a_{1 j}^{(0)}, b_i^{(1)}=b_i^{(0)}-\left(a_{i 1}^{(0)} / a_{11}^{(0)}\right) b_1^{(0)}, i, j=2,3, \cdots, n$ ，元素上标 $k$ 表示元素经过第 $k$ 轮消元．在第一轮消元中，除法运算为 $n-1$ 次，乘法和加减运算各为 $(n-1) n$ 次。

经过第 $k-1$ 轮消元，得到如下线性方程组：

$$
\left\{\begin{aligned}
& a_{11}^{(0)} x_1+a_{12}^{(0)} x_2+\cdots+a_{1 k}^{(0)} x_k+a_{1, k+1}^{(0)} x_{k+1}+\cdots+a_{1 n}^{(0)} x_n=b_1^{(0)} \\
& a_{22}^{(1)} x_2+\cdots+a_{2 k}^{(1)} x_k+a_{2, k+1}^{(1)} x_{k+1}+\cdots+a_{2 n}^{(1)} x_n=b_2^{(1)} \\
& \cdots \cdots \\
& a_{k k}^{(k-1)} x_k+a_{k, k+1}^{(k-1)} x_{k+1}+\cdots+a_{k n}^{(k-1)} x_n=b_k^{(k-1)} \\
& a_{k+1, k}^{(k-1)} x_k+a_{k+1, k+1}^{(k-1)} x_{k+1}+\cdots+a_{k+1, n}^{(k-1)} x_n=b_{k+1}^{(k-1)} \\
& \cdots \cdots \\
& a_{n k}^{(k-1)} x_k+a_{n, k+1}^{(k-1)} x_{k+1}+\cdots+a_{n n}^{(k-1)} x_n=b_n^{(k-1)}
\end{aligned}\right.
$$

对上述线性方程组进行第 $k$ 轮消元得

$$
\left\{\begin{aligned}
a_{11}^{(0)} x_1+a_{12}^{(0)} x_2+\cdots+a_{1 k}^{(0)} x_k+a_{1, k+1}^{(0)} x_{k+1}+\cdots+a_{1 n}^{(0)} x_n & =b_1^{(0)}, \\
a_{22}^{(1)} x_2+\cdots+a_{2 k}^{(1)} x_k+a_{2, k+1}^{(1)} x_{k+1}+\cdots+a_{2 n}^{(1)} x_n & =b_2^{(1)}, \\
\cdots \cdots & \\
a_{k k}^{(k-1)} x_k+a_{k, k+1}^{(k-1)} x_{k+1}+\cdots+a_{k n}^{(k-1)} x_n & =b_k^{(k-1)}, \\
a_{k+1, k+1}^{(k)} x_{k+1}+\cdots+a_{k+1, n}^{(k)} x_n & =b_{k+1}^{(k)}, \\
\cdots \cdots & \\
a_{n, k+1}^{(k)} x_{k+1}+\cdots+a_{n n}^{(k)} x_n & =b_n^{(k)} .
\end{aligned}\right.
$$

在第 $k$ 轮消元中，除法运算为 $n-k$ 次，乘法和加减运算各为 $(n-k)(n-k+1)$ 次．经过最后一轮消元得到如下上三角线性方程组：

$$
\left\{\begin{aligned}
a_{11}^{(0)} x_1+a_{12}^{(0)} x_2+\cdots+a_{1 n}^{(0)} x_n & =b_1^{(0)}, \\
a_{22}^{(1)} x_2+\cdots+a_{2 n}^{(1)} x_n & =b_2^{(1)}, \\
\cdots \cdots & \\
a_{n n}^{(n-1)} x_n & =b_n^{(n-1)} .
\end{aligned}\right.
$$

整个消元阶段乘除运算次数为

$$
\sum_{k=1}^{n-1}(n-k)+\sum_{k=1}^{n-1}(n-k)(n-k+1)=\frac{n^3}{3}+\frac{n^2}{2}-\frac{5 n}{6}
$$

和加减运算次数为

$$
\sum_{k=1}^{n-1}(n-k)(n-k+1)=\frac{n^3}{3}-\frac{n}{3} .
$$

求解上三角线性方程组的过程（称为回代阶段）中需要乘除运算次数和加减运算次数分别为 $\frac{n(n+1)}{2}$ 和 $\frac{n(n-1)}{2}$ ．

高斯消元法包括消元阶段和回代阶段。乘除法运算次数共计

$$
\frac{n^3}{3}+n^2-\frac{n}{3}
$$

和加减运算次数共计

$$
\frac{n^3}{3}+\frac{n^2}{2}-\frac{5 n}{6} .
$$

我们经常忽略低阶项及最高阶项系数，用记号 $O$ 表示算法运算的最高次幂是多少次，称为算法的复杂度．复杂度是衡量算法性能优劣的主要指标．上述例子中高斯消元法的复杂度为 $O\left(n^3\right)$ 。

由于主元为零或绝对值很小可能产生麻烦，为了数值稳定性通常在消元后低

阶子矩阵元素中选取新主元并通过交换方程使其位于主对角线上再进行消元。常用新主元选取策略为列选主元策略，即第 $k$ 轮消元过程中，在 $\left|a_{i, k}^{(k-1)}\right|(i=k, \cdots, n)$ 中选择最大者作为新主元。下面我们通过一个例子说明基于列选主元策略的高斯消元法．

例 3.2 通过基于列选主元策略的高斯消元法求解如下线性方程组：

$$
\left\{\begin{aligned}
x_1-x_2+3 x_3 & =-3, \\
-x_1-2 x_3 & =1, \\
2 x_1+2 x_2+4 x_3 & =0 .
\end{aligned}\right.
$$

解 根据列选主元策略选择主元即第 $k$ 轮消元过程中，在 $\left|a_{i, k}^{(k-1)}\right|(i=k, \cdots, n)$ 中选择最大者作为新主元，并通过交换方程使其位于主对角线上再进行消元．

![图片](/uploads/2026-06/bb480d.jpg)

其他版本
【线性代数】矩阵的LU分解

科数题库(单机版) 会议室预约系统(book)

今日还可看 0 篇未注册用户每天查看4篇，注册用户每天8篇，开通VIP会员无限制查看。

免费注册

《高等数学》难点解析

高数教程 泰勒公式切线与法线切平面与法平面驻点·拐点·极值点·零点间断点渐进线瑕积分欧拉方程伯努利方程 Abel 收敛定理偏导数的几何意义偏导数的几何意义梯度数量场与向量场多元函数极值拉格朗日算子通量与散度环流量与旋度格林公式高斯公式斯托克斯公式三大公式比较傅里叶级数极坐标微元点法式方程变上限定积分 X型计算面积 Y型计算面积微分的意义渐近线间断点 y''+py'+qy=f(x)方程高斯黎曼傅里叶变换(复数) 拉普拉斯变换(复数)

《线性代数》难点解析

线代教程 近世代数对数学的整体思考线性的意义矩阵乘法(列视角) 矩阵乘法(行视角) 矩阵左乘矩阵右乘逆矩阵求解方程组阶梯形矩阵的求法方程组解的判定四阶行列式的计算线性变换的意义线性空间向量组的等价线性空间的几何意义基础解系的求法施密特正交化特征值与特征向量的意义矩阵相似的几何意义矩阵可对角化的理解秩的意义(向量版) 秩的意义(方程版) 二次型的意义

《概率论与数理统计》难点解析

概率教程 置信区间与上a分位数概率中的“取”与“放” 贝叶斯公式全概率公式泊松分布指数分布伽玛分布二维密度图的意义卷积的意义相关系数的意义 k阶矩是与矩母函数卡方分布的作用单正态区间估计理解假设检验理解切比雪夫不等式中心极限定理

上一篇：没有了

下一篇：经典迭代法

本文对您是否有用？有用 (0) 无用 (0)