# Gröbner 基 · 多项式方程组的高斯消元

> 线性方程组有高斯消元，把它化成上三角、逐个回代。多元「非线性」多项式方程组呢？Gröbner 基就是它的对应物——一组等价却「三角化」的多项式，让方程组能被逐个解出。这一章用一个能跑的例子，把这个被誉为计算机代数明珠的算法讲得看得见摸得着。

- 作者：David（道雾轩）
- 专栏：符号计算的艺术（https://daiw.org/manual/symbolic-computing.md）
- 最后更新：2026-10-01
- 原文：https://daiw.org/manual/symbolic-computing/groebner
- 转载与引用：请注明出处并附原文链接（https://daiw.org/about/copyright）

# Gröbner 基 · 多项式方程组的高斯消元

这是代数引擎的高潮。前面处理的是**单个 / 两个**多项式；现实里我们常要一次解**一整组**多元多项式方程——两条曲线交在哪、一个机械臂怎么摆到目标位置。**Gröbner 基**就是解这类问题的利器，被誉为**计算机代数皇冠上的明珠**。别被名字吓到，它的思想其实你早就见过。

## 先回忆：线性方程组怎么解

解线性方程组，你用**高斯消元**：通过加减消元，把方程组化成**上三角**的阶梯形，让**最后一个方程只剩一个未知数**，解出它，再往回**逐个回代**。比如：

$$
\begin{cases} x + y = 3 \\ x - y = 1 \end{cases}
\;\xrightarrow{\text{消元}}\;
\begin{cases} x + y = 3 \\ \quad\ 2y = 2 \end{cases}
$$

下面那个方程只含 $y$，解出 $y=1$，回代得 $x=2$。**高斯消元的精髓，是把「纠缠在一起的方程」变成「能逐个击破的三角形」。**

## Gröbner 基：把这套搬到「非线性」

问题来了：如果方程是**非线性**的多项式呢？比如求圆 $x^2+y^2=1$ 和抛物线 $x^2=y$ 的交点：

$$
\begin{cases} x^2 + y^2 = 1 \\ x^2 = y \end{cases}
$$

高斯消元只会对线性方程，这里失灵。**Gröbner 基**就是它的「非线性推广」：

<Callout type="info">
  **Gröbner 基，就是多项式方程组的「高斯消元」。** 给你一组多元多项式方程，它算出**另一组等价的多项式**（解完全相同），但这组新多项式被巧妙地「**三角化**」了——其中会出现**只含一个变量**的方程。于是你能像解线性方程组一样：先解那个单变量方程，再逐个回代。

  **对应关系一目了然：**

  | 线性方程组 | 多项式方程组 |
  | --- | --- |
  | 高斯消元 | **Buchberger 算法** |
  | 上三角 / 阶梯形 | **Gröbner 基（字典序）** |
  | 逐个回代 | 逐个回代 |
  | 行变换 | 多项式的加减与相乘消去 |

  它由数学家 Bruno Buchberger 在 1965 年的博士论文里提出，以他导师 Wolfgang Gröbner 命名。**Buchberger 算法**是计算它的经典方法（核心是不断构造并约化「S-多项式」来消去最高次项，恰似消元）。
</Callout>

## 眼见为实：三角化就在眼前

让 SymPy 算上面那个圆与抛物线方程组的 Gröbner 基（用**字典序** `lex`，它最擅长三角化）：

```python
from sympy import *
x, y = symbols('x y')

G = groebner([x**2 + y**2 - 1, x**2 - y], x, y, order='lex')
print(list(G.exprs))       # [x**2 - y, y**2 + y - 1]
```

看那第二个多项式 `y**2 + y - 1`——**它只含 $y$，不含 $x$！** 这正是「三角化」的成果：纠缠的方程组被整理成

$$
\begin{cases} x^2 - y = 0 \\ y^2 + y - 1 = 0 \end{cases}
$$

下面的方程只有 $y$，解出 $y=\frac{-1\pm\sqrt5}{2}$，再代入 $x^2=y$ 解 $x$。**和高斯消元回代一模一样**，只不过每一步是多项式。SymPy 的 `solve` 解多项式方程组时，内部正是这么干的：

```python
sols = solve([x**2 + y**2 - 1, x**2 - y], [x, y])
print(len(sols))           # 4    —— 圆和抛物线的 4 个精确交点
print(sols[1])             # (sqrt(-1/2 + sqrt(5)/2), -1/2 + sqrt(5)/2)
```

四个**精确**交点（带根式），一个不漏、一个不错。这是数值方法很难做到的——数值解只能一个个去逼近，还可能漏根；符号的 Gröbner 基**一次性、精确地**给出全部。

## 它能做的，远不止解方程

Gröbner 基是个惊人通用的工具，凡是能翻译成「多项式方程组」的问题，它都能碰：

- **机器人学**：机械臂逆运动学——已知手要到的位置，反解各关节角度，是一组多项式方程。
- **几何定理证明**：把「三点共线」「三线共点」写成多项式条件，用 Gröbner 基**自动证明**几何定理（吴文俊的工作与此相关）。
- **密码学与编码**：某些方程组求解、纠错码分析。
- **判定「一个多项式能否由一组多项式生成」**：理想成员问题，Gröbner 基给出判定算法。

<Callout type="warn">
  **代价提醒：Gröbner 基可能非常「贵」。** Buchberger 算法在最坏情况下是**双指数**复杂度，中间还会遭遇严重的[表达式膨胀](https://daiw.org/manual/symbolic-computing/expression-swell)——变量一多、次数一高，计算时间和内存可能爆炸。所以它威力巨大但**不是万能钥匙**：适合变量不太多的精确求解，大规模问题往往还得回到[数值方法](https://daiw.org/manual/numerical-computing)。这是符号计算「精确但可能极慢」的又一次体现。
</Callout>

## 小结与下一站

**Gröbner 基是多项式方程组的高斯消元**：把一组纠缠的多元多项式方程，化成等价却**三角化**的一组（字典序下会出现**单变量**方程），从而逐个回代求出**全部精确解**。**Buchberger 算法**（约化 S-多项式）是经典计算方法。它是解非线性方程组、机器人学、几何证明的利器，但最坏情况**双指数**、易[膨胀](https://daiw.org/manual/symbolic-computing/expression-swell)，非万能。

代数引擎到此告一段落。接下来进入符号计算大放异彩的另一片天地——**微积分**。你会看到一个迷人的不对称：**求导**是机械的、总能算；而**积分**难得多，有些函数甚至**根本没有初等原函数**——而计算机能证明这件事。先从简单的求导说起。👉 [符号微分：机械的规则](https://daiw.org/manual/symbolic-computing/symbolic-diff)。

## 参考文献

- [1] Bruno Buchberger.「Ein Algorithmus zum Auffinden der Basiselemente...」(博士论文)1965. —— Gröbner 基与 Buchberger 算法。
- [2] Cox, Little & O'Shea.《Ideals, Varieties, and Algorithms》—— Gröbner 基最佳入门，极其易读。
- [3] SymPy 文档.「groebner, solve (polynomial systems).」https://docs.sympy.org/latest/modules/polys/reference.html