Gröbner 基 · 多项式方程组的高斯消元 · 符号计算的艺术

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

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 基就是它的「非线性推广」：

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

对应关系一目了然：

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

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

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

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

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 解多项式方程组时，内部正是这么干的：

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 基给出判定算法。

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

小结与下一站

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

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

参考文献

[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

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